Новосибирский государственный университет Факультет информационных технологий

Словарь терминов в коллекции "Вычислительные системы"

Топология гиперкуба

Гиперкуб (hypercube) - данная топология представляет собой частный случай структуры решетки, когда по каждой размерности сетки имеется только два процессора (т.е. гиперкуб содержит 2_N процессоров при размерности N).

Топология гиперкуба достаточно широко распространена на практике при объединении параллельных процессоров. Линия, соединяющая два узла определяет одномерный гиперкуб. Квадрат, образованный четырьмя узлами - двумерный гиперкуб, а куб из восьми узлов - трехмерный гиперкуб и т.д. Из этого ряда следует алгоритм получения n-мерного гиперкуба: начать с (n-1)-мерного гиперкуба, сделать его идентичную копию, а затем добавить связи между каждым узлом исходного гиперкуба и одноименным узлом копии. Гиперкуб размерности n = log₂N имеет следующие характеристики: D = n; d = n; I = nN/2; B = N/2. Увеличение размерности гиперкуба на единицу ведет к удвоению числа его узлов, увеличению порядка узлов и диаметра сети на единицу.
Обмен сообщениями в гиперкубе базируется на двоичном представлении номеров узлов. Нумерация узлов производится так, что для любой пары смежных узлов двоичное представление номеров этих узлов отличается только в одной позиции. В силу сказанного, узлы 0010 и 0110 - соседи, а узлы 0110 и 0101 таковыми не являются.
Номера узлов являются основой маршрутизации сообщений в гиперкубе. Такие номера в n-мерном гиперкубе состоят из n битов, а пересылка сообщения из одного узла в другой выполняется за n шагов. На каждом шаге узел может либо сохранить сообщение и не пересылать его дальше до следующего шага, либо отправить его дальше по одной из линий. На шаге i узел, хранящий сообщение, сравнивает i-й бит своего собственного номера с i-м битом номера узла назначения. Если они совпадают, продвижение сообщения прекращается, если нет - сообщение передается вдоль линии i-гo измерения. Линией i-го измерения считается та, которая была добавлена на этапе построения i-мерного гиперкуба из двух (i-1)-мерных.
Создание гиперкуба при большом числе процессоров требует увеличения порядка узлов, что сопряжено с большими техническими проблемами. Компромиссное решение, несколько увеличивающее диаметр сети при сохранении базовой структуры, представляет собой куб из циклически соединенных узлов. Здесь порядок узла равен трем при любом размере сети.

Литература
• Цилькер Б.Я. Организация ЭВМ и систем: учебник для вузов / С.А. Орлов, Б.Я. Цилькер. - СПб.: Питер, 2011. - 688 с.

Ключевые термины, связанные с термином "топология гиперкуба":

1. Топология k-ичного n-куба

Ключевые термины:  статическая топология;   решетка;   размер сети;   число связей;   диаметр сети;   степень узла;   пропускная способность сети;   задержка сети;   связность сети;   ширина бисекции сети;   полоса бисекции сети;

Контекстный поиск: Задайте образец для поиска:
    

Федотова Ольга

НГУ ФИТ НГУ ИВТ СО РАН