Презентация "Методы построения параллельных программ" по информатике – проект, доклад

Лекция 2 Методы построения параллельных программ

Учебный курс Введение в параллельные алгоритмы

Якобовский М.В., д.ф.-м.н. Институт математического моделирования РАН, Москва

… если для нас представляют интерес реально работающие системы, то требуется убедиться, (и убедить всех сомневающихся) в корректности наших построений … системе часто придется работать в невоспроизводимых обстоятельствах, и мы едва ли можем ожидать сколько-нибудь серьезной помощи от тестов Dijkstra E.W. 1966

Предварительные замечания

Москва, 2009 г.

Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

2 из 26

Методы построения параллельных алгоритмов и их свойства: Статическая балансировка метод сдваивания геометрический параллелизм конвейерный параллелизм Динамическая балансировка коллективное решение Пример задачи, для параллельного решения которой необходимо создание качественно нового алгоритма

Содержание лекции

3 из 26

Обладает запасом внутреннего параллелизма Есть возможность одновременного выполнения операций Допускает возможность равномерного распределения вычислительных операций между процессорами Обладает низким уровнем накладных расходов

Хороший параллельный алгоритм

большим большим числом 4 из 26

Операции, отсутствующие в наилучшем последовательном алгоритме: Синхронизация Обмен данными Дублирование операций Новые операции

Накладные расходы

5 из 26

Потери времени на передачу данных между процессами Процессор 1 Процессор 2

Обмен данными 6 из 26

Потери времени на ожидание долго выполняющихся процессов Процессор 1 Процессор 2 Процессор 3

Синхронизация 7 из 26

S=0; For(i=0;i

Дублирование операций

S=0; For(i=n1;i

Recv(S1) Recv(S2) S=S1+S2 8 из 26

Вычисление всех факториалов до 8! включительно

F=1; for(i=2;i <= n;i++) F*=i; 9 из 26

1 2 4 3 8 5 9 11 6 7 12 10 из 26

Метод сдванивания

Каскадная схема Модифицированная каскадная схема В.П.Гергель Основы параллельных вычислений, лекция 4, слайд 23

11 из 26

Стена Фокса

n – ширина стены к – высота стены

12 из 26

Метод геометрического параллелизма

13 из 26

Метод коллективного решения (укладка паркета)

14 из 26

Число порций Обработка порции r – размер порции 15 из 26

Send(ai); Send(ai+1); Recv(s);

Вычисление определенного интеграла

16 из 26

Метод конвейерного параллелизма

17 из 26

Статическая и динамическая балансировка загрузки процессоров Статическая балансировка метод сдваивания геометрический параллелизм конвейерный параллелизм Динамическая балансировка коллективное решение

18 из 26

r=0; for(i=0;i<=n;i++) { d=a[i]+b[i]+r; c[i]=d%10; r=d/10; } c[i]=r;

Определение суммы двух многоразрядных чисел

T1= 4nс 19 из 26

Последовательное распространение разряда переноса на четырёх процессорах

«Параллельный» алгоритм

20 из 26

Спекулятивное вычисление двух сумм

Спекулятивный алгоритм

21 из 26

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;

T’= 8n1с 22 из 26

23 из 26

Рассмотрены методы построения параллельных алгоритмов Рассмотрена проблема балансировки загрузки процессоров Представлен масштабируемый параллельный метод сложения многоразрядных чисел, основанный на неэффективном последовательном алгоритме

Заключение 24 из 26

В чем заключается проблема балансировки загрузки? В чем заключаются методы геометрического параллелизма, конвейерного параллелизма и коллективного решения? Чем определяются максимальные ускорения, достигаемые при применении этих методов? В чем отличие методов статической и динамической балансировки загрузки?

Вопросы для обсуждения

25 из 26

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

Контакты 26 из 26