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

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

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

Лекция 4

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

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

Лекция 4

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

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

Лекция 4

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

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

Лекция 4

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

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

Лекция 4

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

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

Лекция 4

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

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

Лекция 4

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

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

Лекция 4

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

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

Лекция 4

одном CPU от всех остальных CPU сети single-node accumulation
Передача сообщений:
От

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

Лекция 4

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

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

Лекция 4

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

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

(сбор)

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

Лекция 4

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

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

Лекция 4

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

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

Лекция 4

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

пакетов

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

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

Лекция 4

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

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

Лекция 4

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


Лекция 4

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