Топология межсетевого взаимодействия Hypercube - Hypercube internetwork topology

В компьютерная сеть, гиперкуб сети - это разновидность топология сети используется для подключения нескольких процессоры с модули памяти и точно данные маршрута. Сети гиперкубов состоят из 2^м узлы, которые образуют вершины квадратов для создания объединенная сеть подключение. Гиперкуб - это, по сути, многомерное ячеистая сеть с двумя узлами в каждом измерении. Из-за схожести такие топологии обычно группируются в k-ари d-мерная топология сеток, где d представляет количество измерений и k представляет количество узлов в каждом измерении.^[1][2]

Различные гиперкубы для разного количества узлов

Топология^[3]

Сеть взаимосвязей гиперкуба формируется путем соединения N узлов, что может быть выражено как степень 2. Это означает, что если сеть имеет n узлов, это можно выразить как:

${\displaystyle N=2^{m}}$

где m - количество битов, необходимых для маркировки узлы в сети. Итак, если в сети 4 узла, для представления всех узлов в сети необходимы 2 бита. сеть. Сеть построена путем соединения узлов, которые отличаются только на один бит в своих двоичный представление. Это обычно называется двоичной маркировкой. Объединенная сеть трехмерного гиперкуба будет представлять собой куб с 8 узлами и 12 края. Сеть гиперкуба 4D может быть создана путем дублирования двух 3D сетей, и добавив старший бит. Новый добавленный бит должен быть «0» для одного трехмерного гиперкуба и «1» для другого трехмерного гиперкуба. Углы соответствующего однобита изменены MSB связаны для создания сети гиперкуба более высокого уровня. Этот метод может использоваться для построения любого гиперкуба, представленного m-битами, с (m-1) -битным представленным гиперкубом.

Маршрутизация E-Cube^[4]

Метод маршрутизации для сети гиперкубов называется маршрутизацией E-Cube. Расстояние между двумя узлами в сети можно определить как Вес Хэмминга из (количество единиц в) XOR -операция между соответствующими двоичными метками.

Расстояние между Узлом 1 (представленным как «01») и Узлом 2 (представленным как «10») в сети определяется следующим образом:

(${\displaystyle Hamming\_weight(01\bigoplus 10)=Hamming\_weight(11)=2}$

Маршрутизация E-Cube - это статическая маршрутизация метод, использующий XY-маршрутизацию алгоритм. Это обычно называют Детерминированный, Размер Заказал Маршрутизация модель. Маршрутизация E-Cube работает путем прохождения сети в k^th размерность, где k - младший значащий ненулевой бит в результате вычисления расстояния.

Например, пусть метка отправителя будет «00», а метка получателя - «11». Итак, расстояние между ними равно 11, а наименее значимый ненулевой бит - это LSB немного. Выбор пути для «0» или «1» определяется алгоритмом маршрутизации XY.

Метрики^[2]

Для оценки эффективности сетевого соединения гиперкуба по сравнению с другими топологиями сети используются разные показатели производительности.

Степень

Это определяет количество узлов, непосредственно примыкающих к конкретному узлу. Эти узлы должны быть непосредственными соседями. В случае гиперкуба степень равна m.

Диаметр

Это определяет максимальное количество узлов, через которые сообщение должно пройти на пути от источника к месту назначения. Это в основном дает нам задержку при передаче сообщения по сети. В случае гиперкуба диаметр равен m.

Среднее расстояние

Расстояние между двумя узлами, определяемое количеством переходов на кратчайшем пути между двумя конкретными узлами. Это дается формулой -

${\displaystyle d_{a}=\sum _{d=1}^{r}{(d.N_{d}) \over N-1}}$

В случае гиперкубов среднее расстояние выражается в м / 2.

Ширина бисекции

Это наименьшее количество проводов, которое вы должны разрезать, чтобы разделить сеть на две равные половины. Дается как 2^м-1 для гиперкубов.

использованная литература

1. Солихин, Ян. Основы параллельной компьютерной архитектуры. Книги Солихина. ISBN  978-0-9841630-0-7.
2. «Параллельные вычисления на гиперкубе».
3. «Межсетевые связи» (PDF).
4. «Механизмы маршрутизации для межсетевых соединений».