Навигация
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 учитывает время на коммуникации, но не пытается распределить блоки на несколько процессоров, используя параллелизм внутри блока.
5 Исследование и построение решения задачи
5.1 Первоначальные предложения по отображению
Попытаемся свести нашу задачу отображения многоблочных задач на процессоры к задаче упаковки в контейнеры с дроблением грузов первого типа – дроблением с увеличением груза (накладными расходами).
Первый вариант:
Квантуем время на достаточно малые равные промежутки dt. Будем считать, что каждый контейнер имеет вместимость N (количество процессоров в вычислительной системе), а количество заполненных контейнеров обозначает время счета совокупности подзадач (если заполнено T контейнеров, то совокупное время счета распределенных на вычислительную систему подзадач будет T*dt). Будем считать, что каждый груз уже раздроблен на части весом Kmax (максимальное возможное количество процессоров для счета подзадачи, для каждого груза этот показатель свой). При дроблении количество частей в зависимости от веса каждой части будем получать по формуле [Time(K)/dt]+1, где Time(K) – время счета подзадачи на K процессорах.
Остается лишь ввести следующие ограничения:
1. При дроблении груза веса частей всегда равны между собой
2. В контейнере не может быть более одной части одного груза
3. После появления части i-го груза в контейнере если i-ый груз не полностью выложен в контейнеры, то в следующем контейнере обязана появится часть i-го груза.
Этот вариант плох тем, что имеет отрицательную динамику роста общего веса груза при его дроблении – то есть полное время выполнения (равное времени выполнения, умноженному на количество задействованных процессоров) подзадачи уменьшается с увеличением количества частей, на которые разбивается соответствующий ей груз. Считаю, что данная отрицательная динамика не позволяет полностью свести нашу задачу к задаче упаковки в контейнеры с дроблением первого типа, а также делает известные методики упаковки неприменимыми.
Второй вариант:
Считаем, что каждый контейнер обозначает процессор. Груз – подзадачу. Будем считать, что каждый груз уже раздроблен на Kmin (минимальное возможное количество процессоров для подзадачи) частей (для каждого груза этот показатель свой). При дроблении вес частей в зависимости от количества будем получать по формуле Time(K), где K – количество частей, на которые раздроблен груз, а Time(K) – время выполнения подзадачи с использованием K процессоров. Далее для получения ответа будем варьировать вместимости контейнеров в поиске минимальной возможной вместимости для размещения всех грузов в данных N контейнерах.
Здесь также вводятся дополнительные ограничения:
1. При дроблении веса частей всегда равные
2. В контейнере не может быть более одной части одного груза
3. А также ограничение, которое заметно сложнее выполнить:
После полной упаковки учитывая ограничения 1 и 2, должна существовать расстановка частей грузов в каждом контейнере (возможно, с добавлением в контейнеры фиктивных грузов для занятия места) такая, что все части одного груза имели бы равные начальные времена (начальное время для части груза в контейнере с упорядоченными частями грузов есть суммарный вес всех частей грузов с номерами меньшими данного). При этом возможно переполнение контейнеров и данное распределение считается неудовлетворяющим ограничению 3.
Второй вариант кажется предпочтительнее своей естественностью, однако поддержание ограничения 3 создает сильное препятствие для работы алгоритма отображения.
5.2 Эволюция предложений по отображению
Рассмотрим сначала второй вариант из подраздела 5.1
Выше изложенный принцип на данный момент не был использован для отображения с учетом параллелизма, однако был использован для отображения без учета параллелизма внутри подзадач. Был реализован и отлажен алгоритм, основанный на данном принципе и названный «Жадное Отображение», принято решение использовать жадную стратегию заполнения контейнеров – такую, при которой следующий груз-кандидат попадает в самый незаполненный контейнер.
Описание алгоритма:
1. Сортируем задачи по сложности в невозрастающем порядке
2. Помечаем все, как нераспределенные
3. Находим самую сложную нераспределенную задачу t
4. Находим самый незанятый процессор (с самым ранним финишным временем) p
5. Ставим задачу t на процессор p и помечаем ее, как распределенную
6. Если есть нераспределенные задачи, то переходим к пункту 3
Алгоритмическая сложность реализованного алгоритма есть O(N*logN + N*M), где N – количество подзадач, а M – количество процессоров.
По этому алгоритму были получены приемлемые отображения модельных и реальных многоблочных задач.
Главная проблема данного подхода в том, что его сложно применить в условиях разрешенного параллелизма внутри подзадачи, поэтому данный подход не был развит.
Теперь рассмотрим первый вариант из подраздела 5.1
Данный ранее изложенный принцип был использован для построения эффективного алгоритма отображения многоблочной задачи с учетом параллелизма ее независимых подзадач на процессоры – алгоритма под названием «Транспонированное Отображение». Была использована «непрерывная» модель при стремлении dt к нулю. Таким образом, уже нет контейнеров, а есть некая неограниченная полоса, поделенная на M (количество процессоров) полос вдоль. Был реализован и отлажен алгоритм, основанный на данной модели, принято решение использовать жадно-переборную стратегию.
Опишем основные принципы работы алгоритма и свойства отображения, поддерживаемые им в процессе работы.
Сначала введем несколько определений:
· Интегральное время подзадачи на заданном количестве процессоров есть Time(K) * K, где Time(K) – время счета подзадачи на количестве процессоров K.
· Минимальное интегральное время подзадачи есть Time(Kmin) * Kmin (здесь работает предположение невозрастающей эффективности распараллеливания)
Первый основной принцип – отображение подзадач в порядке невозрастания их минимального интегрального времени – жадная стратегия. Смысл этого принципа в том, чтобы сначала отобразить наиболее крупные подзадачи, а затем «заткнуть» свободные места задачами поменьше.
Второй основной принцип – для каждой подзадачи перебор ее возможных расположений – переборная стратегия. Была выбрана именно переборная стратегия, ибо чисто жадная стратегия давала слишком неэффективные отображения. Этот принцип позволяет более полно рассмотреть варианты отображения каждой конкретной подзадачи.
Третий основной принцип – отсечение перебора:
· Если текущее промежуточное отображение позволяет отобразить рассматриваемую в данный момент подзадачу на k процессоров, дав ей стартовое время x, то алгоритм не будет исследовать возможность ее отображения на k процессоров с более поздним стартовым временем y, большим x.
· Пусть tMax – максимальное по всем процессорам время освобождения процессора (по сути – промежуточный вариант итогового времени). Вариант расположения следующей рассматриваемой подзадачи назовём хорошим, если для него curStartTime + curTime <= tMax, где curStartTime – допустимое стартовое время для рассматриваемой подзадачи на k процессоров, а curTime – время ее исполнения на некотором рассматриваемом количестве процессоров k.
· Если для подзадачи есть хорошее расположение, то выбираем в качестве результата хорошее расположение с минимальным стартовым временем, а среди хороших расположений с минимальным стартовым временем – хорошее расположение с минимальным количеством используемых процессоров.
· Если хороших расположений нет, то выбираем то (предпочтение более раннему стартовому времени, а среди расположений с равным стартовым временем – расположению с меньшим количеством используемых процессоров), которое минимизирует выражение max((curStartTime + curTime) * M, tOccupied + curTime * k + tRestMin), где tOccupied – уже занятое отображенными подзадачами интегральное время, k – допустимое количество процессоров для рассматриваемой подзадачи, tRestMin – сумма минимальных интегральных времен еще не отображенных подзадач (не включая рассматриваемую в данный момент подзадачу)
Также стоит отметить, что данный алгоритм транспонированного отображения при запрете параллелизма подзадач переходит в описанный выше алгоритм жадного отображения, основанный на втором варианте модели.
6 Описание практической части
Практическая реализация служит для предоставления программистам Fortran-DVM и C-DVM возможности эффективно исполнять многоблочные задачи. Представляет собой статическую библиотеку, предоставляющую вызовы для генерации отображения, а также исполняемый файл для генерации отображения в диалоговом режиме.
0 комментариев