№ | Слайд | Текст |
1 |
 |
Учебный курс Введение в параллельные алгоритмыЛекция 2 Методы построения параллельных программ Якобовский М.В., д.ф.-м.н. Институт математического моделирования РАН, Москва |
2 |
 |
Предварительные замечания… Если для нас представляют интерес реально работающие системы, то требуется убедиться, (и убедить всех сомневающихся) в корректности наших построений … системе часто придется работать в невоспроизводимых обстоятельствах, и мы едва ли можем ожидать сколько-нибудь серьезной помощи от тестов dijkstra E.W. 1966 2 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
3 |
 |
Содержание лекцииМетоды построения параллельных алгоритмов и их свойства: Статическая балансировка метод сдваивания геометрический параллелизм конвейерный параллелизм Динамическая балансировка коллективное решение Пример задачи, для параллельного решения которой необходимо создание качественно нового алгоритма 3 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
4 |
 |
Хороший параллельный алгоритмБольшим Обладает запасом внутреннего параллелизма Есть возможность одновременного выполнения операций Допускает возможность равномерного распределения вычислительных операций между процессорами Обладает низким уровнем накладных расходов Большим числом 4 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
5 |
 |
Накладные расходыОперации, отсутствующие в наилучшем последовательном алгоритме: Синхронизация Обмен данными Дублирование операций Новые операции 5 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
6 |
 |
Обмен даннымиПотери времени на передачу данных между процессами Процессор 1 Процессор 2 6 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
7 |
 |
СинхронизацияПотери времени на ожидание долго выполняющихся процессов Процессор 1 Процессор 2 Процессор 3 7 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
8 |
 |
Дублирование операцийS=0; For(i=n1;i<n;i++) S+=a[i]; Send(S) S=0; For(i=0;i<n1;i++) S+=a[i]; Send(S) Recv(S1) Recv(S2) S=S1+S2 8 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
9 |
 |
Вычисление всех факториалов до 8включительно. F=1; for(i=2;i <= n;i++) F*=i; 9 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
10 |
 |
Вычисление всех факториалов до 8включительно. 1 8 9 10 2 3 11 12 4 5 6 7 10 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
11 |
 |
Метод сдваниванияКаскадная схема Модифицированная каскадная схема В.П.Гергель Основы параллельных вычислений, лекция 4, слайд 23 11 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
12 |
 |
Стена ФоксаN – ширина стены к – высота стены 12 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
13 |
 |
Метод геометрического параллелизма13 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
14 |
 |
Метод коллективного решения (укладка паркета)14 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
15 |
 |
Метод коллективного решения (укладка паркета)R – размер порции Число порций Обработка порции Обмен данными 15 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
16 |
 |
Вычисление определенного интегралаSend(ai); Send(ai+1); Recv(s); 16 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
17 |
 |
Метод конвейерного параллелизма17 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
18 |
 |
Статическая и динамическая балансировка загрузки процессоровСтатическая балансировка метод сдваивания геометрический параллелизм конвейерный параллелизм Динамическая балансировка коллективное решение. 18 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
19 |
 |
T1= 4nс. r=0; for(i=0;i<=n;i++) { d=a[i]+b[i]+r; c[i]=d%10; r=d/10; } c[i]=r; Определение суммы двух многоразрядных чисел 19 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
20 |
 |
«Параллельный» алгоритмПоследовательное распространение разряда переноса на четырёх процессорах 20 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
21 |
 |
Спекулятивный алгоритмСпекулятивное вычисление двух сумм 21 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
22 |
 |
T’= 8n1с. Спекулятивный алгоритм r1=0; r2=1; for(i=0;i<=n1;i++) { d1=a[i]+b[i]+r1; c1[i]=d1%10; r1=d1/10; d2=a[i]+b[i]+r2; c2[i]=d2%10; r2=d2/10; } Recv(&r) if(r)c=c1; else c=c2; 22 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
23 |
 |
Спекулятивный алгоритмСпекулятивное вычисление двух сумм 23 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
24 |
 |
ЗаключениеРассмотрены методы построения параллельных алгоритмов Рассмотрена проблема балансировки загрузки процессоров Представлен масштабируемый параллельный метод сложения многоразрядных чисел, основанный на неэффективном последовательном алгоритме 24 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
25 |
 |
Вопросы для обсужденияВ чем заключается проблема балансировки загрузки? В чем заключаются методы геометрического параллелизма, конвейерного параллелизма и коллективного решения? Чем определяются максимальные ускорения, достигаемые при применении этих методов? В чем отличие методов статической и динамической балансировки загрузки? 25 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
26 |
 |
КонтактыЯкобовский М.В. д.ф.-м.н., зав. сектором «Программного обеспечения многопроцессорных систем и вычислительных сетей» Института математического моделирования Российской академии наук mail: lira@imamod.ru web: http://lira.imamod.ru 26 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. |
«Параллельные алгоритмы» |
http://900igr.net/prezentatsii/informatika/Parallelnye-algoritmy/Parallelnye-algoritmy.html