20160905_msu_yak_01b_0 (1185579)

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

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

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

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

Тип файла PDF

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

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

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