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


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

Содержание

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

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

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

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

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

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

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

Лекция 4

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

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

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

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

Лекция 4

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

Слайд 4Лекция 4


Лекция 4

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

данных определяют:
Время начальной подготовки сообщения для передачи, поиска маршрута в

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

Лекция 4

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

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

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

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




Лекция 4

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

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

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

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

Лекция 4


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

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

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

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

Лекция 4

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

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

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

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

Лекция 4

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

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

Диаметр

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

сети (расстояние равно величине кратчайшего пути).

Лекция 4

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

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

пересылки.
В формулы вместо l подставить значение диаметра
Передача сообщений
tпд = tн

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

Лекция 4

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

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



Лекция 4

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

Слайд 13Лекция 4

Лекция 4

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

всех CPU от всех остальных CPU сети multinode accumulation
Передача сообщений:
Все

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

Лекция 4

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

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

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

Лекция 4Цикл 1 рассылки сообщенийЦикл 2 рассылки сообщенийЦикл p-1 рассылки сообщенийЧьи сообщения пришлиЧье сообщение передается

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

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

(сбор)

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

Лекция 4

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

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

всех CPU от всех CPU сети total exchange
Передача сообщений:
Все CPU

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


Лекция 4

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

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

станций (объединены в ЛВС, работают как единый вычислительный ресурс, используется

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

Лекция 4

Оценки коммуникационной трудоемкости для кластеров Кластер – группа выделенных рабочих станций  (объединены в ЛВС, работают как

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

1:
tн не зависит от объема данных,
tс не зависит от числа

пакетов

tпд = tн + mtк + tс

Ограничения не соответствуют действительности ?
Оценка времени (трудоемкости) неточна

Лекция 4

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

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

2:
Учитывается
n - число пакетов, n = m/(Vmax – Vc)


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



Лекция 4

Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 2:Учитывается n - число пакетов, n =

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

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


Лекция 4

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

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


Лекция 4

Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 3 – модель Хокни (R.W. Hocney, 1994)

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

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

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

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

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


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

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