20151111_msu_ServPar (1185577)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

ВМК МГУДинамическая балансировказагрузки процессоровПараллельные вычисленияЯкобовский Михаил Владимирович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ЛитератураЯкобовский М.В.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций