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

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


Вашему вниманию предлагается презентация на тему «Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов.», с которой можно предварительно ознакомиться, просмотреть текст и слайды к ней, а так же, в случае, если она вам подходит - скачать файл для редактирования или печати.

Презентация содержит 22 слайда и доступна для скачивания в формате ppt. Размер скачиваемого файла: 946.88 KB

Просмотреть и скачать

Pic.1
2. Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгори
2. Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов.
Pic.2
Передача данных. Коммуникационная трудоемкость алгоритмов В рассмотренных оценках не учтены затраты
Передача данных. Коммуникационная трудоемкость алгоритмов В рассмотренных оценках не учтены затраты времени на передачу данных. Основа для характеристики передачи данных – алгоритмы маршрутизизации (АМ). АМ определяет путь передачи данных от CPU1 (источника сообщения) до CPU2 (адресата доставки). Классификация АМ: Оптимальные (определяют кратчайшие пути передачи данных) и неоптимальные АМ. Адаптивные (учитывают загрузку каналов связи) и неадаптивные АМ.
Pic.3
Пример оптимальных АМ Алгоритмы, основанные на покоординатной маршрутизации (dimension ordered routi
Пример оптимальных АМ Алгоритмы, основанные на покоординатной маршрутизации (dimension ordered routing) – поочередный поиск путей передачи данных для каждой размерности топологии сети. Пример: алгоритм ХY-маршрутизации для решетки: Передача данных по горизонтали до пересечения с вертикалью CPU2 Передача данных по вертикали и т. д.
Pic.4
Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд 4
Pic.5
Характеристики коммуникационной составляющей длительности выполнения параллельного алгоритма в МВС В
Характеристики коммуникационной составляющей длительности выполнения параллельного алгоритма в МВС Время передачи данных определяют: Время начальной подготовки сообщения для передачи, поиска маршрута в сети – tн Время передачи служебных данных (заголовок сообщения, диагностический блок) между соседними CPU (имеющими между собой физический канал передачи данных) – tс Время передачи одного байта по одному каналу (определяется полосой пропускания каналов сети) – tк =1/R, где R - ширина полосы, количество битов, передаваемых за 1сек.
Pic.6
Методы передачи данных 1. Метод передачи данных (сообщений) как неделимых блоков информации (store-a
Методы передачи данных 1. Метод передачи данных (сообщений) как неделимых блоков информации (store-and-forward routing, SFR): CPU1 Готовит данные (сообщение) для передачи Определяет CPU2 для пересылки (промежуточный) Запускает операцию пересылки данных CPU2 Принимает полностью все пересылаемые данные Выполняет пересылку далее по маршруту Время пересылки m байт по маршруту длины l (через l узлов) : tпд = tн + (mtк + tс )l Для «длинных» сообщений, где можно пренебречь временем пересылки служебных данных: tпд = tн +mtкl
Pic.7
Методы передачи данных 2. Метод передачи пакетов – сообщение состоит из блоков информации (пакетов)
Методы передачи данных 2. Метод передачи пакетов – сообщение состоит из блоков информации (пакетов) (cut-through-routing, CTR) CPU1 Готовит данные (сообщение) в виде пакетов для передачи Определяет CPU2 для пересылки (промежуточный) Запускает операцию пересылки пакетов CPU2 Принимает пакет Выполняет пересылку далее по маршруту как только получил и обработал заголовок (учитывает tс) Время пересылки m байт по маршруту длины l : tпд = = tн + mtк + tсl
Pic.8
Преимущества и недостатки CTR Ускоряет пересылку данных. Снижает потребность в памяти для хранения п
Преимущества и недостатки CTR Ускоряет пересылку данных. Снижает потребность в памяти для хранения пересылаемых данных и организации приема-передачи сообщений. Для передачи могут использоваться одновременно разные коммуникационные каналы (в зависимости от топологии сети). Требует разработки более сложного аппаратного и программного обеспечения сети. Может увеличить накладные расходы (время подготовки и время передачи служебных данных), При передаче пакетов возможно возникновение конфликтных ситуаций.
Pic.9
Классификация операций передачи данных в МВС передача данных (сообщений): между двумя CPU сети, от о
Классификация операций передачи данных в МВС передача данных (сообщений): между двумя CPU сети, от одного CPU всем остальным CPU сети, от всех CPU всем CPU сети, то же для различных сообщений; прием данных (сообщений): на один CPU от всех CPU сети, на каждом CPU от всех CPU сети, то же для различных сообщений.
Pic.10
Оценки трудоемкости для различных топологий Топология Диаметр Граф 1 Звезда 2 Линейка р - 1 Кольцо р
Оценки трудоемкости для различных топологий Топология Диаметр Граф 1 Звезда 2 Линейка р - 1 Кольцо р/2 Решетка (2D) 2(√р - 1) Диаметр – определяет время передачи данных, max расстояние между 2 CPU сети (расстояние равно величине кратчайшего пути).
Pic.11
Передача между двумя CPU сети (топология «кольцо») Для оценки нужно: Определить алгоритм пересылки.
Передача между двумя CPU сети (топология «кольцо») Для оценки нужно: Определить алгоритм пересылки. В формулы вместо l подставить значение диаметра Передача сообщений tпд = tн +mtк p/2 («длинные» сообщения) Передача пакетов tпд = = tн + mtк + tс p/2
Pic.12
Передача от одного CPU всем остальным CPU сети single-node broadcast Прием на одном CPU от всех оста
Передача от одного CPU всем остальным CPU сети single-node broadcast Прием на одном CPU от всех остальных CPU сети single-node accumulation Передача сообщений: От источника к 2 соседним CPU 2 соседних – далее по сети (кольцо) tпд = (tн +mtк )p/2 Передача пакетов – «каскадно» От источника к CPU на расстоянии р/2 CPU1 и CPU2 – CPU на расстоянии р/4 …
Pic.13
Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд 13
Pic.14
Передача от всех CPU всем остальным CPU сети multinode broadcast Прием на всех CPU от всех остальных
Передача от всех CPU всем остальным CPU сети multinode broadcast Прием на всех CPU от всех остальных CPU сети multinode accumulation Передача сообщений: Все CPU могут одновременно рассылать сообщение в определенном направлении по кольцу Рассылка закончится через р-1 шаг tпд = (tн +mtк )(p – 1) Передача пакетов Обобщение алгоритмов одиночной рассылки на случай множественной приводит к перегрузке каналов передачи данных  По одной линии собирается очередь - несколько пакетов, ожидающих передачи. Теряется преимущество пакетной передачи.
Pic.15
Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов., слайд 15
Pic.16
Обобщенная передача от одного CPU всем CPU сети single-node scatter (рассеивание) Обобщенный прием н
Обобщенная передача от одного CPU всем CPU сети single-node scatter (рассеивание) Обобщенный прием на одном CPU от всех CPU сети single-node gather (сбор) Передача разных сообщений: От источника половину сообщений для рассылки соседнему CPU И т. д. tпд >= atн +mtк (p-1) Передача пакетов Сопоставима по трудности с multi, т. к. разные данные не могут взаимодействовать при пересылке.
Pic.17
Обобщенная передача от всех CPU всем CPU сети Обобщенный прием на всех CPU от всех CPU сети total ex
Обобщенная передача от всех CPU всем CPU сети Обобщенный прием на всех CPU от всех CPU сети total exchange Передача сообщений: Все CPU одновременно рассылают свои сообщения в определенном направлении соседу по кольцу. Все CPU отбирают среди полученных сообщений адресованные им. Остальные сообщения пересылаются дальше. tпд = (tн +0. 5р mtк )(p – 1) Передача пакетов Преимущества у пакетной передачи нет.
Pic.18
Оценки коммуникационной трудоемкости для кластеров Кластер – группа выделенных рабочих станций (объе
Оценки коммуникационной трудоемкости для кластеров Кластер – группа выделенных рабочих станций (объединены в ЛВС, работают как единый вычислительный ресурс, используется серийное оборудование). Использование коммуникаторов (hub, switch)  Топология сети кластера – полный граф (l=1), но: Hub – : в каждый момент передача данных только между 2 узлами. Switch + : м. б. взаимодействие >1 непересекающихся пар узлов. Основной способ выполнения коммуникационных операций – пакетный метод (часто на основе протокола TCP/IP)
Pic.19
Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 1: tн не зависит от объе
Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 1: tн не зависит от объема данных, tс не зависит от числа пакетов tпд = tн + mtк + tс Ограничения не соответствуют действительности  Оценка времени (трудоемкости) неточна
Pic.20
Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 2: Учитывается n - число
Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 2: Учитывается n - число пакетов, n = m/(Vmax – Vc) Vc - объем служебных данных в каждом пакете, Vmax - максимально возможный для сети размер пакета, tнач0 – аппаратная (сетевая) задержка (латентность), tнач1 – время подготовки к передаче в сети 1 байта. Предполагается Подготовка данных для 2,3, … пакетов совмещена с пересылкой предшествующих пакетов. Нужно учитывать рост объема передаваемой информации за счет добавления служебных данных (заголовков пакетов)
Pic.21
Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 2 – итоговое соотношение
Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 2 – итоговое соотношение
Pic.22
Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 3 – модель Хокни (R. W.
Оценка трудоемкости операции передачи данных между 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


Скачать презентацию

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