Моделирование и анализ параллельных вычислений. - презентация, доклад, проект скачать

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Моделирование и анализ параллельных вычислений.. Доклад-сообщение содержит 28 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

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

Слайд 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 при р → ∞

Слайд 15

Описание слайда:

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

Слайд 16

Описание слайда:

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

Слайд 17

Описание слайда:

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

Слайд 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 при р → ∞

Слайд 19

Описание слайда:

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

Слайд 20

Описание слайда:

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

Слайд 21

Описание слайда:

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

Слайд 22

Описание слайда:

Слайд 23

Описание слайда:

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

Слайд 24

Описание слайда:

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

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

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