Без темы
<<  Учебный курс Основы параллельных вычислений Хэсэ пр?ямой гучи???иен  >>
Учебный курс Основы параллельных вычислений
Учебный курс Основы параллельных вычислений
Содержание
Содержание
Введение
Введение
Граф "операции-операнды"…
Граф "операции-операнды"…
Граф "операции-операнды"…
Граф "операции-операнды"…
Граф "операции-операнды"…
Граф "операции-операнды"…
Граф "операции-операнды"
Граф "операции-операнды"
Схема параллельного выполнения алгоритма
Схема параллельного выполнения алгоритма
Модель параллельного алгоритма: Время выполнения параллельного
Модель параллельного алгоритма: Время выполнения параллельного
Минимально возможное время решения задачи при заданном количестве
Минимально возможное время решения задачи при заданном количестве
Время выполнения последовательного алгоритма для заданной
Время выполнения последовательного алгоритма для заданной
Теорема 1 Минимально возможное время выполнения параллельного
Теорема 1 Минимально возможное время выполнения параллельного
Теорема 2 Пусть для некоторой вершины вывода в вычислительной схеме
Теорема 2 Пусть для некоторой вершины вывода в вычислительной схеме
Теорема 3 При уменьшении числа используемых процессоров время
Теорема 3 При уменьшении числа используемых процессоров время
Теорема 4 Для любого количества используемых процессоров справедлива
Теорема 4 Для любого количества используемых процессоров справедлива
Теорема 5 Времени выполнения алгоритма, которое сопоставимо с
Теорема 5 Времени выполнения алгоритма, которое сопоставимо с
Рекомендации при выборе вычислительной схемы алгоритма должен
Рекомендации при выборе вычислительной схемы алгоритма должен
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм…
Пример: Вычисление частных сумм
Пример: Вычисление частных сумм
Пример: Умножение матриц…
Пример: Умножение матриц…
Пример: Умножение матриц
Пример: Умножение матриц
Заключение
Заключение
Вопросы для обсуждения
Вопросы для обсуждения
Темы заданий для самостоятельной работы
Темы заданий для самостоятельной работы
Литература…
Литература…
Следующая тема
Следующая тема
Контакты
Контакты
О проекте
О проекте

Презентация на тему: «Учебный курс Основы параллельных вычислений». Автор: Гергель В.П.. Файл: «Учебный курс Основы параллельных вычислений.ppt». Размер zip-архива: 243 КБ.

Учебный курс Основы параллельных вычислений

содержание презентации «Учебный курс Основы параллельных вычислений.ppt»
СлайдТекст
1 Учебный курс Основы параллельных вычислений

Учебный курс Основы параллельных вычислений

Анализ сложности вычислений и оценка возможности распараллеливания

Лекция 4:

Гергель В.П., профессор, д.т.н. Нижегородский университет

2 Содержание

Содержание

Модель вычислений в виде графа "операции-операнды" Схема параллельного выполнения алгоритма Определение времени выполнения параллельного алгоритма Пример: Вычисление частных сумм последовательности числовых значений Пример: Умножение матриц Заключение

2 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

3 Введение

Введение

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

3 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

4 Граф "операции-операнды"…

Граф "операции-операнды"…

Модель в виде графа "операции-операнды" используется для описания существующих информационных зависимостей в выбираемых алгоритмах В наиболее простом виде модель основывается на предположениях: время выполнения любых вычислительных операций является одинаковым и равняется 1, передача данных между вычислительными устройствами выполняется мгновенно без каких-либо затрат времени.

4 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

5 Граф "операции-операнды"…

Граф "операции-операнды"…

R

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

Множество вершин графа, представляющих выполняемые операции алгоритма,

Множество дуг графа; дуга r(i,j) принадлежит графу только если операция j использует результат выполнения операции i

Вершины без входных дуг могут использоваться для задания операций ввода, а вершины без выходных дуг – для операций вывода.

– Множество вершин графа без вершин ввода,

– Диаметр графа (длина максимального пути)

5 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

6 Граф "операции-операнды"…

Граф "операции-операнды"…

Пример: граф алгоритма вычисления площади прямоугольника, заданного координатами двух противолежащих углов

6 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

7 Граф "операции-операнды"

Граф "операции-операнды"

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

7 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

8 Схема параллельного выполнения алгоритма

Схема параллельного выполнения алгоритма

Пусть p есть количество процессоров, используемых для выполнения алгоритма. Тогда для параллельного выполнения вычислений необходимо задать множество (расписание): i - есть номер операции, Pi - есть номер процессора, ti - есть время начала выполнения i-ой операции. Должны выполняться условия: один и тот же процессор не должен назначаться разным операциям в один и тот же момент времени: к назначаемому моменту выполнения операции все необходимые данные уже должны быть вычислены:

8 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

9 Модель параллельного алгоритма: Время выполнения параллельного

Модель параллельного алгоритма: Время выполнения параллельного

алгоритма с заданным расписанием: Время выполнения параллельного алгоритма с оптимальным расписанием:

Определение времени выполнения параллельного алгоритма…

9 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

10 Минимально возможное время решения задачи при заданном количестве

Минимально возможное время решения задачи при заданном количестве

процессоров (определение наилучшей вычислительной схемы): Оценка наиболее быстрого исполнения алгоритма (при использовании паракомпьютера – системы с неограниченным числом процессоров):

Определение времени выполнения параллельного алгоритма…

10 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

11 Время выполнения последовательного алгоритма для заданной

Время выполнения последовательного алгоритма для заданной

вычислительной схемы: Время выполнения последовательного алгоритма: Время последовательного решения задачи:

Определение времени выполнения параллельного алгоритма…

Подобные оценки необходимы для определения эффекта использования параллелизма

11 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

12 Теорема 1 Минимально возможное время выполнения параллельного

Теорема 1 Минимально возможное время выполнения параллельного

алгоритма определяется длиной максимального пути вычислительной схемы алгоритма:

Определение времени выполнения параллельного алгоритма…

12 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

13 Теорема 2 Пусть для некоторой вершины вывода в вычислительной схеме

Теорема 2 Пусть для некоторой вершины вывода в вычислительной схеме

алгоритма существует путь из каждой вершины ввода. Кроме того, пусть входная степень вершин схемы (количество входящих дуг) не превышает 2. Тогда минимально возможное время выполнения параллельного алгоритма ограничено снизу значением: где n есть количество вершин ввода в схеме алгоритма

Определение времени выполнения параллельного алгоритма…

13 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

14 Теорема 3 При уменьшении числа используемых процессоров время

Теорема 3 При уменьшении числа используемых процессоров время

выполнения алгоритма увеличивается пропорционально величине уменьшения количества процессоров, т.е. :

Определение времени выполнения параллельного алгоритма…

14 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

15 Теорема 4 Для любого количества используемых процессоров справедлива

Теорема 4 Для любого количества используемых процессоров справедлива

следующая верхняя оценка для времени выполнения параллельного алгоритма:

Определение времени выполнения параллельного алгоритма…

15 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

16 Теорема 5 Времени выполнения алгоритма, которое сопоставимо с

Теорема 5 Времени выполнения алгоритма, которое сопоставимо с

минимально возможным временем T?, можно достичь при количестве процессоров порядка p~T1/T?, а именно: При меньшем количестве процессоров время выполнения алгоритма не может превышать более, чем в 2 раза, наилучшее время вычислений при имеющемся числе процессоров, т.е.:

Определение времени выполнения параллельного алгоритма…

16 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

17 Рекомендации при выборе вычислительной схемы алгоритма должен

Рекомендации при выборе вычислительной схемы алгоритма должен

использоваться граф с минимально возможным диаметром (теорема 1), для параллельного выполнения целесообразное количество процессоров определяется величиной p~T1/T? (теорема 5), время выполнения параллельного алгоритма ограничивается сверху величинами, приведенными в теоремах 4 и 5.

Определение времени выполнения параллельного алгоритма…

17 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

18 Пример: Вычисление частных сумм…

Пример: Вычисление частных сумм…

Задача нахождения частных сумм последовательности числовых значений (prefix sum problem): Задача вычисления общей суммы имеющегося набора значений:

18 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

19 Пример: Вычисление частных сумм…

Пример: Вычисление частных сумм…

Последовательный алгоритм суммирования элементов числового вектора

Данный "стандартный" алгоритм суммирования допускает только строго последовательное исполнение и не может быть распараллелен

19 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

20 Пример: Вычисление частных сумм…

Пример: Вычисление частных сумм…

Каскадная схема суммирования

V2 = { (vi1,…,vili), 0?i?k, 1?li?2-in } есть вершины графа, (v01,…, v0n) есть операции ввода, (v11,…,v1n/2) есть операции первой итерации и т.Д., R2 = { (vi-1,2j-1vij),(vi-1,2jvij), 1?i?k, 1?li?2-in } есть множество дуг графа.

20 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

21 Пример: Вычисление частных сумм…

Пример: Вычисление частных сумм…

Количество итераций каскадной схемы суммирования: Общее количество операций суммирования: При параллельном исполнении отдельных итераций каскадной схемы общее количество параллельных операций суммирования является равным:

21 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

22 Пример: Вычисление частных сумм…

Пример: Вычисление частных сумм…

Показатели ускорения и эффективности каскадной схемы алгоритма суммирования: где p=n/2 есть необходимое для выполнения каскадной схемы количество процессоров. время параллельного выполнения каскадной схемы совпадает с оценкой для паракомпьютера (теорема 2), эффективность использования процессоров уменьшается при увеличении количества суммируемых значений:

22 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

23 Пример: Вычисление частных сумм…

Пример: Вычисление частных сумм…

Модифицированная каскадная схема: Все суммируемые значения подразделяются на (n/log2n) групп, в каждой из которых содержится (log2n) элементов; для каждой группы вычисляется сумма значений при помощи последовательного алгоритма суммирования; На втором этапе для полученных (n/log2n) сумм отдельных групп применяется обычная каскадная схема:

23 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

24 Пример: Вычисление частных сумм…

Пример: Вычисление частных сумм…

Для выполнения первого этапа требуется (log2n) выполнение параллельных операций при использовании p= (n/log2n) процессоров Для выполнения второго этапа необходимо log2(n/log2n)?log2n параллельных операций для p=(n/log2n)/2 процессоров Время выполнения параллельного алгоритма составляет для p= (n/log2n) процессоров.

24 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

25 Пример: Вычисление частных сумм…

Пример: Вычисление частных сумм…

С учетом полученных оценок показатели ускорения и эффективности модифицированной каскадной схемы определяются соотношениями:

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

Модифицированный каскадный алгоритм является стоимостно-оптимальным (стоимость вычислений пропорциональна времени выполнения последовательного алгоритма):

25 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

26 Пример: Вычисление частных сумм…

Пример: Вычисление частных сумм…

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

Достижение эффективного распараллеливания требует привлечения новых подходов (может быть, даже не имеющих аналогов при последовательном программировании) для разработки новых параллельно-ориентированных алгоритмов решения задач

26 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

27 Пример: Вычисление частных сумм…

Пример: Вычисление частных сумм…

Вычисление всех частных сумм… Алгоритм, обеспечивающий получение результатов за log2n параллельных операций: Перед началом вычислений создается копия S вектора суммируемых значений (S=x), Далее на каждой итерации суммирования i, 1?i?log2n, формируется вспомогательный вектор Q путем сдвига вправо вектора S на 2i-1 позиций (освобождающиеся при сдвиге позиции слева устанавливаются в нулевые значения); итерация алгоритма завершается параллельной операцией суммирования векторов S и Q.

27 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

28 Пример: Вычисление частных сумм…

Пример: Вычисление частных сумм…

Вычисление всех частных сумм…

28 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

29 Пример: Вычисление частных сумм

Пример: Вычисление частных сумм

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

29 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

30 Пример: Умножение матриц…

Пример: Умножение матриц…

Умножение матриц:

Или

Или

30 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

31 Пример: Умножение матриц

Пример: Умножение матриц

Граф информационных зависимостей (до уровня операций умножения строк матрицы А и столбцов матрицы В):

? Задача умножения матрицы на вектор может быть сведена к выполнению m·n независимых операций умножения строк матрицы A на столбцы матрицы B

31 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

32 Заключение

Заключение

Описывается модель вычислений в виде графа "операции-операнды", которая может использоваться для описания существующих информационных зависимостей в выбираемых алгоритмах решения задач Приводятся теоретические оценки, которые могут быть использованы при определении максимального возможного распараллеливания Для демонстрации применимости рассмотренных моделей и методов анализа параллельных алгоритмов в разделе рассматриваются задачи нахождения частных сумм последовательности числовых значений и умножения матриц

32 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

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

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

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

33 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

34 Темы заданий для самостоятельной работы

Темы заданий для самостоятельной работы

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

34 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

35 Литература…

Литература…

Гергель В.П. Теория и практика параллельных вычислений. - М.: Интернет-Университет, БИНОМ. Лаборатория знаний, 2007. – Лекция 2 Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002. Дополнительные учебные курсы: Барский А.Б. Параллельное программирование. — http://www.intuit.ru/department/se/parallprog/ Воеводин В.В. Вычислительная математика и структура алгоритмов. — http://www.intuit.ru/department/calculate/calcalgo/

35 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

36 Следующая тема

Следующая тема

Общая схема разработки параллельных методов

36 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

37 Контакты

Контакты

Гергель В.П., профессор, д.т.н., декан факультета вычислительной математики и кибернетики Нижегородский университет gergel@unn.ru http://www.software.unn.ru/?dir=17

37 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

38 О проекте

О проекте

Целью проекта является организация массовой подготовки специалистов в области суперкомпьютерных вычислительных технологий с активным использованием возможностей современных ИТ-технологий. Образовательная деятельность ориентирована на обучение самого широкого круга обучаемых (студентов, специалистов, преподавателей) и предусматривает наличие различных направлений подготовки для учета разных профессиональных требований в области суперкомпьютерных технологий (пользователи, программисты, инженеры). Исполнители проекта - Интернет университет информационных технологий, Научно-исследовательский вычислительный центр Московского университета и Нижегородский университет. Проект выполняется в рамках деятельности Суперкомпьютерного консорциума университетов России (http://www.hpc-russia.ru)/ Сайт проекта – http://www.hpcu.ru

38 из 38

Н.Новгород, 2008 г.

Основы параллельных вычислений: Оценка возможности распараллеливания © Гергель В.П.

«Учебный курс Основы параллельных вычислений»
http://900igr.net/prezentacija/geometrija/uchebnyj-kurs-osnovy-parallelnykh-vychislenij-215357.html
cсылка на страницу

Без темы

105 презентаций
Урок

Геометрия

40 тем
Слайды
900igr.net > Презентации по геометрии > Без темы > Учебный курс Основы параллельных вычислений