Разделы презентаций


lec03.pptx

Содержание

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

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

Слайд 12. Моделирование и анализ параллельных вычислений.
Модели вычислений.
Оценки эффективности параллельных

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

2. Моделирование и анализ параллельных вычислений.Модели вычислений. Оценки эффективности параллельных алгоритмов. Коммуникационная трудоемкость параллельных алгоритмов.

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

геофизика, геном и др.):

исследуемые объекты – 3D,
для приемлемой точности нужна

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

Лекция 3

Эффективность параллельных вычисленийЖесткие требования к эффективности определены задачами (экология, аэродинамика, геофизика, геном и др.):исследуемые объекты – 3D,для

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

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

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

Лекция 3

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

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

операций и информационных зависимостей.
Предположения упрощенной модели:
Время выполнения всех вычислительных операций

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

Лекция 3

Модель вычисленийГраф «операции – операнды» описывает алгоритм вычислений на уровне операций и информационных зависимостей.Предположения упрощенной модели:Время выполнения

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

R) – ациклический ориентированный (направленный) граф -  в нем отсутствуют  пути,

начинающиеся и кончающиеся в одной и той же вершине.

Лекция 3

1

6

5

3

4

2

Определение  графа «операции-операнды» (граф О-О)Граф О-О G = (V , R) – ациклический ориентированный (направленный) граф

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

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

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

Лекция 3

Определение  графа «операции-операнды» (граф О-О)G = (V , R) V – множество вершин графа, представляющих выполняемые

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

Пример модели вычислений (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

Оценки трудоемкости параллельных алгоритмовSpeedup - ускорение за счёт параллельного выполнения на N процессорах (потоках) a(N) = T(1)

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

3

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




Частная задача

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

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

выполнить нельзя.
Лекция 3

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

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

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

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

n=4, k=2)
Общее количество операций суммирования по всем уровням без распараллеливания

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

Общее количество операций суммирования с распараллеливанием (равно количеству итераций):
Kпар = log2n

Лекция 3

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

Слайд 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

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

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

подразделяются на (n/log2n) групп, в каждой из которых содержится (log2n)

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

Лекция 3

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

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

группы, в каждой из которых содержится (log2n)=4 элемента;
для каждой

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

Лекция 3

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

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

Модифицированная каскадная схемаЛекция 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

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

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

на графах

Лекция 3

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

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

времени на передачу данных.
Основа для характеристики передачи данных – алгоритмы

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

Лекция 3

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

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

– поочередный поиск путей передачи данных для каждой размерности топологии

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

Лекция 3

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

Слайд 22Лекция 3


Лекция 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

Методы передачи данных1. Метод передачи сообщений как неделимых блоков информации (store-and-forward routing, SFR):CPU1Готовит данные (сообщение) для передачиОпределяет

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

блоков информации (пакетов) (cut-through-routing, CTR)
CPU1
Готовит данные (сообщение) в виде пакетов

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

Лекция 3


Методы передачи данных2. Метод передачи пакетов – сообщение состоит из блоков информации (пакетов) (cut-through-routing, CTR)CPU1Готовит данные (сообщение)

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

для хранения пересылаемых данных и организации приема-передачи сообщений.
Для передачи

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

Лекция 3

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

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

сети,
от одного CPU всем остальным CPU сети,
от всех CPU

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

Лекция 3

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

Слайд 28Оценки трудоемкости для различных топологий
Топология Диаметр
Граф 1
Звезда 2
Линейка р - 1
Кольцо р/2
Решетка (2D) 2(√р - 1)

Диаметр

– определяет время передачи данных, max расстояние между 2 CPU

сети (расстояние равно величине кратчайшего пути).
Для оценки нужно:
Определить алгоритм пересылки.
В формулы вместо l подставить значение диаметра

Лекция 3

Оценки трудоемкости для различных топологийТопология		ДиаметрГраф			1Звезда			2Линейка		р - 1Кольцо			р/2Решетка (2D)	2(√р - 1)Диаметр – определяет время передачи данных, max расстояние

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика