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

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 (моделирование подвижных объектов в аэродинамике) и показал весьма неплохой результат.

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

Пусть:

z_i – задача i

X_i – время выполнения z_i

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

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

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

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

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

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

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

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

3.2: Для каждой задачи z_r в R(z_i ), назначенной на процессор p_k != p_j выполнить

T(p_j ) = T(p_j ) + C_ir

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

3.3: Для каждой задачи z_d в D(z_i ), назначенной на процессор p_m != p_j выполнить

T(p_m ) = T(p_m ) + C_di

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

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

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

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

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

Шаг 1. Четыре блока отсортированы в убывающем порядке по времени выполнения (X_i ), получаем: z₃ , z₂ , z₀ , z₁

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