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

         

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


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

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

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

Таблица 1.1. Характеристики топологий сети передачи данных (p – количество процессоров)

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



Содержание раздела