Топологии коммуникационных сетей

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

С точки зрения топологии коммуникационные сети разделяются на сети с фиксированной топологией и на реконфигурируемые сети. С другой стороны, с этой же точки зрения коммуникационные сети разделяются на регулярные сети и нерегулярные сети.

Чаще всего в параллельных вычислительных системах используют регулярные сети с фиксированной топологией. Среди этих сетей наиболее распространены топологии сетей, предоставленные на Рис.1–8, где квадратики обозначают процессоры системы.

Рис. 1. Некоммутируемая коммуникационная сеть с топологий сети типа «шина» (bus).d=1 .

Диаметр сети с топологией типа "шина" - см. рис. 1. Здесь и далее – количество процессоров в системе. Заметим, что шину можно интерпретировать как сетевой коммутатор с временным разделением (см. параграф 3).

Рис. 2. Некоммутируемая коммуникационная сеть с топологий сети типа «линейка» (linear array, farm).

В сети с топологией типа "линейка" (см. рис. 2) каждый процессор связан непосредственно только с двумя соседними (с предыдущим и последующим) процессорами. Топология является, с одной стороны, просто реализуемой, а? с другой стороны, соответствует структуре передачи данных при решении многих вычислительных задач. Диаметр сети с топологий типа «линейка» .

Рис. 3. Некоммутируемая коммуникационная сеть с топологий сети типа «кольцо» (ring).

Сеть с топологией типа "кольцо" (см. рис. 3) получается из топологии типа «линейка» путем соединения между собой первого и последнего процессоров «линейки». Диаметр сети с топологий типа «кольцо» .

Сеть с топологий типа «двумерная решетка» (см. рис. 4) может быть достаточно просто реализована и, вместе с тем, эффективно использована при реализации многих численных алгоритмов (например, при интегрировании многих систем дифференциальных уравнений в частных производных). Диаметр сети с топологий типа . Из сети с топологией типа «двумерная решетка» может быть получена сеть с топологией сети типа «тор». Для этого достаточно соединить между собой граничные процессоры по «горизонтали» - , ,…, и по «вертикали» , ,…, .

Рис. 4. Некоммутируемая коммуникационная сеть с топологий сети типа «двумерная решетка» (mesh).

Рис. 5. Пример (N=6) некоммутируемой полносвязной коммуникационной сети – «клика» (full connect).

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

Рис. 6. Некоммутируемая коммуникационная сеть с топологий сети типа «бинарное дерево» (tree).

Диаметр сети с топологией типа "бинарное дерево" log₂ - см. рис. 6.

Рис. 7. Пример (N=7) некоммутируемой коммуникационной сети с топологий сети типа «звезда» (star).

Сеть с топологией типа "звезда" (см. рис. 7) эффективна, например, при организации централизованных схем параллельных вычислений. Диаметр сети с топологий типа «звезда» =2.

Диаметр сети с топологией типа "гиперкуб" =log₂ , =2^p где – количество измерений гиперкуба – см. рис. 8. В сети с топологий «гиперкуб» диаметр сети медленно растет с ростом числа процессоров в системе. Например, при , при , . заметим, что в p-мерном гиперкубе каждый процессор непосредственно связан ровно с p соседями.

Рис. 8. Пример (трехмерный гиперкуб,N=8) некоммутируемых коммуникационных сетей с топологий сети типа «гиперкуб» (hypercube).

Процессоры в гиперкубе нумеруют с помощью бинарного отраженного кода Грея по следующему правилу (см. рис. 8):

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

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

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

Заметим, что вычислительные системы, имеющее большое количество процессоров, имеют обычно иерархическую коммуникационную сеть. В такой сети все процессоры разбиваются на группы с одинаковым и относительно небольшим количеством процессоров (~32 - 64) в каждой. Физически группа процессоров монтируется в один блок или стойку. Каждая из этих групп процессоров имеет коммуникационную сеть одной топологии. Группы процессоров объединяются между собой коммуникационной сетью той же или другой топологии.