20161114_msu_yak_DiffBallance (Лекции)

ВМК МГУДиффузная балансировка загрузкипроцессоровФрагмент лекцииЯкобовский Михаил Владимировичпроф., д.ф.-м.н.ВМК МГУ,Институт прикладной математикиим. М.В.Келдыша РАН, Москва1Содержание лекцииМетоды построения параллельных алгоритмов иих свойства:– Статическая балансировка• метод сдваивания• геометрический параллелизм• конвейерный параллелизм– Динамическая балансировка• коллективное решение• диффузная балансировка загрузкиМосква, 2016 г.Параллельные вычисления© Якобовский М.В.2Метод сдваиванияКаскадная схемаa1a2a1+a2a3a4a3+a4a1+a2+a3+a4a5a6a5+a6a7a8a7+a8a5+a6+a7+a8a1+a2+a3+a4+a5+a6+a7+a8Tp  n / 2 (n)   c log 2 nS p n / 2Москва, 2016 г.n  1( n) log 2 nПараллельные вычисления1E p  n / 2 ( n) log 2 n© Якобовский М.В.3Метод сдваиванияМодифицированная каскадная схемаnTp   c  ( c   s ) log 2 ppT n (n)  2 c log 2 n,s  0p21X1 X2 X3 X4X5 X6 X7 X8X9 X1 0 X1 1 X12X1 3 X1 4 X1 5 X1log2 nnnpS n ( n) p2 log 2 n  log 2 log 2 n 2 log 2 n 2log2 n1E n ( n) p2log2 nМосква, 2016 г.Параллельные вычисления© Якобовский М.В.46Метод геометрического параллелизмаT1 (kn)   c kn1S p (kn)  pp s1 4n cМосква, 2016 г.knTp (kn)   c 4k sp1E p (kn) p s1 4n cПараллельные вычисления© Якобовский М.В.5Метод коллективного решенияNTp   c   s pcsmasterpmaxМосква, 2016 г.Параллельные вычисления© Якобовский М.В.cs6 из 41Метод коллективного решения (укладка паркета)Число порцийT1 (kn)   c knОбработка порцииknTp (kn)  r c   s rp2Обмен данными r c 11S r c (kn)   pmaxp1  s  1  r cs1pmaxsEpr cs(kn) 1s1r cМосква, 2016 г.pmax r csr – размер порцииПараллельные вычисления© Якобовский М.В.7Метод конвейерного параллелизмаT1 (kn)   c knS p (kn)  pМосква, 2016 г.1s1cknnTp (kn)   c k spp1E p (kn) s1Параллельные вычисленияc© Якобовский М.В.8Метод конвейерного параллелизмапроцессор 0процессор 1процессор 2T1 (kn)   c kn1S p (kn)  pp s1 2n cМосква, 2016 г.Параллельные вычисленияпроцессор 3knTp (kn)   c 2k sp1E p (kn) p s1 2n c© Якобовский М.В.9Учет стартовых и финальных затратМетод эффективен приМаксимальная степень параллелизма:Максимальное ускорение:Москва, 2016 г.Параллельные вычисления© Якобовский М.В.10Диффузная балансировкаПричины дисбаланса вычислительной нагрузки– Разные процессоры– Внешнее воздействие– Разная вычислительная сложность заданийРезультат дисбаланса– Эффективная производительность определяетсясамым медленным процессоромМосква, 2016 г.Параллельные вычисления© Якобовский М.В.11Медленный процессорКакой объем работ забрать у среднегопроцессора и кому его передать?Москва, 2016 г.Параллельные вычисления© Якобовский М.В.12Метод геометрического параллелизмаМосква, 2016 г.Параллельные вычисления© Якобовский М.В.13Метод геометрического параллелизмаМосква, 2016 г.Параллельные вычисления© Якобовский М.В.14Диффузная балансировка загрузкиМосква, 2016 г.Параллельные вычисления© Якобовский М.В.15Диффузная балансировка загрузкиМосква, 2016 г.Параллельные вычисления© Якобовский М.В.16Диффузная балансировка загрузкиМосква, 2016 г.Параллельные вычисления© Якобовский М.В.17Статическое распределениеМосква, 2016 г.Параллельные вычисления© Якобовский М.В.18Постановка задачи диффузной балансировкиДано:• Количество точек – N• Количество процессоров – p• Процессор i обработал ni точек за время ti• Для обработки любой точки требуется одинаковое числооперацийТребуется:• Найти количества точек n’i , которое следует обработатьпроцессорам на следующем шаге• Определить сколько точек каждый из процессоров долженпередать соседним процессорамМосква, 2016 г.Параллельные вычисления© Якобовский М.В.19Диффузная балансировкаn N'initip 1j 0njtjВ предположении одинаковой трудоёмкости обработки каждой из точекМосква, 2016 г.Параллельные вычисления© Якобовский М.В.20Диффузная балансировкаn N'initip 1j 0njtjВ предположении одинаковой трудоёмкости обработки каждой из точекМосква, 2016 г.Параллельные вычисления© Якобовский М.В.21КонтактыЯкобовский М.В.проф., д.ф.-м.н.,зав.

сектором«Программного обеспечения вычислительныхсистем и сетей»Института прикладной математики им.М.В.Келдыша Российской академии наукmail: lira@imamod.ruweb: http://lira.imamod.ruМосква, 2016 г.Параллельные вычисления© Якобовский М.В.22.