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

Топология сети вычислительных кластеров

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

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

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

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

· ширина бинарного деления (bisection width) – показатель, определяемый как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области одинакового размера;

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

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

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