20160912_msu_yak_02b (Лекции)

Базовые алгоритмы. Часть 2ПараллельныевысокопроизводительныевычисленияЯкобовский М.В., проф., д.ф.-м.н.СКИ МГУ,Институт прикладной математикиим. М.В.Келдыша РАН, МоскваМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.1Содержание лекцииМетоды построения параллельных алгоритмов иих свойства:– Статическая балансировка• метод сдваивания• геометрический параллелизм• конвейерный параллелизм– Динамическая балансировка• коллективное решение• диффузная балансировка загрузкиМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.2Метод коллективного решенияРешение множества независимых друг от другазаданий, в таких прикладных областях как:– Табулирование функций– Решение задач методами Монте-Карло– Численное интегрирование гладких многомерныхфункций–…Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.3Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.4Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.5Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.6Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.7Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.8Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.9Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.10Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.11Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.12Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.13Найти самую глубокую скважинуМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.14Метод коллективного решенияNTp = (τ c + τ s )pτcτsmasterpmaxМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.τc=τs15Пример модельной задачи: Укладка паркетаT1 (kn) = τ c knT p (kn) =Число порцийОбработка порцииkn(rτ c + τ s )rp2Обмен данными rτ c 11S rτ c (kn) = = pmaxp=1 τ s  1 + rτ cτs1+pmaxτsEp=rτ cτs(kn) =1τs1+rτ cМосква, 2016 г.pmax =rτ cτsr – размер порцииПараллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.16Как правильно?r – размер порцииpmax =rτ cτsилиpmaxrτ c τ c==rτ s τ sЗависит ли время передачи данных от размера порции (задания)?Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.17Вычисление определенного интегралаSend(ai); Send(ai+1); Recv(s);BI = ∫ f ( x )dx = ∑iAai +1∫ f (x )dxaiT p = τ s + max τ iiaiМосква, 2016 г.τ1ai+1τ2Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.18Метод конвейерного параллелизмаkn+?T1 (kn) = τ c kn Tp (kn) = τ cpМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.19Метод конвейерного параллелизмаT1 (kn) = τ c knS p (kn) = pМосква, 2016 г.1τs1+τcnkn+ k τsT p (kn) = τ cpp1E p (kn) =τs1+τcПараллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.20Метод геометрического параллелизмаT1 (kn) = τ c kn1S p (kn) = pp τs1+ 4n τcМосква, 2016 г.kn+ 4kτ sTp (kn) = τ cp1E p (kn) =p τs1+ 4n τcПараллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.21Метод конвейерного параллелизмаfor(t=0; t<tmax; t+=dt){fnew[0]=g(t);for(i=1; i<n; i++)fnew[i]= fnew[i-1]+f[i]for(i=0;i<n;i++)f[i] = fnew [i]fnew[i]}f[i]0Москва, 2016 г.123456Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.722Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.23Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.24Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.25Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.26Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.27Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.28Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.29Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.30Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.31Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.32Метод конвейерного параллелизмапроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.33Метод конвейерного параллелизмаT1 (kn) = τ c knS p (kn) = pМосква, 2016 г.1τs1+τcnkn+ k τsT p (kn) = τ cpp1E p (kn) =τs1+τcПараллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.34Метод конвейерного параллелизмапроцессор 0процессор 1процессор 2T1 (kn) = τ c kn1S p (kn) = pp τs1+ 2n τcМосква, 2016 г.процессор 3kn+ 2kτ sTp (kn) = τ cp1E p (kn) =p τs1+ 2n τcПараллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.35Объём хранимых данныхпроцессор 0процессор 1процессор 2T1 (kn) = τ c kn1S p (kn) = pp τs1+ 2n τcМосква, 2016 г.процессор 3kn+ 2kτ sTp (kn) = τ cp1E p (kn) =p τs1+ 2n τcПараллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.36Учет стартовых и финальных затратпроцессор 0Москва, 2016 г.процессор 1процессор 2процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.37Учет стартовых и финальных затратМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.38Учет стартовых и финальных затратМетод эффективен приМаксимальная степень параллелизма:Максимальное ускорение:Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.39Диффузная балансировкаПричины дисбаланса вычислительной нагрузки– Разные процессоры– Внешнее воздействие– Разная вычислительная сложность заданийРезультат дисбаланса– Эффективная производительность определяетсясамым медленным процессоромМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.40Медленный процессорКакой объем работ забрать у среднегопроцессора и кому его передать?Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.41Метод геометрического параллелизмаМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.42Метод геометрического параллелизмаМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.43Диффузная балансировка загрузкиМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.44Диффузная балансировка загрузкиМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.45Диффузная балансировка загрузкиМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.46Статическое распределениеМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.47Постановка задачи диффузной балансировкиДано:• Количество точек – N• Количество процессоров – p• Процессор i обработал ni точек за время ti• Для обработки любой точки требуется одинаковое числооперацийТребуется:• Найти количества точек n’i , которое следует обработатьпроцессорам на следующем шаге• Определить сколько точек каждый из процессоров долженпередать соседним процессорамМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.48Диффузная балансировкаn =N'initip −1∑j =0njtjВ предположении одинаковой трудоёмкости обработки каждой из точекМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.49Диффузная балансировкаn =N'initip −1∑j =0njtjВ предположении одинаковой трудоёмкости обработки каждой из точекМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.50Простые алгоритмыСтатическая и динамическая балансировказагрузки процессоров– Статическая балансировка• метод сдваивания• геометрический параллелизм• конвейерный параллелизм– Динамическая балансировка• коллективное решение• диффузная балансировкаМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.51ЗаключениеОтмечена важность использования простых слогической точки зрения алгоритмов Рассмотрен метод коллективного решения,относящийся к классу методов динамическойбалансировки загрузки процессоров Рассмотрены методы динамическойбалансировки загрузки процессоров:– метод коллективного решения– метод диффузной балансировки загрузкиРассмотрен метод конвейерного параллелизмаМосква, 2016 г.Параллельные высокопроизводительные вычисления.

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