Распараллеливание многоблочных задач для SMP-кластера

Имеем список объектов L=(a1, a2, …, an) и их размеры s(ai) Є {1, 2, …, U}, U – размер контейнеров.

Введем некоторые понятия:

· Эффективность алгоритма A: RA(L) = A(L)/OPT(L), где A(L) – нужное количество контейнеров когда применяем алгоритм A на список объектов L, OPT(L) – оптимальное количество контейнеров для данного списка объектов.

· R называется асимптотической эффективностью в

худшем случае, если

R = inf{r>=1: для некоторых N>0, RA(L)<=r для всех L где OPT(L)>=N}

· Алгоритм А называется алгоритмом без лишнего разбиения если:

a) Разбивает объект только тогда, когда его размер больше размера контейнера

б) Разбивает объект на два фрагмента так, чтобы первый фрагмент вместится полностью в одном из контейнеров

в) Открывает новый контейнер только тогда, когда в уже открытых контейнерах нельзя упаковать новый фрагмент.

Известно, что для всех алгоритмов упаковки в контейнеры без лишнего разбиения:

R <= U/(U-2), U>2

Теперь рассмотрим алгоритмы NF, NFD, NFI, FFD-I

· NF - Next-Fit

На каждом шаге открываем только один контейнер, упаковываем объекты по очереди, если размер объекта больше размера свободной части контейнера – разобьем на две части так, чтобы первая часть заполнила контейнер. После этого открываем новый контейнер и вторую часть туда упаковываем. Это очень простой алгоритм и имеет плохую эффективность

RNF=U/(U-2), U>=6

· NFD, NFI (Next-Fit с ранее отсортированным списком объектов по размеру в убывающем/возрастающем порядке)

RNFD >= U/(U-2) если U=2n, n>=3

RNFD >= (U+1)/(U-1) если U=2n+1, n>=2

Но это только нижняя оценка, мы вполне сможем подобрать пример, когда NFD и NFI работают тоже плохо, как и NF.

· FFD-I и FFI-I (Iterative First-Fit Decreasing/Increasing with Item fragmentation)

Попробуем упаковать все объекты списка L в фиксированное количество m контейнеров. Сортируем список объектов по размеру в невозрастающем порядке. Каждый объект будем упаковывать в первый подходящий контейнер, если такого нет, разобьем объект на две части. Первая часть должна заполнить первый свободный контейнер, а вторую часть положим в отсортированный список объектов. Если не удалось упаковать все объекты в m контейнеров, увеличиваем m и повторяем.

Пусть s(L) – сумма всех объектов в списке L.

1) Взять m=[s(L)/U]

2) FFD()

3) Если успешно, останавливаем

4) Иначе m=m+1 и goto 2)

Для алгоритма FFD-I:

RFFD-I <= U/(U-1) если U<=15

U/(U-1) < RFFD-I < U/(U-2) если U>=16

Получаем, что FFD-I лучше NFD/NFI и NF.

Алгоритм упаковки в контейнеры без разбиения показывает хорошие результаты, но не учитывает параллелизм внутри блоков (исходит из последовательной постановки). Так как алгоритм упаковки в контейнеры с разбиением исходит из идеального распараллеливания на мультикомпьютере – без обменов, то, в условиях необходимости синхронизации в процессе счета подзадачи, он не даёт ответа на вопрос составления итогового расписания, расположения объектов внутри контейнера, а также не учитывает необходимость разбиения объекта на равные части.

4.3 Алгоритмы EVAH

В 2001-ом году на международной конференции по параллельной обработке, организованной IEEE (Институтом Инженеров по Электротехнике и Радиоэлектронике) Джомери и Рупак Бизвас предложили ряд новых алгоритмов для решения задачи балансировки в приложениях гидрогазодинамики [2]. Эти алгоритмы описаны в статье “Task Assignment Heuristics for Distributed CFD Applications”. Этой статьи нет в свободном доступе, но идею алгоритма можно взять в другой статье этих же самых авторов.

В рамках этой работы будем использовать один алгоритм из этой серии, который называется Largest Task First with Minimum Finish Time and Available Communication Costs” (LTF_MFT_ACC, в первую очередь большие задачи с наименьшим временем выполнения и известными затратами на коммуникации). Позже EVAH был интегрирован другими разработчиками в реальных приложениях типа OVERFLOW-D (моделирование подвижных объектов в аэродинамике) и показал весьма неплохой результат.

Ядро алгоритма можно описать следующим образом:

Пусть:

zi – задача i

Xi – время выполнения zi

R(zi) – совокупность всех задач, от которых zi получает данных

D(zi) – совокупность всех задач, которые получают данные от задачи zi

C – время коммуникации

T(pi) – суммарное время выполнения задач на процессоре pi

1: Отсортируем список задач по весу (времени выполнения) в убывающем порядке

2: В начале время выполнения задач на каждом процессоре = 0 (процессоры свободные)

3: Для каждой отсортированной задачи zi выполнять:

3.1: Распределить задачу на процессор pj, у которого загрузка T(pj) наименьшая. Пересчитать T(pj) = T(pj) + Xi

3.2: Для каждой задачи zr в R(zi), назначенной на процессор pk != pj выполнить

T(pj) = T(pj) + Cir

Если задача zr (которая уже распределена на другой процессор) получает данные от задачи zi то надо добавить в T(pj) время коммуникации между zi и zr */

3.3: Для каждой задачи zd в D(zi), назначенной на процессор pm != pj выполнить

T(pm) = T(pm) + Cdi

Если задача zi получает данные от zd (которая уже распределена на процессор pm) то надо добавить в T(pm) время коммуникации */

4: Конец цикла

Для иллюстрации работы алгоритма рассмотрим следующий пример (рисунок 3).

Имеем четыре пересекающиеся сетки (блоки) zi (i=0 3). Надо распределить блоки по двум процессорам p0 и p1 так, чтобы минимизировать время выполнения.

Рисунок 3. Иллюстрация работы алгоритма EVAH

Шаг 1. Четыре блока отсортированы в убывающем порядке по времени выполнения (Xi), получаем: z3, z2, z0, z1

Шаг 2. В начале суммарное время выполнения на процессорах равно 0, T(p0) = T(p1) = 0

Шаг 3. Самый большой блок z3 назначен на процессор p0. Получаем T (po) = 75 в шаге 3.1. Так как никакие другие блоки не были еще назначены на процессоры, пропустим шаги 3.2 и 3.3 для z3.

Повторяем шаг 3 для задачи z2. По предложенному алгоритму z2 должна быть назначена на процессор, где нагрузка наименьшая и поэтому z2 назначена на процессор p1. Получаем T(p1) = 60 в шаге 3.1. На шаге 3.2 очевидно, что z3 получает от z2 данные и поэтому T(p1) = 60 + 4 = 64. На шаге 3.3 наоборот, z2 получает данные от z3 и поэтому T(p0) = 75 + 4 = 79.

Аналогично повторяем шаг 3 для распределения задач z0 и z1.

В результате распределения T(p0)=123, T(p1)=122. Значит, время параллельного выполнения будет 123 а время последовательного 225 (сумма всех Xi без затрат времени на коммуникации)

Заметим, что алгоритм EVAH имеет большое преимущество перед традиционными алгоритмами на неориентированных графах именно в силу возможной обработки ориентированного графа. Для многоблочных задач объем коммуникации между соседними блоками не всегда симметричный.

Алгоритм EVAH учитывает время на коммуникации, но не пытается распределить блоки на несколько процессоров, используя параллелизм внутри блока.

 Скачать реферат