20161114_msu_yak_DiffBallance (Лекции)
Описание файла
Файл "20161114_msu_yak_DiffBallance" внутри архива находится в папке "Лекции". PDF-файл из архива "Лекции", который расположен в категории "". Всё это находится в предмете "параллельные методы решения задач" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
ВМК МГУДиффузная балансировка загрузкипроцессоровФрагмент лекцииЯкобовский Михаил Владимировичпроф., д.ф.-м.н.ВМК МГУ,Институт прикладной математикиим. М.В.Келдыша РАН, Москва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 0p21X1 X2 X3 X4X5 X6 X7 X8X9 X1 0 X1 1 X12X1 3 X1 4 X1 5 X1log2 nnnpS n ( n) p2 log 2 n log 2 log 2 n 2 log 2 n 2log2 n1E n ( n) p2log2 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 pcsmasterpmaxМосква, 2016 г.Параллельные вычисления© Якобовский М.В.cs6 из 41Метод коллективного решения (укладка паркета)Число порцийT1 (kn) c knОбработка порцииknTp (kn) r c s rp2Обмен данными r c 11S r c (kn) pmaxp1 s 1 r cs1pmaxsEpr cs(kn) 1s1r cМосква, 2016 г.pmax r csr – размер порцииПараллельные вычисления© Якобовский М.В.7Метод конвейерного параллелизмаT1 (kn) c knS p (kn) pМосква, 2016 г.1s1cknnTp (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 1j 0njtjВ предположении одинаковой трудоёмкости обработки каждой из точекМосква, 2016 г.Параллельные вычисления© Якобовский М.В.20Диффузная балансировкаn N'initip 1j 0njtjВ предположении одинаковой трудоёмкости обработки каждой из точекМосква, 2016 г.Параллельные вычисления© Якобовский М.В.21КонтактыЯкобовский М.В.проф., д.ф.-м.н.,зав.
сектором«Программного обеспечения вычислительныхсистем и сетей»Института прикладной математики им.М.В.Келдыша Российской академии наукmail: lira@imamod.ruweb: http://lira.imamod.ruМосква, 2016 г.Параллельные вычисления© Якобовский М.В.22.