Основные подходы к распараллеливанию - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Основные подходы к распараллеливанию, слайд №1

Основные подходы к распараллеливанию, слайд №2

Основные подходы к распараллеливанию, слайд №3

Основные подходы к распараллеливанию, слайд №4

Основные подходы к распараллеливанию, слайд №5

Основные подходы к распараллеливанию, слайд №6

Основные подходы к распараллеливанию, слайд №7

Основные подходы к распараллеливанию, слайд №8

Основные подходы к распараллеливанию, слайд №9

Основные подходы к распараллеливанию, слайд №10

Основные подходы к распараллеливанию, слайд №11

Основные подходы к распараллеливанию, слайд №12

Основные подходы к распараллеливанию, слайд №13

Основные подходы к распараллеливанию, слайд №14

Основные подходы к распараллеливанию, слайд №15

Основные подходы к распараллеливанию, слайд №16

Основные подходы к распараллеливанию, слайд №17

Основные подходы к распараллеливанию, слайд №18

Основные подходы к распараллеливанию, слайд №19

Основные подходы к распараллеливанию, слайд №20

Основные подходы к распараллеливанию, слайд №21

Основные подходы к распараллеливанию, слайд №22

Основные подходы к распараллеливанию, слайд №23

Основные подходы к распараллеливанию, слайд №24

Основные подходы к распараллеливанию, слайд №25

Основные подходы к распараллеливанию, слайд №26

Основные подходы к распараллеливанию, слайд №27

Основные подходы к распараллеливанию, слайд №28

Основные подходы к распараллеливанию, слайд №29

Основные подходы к распараллеливанию, слайд №30

Основные подходы к распараллеливанию, слайд №31

Основные подходы к распараллеливанию, слайд №32

Основные подходы к распараллеливанию, слайд №33

Основные подходы к распараллеливанию, слайд №34

Основные подходы к распараллеливанию, слайд №35

Основные подходы к распараллеливанию, слайд №36

Основные подходы к распараллеливанию, слайд №37

Основные подходы к распараллеливанию, слайд №38

Основные подходы к распараллеливанию, слайд №39

Основные подходы к распараллеливанию, слайд №40

Основные подходы к распараллеливанию, слайд №41

Основные подходы к распараллеливанию, слайд №42

Основные подходы к распараллеливанию, слайд №43

Основные подходы к распараллеливанию, слайд №44

Основные подходы к распараллеливанию, слайд №45

Основные подходы к распараллеливанию, слайд №46

Основные подходы к распараллеливанию, слайд №47

Основные подходы к распараллеливанию, слайд №48

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Основные подходы к распараллеливанию. Доклад-сообщение содержит 48 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Основные подходы к распараллеливанию Судаков А.А. “Параллельные и распределенные вычисления” Лекция 16

Слайд 2

Описание слайда:

План Конвейер Матричная обработка Распараллеливание циклов

Слайд 3

Описание слайда:

Конвейер Конвейерная обработка – метод распараллеливания существенно последовательных операций Процессоры соединяются так, чтобы результат работы одного процессора поступал на вход другого (линейная топология) Сложная операция разбивается на несколько последовательных стадий, каждая стадия выполняется своим процессором

Слайд 4

Описание слайда:

Использование конвейера Параллелизм на уровне инструкций Конвейерная обработка в процессорах Параллелизм на уровне процедур Конвейерное объединение потоков Параллелизм на уровне приложений Передача выхода одной программы на вход другой Передача сообщений

Слайд 5

Описание слайда:

Когда конвейер эффективный Три случая С помощью конвейера необходимо решить несколько последовательных задач С помощью конвейера необходимо решить одну задачу для большой последовательности входных данных Когда каждый процессор еще до завершения своей работы может отправить данные следующему процессору и запустить его работу

Слайд 6

Описание слайда:

Пример: конвейер первого типа Пример: Нахождение суммы нескольких значений Есть p процессоров У каждого процессора есть свои данные di Необходимо найти сумму

Слайд 7

Описание слайда:

Реализация // i – номер поточного процессора // d- дані поточного процесора // sum – проміжне значення, яке на // останньому процесорі буде містити // результат розв’язання задачі recv(i-1,&sum) sum=+d send(i+1,sum)

Слайд 8

Описание слайда:

Время выполнения первой задачи Каждый процессор получает результат предыдущего Добавляет к нему свое значение и отправляет результат дальше Время вычисления первой суммы: Суммарное время работы всех процессоров Время передачи данных от первого процессора до последнего Это время называется временем заполнения конвейера (существенно последовательная операция) Время выполнения последовательного алгоритма Ускорение Для решения одной задачи конвейер не эффективен!

Слайд 9

Описание слайда:

Время решения нескольких задач Пусть задачу необходимо решить m раз для m наборов данных на каждом процессоре Каждую следующую операцию процессор будет выполнять за время Общее время решения задачи Время решения m задач на 1 процессоре Ускорение

Слайд 10

Описание слайда:

Время выполнения при большом количестве задач Предел коэффициента ускорения при m->∞ При очень большом количестве задач ускорение стремится к идеальному При малом количестве ограничивается законом Амдала

Слайд 11

Описание слайда:

Иллюстрация

Слайд 12

Описание слайда:

Графическая иллюстрация Доля последовательных вычислений зависит от количества задач

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

Конвейер второго типа Пример: сортировка массива значений На входе есть большой массив данных Каждый процессор получает информацию от предыдущего и передает наибольшее из своих значений следующему процессору В результате процессор с меньшим номером будет содержать элементы массива с меньшими значениями

Слайд 15

Описание слайда:

Программа recv(i-1,x) for(j=0;j x) { Send(i+1,x); } else { send(i+1, number); } }

Слайд 16

Описание слайда:

Оценка времени Каждый процессор выполняет порядка n операций сравнения параллельно с остальными Самый быстрый последовательный алгоритм требует порядка n(log2n) операций Коэффициент ускорения Эффективность достаточно маленькая

Слайд 17

Описание слайда:

Конвейер третьего типа Одновременная передача данных и обработка (Send-ahead) Если полученные от предыдущего процессора данные можно передать на следующий процессор, а потом начать их обработку

Слайд 18

Описание слайда:

Пример конвейера третьего типа Обратный ход метода Гаусса Матрица треугольной формы

Слайд 19

Описание слайда:

Решение

Слайд 20

Описание слайда:

Последовательная программа // по всем неизвестным for(i=1; i

Слайд 21

Описание слайда:

Параллельная программа Процессор 1 –вычисляет x1 и передает его дальше Процессор 2 принимает x1 передает его дальше, вычисляет x2 и тоже передает его дальше Процессор 3 принимает x1 , принимает x2 , передает их дальше, вычисляет x3 и передает его дальше … Вычисление выполняется параллельно с передачей данных разные процессоры работают одновременно

Слайд 22

Описание слайда:

Параллельная программа for(j=1;j

Слайд 23

Описание слайда:

Эффективность Последовательный алгоритм O(n2) операций Параллельный алгоритм – каждый процессор порядка O(n) операций Ускорение порядка O(n) С увеличением порядка матрицы ускорение растет

Слайд 24

Описание слайда:

Выводы относительно конвейера Самый простой и дешевый вариант распараллеливания Возможность распараллеливания принципиально последовательных операций Возможность одновременного выполнения передачи данных и их обработки (асинхронные операции) Эффективность всегда меньше 1

Слайд 25

Описание слайда:

Матричная (векторная, параллельная) обработка Каждый процессор получает часть своей задачи и выполняет ее параллельно с другими процессорами В конце выполнения процессоры синхронизируются (барьер)

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

Преимущества Высокая эффективность Обмен мало влияет на скорость выполнения

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

Векторно-конвейерная схема Вектор – массив элементов одинакового типа Векторные операции – большое количество одинаковых операций с разными данными x[i]+y[i]=z[i] Конвейер второго типа может быть эффективным для таких операций

Слайд 30

Описание слайда:

сложение двух чисел Сложение чисел стандарт ANSI/IEEE [A:] сравнение порядков и определение меньшего числа [B:] сдвиг мантиссы числа с меньшим порядком, чтобы порядки стали одинаковыми [C:] складываются мантиссы полученных чисел [D:] результат нормализируется [E:] проверка на возникновение исключительных ситуаций [F:] Округление

Слайд 31

Описание слайда:

Пример сложения x+y, где x=1234,00 y = -567,8

Слайд 32

Описание слайда:

Оценка времени Время выполнения одной стадии t Время сложения двух чисел 6t Сложение двух векторов длины n выполнится за 6tn

Слайд 33

Описание слайда:

Диаграмма состояний

Слайд 34

Описание слайда:

Конвейерное выполнение После выполнения первой стадии с первым числом сразу же запускается первая стадия со вторым числом

Слайд 35

Описание слайда:

Оценка времени Время сложения двух векторов Коэффициент ускорения

Слайд 36

Описание слайда:

Параметры векторно-конвейерной системы Размерность вектора, при котором скорость работы векторного процессора становится большей, чем скалярного (2 в данном случае) Максимально возможный коэффициент ускорения (векторная скорость света) = 6 При размерности вектора 4096 ускорение равно 5.99268 Размерность вектора при которой производительность равна половине от максимальной (5 в данном случае)

Слайд 37

Описание слайда:

Распараллеливание циклов Циклы типа for() обычно хорошо распараллеливаются Циклы типа while распараллеливаются обычно плохо Два подхода Развертка циклов (unroll) Векторизация циклов Разбивка на блоки (blocking)

Слайд 38

Описание слайда:

Разбивка на блоки for(i=0; i

Слайд 39

Описание слайда:

Пример разбивки на блоки Цикл разбивается на p циклов Каждый процессор выполняет свой цикл for(j=0;j

Слайд 40

Описание слайда:

Эффективность При отсутствии связи между данными внутри цикла эффективность стремится к 1

Слайд 41

Описание слайда:

Развертка циклов Часть операций цикла можно заменить последовательностью операций и выполнить с помощью конвейера for(i=0; i

Слайд 42

Описание слайда:

Векторизация циклов Часть операций цикла можно заменить последовательностью операций и выполнить с помощью векторных команд (mmx, sse) for(i=0; i

Слайд 43

Описание слайда:

Работа с большими матрицами В прикладных задачах часто возникает проблема работы с матрицами большого размера (100000х100000 ) Для размещения такой матрицы чисел типа double потребуется 76 ГБайт В оперативную память одной машины такая матрица не влезет Используются блочные методы

Слайд 44

Описание слайда:

Блочные методы Матрица разбивается на части – блоки (rxq блоков) Каждый блок хранится в памяти одного узла массивно параллельной системы (кластера) Говорят: «На матрицу накладывается процессорная сетка» Каждому узлу сетки (блоку матрицы) соответствует процессор с координатами (i,j) Для выполнения операций с матрицами процессоры должны обмениваться данными между собой (топология решетка)

Слайд 45

Описание слайда:

Математика блочных операций Математически операции с блочными матрицами выполняются так же, как и операции с обычными матрицами, но умножение чисел заменяется умножением матриц, сложение…

Слайд 46

Описание слайда:

Распараллеливание блочных операций Вычисление каждого блока результата может выполняться параллельно с вычислением других блоков результата Эффективность таких операций увеличивается при увеличении размерности матриц Количество операций обработки данных порядка O(m3) Время передачи данных O(m2)

Слайд 47

Описание слайда:

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