Презентация «Основные подходы к распараллеливанию»

Pic.1

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

Pic.2

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

Pic.3

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

Pic.4

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

Pic.5

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

Pic.6

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

Pic.7

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

Pic.8

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

Pic.9

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

Pic.10

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

Pic.11

Иллюстрация

Pic.12

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

Pic.13

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

Pic.14

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

Pic.15

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

Pic.16

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

Pic.17

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

Pic.18

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

Pic.19

Решение

Pic.20

Последовательная программа // по всем неизвестным for(i=1; i<=n; i++){ sum=0; // по всем найденным неизвестным for(j=1;j<i; j++){ sum+=a[i][j]*x[j]; x[i]=(b[i]-sum)/a[i][j]; } }

Pic.21

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

Pic.22

Параллельная программа for(j=1;j<=i; j++){ recv(p-1,x[j]) send(p+1,x[j]) } sum=0; for(j=1; i<=j; j++){ sum+=a[i][j]*x[j]; } x[i]=(b[i]-sum)/a[i][j]; send(p+1,x[i])

Pic.23

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

Pic.24

Выводы относительно конвейера Самый простой и дешевый вариант распараллеливания Возможность распараллеливания принципиально последовательных операций Возможность одновременного выполнения передачи …

Pic.25

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

Pic.26

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

Pic.27

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

Pic.28

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

Pic.29

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

Pic.30

сложение двух чисел Сложение чисел стандарт ANSI/IEEE [A:] сравнение порядков и определение меньшего числа [B:] сдвиг мантиссы числа с меньшим порядком, чтобы порядки стали одинаковыми [C:] …

Pic.31

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

Pic.32

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

Pic.33

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

Pic.34

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

Pic.35

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

Pic.36

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

Pic.37

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

Pic.38

Разбивка на блоки for(i=0; i<N;i++){ // тіло циклу a[i]=b[i]+1; } Цикл разбивается на блоки каждый блок выполняется своим процессором с помощью параллельной схемы

Pic.39

Пример разбивки на блоки Цикл разбивается на p циклов Каждый процессор выполняет свой цикл for(j=0;j<p; j++){ for(i=j; i<N;i+=p){ // тіло циклу a[i]=b[i]+1 } } Внутренний цикл выполняется своим …

Pic.40

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

Pic.41

Развертка циклов Часть операций цикла можно заменить последовательностью операций и выполнить с помощью конвейера for(i=0; i<N;i+=k){ // тіло циклу a[i]=b[i]+1; a[i+1]=b[i+1]+1; a[i+2]=b[i+2]+1; …

Pic.42

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

Pic.43

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

Pic.44

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

Pic.45

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

Pic.46

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

Pic.47

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

Pic.48

Вопросы?

Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!