Шаг 16.
Параллельные алгоритмы.
Топология сети вычислительных кластеров и ее характеристики

    На этом шаге мы приведем некоторые характеристики тополигии вычислительных кластеров.

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

Характеристики топологии сети

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

    Для сравнения в таблице 1 приводятся значения перечисленных показателей для различных топологий сети передачи данных.

Таблица 1. Характеристики топологий сети передачи данных (р - количество процессоров)
Топология Диаметр Ширина Связность бисекции Стоимость
Полный граф 1 p2/4 p - 1 p(p - 1)/2
Звезда 2 1 1 p - 1
Полное двоичное дерево 2log2((p+1)/2) 1 1 p - 1
Линейка p-1 1 1 p-1
Кольцо [p/2] 2 2 p
Решетка (N=2) 2(квадратный_корень(p) - 1) квадратный_корень(p) 2 2(p - квадратный_корень(p))
Решетка-тор (N=2) 2[квадратный_корень(p)/2] 2квадратный_корень(p)/2 4 2p
Гиперкуб log2p p/2 log2p (p log2p)/2

    На следующем шаге мы рассмотрим алгоритмы маршрутизации.




Предыдущий шаг Содержание Следующий шаг