Динамическая балансировка загрузки Алгоритм серверного параллелизма

W i j - вычислительная нагрузка, ассоциированная с узлом сетки i на шаге j W i j = W i j – не зависит от времени W i j W i j-1 – меняется медленно W i j W i j-1 – меняется значительно и не прогнозируемо Стратегии балансировки загрузки Статическая Динамическая диффузная Динамическая ? 2 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

3 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Блок схема алгоритма 4 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Метановый факел 5 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Распределение времени счета 6 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Динамичекая балансировка 7 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Основные процессы 8 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Сотояния обрабатывающего процесса занят - если установлен соответствующий флаг. Этот флаг устанавливается перед передачей обрабатывающему процессу необработанной точки (неважно локальной или внешней) и сбрасывается после того, как точка уже обработана и управляющий процесс получил от обрабатывающего процесса результат; свободен - если не занят, т.е. готов к получению очередной свободной точки.

Управляющий процесс 1. если - есть необработанные точки (неважно локальные или внешние) и - обрабатывающий процесс свободен, то установить флаг обрабатываемой точки, одна из необработанных точек передается на обработку обрабатывающему процессу.

Управляющий процесс 2. если - нет локальных необработанных точек и - нет внешних точек и - нет обрабатываемых точек и - флаг запроса на получение необработанных точек не установлен и - есть процессоры, которые еще не ответили, что не могут предоставить точки для обработки (соответствующий флаг флаг запрета обменов не установлен), то послать запрос на получение необработанных точек одному из таких процессоров. установить флаг запроса на получение необработанных точек

Управляющий процесс Иначе (если не 2) 3. если - все переданные точки получены обратно обработанными и - от всех процессоров получено сообщение о том, что точки для обработки предоставлены быть не могут и - всем процессорам послано сообщение о том, что точки для обработки предоставлены быть не могут, то завершение работы

Управляющий процесс 4. получить очередное сообщение от любого процессора или от своего обрабатывающего процесса. 5. обработать полученное сообщение 6. перейти к началу цикла (п. 1)

нет локальных необработанных точек нет внешних точек нет обрабатываемых точек всем процессорам был послан запрос на получение необработанных точек всем процессорам было послано сообщение о том, что необработанные точки предоставлены быть не могут от всех процессоров получено сообщение о том, что необработанные точки предоставлены быть не могут все локальные точки обработаны и получены результаты обработки всех переданных точек Окончание при выполнение всех условий: 14 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Сообщение от обрабатывающего процессора сбросить флаг обрабатываемой точки если обработана локальная точка, то записать результат обработки в массив локальных точек иначе (обработана внешняя точка) записать результат обработки в массив внешних точек если внешних необработанных точек больше не осталось то вернуть точки их локальному процессору

Сообщения от процессора P если есть необработанные точки тогда передать часть необработанных точек процессору P иначе послать процессору P сообщение о том, что точки предоставлены быть не могут

Сообщения от процессора P получить точки записать их в массив локальных точек

Сообщения от процессора P сбросить флаг запроса на получение необработанных точек получить точки для обработки

Сообщения от процессора P установить флаг запрета обменов с процессором P

Структура программы при совместном использовании двух многопроцессорных комплексов 20 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Эффективность и ускорение сетка 1000x1000 Два кластера процессоров 21 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Траектории пробных частиц Москва, 2009 г. 22 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В.

Хищник - жертва 23 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Расщепление 24 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Решение одномерной задачи 25 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Число процессоров ВремяУскорение статическая балансировка 26 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Число физических процессоров Число процессов ВремяУскорениеЭффективность 55(2) % 77(3) % 99(4) % 25(2) % 37(3) % 49(4) % 511(5) % 613(6) % 715(7) % 817(8) % Динамическая балансировка загрузки 27 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Тип процессаФизические номера Логические номера Синхронизирующий0 Управляющиенечетные[0, p-1] Обрабатывающиечетные[p, 2p-1] Инициализация виртуальной топологии Каждый процесс получает два номера : физический и логический. Процессы по выполняемым ими заданиям разделены на три группы. Общее число выполняющих задачу процессоров равно 2p Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Схема взаимодействия процессов 29 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Тип процесса может быть определен с помощью функции proc_type(void) Синхронизирующий процесс T_MASTER обеспечивает согласованность выполнения расчета и записи результатов Управляющие процессы T_TASK отвечают за хранение данных, выполнение «диффузионного блока» и распределение заданий на этапе динамической балансировки загрузки. Обрабатывающие процессы T_CHEM выполняют обработку заданий из списков, формируемых на этапе динамической балансировки. Типы процессов 30 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Внести изменения в функции, определяемые в файлах main1.c, user_task.c и user_task.h библиотеки динамической балансировки. Соответсвующие пояснения даны в комментариях непосредственно в тексте определения функций. Изменяемы модули 31 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

main_master main_task GD PrepareOwnPointList TestForCalculating ExtractChemData StoreChemData ch4 Подпрограммы 32 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

void main_master(int argc, char *argv[]) { int j,t,t1; for(j=0;j

void main_task(void) { // РАСПРЕДЕЛЕНИЕ ПАМЯТИ И ОПРЕДЕЛЕНИЕ ЗАДАНИЙ // ИНИЦИАЛИЗАЦИЯ МАССИВОВ ОБМЕНА ДАННЫМИ // ЗАДАНИЕ НАЧАЛЬНЫХ УСЛОВИЙ ЗАДАЧИ for(I=0;I

for(I=0;I

int TestForCalculating(int name) { int i, j; i = name / n2; j = name % n2; if( (fn[i][j] + fm[i][j]) > 0.0 ) return 1; else return 0; } TestForCalculating 36 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

int ExtractChemData(int name, USER_TASKPOINT *buf) { int ik; int i, j; i = name / n2; j = name % n2; for(ik=0;ik yi[ ik]=0; buf->yi[0] = fn[i][j]; buf->yi[1] = fm[i][j]; return 0; } ExtractChemData 37 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

int StoreChemData(int name, USER_TASKPOINT *p) { int i, j; i = name / n2; j = name % n2; N_PLUS[i][j] = p->yi[0]; M_PLUS[i][j] = p->yi[1]; return 0; } StoreChemData 38 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

int ch4(USER_TASKPOINT *ptask) { double r0, r1; RungeStep(ptask->yi[0], ptask->yi[1], tau, &r0, &r1); ptask->yi[0] = r0; ptask->yi[1] = r1; return 1; } ch4 39 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

// МАКРОСЫ ДЛЯ РЕШЕНИЯ ОДУ #define AA (int n, double x, double *y){ return // ФУНКЦИИ, ЗАДАЮЩИЕ ПРАВУЮ ЧАСТЬ double f0xx AA (alfa - c * y[1]) * y[0]; } double f1xx AA ((- beta) + gam * y[0]) * y[1]; } int RungeStep(double fn, double fm, double tau, double *r0, double *r1) { double y[2]; int n = 0; FUNEQ ff[2] = {f0xx, f1xx}; n = (int)((fm + fn) * ); if(n < 1) n = 1; y[0] = fn; y[1] = fm; SolverRK4(2, ff, 0., tau, n, &y[0]); (*r0) = y[0]; (*r1) = y[1]; return 0; } RungeStep 40 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Исходная система уравнений Квадратная решетка размера 300x Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

N(0,x,y)=1-0.08*sqrt((x-15)^2+(y-15)^2) M(0,x,y)= *sqrt((x-15)^2+(y-15)^2) M,N>=0 Начальные условия 42 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Эволюция популяций Хищники Жертвы Москва, 2009 г. 43 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В.

Рассмотрен метод динамической балансировки загрузки применимыq в случае распределенного множества элементарных заданий непредсказуемой трудоёмкости Заключение 44 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.

Якобовский М.В. д.ф.-м.н., зав. сектором «Программного обеспечения многопроцессорных систем и вычислительных сетей» Института математического моделирования Российской академии наук Контакты 45 Введение в параллельные алгоритмы: Динамическая балансировка загрузки © Якобовский М.В. Москва, 2009 г.