'

Интернет Университет Суперкомпьютерных технологий

Понравилась презентация – покажи это...





Слайд 0

Интернет Университет Суперкомпьютерных технологий Лекция 3 Методы построения параллельных программ (продолжение) Учебный курс Введение в параллельные алгоритмы Якобовский Михаил Владимирович проф., д.ф.-м.н. Институт прикладной математики им. М.В.Келдыша РАН, Москва 1


Слайд 1

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


Слайд 2

Методы построения параллельных алгоритмов и их свойства: Статическая балансировка метод сдваивания геометрический параллелизм конвейерный параллелизм Динамическая балансировка коллективное решение диффузная балансировка загрузки Содержание лекции Москва, 2010 г. 3 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 3

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


Слайд 4

Стена Фокса Москва, 2010 г. n – ширина стены к – высота стены 5 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 5

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


Слайд 6

Метод коллективного решения (укладка паркета) Москва, 2010 г. 7 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 7

Метод коллективного решения (укладка паркета) Москва, 2010 г. Число порций Обработка порции Обмен данными r – размер порции 8 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 8

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


Слайд 9

Москва, 2010 г. ? Метод конвейерного параллелизма Время выполнения на p процессорах 10 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 10

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


Слайд 11

Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 12 Метод конвейерного параллелизма for(t=0;t<tmax;t+=dt) { fnew[0]=g(t); for(i=1;i<n;i++) fnew[i]= f[i-1]+f[i] for(i=0;i<n;i++) f[i]= fnew [i] } 0 1 2 3 4 5 6 7 f[i] fnew[i]


Слайд 12

Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 13 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3


Слайд 13

Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 14 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3


Слайд 14

Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 15 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3


Слайд 15

Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 16 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3


Слайд 16

Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 17 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3


Слайд 17

Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 18 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3


Слайд 18

Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 19 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3


Слайд 19

Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 20 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3


Слайд 20

Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 21 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3


Слайд 21

Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 22 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3


Слайд 22

Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 23 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3


Слайд 23

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


Слайд 24

Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 25 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3


Слайд 25

Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 26 Объём хранимых данных процессор 0 процессор 1 процессор 2 процессор 3


Слайд 26

Причины дисбаланса вычислительной нагрузки Разные процессоры Внешнее воздействие Разная вычислительная сложность заданий Результат дисбаланса Эффективная производительность определяется самым медленным процессором Диффузная балансировка Москва, 2010 г. 27 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 27

Медленный процессор Москва, 2010 г. Какой объем работ забрать у среднего процессора и кому его передать? 28 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 28

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


Слайд 29

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


Слайд 30

Диффузная балансировка загрузки Москва, 2010 г. 31 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 31

Диффузная балансировка загрузки Москва, 2010 г. 32 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 32

Диффузная балансировка загрузки Москва, 2010 г. 33 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 33

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


Слайд 34

Москва, 2010 г. Постановка задачи диффузной балансировки Дано: Количество точек – N Количество процессоров – p Процессор i обработал ni точек за время ti Требуется: Найти количества точек n’i , которое следует обработать процессорам на следующем шаге Определить сколько точек каждый из процессоров должен передать соседним процессорам 35 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 35

Москва, 2010 г. 36 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. Диффузная балансировка


Слайд 36

Статическая и динамическая балансировка загрузки процессоров Статическая балансировка метод сдваивания геометрический параллелизм конвейерный параллелизм Динамическая балансировка коллективное решение диффузная балансировка Москва, 2010 г. 37 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. Резюме


Слайд 37

Общая схема вычислений Москва, 2010 г. K = 1 000 000; шаг_вывода = 10 000; for(шаг=0;шаг<k;шаг++) { for(кирпич=rank*n/p;кирпич<(rank+1)*n/p;кирпич++) Уложить (кирпич) Обменяться данными о точках, прилегающих к внутренним границам() if( шаг % шаг_вывода == 0 ) { Вывести промежуточные результаты() } } 38 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 38

r=0; for(i=0;i<=n;i++) { d=a[i]+b[i]+r; c[i]=d%10; r=d/10; } c[i]=r; Определение суммы двух многоразрядных чисел Москва, 2010 г. T1= 4n?с 39 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 39

Последовательное распространение разряда переноса на четырёх процессорах «Параллельный» алгоритм Москва, 2010 г. 40 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 40

Москва, 2010 г. ? Параллельный алгоритм « » 41 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 41

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


Слайд 42

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; Спекулятивный алгоритм Москва, 2010 г. T’= 8n1?с 43 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 43

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


Слайд 44

Рассмотрены некоторые методы построения параллельных алгоритмов Рассмотрен алгоритм диффузной балансировки загрузки процессоров Представлен масштабируемый параллельный алгоритм, основанный на неэффективном последовательном алгоритме Заключение Москва, 2010 г. 45 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.


Слайд 45

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


×

HTML:





Ссылка: