20160905_msu_yak_01b_0 (Лекции)

Основные понятияПараллельныевысокопроизводительныевычисленияЯкобовский М.В., проф., д.ф.-м.н.СКИ МГУ,Институт прикладной математикиим. М.В.Келдыша РАН, МоскваМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.1Содержание лекцииМногопроцессорные системы– с распределенной памятью– с общей памятью– ГибридныеМодели выполнения программСвойства канала передачи данныхМетоды взаимодействия процессов– Методы передачи данных– СемафорыУскорение и эффективность параллельных алгоритмовПример алгоритма с низкой эффективностью, но высокимбыстродействиемМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.2Транспьютерная материнская плата МТБ-8Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.3Транспьютер и оперативная памятьМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.4Три транспьютера на плате МТБ-8Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.5Структура транспьютера T-800Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.6Узел с общей памятью – транспьютер и процессоробщего назначенияМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.7Узел PowerXplorerМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.8Гибридная системаМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.9ВопросЗачем нужны транспьютерные линки?a.

Для ввода-вывода данныхb. Для подвода питания к транспьютерамc. Для передачи данных между транспьютерамиМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.10ВопросМожно ли на основе транспьютеров делатьсистемы с общей памятью?a. Можно делатьb. Нельзя делатьc. Только такие системы и можно делатьМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.11Уточнение круга рассматриваемых системСистемы на основе объединенныхсетью типовых вычислительныхузлов – системы с распределеннойоперативной памятьюСеть передачи данныхСистемы с доступом всехпроцессоров к общей оперативнойпамятипроцессороперативная памятьвычислительный узелПараллельные высокопроизводительныеМосква, 2016 г.вычисления: Основные понятия ©12Модель выполнения программы на распределеннойпамятиПри запуске указывается число требуемых процессоров Np и названиепрограммыНа выделенных для расчета узлах запускается Npкопий программы– Например, на двух узлах запущены три копии программы.

Копия программы сномером 1 не имеет непосредственного доступа к оперативной памяти копий 0 и 2:Вычислительный узел 10Вычислительный узел 212В каждой копии программы известны значения двух переменных– Np – одинаковое во всех копиях – число копий– rank из диапазона [0 … Np-1] – уникальный номер копииЛюбые две копии программы могут непосредственно обмениватьсяданными с помощью функций передачи сообщений Send/RecvМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.13Синхронные обмены даннымиA=3Send(&A)A=5A=3B=4Recv(&B)Print(B)B=4SendRecvРезультат3Print(B)A=5Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.14Свойства канала передачи данныхT(n)=n*Tпередачи байта+ TлатентностиGbit EthernetЧисло передаваемых байтМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.15Свойства канала передачи данныхT(n)=n*Tпередачи байта+ TлатентностиВремя передачи данных (мкс)2.001.501.000.50Infiniband0.000100020003000400050006000Число передаваемых байт6.8 Гбайт/сЗа 0.7 мкс передаётся 5 КбайтМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.16ВопросПри каком способе передачи массива чисел будетзатрачено меньше времени?a.

Передача каждого числа отдельным сообщениемb. Объединение всех чисел в единый массив и передачамассива одним сообщениемc. Не имеет значенияМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.17Модель выполнения программы на общей памятиРабота начинается с запуска одногоэкземпляра программыПри необходимости программа порождает новые процессы, каждый из которых:– Обладает собственными локальными переменными– Имеет доступ к глобальным переменнымint a_global;mainmain(){int b1_local;Запуск нити(fun())}fun(){int b2_local;Запуск нити(…)}Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.18Модель выполнения программы на общей памятиРабота начинается с запуска одногоэкземпляра программыПри необходимости программа порождает новые процессы, каждый из которых:– Обладает собственными локальными переменными– Имеет доступ к глобальным переменнымint a_global;mainнить1main(){int b1_local;Запуск нити(fun())}fun(){int b2_local;Запуск нити(…)}Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.19Модель выполнения программы на общей памятиРабота начинается с запуска одногоэкземпляра программыПри необходимости программа порождает новые процессы, каждый из которых:– Обладает собственными локальными переменными– Имеет доступ к глобальным переменнымint a_global;mainнить1нить2main(){int b1_local;Запуск нити(fun())}fun(){int b2_local;Запуск нити(…)}Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.20Модель выполнения программы на общей памятиРабота начинается с запуска одногоэкземпляра программыПри необходимости программа порождает новые процессы, каждый из которых:– Обладает собственными локальными переменными– Имеет доступ к глобальным переменнымint a_global;mainнить1нить2main(){int b1_local;Запуск нити(fun())}fun(){int b2_local;Запуск нити(…)}Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.21Что будет напечатано?int a=1;Нить1Нить2{{a=a+2}a=a+3}Нить3{print(a)}a=?Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.22Что будет напечатано?int a=1;Нить1{a=a+2}Нить2{a=a+3}Нить3{print(a)}6Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.23Что будет напечатано?int a=1;Нить1{a=a+2}Нить3{print(a)}Нить2{a=a+3}Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.324Что будет напечатано?int a=1;Нить1Нить2{{a=a+2a=a+3}}Нить332Процессор1Процессор22+1=33+1=434{print(a)}6 ? 4 ? 3Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.25Что будет напечатано?int a=1;Нить1Нить2{{a=a+2}Нить3a=a+3}{print(a)}6 ? 4 ? 3 ? __Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.26СемафорЦелочисленная неотрицательная переменная Инициализация и две атомарные операцииОперация V(S)– Увеличивает значение S на 1Операция P(S)– Если S положительно, то уменьшает S на 1– Иначе ждет, пока S не станет больше 0Языки программирования.

Редактор Ф.Женюи. Перевод с англ.В.П.Кузнецова. Под ред. В.М.Курочкина. М:."Мир", 1972 Э. Дейкстра.Взаимодействие последовательных процессов.http://khpi-iip.mipk.kharkiv.edu/library/extent/dijkstra/ewd123/index.htmlМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.27Что будет напечатано?int a=0;Sem S=1, S1=0, S2=0;Нить1Нить2{P(S)a=a+2V(S)V(S1)}{P(S)a=a+3V(S)V(S2)}Нить3{P(S1)P(S2)print(a)}6Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.28Ускорение и эффективность параллельныхалгоритмовускорениепараллельногоалгоритмаэффективностьиспользованиявычислительной мощностиE(p)=S(p)/pS(p)=T(1)/T(p)Может ли ускорение превышать число процессоров?S(p)> pE(p)>100%Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.29Ускорение и эффективность параллельныхалгоритмовускорениепараллельногоалгоритмаэффективностьиспользованиявычислительной мощностиS(p)=T(1)/T(p)Может ли ускорение превышать число процессоров?S(p)> pE(p)>100%Москва, 2016 г.E(p)=S(p)/pДа, если учитывать влияниеаппаратных особенностейвычислительной системыПараллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.30Ускорение и эффективность параллельныхалгоритмовускорениепараллельногоалгоритмаэффективностьиспользованиявычислительной мощностиS(p)=T(1)/T(p)Может ли ускорение превышать число процессоров?S(p)> pE(p)>100%Москва, 2016 г.E(p)=S(p)/pДа, если выбран неудачныйпоследовательный алгоритмПараллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.31Может ли быть S(p)>p ?– Пример неудачного последовательного алгоритмаСортировкамассивасортировкаполовинымассивасортировкаполовинымассиваслияние отсортированных половинок массиваМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.32Может ли быть S(p)>p ?– Пример неудачного последовательного алгоритмаСортировкамассивасортировкаполовинымассивасортировкаполовинымассиваслияние отсортированных половинок массиваМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.33Может ли быть S(p)>p ?– В последовательном алгоритме выполняется большеопераций, чем в параллельномСортировкамассивасортировкаполовинымассивасортировкаполовинымассиваслияние отсортированных половинок массиваМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.34Ускорение и эффективность параллельныхалгоритмовускорениепараллельногоалгоритмаэффективностьиспользованиявычислительной мощностиE(p)=S(p)/pS(p)=T(1)/T(p)Ускорение параллельногоалгоритма относительнонаилучшего последовательного**S (p)= T (1)/T(p)**E (p)= S (p)/pМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.35Может ли неэффективный алгоритм работатьбыстрее эффективного?Да– Если первый алгоритм позволяет использовать большепроцессоров, чем второй.Самый эффективный алгоритм – использующийодин (1) процессор.– Его эффективность равна 100%,но он не всегда самый быстрый.Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.36Определить сумму конечного рядаn известно заренее, меняется только х Все элементарные операции (+ - * / )выполняются за время с Все операции выполняются точно, результат независит от порядка их выполнения Число процессоров не ограниченоМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.37Последовательный алгоритмS=1;a=1;for(i=1;i<= n;i++){a=a*x/i;S=S+a;}Москва, 2016 г.T1= 3nсПараллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.38Параллельный алгоритмВычислить для всехi =1,…,n :xiВычислить для всехi =1,…,n :i!Вычислить для всехi =1,…,n : ai =Вычислить сумму всех членовМосква, 2016 г.aiПараллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.39xiДля вычисления xi воспользуемся методомбинарного умноженияxx212x3x534 x9 x10Москва, 2016 г.x6x11 x12x4x7x8x13 x14 x15 x16Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.40Параллельное вычисление всех требуемыхi! ??Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.41i!4 12 34 56 78910 1112 1314 1516=16!3 1 2  3 4  5 6  7 8910 1112 1314 15162 12 34 56 78 910 1112 1314 15161 12 34 56 78Москва, 2016 г.910 1112 1314 1516Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.4214!Для вычисления i! воспользуемсяаналогичным методом4 12 34 56 78910 1112 1314=14!3 1 2  3 4  5 6  7 82910 1112 131412 34 56 78 910 11121 1 2 3 4 5 6 7 8Москва, 2016 г.910 1112 1314 1516Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.43Новые операцииВычисление всех факториалов до 4! включительноШаг123Москва, 2009 г.Процессор 1Процессор 2Процессор 3Процессор 42!=123!= 123 4!=1234Параллельные методы и алгоритмы: Методы построенияпараллельных программ © Якобовский М.В.44 из 60Новые операцииВычисление всех факториалов до 4! включительноШаг123Шаг123Процессор 1Процессор 22!=123!=(2!) (3)4!=(12)(34)Процессор 1Процессор 22!=123!=12 34!=1234Москва, 2009 г.Процессор 3 Процессор 4Процессор 3 Процессор 4Параллельные методы и алгоритмы: Методы построенияпараллельных программ © Якобовский М.В.45 из 60Новые операцииВычисление всех факториалов до 4! включительноШаг123Москва, 2009 г.Процессор 1Процессор 21 21233 41234Процессор 3Параллельные методы и алгоритмы: Методы построенияпараллельных программ © Якобовский М.В.Процессор 446 из 60Новые операцииВычисление всех факториалов до 8! включительноШаг123Москва, 2009 г.Процессор 1Процессор 21 2123123453 41234123456Процессор 3Процессор 45 67 856756781234567 12345678Параллельные методы и алгоритмы: Методы построенияпараллельных программ © Якобовский М.В.47 из 60Новые операцииВычисление всех факториалов до 8! включительноШаг123Процессор 1Процессор 21 2123123453 41234123456F=1;for(i=2;i <= n;i++)F*=i;Процессор 3Процессор 45 67 856756781234567 12345678Tp  n / 2 (n)   c log 2 nn 17S  2.33(3)  4  plog 2 n n 8 3p 4T1 (n)   c (n  1)Москва, 2009 г.E p  4 (n  8) 712Параллельные методы и алгоритмы: Методы построенияпараллельных программ © Якобовский М.В.48 из 60Новые операцииШаг123Процессор 1Процессор 2Процессор 3Процессор 41 2123123453 45 67 812345675678123456 1234567 12345678n 177Tp n / 2 (n)   c log 2 n S   4  p E p 4 (n  8) log 2 n n 8 312p 4Шаг123Москва, 2009 г.Процессор 11242!3!5!Процессор 28353 44!6!Процессор 391165 65677!Параллельные методы и алгоритмы: Методы построенияпараллельных программ © Якобовский М.В.Процессор 4101277 856788!49 из 60Параллельный алгоритмВычислить для всехi =1,…,n : xiTp n / 2 (n)   c log 2 nВычислить для всехi =1,…,n : i!Tp n / 2 (n)   c log 2 nВычислить для всехi =1,…,n : ai =Вычислить сумму всех членовМосква, 2016 г.aiПараллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.xii!Tp n (n)   cTp n / 2 (n)   c log 2 n50ЗаключениеОпределены классы рассматриваемыхвычислительных систем Представлены модели параллельных программ Представлен ряд способов организациивзаимодействия последовательных процессов Представлен алгоритм, обладающий низкойэффективностью, но высоким быстродействиемМосква, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.64Вопросы для обсужденияСколько нужно процессоров для вычислениясуммы рядаза время2где q – константа+q,Приведите примеры алгоритмов, обладающихэффективностью больше 100%.Есть ли процессорные инструкции P(S) и V(S)?Москва, 2016 г.Параллельные высокопроизводительные вычисления: Основныепонятия © Якобовский М.В.65КонтактыЯкобовский М.В.д.ф.-м.н., проф.,зав.

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