20161114_msu_yak_DiffBallance (1185582)

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

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

ВМК МГУДиффузная балансировка загрузкипроцессоровФрагмент лекцииЯкобовский Михаил Владимировичпроф., д.ф.-м.н.ВМК МГУ,Институт прикладной математикиим. М.В.Келдыша РАН, Москва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.

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

Тип файла PDF

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

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

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