Лекция 3. Оценка коммуникационной трудоемкости параллельных алгоритмов

Характеристики топологии сети передачи данных. Общая характеристика механизмов передачи данных. Алгоритмы маршрутизации. Методы передачи данных. Анализ трудоемкости основных операций передачи данных. Передача данных между двумя процессорами сети. Передача данных от одного процессора всем остальным процессорам сети. Передача данных от всех процессоров всем процессорам. Обобщенная передача данных от одного процессора всем остальным процессорам сети. Обобщенная передача данных от всех процессоров всем процессорам сети. Циклический сдвиг.

Удобной моделью вычислительных систем является граф [__]. Граф вычислительной системы определяется структурой линий коммутации между процессорами ВС (топологией сети передачи данных). К числу типовых топологий обычно относят следующие схемы коммуникации процессоров (рисунок 3.3).

Полный граф (completely-connected graph или clique) – между любой парой процессоров существует линия связи. Такая топология обеспечивает минимальные затраты при передаче данных, однако оказывается сложной при большом количестве процессоров.

Линейка (linear array или farm) – все процессоры перенумерованы по порядку и каждый процессор, кроме первого и последнего, имеет линии связи только с двумя соседними. Достоинство – простая реализация, однако класс задач, которым эта схема соответствует, ограничен. Топология является подходящей для конвейерных вычислений.

Кольцо (ring) – получается из линейки процессоров соединением первого и последнего процессоров линейки.

Звезда (star) – все процессоры имеют связь с одним (управляющим) процессором. Топология эффективна для централизованной схемы вычислений.

Решетка (mesh) – граф связей образует (двух- или трехмерную) сетку. Топология реализуется достаточно просто и может эффективно использоваться при решении сеточных задач, описываемых уравнениями в частных производных.

Гиперкуб (hypercube) – частный случай решетки, когда по каждой размерности сетки имеется только два процессора (при размерности N гиперкуб содержит 2^N процессоров).

Гиперкуб обладает следующими свойствами:

- два процессора имеют соединение, если двоичные представления их номеров имеют только одну различающуюся позицию;

- в N-мерном гиперкубе каждый процессор связан ровно с N соседями;

- N-мерный гиперкуб может быть разделен на два (N–1)-мерных гиперкуба (всего возможно N таких разбиений);

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

Полный граф	Линейка
Кольцо	Звезда
2-мерная решетка	3-мерная решетка

Рис. 3.1. Примеры топологий многопроцессорных вычислительных систем

Основные характеристики топологии сети:

- диаметр – максимальное (по всем возможным парам) расстояние между двумя процессорами сети измеряемое по кратчайшему пути,эта величина обычно характеризует максимально время, необходимое для передачи данных между процессорами;

- связность (connectivity) – характеризует наличие разных маршрутов передачи данных между процессорами, показатель может быть определен, например, как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области;

- стоимость – общее количество линий передачи данных в многопроцессорной вычислительной системе.

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

− оптимальные, определяющие всегда наикратчайшие пути передачи данных, и неоптимальные алгоритмы маршрутизации;

− детерминированные и адаптивные методы выбора маршрутов (адаптивные алгоритмы определяют пути передачи данных в

зависимости от существующей загрузки коммуникационных каналов).

К числу наиболее распространенных оптимальных алгоритмов относится класс методов покоординатной маршрутизации (dimension-ordered routing), в которых поиск путей передачи данных осуществляется поочередно для каждой размерности топологии сети коммуникации. Так, для двумерной решетки такой подход приводит к маршрутизации, при которой передача данных сначала выполняется по одному направлению (например, по горизонтали до достижения вертикали процессоров, в которой располагается процессор назначения), а затем данные передаются вдоль другого направления (данная схема известна под названием алгоритма XY-маршрутизации).

Для гиперкуба покоординатная схема маршрутизации может состоять, например, в циклической передаче данных процессору, определяемому первой различающейся битовой позицией в номерах процессоров, на котором сообщение располагается в данный момент времени и на который сообщение должно быть передано.

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

Время передачи данных между процессорами определяет коммуникационную составляющую (communication overhead) длительности выполнения параллельного алгоритма в многопроцессорной вычислительной системе. Основной набор параметров, описывающих время передачи данных, состоит из следующего ряда величин:

− время начальной подготовки (t_m) характеризует длительность подготовки сообщения для передачи, поиска маршрута в сети и т.п.;

− время передачи служебных данных (t_c) между двумя соседними процессорами (т.е. для процессоров, между которыми имеется физический канал передачи данных); к служебным данным может относиться заголовок сообщения, блок данных для обнаружения ошибок передачи и т.п.;

− время передачи одного слова данных по одному каналу передачи данных (t_k); длительностьподобной передачи определяется полосой пропускания коммуникационных каналов в сети.