Теория и практика параллельных вычислений
Характеристики топологии сети
В качестве основных характеристик топологии сети передачи данных наиболее широко используется следующий ряд показателей:
- диаметр – показатель, определяемый как максимальное расстояние между двумя процессорами сети (под расстоянием обычно понимается величина кратчайшего пути между процессорами). Эта величина может характеризовать максимально необходимое время для передачи данных между процессорами, поскольку время передачи обычно прямо пропорционально длине пути;
- связность (connectivity) – показатель, характеризующий наличие разных маршрутов передачи данных между процессорами сети. Конкретный вид данного показателя может быть определен, например, как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области;
- ширина бинарного деления (bisection width) – показатель, определяемый как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области одинакового размера;
- стоимость – показатель, который может быть определен, например, как общее количество линий передачи данных в многопроцессорной вычислительной системе.
Для сравнения в таблице 1.1 приводятся значения перечисленных показателей для различных топологий сети передачи данных.
| Полный граф | 1 | p2/4 | p–1 | p(p–1)/2 |
| Звезда | 2 | 1 | 1 | p–1 |
| Полное двоичное дерево | 2log((p+1)/2) | 1 | 1 | p–1 |
| Линейка | p–1 | 1 | 1 | p–1 |
| Кольцо | p/2 | 2 | 2 | p |
| Решетка N=2 | 2 | |||
| Решетка-тор N=2 | 4 | 2p | ||
| Гиперкуб | log p | p/2 | log p | (p log p)/2 |
