Презентация Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов. онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов. абсолютно бесплатно. Урок-презентация на эту тему содержит всего 22 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:22 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:946.88 kB
- Просмотров:57
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№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
Скачать все slide презентации Моделирование и анализ параллельных вычислений. Коммуникационная трудоемкость параллельных алгоритмов. одним архивом:
