Моделирование и анализ параллельных вычислений.

Сентябрь 3, 2022

Главная
Алгебра
Моделирование и анализ параллельных вычислений.

Содержание

2. Эффективность параллельных вычислений Жесткие требования к эффективности определены задачами (экология, аэродинамика, геофизика, геном и др.): исследуемые
3. Зачем нужны модели и их анализ? Для разработки эффективных параллельных алгоритмов оценивают эффективность использования параллелизма: эффективность
4. Модель вычислений Граф «операции – операнды» описывает алгоритм вычислений на уровне операций и информационных зависимостей. Предположения
5. Определение графа «операции-операнды» (граф О-О) Граф О-О G = (V , R) – ациклический ориентированный (направленный)
6. Определение графа «операции-операнды» (граф О-О) G = (V , R) V – множество вершин графа, представляющих
7. Пример модели вычислений (S прямоугольника) Лекция 3
8. Комментарии к модели Можно выбрать иную схему вычислений и построить другую модель. Операции, между которыми нет
9. Оценки трудоемкости параллельных алгоритмов Speedup - ускорение за счёт параллельного выполнения на N процессорах (потоках) a(N)
10. Граф О-О и показатели эффективности для типовых задач Алгоритмы вычисления сумм Лекция 3 Общая задача -
11. Последовательный алгоритм S=0; S+=x1; … Возможно только последовательное выполнение, распараллеливание данного алгоритма выполнить нельзя. Лекция 3
12. Каскадная схема Возможно распараллеливание алгоритма суммирования Лекция 3
13. Оценка эффективности Количество итераций (уровней) каскадной схемы: k = log2n (на рисунке при n=4, k=2) Общее
14. Оценка эффективности Время выполнения на 1 процессоре (равно количеству операций): Т1 = Kпосл Время выполнения на
15. Улучшение каскадной схемы Цель – асимптотически ненулевая эффективность. Суть алгоритма: все суммируемые значения подразделяются на (n/log2n)
16. Улучшение каскадной схемы Пример при n=16: все суммируемые значения подразделяются на (n/log2n)=4 группы, в каждой из
17. Модифицированная каскадная схема Лекция 3
18. Оценка эффективности Для этапа 1 число параллельных операций k1 = log2n необходимое число процессоров р1= n/log2n
19. Выводы Неочевидность приемов распараллеливания Неочевидность оценок эффективности Возможность разных вариантов параллельных схем Наглядность модели на графах
20. Передача данных. Коммуникационная трудоемкость алгоритмов В рассмотренных оценках не учтены затраты времени на передачу данных. Основа
21. Пример оптимальных АМ Алгоритмы, основанные на покоординатной маршрутизации (dimension ordered routing) – поочередный поиск путей передачи
22. Лекция 3
23. Характеристики коммуникационной составляющей длительности выполнения параллельного алгоритма в МВС Время передачи данных определяют: Время начальной подготовки
24. Методы передачи данных 1. Метод передачи сообщений как неделимых блоков информации (store-and-forward routing, SFR): CPU1 Готовит
25. Методы передачи данных 2. Метод передачи пакетов – сообщение состоит из блоков информации (пакетов) (cut-through-routing, CTR)
26. Преимущества и недостатки CTR Ускоряет пересылку данных. Снижает потребность в памяти для хранения пересылаемых данных и
27. Классификация операций передачи данных в МВС передача данных (сообщений): между двумя CPU сети, от одного CPU
29. Скачать презентацию

Слайд 2

Эффективность параллельных вычислений
Жесткие требования к эффективности определены задачами (экология, аэродинамика, геофизика,

геном и др.):
исследуемые объекты – 3D,
для приемлемой точности нужна сетка > 103 узлов,
в каждом узле надо найти значения > 10 функций,
при изучении динамики объекта определить его состояние в 102-104 моментах времени,
на вычисление каждого результата в среднем приходится 102-103 арифметических действий,
вычисления могут циклически повторяться для уточнения результата.

Лекция 3

Слайд 3

Зачем нужны модели и их анализ?
Для разработки эффективных параллельных алгоритмов оценивают

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

Лекция 3

Слайд 4

Модель вычислений
Граф «операции – операнды» описывает алгоритм вычислений на уровне операций

и информационных зависимостей.
Предположения упрощенной модели:
Время выполнения всех вычислительных операций = const = 1.
Передача данных между PU выполняется мгновенно (например, в системе в общей памятью) ?
можно не учитывать коммуникационную трудоемкость алгоритмов

Лекция 3

Слайд 5

Определение графа «операции-операнды» (граф О-О)
Граф О-О G = (V , R)

– ациклический ориентированный (направленный) граф - в нем отсутствуют пути, начинающиеся и кончающиеся в одной и той же вершине.

Лекция 3

Слайд 6

Определение графа «операции-операнды» (граф О-О)
G = (V , R)
V –

множество вершин графа, представляющих выполняемые операции алгоритма.
R – множество дуг графа, определяющих последовательность операций.
Дуга r(i,j) принадлежит графу G только, если операция j использует результат выполнения операции i
Вершины без входных дуг могут использоваться для указания операций ввода
Вершины без выходных дуг – для указания операций вывода.

Лекция 3

Слайд 7

Пример модели вычислений (S прямоугольника)
Лекция 3

Слайд 8

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

между которыми нет пути, можно выполнять параллельно (сначала все «*», потом «-»)

Лекция 3

Слайд 9

Оценки трудоемкости параллельных алгоритмов
Speedup - ускорение за счёт параллельного выполнения на

N процессорах (потоках)
a(N) = T(1) / T(N)
Efficiency - эффективность системы из N процессоров
E(N) = a(N) / N
Scalability - масштабируемость системы (возможность ускорения вычислений пропорционально числу процессоров, т.е. линейное ускорение)
a(N)=N
a(N)>N – суперлинейное ускорение

Лекция 3

Слайд 10

Граф О-О и показатели эффективности для типовых задач Алгоритмы вычисления сумм
Лекция 3
Общая

задача - нахождение частных сумм последовательности числовых значений
Частная задача - нахождение общей суммы последовательности числовых значений

Слайд 11

Последовательный алгоритм S=0; S+=x1; …
Возможно только последовательное выполнение, распараллеливание данного алгоритма выполнить

нельзя.

Лекция 3

Слайд 12

Каскадная схема
Возможно распараллеливание алгоритма суммирования
Лекция 3

Слайд 13

Оценка эффективности
Количество итераций (уровней) каскадной схемы:
k = log2n
(на рисунке при n=4,

k=2)
Общее количество операций суммирования по всем уровням без распараллеливания (равно количеству суммирований для последовательной схемы):
Kпосл = n/2 + n/4 + …+ 1 = n - 1
Общее количество операций суммирования с распараллеливанием (равно количеству итераций):
Kпар = log2n

Лекция 3

Слайд 14

Оценка эффективности
Время выполнения на 1 процессоре (равно количеству операций):
Т1 = Kпосл
Время

выполнения на р процессорах (равно количеству итераций):
Тр = Kпар
Ускорение:
a(p) = Т1 /Тр = (n – 1)/log2n
Эффективность:
E(p) = a(p)/p = (n – 1)/(p * log2n)
Для реализации вычислительной схемы необходимо n/2 процессоров ?
E(p) = a(p)/p = (n – 1)/((n/2) * log2n) ?
lim E(p) = 0 при р → ∞

Лекция 3

Слайд 15

Улучшение каскадной схемы
Цель – асимптотически ненулевая эффективность.
Суть алгоритма:
все суммируемые значения подразделяются

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

Лекция 3

Слайд 16

Улучшение каскадной схемы
Пример при n=16:
все суммируемые значения подразделяются на (n/log2n)=4 группы,

в каждой из которых содержится (log2n)=4 элемента;
для каждой группы вычисляется (параллельно) сумма значений при помощи последовательного алгоритма суммирования;
для полученных (n/log2n)=4 сумм отдельных групп применяется обычная каскадная схема.

Лекция 3

Слайд 17

Модифицированная каскадная схема
Лекция 3

Слайд 18

Оценка эффективности
Для этапа 1
число параллельных операций k1 = log2n
необходимое число

процессоров р1= n/log2n
Для этапа 2
число параллельных операций k2 = log2(n/log2n) ≤ log2n
необходимое число процессоров р2= р1 /2 = (n/log2n)/2
Время выполнения на р = р1 процессорах:
Тр = k1 + k2 ≤ 2 log2n
Ускорение (меньше в 2 раза):
a(p) = Т1 /Тр = (n – 1)/2 log2n
Эффективность (асимптотически ненулевая):
E(p) = a(p)/p = (n – 1)/2 plog2n = (n – 1)/2n
lim E(p) = 0.5 при р → ∞

Лекция 3

Слайд 19

Выводы
Неочевидность приемов распараллеливания
Неочевидность оценок эффективности
Возможность разных вариантов параллельных схем
Наглядность модели на

графах

Лекция 3

Слайд 20

Передача данных. Коммуникационная трудоемкость алгоритмов
В рассмотренных оценках не учтены затраты времени

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

Лекция 3

Слайд 21

Пример оптимальных АМ
Алгоритмы, основанные на покоординатной маршрутизации (dimension ordered routing) –

поочередный поиск путей передачи данных для каждой размерности топологии сети.
Пример: алгоритм ХY-маршрутизации для решетки:
Передача данных по горизонтали до пересечения с вертикалью CPU2
Передача данных по вертикали и т.д.

Лекция 3

Слайд 22

Лекция 3

Слайд 23

Характеристики коммуникационной составляющей длительности выполнения параллельного алгоритма в МВС
Время передачи данных

определяют:
Время начальной подготовки сообщения для передачи, поиска маршрута в сети – tн
Время передачи служебных данных (заголовок сообщения, диагностический блок) между соседними CPU (имеющими между собой физический канал передачи данных) – tс
Время передачи одного байта по одному каналу (определяется полосой пропускания каналов сети) – tк =1/R, где R - ширина полосы

Лекция 3

Слайд 24

Методы передачи данных
1. Метод передачи сообщений как неделимых блоков информации (store-and-forward

routing, SFR):
CPU1
Готовит данные (сообщение) для передачи
Определяет CPU2 для пересылки (промежуточный)
Запускает операцию пересылки данных
CPU2
Принимает полностью все пересылаемые данные
Выполняет пересылку далее по маршруту
Время пересылки m байт по маршруту длины l (через l узлов) :
tпд = tн + (mtк + tс )l
Для «длинных» сообщений, где можно пренебречь пересылкой служебных данных:
tпд = tн +mtкl

Лекция 3

Слайд 25

Методы передачи данных
2. Метод передачи пакетов – сообщение состоит из блоков

информации (пакетов) (cut-through-routing, CTR)
CPU1
Готовит данные (сообщение) в виде пакетов для передачи
Определяет CPU2 для пересылки (промежуточный)
Запускает операцию пересылки пакетов
CPU2
Принимает пакет
Выполняет пересылку далее по маршруту как только получил и обработал заголовок (учитывает tс)
Время пересылки m байт по маршруту длины l :
tпд = = tн + mtк + tсl

Лекция 3

Слайд 26

Преимущества и недостатки CTR
Ускоряет пересылку данных.
Снижает потребность в памяти для

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

Лекция 3

Слайд 27

Классификация операций передачи данных в МВС
передача данных (сообщений):
между двумя CPU сети,
от

одного CPU всем остальным CPU сети,
от всех CPU всем CPU сети,
то же для различных наборов данных;
прием данных (сообщений):
на один CPU от всех CPU сети,
на каждом CPU от всех CPU сети,
то же для различных сообщений.

Лекция 3

Моделирование и анализ параллельных вычислений.

Содержание

Эффективность параллельных вычисленийЖесткие требования к эффективности определены задачами (экология, аэродинамика, геофизика,

Зачем нужны модели и их анализ?Для разработки эффективных параллельных алгоритмов оценивают

Модель вычисленийГраф «операции – операнды» описывает алгоритм вычислений на уровне операций

Определение графа «операции-операнды» (граф О-О)Граф О-О G = (V , R)

Определение графа «операции-операнды» (граф О-О)G = (V , R) V –

Пример модели вычислений (S прямоугольника)Лекция 3

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

Оценки трудоемкости параллельных алгоритмовSpeedup - ускорение за счёт параллельного выполнения на

Граф О-О и показатели эффективности для типовых задач Алгоритмы вычисления суммЛекция 3Общая

Последовательный алгоритм S=0; S+=x1; …Возможно только последовательное выполнение, распараллеливание данного алгоритма выполнить

Каскадная схемаВозможно распараллеливание алгоритма суммированияЛекция 3

Оценка эффективностиКоличество итераций (уровней) каскадной схемы:k = log2n(на рисунке при n=4,

Оценка эффективностиВремя выполнения на 1 процессоре (равно количеству операций):Т1 = KпослВремя

Улучшение каскадной схемыЦель – асимптотически ненулевая эффективность.Суть алгоритма:все суммируемые значения подразделяются

Улучшение каскадной схемыПример при n=16:все суммируемые значения подразделяются на (n/log2n)=4 группы,

Модифицированная каскадная схемаЛекция 3

Оценка эффективностиДля этапа 1 число параллельных операций k1 = log2nнеобходимое число

ВыводыНеочевидность приемов распараллеливанияНеочевидность оценок эффективностиВозможность разных вариантов параллельных схемНаглядность модели на

Передача данных. Коммуникационная трудоемкость алгоритмовВ рассмотренных оценках не учтены затраты времени

Пример оптимальных АМАлгоритмы, основанные на покоординатной маршрутизации (dimension ordered routing) –

Лекция 3

Характеристики коммуникационной составляющей длительности выполнения параллельного алгоритма в МВСВремя передачи данных

Методы передачи данных1. Метод передачи сообщений как неделимых блоков информации (store-and-forward

Методы передачи данных2. Метод передачи пакетов – сообщение состоит из блоков

Преимущества и недостатки CTR Ускоряет пересылку данных.Снижает потребность в памяти для

Классификация операций передачи данных в МВСпередача данных (сообщений):между двумя CPU сети,от

Похожие презентации

Эффективность параллельных вычислений
Жесткие требования к эффективности определены задачами (экология, аэродинамика, геофизика,

Зачем нужны модели и их анализ?
Для разработки эффективных параллельных алгоритмов оценивают

Модель вычислений
Граф «операции – операнды» описывает алгоритм вычислений на уровне операций

Определение графа «операции-операнды» (граф О-О)
Граф О-О G = (V , R)

Определение графа «операции-операнды» (граф О-О)
G = (V , R)
V –

Пример модели вычислений (S прямоугольника)
Лекция 3

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

Оценки трудоемкости параллельных алгоритмов
Speedup - ускорение за счёт параллельного выполнения на

Граф О-О и показатели эффективности для типовых задач Алгоритмы вычисления сумм
Лекция 3
Общая

Последовательный алгоритм S=0; S+=x1; …
Возможно только последовательное выполнение, распараллеливание данного алгоритма выполнить

Каскадная схема
Возможно распараллеливание алгоритма суммирования
Лекция 3

Оценка эффективности
Количество итераций (уровней) каскадной схемы:
k = log2n
(на рисунке при n=4,

Оценка эффективности
Время выполнения на 1 процессоре (равно количеству операций):
Т1 = Kпосл
Время

Улучшение каскадной схемы
Цель – асимптотически ненулевая эффективность.
Суть алгоритма:
все суммируемые значения подразделяются

Улучшение каскадной схемы
Пример при n=16:
все суммируемые значения подразделяются на (n/log2n)=4 группы,

Модифицированная каскадная схема
Лекция 3

Оценка эффективности
Для этапа 1
число параллельных операций k1 = log2n
необходимое число

Выводы
Неочевидность приемов распараллеливания
Неочевидность оценок эффективности
Возможность разных вариантов параллельных схем
Наглядность модели на

Передача данных. Коммуникационная трудоемкость алгоритмов
В рассмотренных оценках не учтены затраты времени

Пример оптимальных АМ
Алгоритмы, основанные на покоординатной маршрутизации (dimension ordered routing) –

Характеристики коммуникационной составляющей длительности выполнения параллельного алгоритма в МВС
Время передачи данных

Методы передачи данных
1. Метод передачи сообщений как неделимых блоков информации (store-and-forward

Методы передачи данных
2. Метод передачи пакетов – сообщение состоит из блоков

Преимущества и недостатки CTR
Ускоряет пересылку данных.
Снижает потребность в памяти для

Классификация операций передачи данных в МВС
передача данных (сообщений):
между двумя CPU сети,
от