20160912_msu_yak_02a (1185580)

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

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

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

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

Тип файла PDF

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

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

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