Москва, 2012 г. Динамическая балансировка загрузки процессоров Якобовский Михаил Владимирович проф., д.ф.-м.н. Институт прикладной математики им. М.В.Келдыша РАН, Москва 1 Динамическая балансировка загрузки © Якобовский М.В.

Москва, 2012 г. Динамическая балансировка загрузки © Якобовский М.В. 2 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 – меняется значительно и не прогнозируемо Стратегии балансировки загрузки Статическая Динамическая диффузная Динамическая ?

3 Динамическая балансировка загрузки © Якобовский М.В. Москва, 2012 г.

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

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

Динамичекая балансировка Москва, 2012 г. Динамическая балансировка загрузки © Якобовский М.В. 6

Основные процессы Москва, 2012 г. Динамическая балансировка загрузки © Якобовский М.В. 7

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

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

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

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

Число процессоров ВремяУскорение статическая балансировка Москва, 2012 г. Динамическая балансировка загрузки © Якобовский М.В. 12

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

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

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

Серверный параллелизм - метод динамической балансировки загрузки, применимый в случае обработки распределенного множества элементарных заданий непредсказуемой трудоёмкости Серверный параллелизм Москва, 2012 г. Динамическая балансировка загрузки © Якобовский М.В. 16

Метод динамической балансировки загрузки, применимый в случае обработки динамически порождаемого множества элементарных заданий непредсказуемой трудоёмкости Параллельный алгоритм адаптивного интегрирования Москва, 2012 г. Динамическая балансировка загрузки © Якобовский М.В. 17

Вычислить с точностью значение определенного интеграла Пусть на отрезке [A,B] задана равномерная сетка, содержащая n+1 узел: Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции на отрезке [A,B]: Будем полагать значение J найденным с точностью, если выполнено условие: Постановка задачи x1x1 x n1 =Bx1x1 x 0 =A x n2 =B x 0 =A Москва, 2012 г. 18 Динамическая балансировка загрузки © Якобовский М.В.

IntTrap01(A,B) { n=1 J 2n =(f(A)+f(B))(B-A)/2 do { J n = J 2n n=2n s=f(A)+f(B) for(i=1;i

Пример функции ABNpointseps realtime, c E E E E E E E Результаты вычисления интеграла на разных отрезках Москва, 2012 г. 20 Динамическая балансировка загрузки © Якобовский М.В.

main() { J= IntTrap03( A, B, f(A),f(B) ) } Адаптивный алгоритм IntTrap03(A,B,fA,fB) { J=0 C=(A+B)/2 fC=f(C) sAB=(fA+fB)*(B-A)/2 sAC=(fA+fC)*(C-A)/2 sCB=(fC+fB)*(B-C)/2 sACB=sAC+sCB if(|sAB-sACB| |sACB|) J=IntTrap03(A,C,fA,fC)+IntTrap03(C,B,fC,fB) else J=sACB return J } x 2 =B x 0 =A x 1 =C Недостаток: координаты концов отрезков хранятся в программном стеке процесса и фактически недоступны программисту Преимущества: - нет повторных вычислений функции - малый объём вычислений на гладких участках Москва, 2012 г. 21 Динамическая балансировка загрузки © Якобовский М.В.

IntTrap04(A,B) { J=0 fA=f(A) fB=f(B) sAB=(fA+fB)*(B-A)/2 while(1) { Тело цикла } return J } Метод локального стека C=(A+B)/2 fC=f(C) sAC=(fA+fC)*(C-A)/2 sCB=(fC+fB)*(B-C)/2 sACB=sAC+sCB if(|sAB-sACB| |sACB|) { PUT_INTO_STACK( A, C, fA, fC, sAC) A=C fA=fC sAB=sCB } else { J+=sACB if(STACK_IS_NOT_FREE) break GET_FROM_STACK( A, B, fA, fB, sAB) } B A C BA Москва, 2012 г. 22 Динамическая балансировка загрузки © Якобовский М.В.

// данные, описывающие стек // указатель вершины стека sp=0 // массив структур в которых // хранятся отложенные задания struct { A,B,fA,fB,s } stk[2000] Процедуры и данные обеспечивающие стек // макроопределения доступа к стеку #define STACK_IS_NOT_FREE (sp>0) #define PUT_INTO_STACK(A,B,fA,fB,s) { stk[sp].A=A stk[sp].B=B stk[sp].fA=fA stk[sp].fB=fB stk[sp].s=s sp++ } #define GET_FROM_STACK(A,B,fA,fB,s) { sp-- A=stk[sp].A B=stk[sp].B fA=stk[sp].fA fB=stk[sp].fB s=stk[sp].s } Москва, 2012 г. 23 Динамическая балансировка загрузки © Якобовский М.В.

Тестирование показало, что при расчете с помощью алгоритма локального стека IntTrap04 время работы было меньше, примерно на 5%, чем при использовании IntTrap03 Примем алгоритм IntTrap04 за «наилучший» последовательный К вопросу о времени выполнения Москва, 2012 г. 24 Динамическая балансировка загрузки © Якобовский М.В.

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

Метод геометрического параллелизма main() { … for(i=0;i

p, (B-C)/ (C-A) интервал 1интервал2время1, свремя2, с 10[1e-5, ] [ , 1] [1e-5, ][ , 1] [1e-5, ][ , 1] [1e-5, ] [ , 1] [1e-5, ] [ , 1] Расчет интеграла на разных отрезках B A=1e-5 C Недостаток: Большой дисбаланс загрузки процессоров Москва, 2012 г. 27 Динамическая балансировка загрузки © Якобовский М.В.

main() { // Порождение p параллельных процессов, // каждый из которых выполняет процедуру slave for(k=0;k

Практически непригодны для решения поставленной задачи методы геометрического параллелизма (статическая балансировка) и коллективного решения (динамическая балансировка) Вывод Москва, 2012 г. 29 Динамическая балансировка загрузки © Якобовский М.В.

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

Пусть есть доступный всем параллельным процессам список отрезков интегрирования, организованный в виде стека. Назовем его глобальным стеком. Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"): –координаты концов отрезка интегрирования, –значения функции на концах, –приближенное значение интеграла на этом отрезке. Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов: Пока в глобальном стеке есть отрезки: - взять один отрезок из глобального стека - выполнить алгоритм локального стека, но, если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то: - переместить часть отрезков из локального стека в глобальный стек. Идея алгоритма Москва, 2012 г. 31 Динамическая балансировка загрузки © Якобовский М.В.

Глобальный стек Локальные стеки Основные структуры данных Москва, 2012 г. 32 Динамическая балансировка загрузки © Якобовский М.В.

Глобальный стек Локальные стеки Стеки алгоритма Только стек Никакого процесса нет Москва, 2012 г. 33 Динамическая балансировка загрузки © Якобовский М.В.

Глобальный стек Локальные стеки Стеки алгоритма Москва, 2012 г. 34 Динамическая балансировка загрузки © Якобовский М.В.

- какую часть отрезков следует перемещать из локального стека в глобальный стек? - в какой момент интеграл вычислен? - что должен делать процесс у которого пуст локальный стек, если глобальный стек тоже пуст? -должен ли процесс закончить работу, если в его локальном и в глобальном стеке отрезков нет? Вопросы Москва, 2012 г. 35 Динамическая балансировка загрузки © Якобовский М.В.

slave_thr() { // цикла обработки стека отрезков while(sdat.ntask>0) { // чтение одного интервала из списка интервалов sdat.ntask-- // указатель глобального стека GET_FROM_GLOBAL_STACK[sdat.ntask](a,b,fa,fb,sab) ИНТЕГРИРОВАНИЕ ОДНОГО ОТРЕЗКА } sdat.s_all = sdat.s_all + s } Схема Интегрирующего процесса Москва, 2012 г. 36 Динамическая балансировка загрузки © Якобовский М.В.

main() {. Sem_init(sdat.sem_sum,1) //доступ к глобальной сумме открыт. } slave_thr() { … // Начало критической секции сложения частичных сумм sem_wait(sdat.sem_sum) sdat.s_all = sdat.s_all + s sem_post(sdat.sem_sum) // Конец критической секции сложения частичных сумм } Правильное определение общей суммы Москва, 2012 г. 37 Динамическая балансировка загрузки © Якобовский М.В.

slave_thr() { // цикла обработки стека отрезков while(sdat.ntask>0) { // чтение одного интервала из списка интервалов sdat.ntask-- // указатель глобального стека GET_FROM_GLOBAL_STACK[sdat.ntask](a,b,fa,fb,sab) ИНТЕГРИРОВАНИЕ ОДНОГО ОТРЕЗКА } sem_wait(sdat.sem_sum) sdat.s_all = sdat.s_all + s sem_post(sdat.sem_sum) } Схема Интегрирующего процесса Москва, 2012 г. 38 Динамическая балансировка загрузки © Якобовский М.В.

slave_thr() { // цикла обработки стека отрезков while(sdat.ntask>0) // изначально там только один отрезок! { // чтение одного интервала из списка интервалов sem_wait(sdat.sem_stack) sdat.ntask-- // указатель глобального стека GET_FROM_GLOBAL_STACK[sdat.ntask](a,b,fa,fb,sab) sem_post(sdat.sem_stack) ИНТЕГРИРОВАНИЕ ОДНОГО ОТРЕЗКА } Схема Интегрирующего процесса Москва, 2012 г. 39 Динамическая балансировка загрузки © Якобовский М.В.

Глобальный стек Локальные стеки Стеки алгоритма Москва, 2012 г. 40 Динамическая балансировка загрузки © Якобовский М.В.

while(1) { // Начало критической секции чтения из глобального // стека очередного интервала интегрирования sem_wait(sdat.sem_list) if(sdat.ntask 0) // заданий нет { sem_post(sdat.sem_list) // разрешить другим процессам // доступ к глобальному стеку break // окончание работы } sdat.ntask-- // указатель глобального стека GET_FROM_GLOBAL_STACK[sdat.ntask](a,b,fa,fb,sab) sem_post(sdat.sem_list) // Конец критической секции чтения из глобального // стека очередного интервала интегрирования … } Преждевременное окончание работы процесса Москва, 2012 г. 41 Динамическая балансировка загрузки © Якобовский М.В. Это плохое решение, задания могут появиться потом

Условие выхода из цикла обработки стека интервалов выбрано неудачно Интегрирующие процессы не должны заканчивать работу до тех пор, пока все отрезки интервала интегрирования не будут полностью обработаны Преждевременное завершение работы приведет к получению верного ответа, но на меньшем числе процессоров и за большее время Преждевременный выход Москва, 2012 г. 42 Динамическая балансировка загрузки © Якобовский М.В.

семафоры доступа: sdat.sem_listсемафор доступа к глобальному стеку отрезков sdat.s_allсемафор доступа к значению интеграла семафоры состояния: sdat.sem_task_presentсемафор наличия записей в глобальном стеке отрезков переменные: sdat.list_of_tasksглобальный стек отрезков sdat.ntaskчисло записей в глобальном стеке отрезков - указатель глобального стека отрезков sdat.nactiveчисло активных процессов sdat.s_allзначение интеграла Необходимые данные Москва, 2012 г. 43 Динамическая балансировка загрузки © Якобовский М.В.

Отрезок интегрирования может находиться в нескольких состояниях: - находится в глобальном стеке интервалов; - обрабатывается некоторым интегрирующим процессом; - находится в локальном стеке интервалов некоторого процесса; - полностью обработан: известно значение интеграла на этом отрезке и оно прибавлено к локальной частичной сумме соответствующего процесса. "Время жизни" отрезка, после того, как некоторый процесс начал его обработку, относительно невелико - отрезок разбивается на две части и перестает существовать, породив два новых отрезка. Таким образом, требование "все отрезки интервала интегрирования полностью обработаны" означает, что: - функция проинтегрирована на всех отрезках, покрывающих исходный интервал интегрирования; - полученные на отрезках интегрирования значения интегралов добавлены к частичным суммам соответствующих процессов. Если глобальный и локальный стеки пусты Москва, 2012 г. 44 Динамическая балансировка загрузки © Якобовский М.В.

while(1) { // Ждать пока появятся отрезки в глобальном стеке sem_post(sdat.sem_task_present) sem_wait(sdat.sem_list) // ждать монопольного доступа if( (!sdat.nactive) && (!sdat.ntask) ) // нет активных процессов и // нет заданий в стеке { // записать в глобальный стек терминальные отрезки sem_post(sdat.sem_list) // разрешить другим процессам // доступ к глобальному стеку } else { // чтение одного интервала из списка интервалов sdat.ntask-- // количество заданий в глобальном стеке GET_OF_GLOBAL_STACK[sdat.ntask](a,b,fa,fb,sab) Окончание работы Москва, 2012 г. 45 Динамическая балансировка загрузки © Якобовский М.В.

Окончание работы, продолжение if(sdat.ntask) // если задания остались – разрешим их читать sem_post(&sdat.sem_task_present) if(ab) // отрезок является терминальным break; // выйти из цикла обработки стека интервалов Москва, 2012 г. 46 Динамическая балансировка загрузки © Якобовский М.В.

Запись терминальных отрезков // Начало критической секции заполнения глобального // стека терминальными отрезками (a>b) // sem_wait(&sdat.sem_list) sdat.nactive-- if( (!sdat.nactive) && (!sdat.ntask) ) // нет активных процессов и // нет заданий в стеке { // запись в глобальный стек списка терминальных отрезков for(i=0;i

Время выполнения Ускорение Эффективность Np1234 tiger.jscc.ru ga03.imamod.ru Результаты тестирования Np1234 tiger.jscc.ru ga03.imamod.ru np1234 tiger.jscc.ru 100%101%102%100% ga03.imamod.ru 100%99% Москва, 2012 г. 48 Динамическая балансировка загрузки © Якобовский М.В.

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, – 30 c. Литература Москва, 2012 г. 49 Динамическая балансировка загрузки © Якобовский М.В.

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