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

Содержание

Слайд 2

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

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

В рассмотренных оценках не учтены затраты времени

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

Лекция 4

Слайд 3

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

Пример оптимальных АМ

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

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

Лекция 4

Слайд 4

Лекция 4

Лекция 4

Слайд 5

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

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

Время передачи данных

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

Лекция 4

Слайд 6

Методы передачи данных 1. Метод передачи данных (сообщений) как неделимых блоков

Методы передачи данных

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

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

Лекция 4

Слайд 7

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

Методы передачи данных

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

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

Лекция 4

Слайд 8

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

Преимущества и недостатки CTR

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

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

Лекция 4

Слайд 9

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

Классификация операций передачи данных в МВС

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

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

Лекция 4

Слайд 10

Оценки трудоемкости для различных топологий Топология Диаметр Граф 1 Звезда 2

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

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

определяет время передачи данных, max расстояние между 2 CPU сети (расстояние равно величине кратчайшего пути).

Лекция 4

Слайд 11

Передача между двумя CPU сети (топология «кольцо») Для оценки нужно: Определить

Передача между двумя CPU сети (топология «кольцо»)

Для оценки нужно:
Определить алгоритм пересылки.
В

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

Лекция 4

Слайд 12

Передача от одного CPU всем остальным CPU сети single-node broadcast Прием

Передача от одного CPU всем остальным CPU сети single-node broadcast Прием на одном

CPU от всех остальных CPU сети single-node accumulation

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

Лекция 4

Слайд 13

Лекция 4

Лекция 4

Слайд 14

Передача от всех CPU всем остальным CPU сети multinode broadcast Прием

Передача от всех CPU всем остальным CPU сети multinode broadcast Прием на всех

CPU от всех остальных CPU сети multinode accumulation

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

Лекция 4

Слайд 15

Лекция 4 Цикл 1 рассылки сообщений Цикл 2 рассылки сообщений Цикл

Лекция 4

Цикл 1 рассылки сообщений

Цикл 2 рассылки сообщений

Цикл p-1 рассылки сообщений

Чьи

сообщения пришли

Чье сообщение передается

Слайд 16

Обобщенная передача от одного CPU всем CPU сети single-node scatter (рассеивание)

Обобщенная передача от одного CPU всем CPU сети single-node scatter (рассеивание) Обобщенный прием

на одном CPU от всех CPU сети single-node gather (сбор)

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

Лекция 4

Слайд 17

Обобщенная передача от всех CPU всем CPU сети Обобщенный прием на

Обобщенная передача от всех CPU всем CPU сети Обобщенный прием на всех

CPU от всех CPU сети total exchange

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

Лекция 4

Слайд 18

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

Оценки коммуникационной трудоемкости для кластеров

Кластер – группа выделенных рабочих станций

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

Лекция 4

Слайд 19

Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 1:

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

Подход 1:
tн

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

Лекция 4

Слайд 20

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

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

Подход 2:
Учитывается


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

Лекция 4

Слайд 21

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

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

Подход 2

– итоговое соотношение

Лекция 4

- Предыдущая
Моделирование и анализ параллельных вычислений.
Следующая -
Моделирование и анализ параллельных вычислений.

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

Презентация по факторам риска ССЗ
Фарфор. Фарфоровая посуда
Деловые культуры мира и техника ведения международных деловых переговоров
Защита синхронного генератора от перегрузок. Техническое обслуживание судовых электроприводов. (Билет 10)
Дополнение определителя
Корпоративный фитнес
Квантовая оптика
Електроємність. Конденсатори. (Лекция 6)
Anti-nuclear movement
Тепловые машины
Серебрякова Галина Борисовна МОУ СОШ №17 Г. Карталы Челябинской области Учитель начальных классов serebriackowa.galina@yandex.ru Конкурс «Чуде
Всероссийская акция, приуроченная к международному дню борьбы с коррупцией
Роль пациентской организации в повышении качества жизни больных с хроническими заболеваниями почек
Типология кризисов Петрова Маргарита Куркина Анна
Қазіргі әлемдегі нанотехнология
Сложные случаи правописания суффиксов
Презентация Минеральные воды
Презентация на тему "Как избежать умственных перегрузок в процессе обучения?" - скачать презентации по Педагогике
синтез спиросоединений из о-аминобензонитрила
Гренландия. Эскимосы
Презентация Виды ценных бумаг
Медико-социальные аспекты здоровья населения
Подготовил воспитатель СП ГБОУ СОШ№6 г.о. Отрадный «Детский сад № 14» Логинова Н.В. Подготовил воспитатель СП ГБОУ СОШ№6 г.о. Отр
Магнитные цепи и электромагнитные устройства. Трансформатор (продолжение)
Облачение православного духовенства
Древние священные сооружения
Классификация отраслей
История возникновения и развития хоккея на Южном Урале
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть