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

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

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

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №3

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №4

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №5

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №6

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №7

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №8

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №9

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №10

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №11

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №12

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №13

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №14

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №15

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №16

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №17

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №18

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №19

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №20

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №21

Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд №22

Содержание ▲

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

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

Слайд 1

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

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

Слайд 2

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

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

Слайд 3

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

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

Слайд 4

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

Слайд 5

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

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

Слайд 6

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

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

Слайд 7

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

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

Слайд 8

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

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

Слайд 9

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

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

Слайд 10

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

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

Слайд 11

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

Передача между двумя CPU сети (топология «кольцо») Для оценки нужно: Определить алгоритм пересылки. В формулы вместо l подставить значение диаметра Передача сообщений tпд = tн +mtк p/2 («длинные» сообщения) Передача пакетов tпд = = tн + mtк + tс p/2

Слайд 12

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

Передача от одного CPU всем остальным CPU сети single-node broadcast Прием на одном CPU от всех остальных CPU сети single-node accumulation Передача сообщений: От источника к 2 соседним CPU 2 соседних – далее по сети (кольцо) tпд = (tн +mtк )p/2 Передача пакетов – «каскадно» От источника к CPU на расстоянии р/2 CPU1 и CPU2 – CPU на расстоянии р/4 …

Слайд 13

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

Слайд 14

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

Передача от всех CPU всем остальным CPU сети multinode broadcast Прием на всех CPU от всех остальных CPU сети multinode accumulation Передача сообщений: Все CPU могут одновременно рассылать сообщение в определенном направлении по кольцу Рассылка закончится через р-1 шаг tпд = (tн +mtк )(p – 1) Передача пакетов Обобщение алгоритмов одиночной рассылки на случай множественной приводит к перегрузке каналов передачи данных  По одной линии собирается очередь - несколько пакетов, ожидающих передачи. Теряется преимущество пакетной передачи.

Слайд 15

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

Слайд 16

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

Обобщенная передача от одного CPU всем CPU сети single-node scatter (рассеивание) Обобщенный прием на одном CPU от всех CPU сети single-node gather (сбор) Передача разных сообщений: От источника половину сообщений для рассылки соседнему CPU И т.д. tпд >= atн +mtк (p-1) Передача пакетов Сопоставима по трудности с multi, т.к. разные данные не могут взаимодействовать при пересылке.

Слайд 17

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

Обобщенная передача от всех CPU всем CPU сети Обобщенный прием на всех CPU от всех CPU сети total exchange Передача сообщений: Все CPU одновременно рассылают свои сообщения в определенном направлении соседу по кольцу. Все CPU отбирают среди полученных сообщений адресованные им. Остальные сообщения пересылаются дальше. tпд = (tн +0.5р mtк )(p – 1) Передача пакетов Преимущества у пакетной передачи нет.

Слайд 18

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

Оценки коммуникационной трудоемкости для кластеров Кластер – группа выделенных рабочих станций (объединены в ЛВС, работают как единый вычислительный ресурс, используется серийное оборудование). Использование коммуникаторов (hub, switch)  Топология сети кластера – полный граф (l=1), но: Hub – : в каждый момент передача данных только между 2 узлами. Switch + : м.б. взаимодействие >1 непересекающихся пар узлов. Основной способ выполнения коммуникационных операций – пакетный метод (часто на основе протокола TCP/IP)

Слайд 19

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

Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 1: tн не зависит от объема данных, tс не зависит от числа пакетов tпд = tн + mtк + tс Ограничения не соответствуют действительности  Оценка времени (трудоемкости) неточна

Слайд 20

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

Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 2: Учитывается n - число пакетов, n = m/(Vmax – Vc) Vc - объем служебных данных в каждом пакете, Vmax - максимально возможный для сети размер пакета, tнач0 – аппаратная (сетевая) задержка (латентность), tнач1 – время подготовки к передаче в сети 1 байта. Предполагается Подготовка данных для 2,3, … пакетов совмещена с пересылкой предшествующих пакетов. Нужно учитывать рост объема передаваемой информации за счет добавления служебных данных (заголовков пакетов)

Слайд 21

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

Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 2 – итоговое соотношение

Слайд 22

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

Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 3 – модель Хокни (R.W. Hocney, 1994) – используется для грубых оценок трудоемкости tпд = tн + mtк = tн + m/R Оценки через вычислительные эксперименты на кластере: tн - время передачи сообщения длины 0 для подходов 1 и 3, tнач0 , tнач1 для подхода 2 - можно оценить через аппроксимацию tпд - времени передачи сообщений размером от 0 до Vmax R = max (tпд / m) при варьировании m