20160912_msu_yak_02a (Лекции)

Базовые алгоритмыПараллельныевысокопроизводительныевычисленияЯкобовский М.В., проф., д.ф.-м.н.СКИ МГУ,Институт прикладной математикиим. М.В.Келдыша РАН, МоскваМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.1Ускорение и эффективность параллельныхалгоритмовускорениепараллельногоалгоритмаэффективностьиспользованиявычислительной мощностиS(p)=T(1)/T(p)Может ли ускорение превышать число процессоров?S(p)> pE(p)>100%Москва, 2016 г.E(p)=S(p)/pДа, если учитывать влияниеаппаратных особенностейвычислительной системыДа, если выбран неудачныйпоследовательный алгоритмПараллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.2Может ли быть S(p)>p ?– В последовательном алгоритме выполняется большеопераций, чем в параллельномСортировкамассивасортировкаполовинымассивасортировкаполовинымассиваслияние отсортированных половинок массиваМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.3Ускорение и эффективность параллельныхалгоритмовускорениепараллельногоалгоритмаэффективностьиспользованиявычислительной мощностиE(p)=S(p)/pS(p)=T(1)/T(p)Ускорение параллельногоалгоритма относительнонаилучшего последовательного**S (p)= T (1)/T(p)**E (p)= S (p)/pМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.4Неубедительность тестирования… если для нас представляют интерес реальноработающие системы, то требуетсяубедиться, (и убедить всех сомневающихся) вкорректности наших построений… системе часто придется работать вневоспроизводимых обстоятельствах, и мы едвали можем ожидать сколько-нибудь серьезнойпомощи от тестовDijkstra E.W.1966Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.5Простые алгоритмы и их свойстваВремя выполнения параллельного алгоритма Методы построения параллельных алгоритмов– Статическая балансировка• метод сдваивания• геометрический параллелизм• конвейерный параллелизм– Динамическая балансировка• коллективное решение• диффузная балансировка загрузкиМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.6Хороший параллельный алгоритмбольшимОбладает запасом внутреннего параллелизма– Есть возможность одновременного выполнениямножества операцийДопускает возможность равномерногораспределения вычислительных операций междупроцессорамибольшим числом Обладает низким уровнем накладных расходовМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.7К вопросу о накладных расходах- доля операций выполняемых последовательно- дополнительные расходы времениМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.8Закон Амдаля- доля операций выполняемых последовательноМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.9Накладные расходыОперации, отсутствующие в наилучшемпоследовательном алгоритме:––––СинхронизацияОбмен даннымиДублирование операцийНовые операцииМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.10Обмен даннымиПотери времени на передачу данных между процессамиПроцессор 1Москва, 2016 г.Процессор 2Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.11СинхронизацияПотери времени на ожидание долго выполняющихся процессовПроцессор 1Москва, 2016 г.Процессор 2Процессор 3Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.12Дублирование операцийS=0;For(i=0;i<n1;i++)S+=a[i];Send(S)S=0;For(i=n1;i<n;i++)S+=a[i];Send(S)Recv(S1)Recv(S2)S=S1+S2Москва, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.13Новые операцииШаг123Процессор 1Процессор 2Процессор 3Процессор 41⋅ 212⋅31234⋅53⋅ 45⋅ 67⋅ 812⋅3456⋅756⋅781234⋅56 1234⋅567 1234⋅5678n −177T p = n / 2 (n) = τ c log 2 n S == < 4 = p E p = 4 (n = 8) =log 2 n n =8 312p =4Шаг123Москва, 2016 г.Процессор 11242!3!5!Процессор 28353⋅ 44!6!Процессор 391165⋅ 656⋅77!Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.Процессор 4101277⋅ 856⋅788!14- дополнительные расходы времениОперации, отсутствующие в наилучшемпоследовательном алгоритме:––––СинхронизацияОбмен даннымиДублирование операцийНовые операцииМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.15Принципы организации параллельныхвычисленийСтатическая балансировка загрузки– метод сдваивания– геометрический параллелизмДинамическая балансировка загрузки– Метод коллективного решенияМосква, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.16Метод сдваиванияВыполнение редукционных и им подобныхопераций––––a1Определение суммы элементов массиваОпределение минимального элемента массиваШироковещательная рассылка данных…a2a1+a2a3a4a3+a4a1+a2+a3+a4a5a6a5+a6a8a7+a8a5+a6+a7+a8a1+a2+a3+a4+a5+a6+a7+a8Москва, 2016 г.a7aaaaaaaaaaaaaaaПараллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.17Метод сдваиванияКаскадная схемаT p = n / 2 (n) = τ c log 2 nS p =n / 2TS(n − 1)( n) =log 2 na1a2a1+a21E p = n / 2 ( n) ≈log 2 na3a4a3+a4a1+a2+a3+a4a5a6a7a5+a6a8a7+a8a5+a6+a7+a8a1+a2+a3+a4+a5+a6+a7+a8Модифицированная каскадная схемаnp=log 2 nnp=log 2 n(n) ≈ 2τ c log 2 n( n) ≈(n − 1)2 log 2 nМосква, 2016 г.211E n ( n) ≈p=2log 2 nX1 X2 X3 X4X5 X6 X7 X8Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.X9 X1 0 X1 1 X12X1 3 X1 4 X1 5 X1186В чем причина низкой эффективности методасдваивания?T p = n / 2 (n) = τ c log 2 n1E p = n / 2 ( n) ≈log 2 nnS p = n / 2 ( n) ≈log 2 nМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.19Метод геометрического параллелизмаЦиклическая обработка локально связанныхданных– Обработка изображений– Обработка данных, заданных на решетках илипроизвольных графах– Моделирование физических процессов (теченийжидкости и газов, теплопереноса, упругости, …)–…Москва, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.20Пример модельной задачи: Стена Фоксаn – ширина стенык – высота стеныМосква, 2016 г.Параллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.21Метод геометрического параллелизмаT1 (kn) = τ c kn1S p (kn) = pp τs1+ 4n τcМосква, 2016 г.kn+ 4kτ sTp (kn) = τ cp1E p (kn) =p τs1+ 4n τcПараллельные высокопроизводительные вычисления. Базовые алгоритмы© Якобовский М.В.22А почему?for(шаг=0;шаг<k;шаг++){knT p (kn) = τ c+ 4kτ spfor(кирпич=rank*n/p;кирпич<(rank+1)*n/p;кирпич++)Уложить(кирпич)if(rank>0)if(rank<p-1)if(rank>0)if(rank<p-1)Send(rank-1,Send(rank+1,Recv(rank-1,Recv(rank+1,кирпич уложен!кирпич уложен!место готово?место готово?))))}Москва, 2016 г.Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.23kn+ 4kτ sTp (kn) = τ cp? Верно ли, что именно 4?for(шаг=0;шаг<k;шаг++){for(кирпич=rank*n/p;кирпич<(rank+1)*n/p;кирпич++)Уложить(кирпич)if(rank>0)if(rank<p-1)if(rank>0)if(rank<p-1)Send(rank-1,Send(rank+1,Recv(rank-1,Recv(rank+1,кирпич уложен!кирпич уложен!место готово?место готово?))))}0⇒=<Москва, 2016 г.1⇐⇒>==<2⇐⇒>==<3⇐⇒>==<4⇐⇒>==<Параллельные высокопроизводительные вычисления.

Базовые алгоритмы© Якобовский М.В.5⇐>=24kn+ 4kτ sTp (kn) = τ cp?for(шаг=0;шаг<k;шаг++){for(кирпич=rank*n/p;кирпич<(rank+1)*n/p;кирпич++)Уложить(кирпич)if(rank>0)if(rank<p-1)if(rank>0)if(rank<p-1)Send(rank-1,Send(rank+1,Recv(rank-1,Recv(rank+1,кирпич уложен!кирпич уложен!место готово?место готово?))))}0⇒=<Москва, 2016 г.1⇐⇒>==<2⇐⇒>==<3⇐⇒>==<4⇐⇒>==<Параллельные высокопроизводительные вычисления.