20151111_msu_ServPar (Лекции)

ВМК МГУДинамическая балансировказагрузки процессоровПараллельные вычисленияЯкобовский Михаил Владимирович1Стратегии балансировки загрузкиWij - вычислительная нагрузка,ассоциированная с узлом сетки i на шаге jСтатическаяW i j = Wi j Wij ≈ Wij-1 Wij ≠ Wij-1Динамическая?Москва, 2015 г.Динамическаядиффузная– не зависит от времени– меняется медленно– меняется значительно ине прогнозируемоДинамическая балансировка загрузки © Якобовский М.В.2Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.3N2, CH4, CH3, CH3O, CH2O, CHO, CO, CO2, H2, O2, H,OH, HO2, H2O.13 веществ - 45 реакцийCH4, CH3, CH2O, CH3O, CHO, CO, CO2, H2, O2, H,OH, HO2, H2O, N2, N, NO, NO2, N2O.19 веществ - 64 реакцииМосква, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.4NOCH4Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.5∂ρ ∂∂∂∂∂ ∂+ρ u) +ρ v) =τρ u2 + p) +τ(((( ρ v2 + p),∂t ∂ x∂y∂x ∂x∂y ∂y(1)∂ ρy ( i ) ∂∂∂∂∂ ∂+ρy( i) u) +ρy( i) v) =τρy( i) u2 + p( i) ) +τ(((( ρy( i) v2 + p( i) ) + ω ( i) , (2)∂t∂x∂y∂x ∂x∂y ∂y∂ ρu ∂∂∂∂∂ ∂+ρ u2 + p) +ρ uv) =τρ u3 + 3 pu) +τ(3)(((( ρ uv2 + pu),∂t ∂ x∂y∂x ∂x∂y ∂y∂ ρv ∂∂∂∂∂ ∂+ρ uv) +ρ v2 + p) =τρ u2 v + pv) +τρv3 + 3 pv),(4)((((∂t ∂ x∂y∂x ∂x∂y ∂y∂E ∂∂∂∂ 2+u( E + p) +v( E + p) =τu ( E + 2 p) +∂t ∂ x∂y∂x ∂x∂ ∂ 2∂ ∂θ ∂ ∂θ+τv ( E + 2 p) +τ+τ,(5)∂y ∂y∂x ∂x ∂ y ∂ y()(()())θ = ∑ p (i ) h (i ) + 0.5 p (u 2 + v 2 ),(i )(())E = ρ ε + 0.5 u + v ,22R(i )p = ∑ p (i ) =∑ ρ (i ) R (i )T ,(i )(i )= R0 / m , ε = ∑ y ε ,(i )(i )(i )ρ = ∑ ρ (i ) ,(i )y(i )= ρ (i ) / ρ ,(i )εT(i )= ∫ c dT + h , h(i )V(i )oT(i )0ω(i )= m (Qi − Li ni )(i )Москва, 2015 г.ρni =mi= ∫ c dT + h , τ =(i )p(i )o0(i )cpµpν,µ T =   , где ν = 0.7,µ 0  T0 5(i )/⋅b1(ij) T j −1 , T ≥ 1000Rm∑0j =1=5 R0 / m(i ) ⋅ ∑ b2(ij) T j −1 , T ≤ 1000j =1()()Динамическая балансировка загрузки © Якобовский М.В.6Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.7Метод решенияМосква, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.8Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.9Блок схема вычисленийМосква, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.10Блок схема алгоритмаГД( k +1)j +1U− U j 1  ( k )j +1+  A U + AU j  = 0,2∆t(0)j +10 ≤ k ≤ s − 1; U= U j,yi, T_ _ХКyi, TdU= f,dtМосква, 2015 г.f = (0, ω i , 0, 0, 0) T .11ДинамическаВремя (сек)Москва, 2015 г.Температура (K°)Динамическая балансировка загрузки © Якобовский М.В.12Метановый факелМосква, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.13Распределение вычислительной нагрузки по процессорам25.00Время расчета с использованием методагеометрического параллелизма20.0015.00время расчета приравномерномраспределении нагрузки10.005.00Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.2927252321номер процессора19171513119750.003счетасек1времяР114Число точек с соответствующим временем обработки прирасчете блока химической кинетикиОсь абсцисс - время обработки одной точки (сек)ось ординат - число точек.45040035030025020015010050Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.0,230,210,190,170,150,130,110,090,070,050,030015Основные положения1.2.3.4.5.6.7.8.9.10.Отсутствует централизованный сбор данных управляющимпроцессором, как при коллективном решенииОтсутствует централизованное управление и сбор информации оналичии горячих точек у процессоров и текущей загрузке системы.Преимущественная обработка локальных точекСтратегия поиска работыКоммуникации (обмен данными и сообщениями) на фоне обработкиВторичное перераспределение точекВозврат точек напрямую, минуя промежуточные этапыСообщения обрабатываются сразу же после полученияНа каждый запрос поступает ответное сообщениеНа каждом процессоре выполняются управляющий иобрабатывающий процессыМосква, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.16Цикл управляющего процессаМосква, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.17Динамичекая балансировка22233131145Москва, 2015 г.45Динамическая балансировка загрузки © Якобовский М.В.4518Основные процессыОбрабатывающий процессуправляющий процесспроцессорМосква, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.19Завершение работы при выполнение всех условийнет локальных необработанных точекнет внешних точекнет обрабатываемых точеквсем процессорам был послан запрос на получениенеобработанных точеквсем процессорам было послано сообщение о том, чтонеобработанные точки предоставлены быть не могутот всех процессоров получено сообщение о том, чтонеобработанные точки предоставлены быть не могутвсе локальные точки обработаны и получены результатыобработки всех переданных точекМосква, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.20Структура программы при совместном использовании двухмногопроцессорных комплексовКластер 1КлиентTCP/IPКластер 2Высокоскоростная сетьСерверTCP/IP, 1Mbyte/secМосква, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.21Эффективность и ускорение100%90%сетка 1000x100080%70%60%50%40%41.0036.0030%20%31.0010%0%010020030040050026.0060021.00Два кластера33+12процессоров16.0011.006.00Np1.001 5 9 13 17 21 25 29 33 37 41 45Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.22Траектории пробных частицМосква, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.23статическая балансировкаЧислопроцессоров12345678Москва, 2015 г.ВремяУскорение2891.002.042.021.961.021.961.211.79141142147283147238161Динамическая балансировка загрузки © Якобовский М.В.24Динамическая балансировказагрузкиЧисло физическихпроцессоровЧислопроцессовВремяУскорениеЭффективность55(2)158.181.828486591%77(3)107.52.690511690%99(4)82.953.486799387%25(2)113.852.540448127%37(3)85.753.3729446112%49(4)70.334.1124698103%511(5)60.614.771984895%613(6)52.565.502853992%715(7)43.886.591385694%817(8)39.77.285390491%Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.25Схема взаимодействия процессовМосква, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.26Типы процессовТип процесса может быть определен с помощьюфункции proc_type(void)Синхронизирующий процесс T_MASTER обеспечиваетсогласованность выполнения расчета и записирезультатовУправляющие процессы T_TASK отвечают за хранениеданных, выполнение «диффузионного блока» ираспределение заданий на этапе динамическойбалансировки загрузки.Обрабатывающие процессы T_CHEM выполняютобработку заданий из списков, формируемых на этапединамической балансировки.Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.27#include < my_net_mpi.h>int main(int argc, char *argv[]){MPI_Init(&argc, &argv);…init_net(argc, argv);logik_init();…if(proc_type()==T_MASTER)main_master( argc, argv);if(proc_type()==T_TASK) main_task();if(proc_type()==T_CHEM) ChemThread();…MPI_Finalize();}Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.28void main_master(int argc, char *argv[]){for(j=0;j<ITT;j++){BarrierFarm();…BarrierFarm();}}Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.29for(I=0;I<ITT;I++){// выполнение диффузионного блокаGD();// обработка легковесных узлов{for(ii=0; ii<n1*n2; ii++){i = ii / n2; j = ii % n2;if(!TestForCalculating(ii)){double y[2] = {fn[i][j], fm[i][j]}, r0, r1;RungeStep(y[0], y[1], tau, &r0, &r1);N_PLUS[i][j] = r0; M_PLUS[i][j] = r1;}} // for ii}Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.30RungeStep(y[0], y[1], tau, &r0, &r1);N_PLUS[i][j] = r0; M_PLUS[i][j] = r1;}} // for ii}// обработка узлов с помощью динамической балансировкиBarrierFarm();MainServer();BarrierFarm();{// ПЕРЕХОД НА НОВЫЙ СЛОЙ ПО ВРЕМЕНИdouble **TMP;TMP = N; N = N_PLUS; N_PLUS = TMP;TMP = M; M = M_PLUS; M_PLUS = TMP;}t += tau;}FinishChemThread();}Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.31ChemThread – процедура обрабатывающего процессаЭта процедура не подлежит модификации пользователем.

Вызовбиблиотечной процедуры ChemThread полностью обеспечиваетвыполнение всех действия необходимых для вызова обрабатывающейфункции ch4 для всех заданий, обрабатываемых с помощьюдинамической балансировки.Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.32PrepareOwnPointList - формирование списка заданийКаждый управляющий процесс на основе имеющихся в его памятиданных формирует список заданий.

Каждое задание описываетсяструктурой USER_TASKPOINT. Определение данного типа дается взаголовочном файле user_task.h. Для формирования списка заданийуправляющим процессом вызывается функция intPrepareOwnPointList(void) (функция определяется в файлеuser_task.c). Внутри функции необходимо определить переменнуюn_of_our_points, в которую записывается число обрабатываемых входе выполнения итерации заданий. Далее при формированиинепосредственно списка заданий n_of_our_points раз будет вызванафункция int ExtractChemData(int name, USER_TASKPOINT *buf)(функция определяется в файле main1.c), где name – порядковый номерузла (задания), а buf – указатель на структуру, в которую будутзаписаны данные для обработки узла.Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.33ExtractChemData – запись данных одного задания в список заданийПодпрограмма заносит все данные, необходимые для автономной обработкиодного задания в список заданий.int ExtractChemData(int name, USER_TASKPOINT *buf){int i, j;i = name / n;j = name % m;buf->f[0] = _F_[i][j];buf->f[1] = _F_[i-1][j];buf->f[2] = _F_[i+1][j];buf->f[3] = _F_[i][j-1];buf->f[4] = _F_[i][j+1];return 0;Москва, 2015 г.}Динамическая балансировка загрузки © Якобовский М.В.34StoreChemData - запись результатов обработкиStoreChemData является обратной по отношению к процедуре ExtractChemDataint StoreChemData(int name, USER_TASKPOINT *p){int i, j;i = name / n;j = name % m;_F_[i][j] = p->f[0];return 0;}Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.35ch4 - обработка элементарных заданийПроцесс динамического перераспределения загрузки процессоров скрыт отпользователя.

Задания автоматически перераспределяются и передаютсяобрабатывающим процессам, которые осуществляют для каждого полученногозадания вызов функции int ch4(USER_TASKPOINT *ptask) (функцияопределяется в файле main1.c) и передают результат работы обратноуправляющему процессору. Результат работы записывается в одно из полейструктуры USER_TASKPOINT.int ch4(USER_TASKPOINT *ptask){ptask->f[0] = FFF(ptask->f[0], ptask->f[1], ptask->f[2], ptask->f[3], ptask->f[4]);return 1;}Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.36TestForCalculating –определение предполагаемого времени обработки узлаПроверка необходимости включения узла в список выполняется с помощьюфункции int TestForCalculating(int name) (функция определяется в файлеmain1.c), которая возвращает 1 при необходимости включения задания в списокдинамической балансировки и 0 – в противном случае.int TestForCalculating(int name){int i, j;i = name / n;j = name % m;if(_F_[i][j] == 0.0)elsereturn 0;return 1;}Москва, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.371.2.3.4.Алгоритм распределенной обработки данных длябалансировки загрузки при решении задач химическойкинетикиКритерий «горячих» точекОбработка своих точек - в первую очередьОтсутствиецентрализованного сбора данныхцентрализованного управления––5.Наличие«рынка» для перераспределения загрузки:–•••6.7.занятые процессорысвободные процессорыдисциплина взаимодействия процессоровМинимизация коммуникаций во время счетаОдновременность счета и коммуникацийМосква, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.38Серверный параллелизмСерверный параллелизм - метод динамическойбалансировки загрузки, применимый в случаеобработки распределенного множестваэлементарных заданий непредсказуемойтрудоёмкостиМосква, 2015 г.Динамическая балансировка загрузки © Якобовский М.В.39ЛитератураЯкобовский М.В.