чтобы результат работы одного процессора поступал на вход другого (линейная
топология)Сложная операция разбивается на несколько последовательных стадий, каждая стадия выполняется своим процессором
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Основные подходы к распараллеливанию
Содержание
- 1. Основные подходы к распараллеливанию
- 2. ПланКонвейерМатричная обработкаРаспараллеливание циклов
- 3. КонвейерКонвейерная обработка – метод распараллеливания существенно последовательных
- 4. Использование конвейераПараллелизм на уровне инструкцийКонвейерная обработка в
- 5. Когда конвейер эффективныйТри случаяС помощью конвейера необходимо
- 6. Пример: конвейер первого типаПример: Нахождение суммы нескольких
- 7. Реализация// i – номер поточного процессора// d-
- 8. Время выполнения первой задачиКаждый процессор получает результат
- 9. Время решения нескольких задачПусть задачу необходимо решить
- 10. Время выполнения при большом количестве задачПредел коэффициента
- 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 операций
- 17. Конвейер третьего типаОдновременная передача данных и обработка
- 18. Пример конвейера третьего типаОбратный ход метода ГауссаМатрица треугольной формы
- 19. Решение
- 20. Последовательная программа// по всем неизвестнымfor(i=1; i
- 21. Параллельная программаПроцессор 1 –вычисляет x1 и передает
- 22. Параллельная программаfor(j=1;j
- 23. ЭффективностьПоследовательный алгоритм O(n2) операцийПараллельный алгоритм – каждый
- 24. Выводы относительно конвейераСамый простой и дешевый вариант
- 25. Матричная (векторная, параллельная) обработкаКаждый процессор получает часть
- 26. УскорениеУскорение при равномерной загрузке процессоров стремится к
- 27. ПреимуществаВысокая эффективностьОбмен мало влияет на скорость выполнения
- 28. НедостаткиСинхронный режим работыВо время синхронизации процессоры простаиваютНет
- 29. Векторно-конвейерная схемаВектор – массив элементов одинакового типаВекторные
- 30. сложение двух чиселСложение чисел стандарт ANSI/IEEE[A:] сравнение
- 31. Пример сложенияx+y, где x=1234,00 y = -567,8
- 32. Оценка времениВремя выполнения одной стадии tВремя сложения
- 33. Диаграмма состояний
- 34. Конвейерное выполнение После выполнения первой стадии с
- 35. Оценка времениВремя сложения двух векторовКоэффициент ускорения
- 36. Параметры векторно-конвейерной системыРазмерность вектора, при котором скорость
- 37. Распараллеливание цикловЦиклы типа for() обычно хорошо распараллеливаютсяЦиклы
- 38. Разбивка на блокиfor(i=0; i
- 39. Пример разбивки на блокиЦикл разбивается на p цикловКаждый процессор выполняет свой циклfor(j=0;j
- 40. ЭффективностьПри отсутствии связи между данными внутри цикла эффективность стремится к 1
- 41. Развертка цикловЧасть операций цикла можно заменить последовательностью операций и выполнить с помощью конвейераfor(i=0; i
- 42. Векторизация цикловЧасть операций цикла можно заменить последовательностью
- 43. Работа с большими матрицамиВ прикладных задачах часто
- 44. Блочные методы Матрица разбивается на части –
- 45. Математика блочных операцийМатематически операции с блочными матрицами
- 46. Распараллеливание блочных операцийВычисление каждого блока результата может
- 47. Геометрическое распараллеливаниеПроцессоры, которые интенсивно взаимодействуют между собой
- 48. Вопросы?
- 49. Скачать презентанцию
ПланКонвейерМатричная обработкаРаспараллеливание циклов
Слайды и текст этой презентации
Слайд 1Основные подходы к распараллеливанию
Судаков А.А.
“Параллельные и распределенные вычисления” Лекция 16
Слайд 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->∞
При
очень большом количестве задач ускорение стремится к идеальному
При малом количестве
ограничивается законом Амдала 
Слайд 13Вводы относительно конвейера первого типа
Эффективность конвейера всегда меньше единицы
Для получения
высоких коэффициентов ускорения необходимо, чтобы скорость обмена дынными была по
возможности меньшеКоэффициент ускорения асимптотически стремится к значению
Эффективность конвейера растет при увеличении времени, которое тратит процессор на обработку данных по сравнению с временем передачи
Даже для медленных каналов связи при большом количестве операций алгоритма конвейер может давать ускорение
Для эффективной работы конвейера его необходимо сильно загрузить
Слайд 14Конвейер второго типа
Пример: сортировка массива значений
На входе есть большой массив
данных
Каждый процессор получает информацию от предыдущего и передает наибольшее из
своих значений следующему процессоруВ результате процессор с меньшим номером будет содержать элементы массива с меньшими значениями
Слайд 16Оценка времени
Каждый процессор выполняет порядка n операций сравнения параллельно с
остальными
Самый быстрый последовательный алгоритм требует порядка n(log2n) операций
Коэффициент ускорения
Эффективность достаточно
маленькая
Слайд 17Конвейер третьего типа
Одновременная передача данных и обработка (Send-ahead)
Если полученные от
предыдущего процессора данные можно передать на следующий процессор, а потом
начать их обработку
Слайд 21Параллельная программа
Процессор 1 –вычисляет x1 и передает его дальше
Процессор 2
принимает x1 передает его дальше, вычисляет x2 и тоже передает
его дальшеПроцессор 3 принимает x1 , принимает x2 , передает их дальше, вычисляет x3 и передает его дальше
…
Вычисление выполняется параллельно с передачей данных
разные процессоры работают одновременно
Слайд 23Эффективность
Последовательный алгоритм O(n2) операций
Параллельный алгоритм – каждый процессор порядка O(n)
операций
Ускорение порядка O(n)
С увеличением порядка матрицы ускорение растет
Слайд 24Выводы относительно конвейера
Самый простой и дешевый вариант распараллеливания
Возможность распараллеливания принципиально
последовательных операций
Возможность одновременного выполнения передачи данных и их обработки (асинхронные
операции)Эффективность всегда меньше 1
Слайд 25Матричная (векторная, параллельная) обработка
Каждый процессор получает часть своей задачи и
выполняет ее параллельно с другими процессорами
В конце выполнения процессоры синхронизируются
(барьер)
Слайд 26Ускорение
Ускорение при равномерной загрузке процессоров стремится к количеству процессоров
Эффективность стремится
к единице
Процессоры большую часть времени загружены
Слайд 28Недостатки
Синхронный режим работы
Во время синхронизации процессоры простаивают
Нет возможности выполнять обмен
одновременно с вычислениями
Требует большого количества одинаковых процессоров
Обычно дорогостоящее решение
Слайд 29Векторно-конвейерная схема
Вектор – массив элементов одинакового типа
Векторные операции – большое
количество одинаковых операций с разными данными
x[i]+y[i]=z[i]
Конвейер второго типа может быть
эффективным для таких операций![Векторно-конвейерная схемаВектор – массив элементов одинакового типаВекторные операции – большое количество одинаковых операций с разными данными x[i]+y[i]=z[i]Конвейер второго](/img/thumbs/1a918dbc9e41f65403029703fe985e66-800x.jpg "Основные подходы к распараллеливанию Векторно-конвейерная схемаВектор – массив элементов одинакового типаВекторные операции – большое количество")
Слайд 30сложение двух чисел
Сложение чисел стандарт ANSI/IEEE
[A:] сравнение порядков и определение
меньшего числа
[B:] сдвиг мантиссы числа с меньшим порядком, чтобы порядки
стали одинаковыми[C:] складываются мантиссы полученных чисел
[D:] результат нормализируется
[E:] проверка на возникновение исключительных ситуаций
[F:] Округление
![сложение двух чиселСложение чисел стандарт ANSI/IEEE[A:] сравнение порядков и определение меньшего числа[B:] сдвиг мантиссы числа с меньшим](/img/thumbs/47eb1a1ada894ff970eb2c10808da651-800x.jpg "Основные подходы к распараллеливанию сложение двух чиселСложение чисел стандарт ANSI/IEEE[A:] сравнение порядков и определение меньшего")
Слайд 32Оценка времени
Время выполнения одной стадии t
Время сложения двух чисел 6t
Сложение
двух векторов длины n выполнится за 6tn
Слайд 34Конвейерное выполнение
После выполнения первой стадии с первым числом сразу
же запускается первая стадия со вторым числом
Слайд 36Параметры векторно-конвейерной системы
Размерность вектора, при котором скорость работы векторного процессора
становится большей, чем скалярного (2 в данном случае)
Максимально возможный коэффициент
ускорения (векторная скорость света) = 6При размерности вектора 4096 ускорение равно 5.99268
Размерность вектора при которой производительность равна половине от максимальной (5 в данном случае)
Слайд 37Распараллеливание циклов
Циклы типа for() обычно хорошо распараллеливаются
Циклы типа while распараллеливаются
обычно плохо
Два подхода
Развертка циклов (unroll)
Векторизация циклов
Разбивка на блоки (blocking)
Слайд 39Пример разбивки на блоки
Цикл разбивается на p циклов
Каждый процессор выполняет
свой цикл
for(j=0;j
Слайд 41Развертка циклов
Часть операций цикла можно заменить последовательностью операций и выполнить
с помощью конвейера
for(i=0; i
при большом k
Слайд 42Векторизация циклов
Часть операций цикла можно заменить последовательностью операций и выполнить
с помощью векторных команд (mmx, sse)
for(i=0; i
рассматриваются как векторы размерности ka[начиная с i]=b[начиная с i]+1;
}
Ускорение почти в k раз
Слайд 43Работа с большими матрицами
В прикладных задачах часто возникает проблема работы
с матрицами большого размера (100000х100000 )
Для размещения такой матрицы чисел
типа double потребуется 76 ГБайт В оперативную память одной машины такая матрица не влезет
Используются блочные методы
Слайд 44Блочные методы
Матрица разбивается на части – блоки (rxq блоков)
Каждый
блок хранится в памяти одного узла массивно параллельной системы (кластера)
Говорят: «На матрицу накладывается процессорная сетка»
Каждому узлу сетки (блоку матрицы) соответствует процессор с координатами (i,j)
Для выполнения операций с матрицами процессоры должны обмениваться данными между собой (топология решетка)
Слайд 45Математика блочных операций
Математически операции с блочными матрицами выполняются так же,
как и операции с обычными матрицами, но умножение чисел заменяется
умножением матриц, сложение…
Слайд 46Распараллеливание блочных операций
Вычисление каждого блока результата может выполняться параллельно с
вычислением других блоков результата
Эффективность таких операций увеличивается при увеличении размерности
матрицКоличество операций обработки данных порядка O(m3)
Время передачи данных O(m2)
Слайд 47Геометрическое распараллеливание
Процессоры, которые интенсивно взаимодействуют между собой должны находится «ближе»
например располагаться на одном узле многопроцессорной машины
