СУЭБ ИВТ СО РАН

А.М.Федотов

Словарные статьи в коллекции: (public_cat = Thesaurus of Information Technology: Dictionary Articles )

Топология Бенеша

Топология Бенеша относится к типу неблокирующих сетей с реконфигурацией. Это означает, что возможна такая установка коммутаторов сети, при которой одновременная передача сообщений между множеством пар входных и выходных узлов будет происходить без взаимного блокирования. Реконфигурирование предполагает разрыв и переустановку всех соединений.

В качестве коммутаторов в сетях Бенеша используются β-элементы. В сети n×n общее количество базовых коммутирующих элементов (БКЭ) равно nlog₂n. Ввиду того, что эти сети не обладают свойством самомаршрутизации, то есть для коммутации маршрута недостаточно информации, содержащейся во входном пакете, для определения состояния всех β-элементов необходим специальный контроллер. Сущность реконфигурирования и достигаемый при этом эффект иллюстрирует рисунок (см. дополнительно файл .pdf). На рисунке показана топология сети Бенеша, обеспечивающая одновременную пересылку трех сообщений: с входа 0₁₀ (000₂) на выход 4₁₀ (100₂), входа 1₁₀ (001₂) на выход 0₁₀ (000₂) и входа 2₁₀ (010₂) на выход 2₁₀ (010₂). Как видно, блокировки сообщений не происходит. При попытке одновременно с этим передать пакет с входа 3₁₀ (011₂) на выход 1₁₀ (001₂) передача блокируется. Однако блокировки можно избежать, если изменить топологию сети. Благодаря изменению трактов прохождения всех четырех сообщений конфликт не возникает.
Все тракты передачи сообщений должны формироваться одновременно. Если новый тракт формируется при уже функционирующих других трактах, неблокируемость без реконфигурирования «старых» трактов не гарантируется.
Сеть Бенеша может рассматриваться как частный случай сети Клоза, для которой выполняется условие m ≥ n. В этом случае, как доказал Бенеш, сеть Клоза можно отнести к неблокирующим сетям с реконфигурацией.
С добавлением к такой сети дополнительной ступени БКЭ число возможных маршрутов удваивается. Дополнительные пути позволяют изменять трафик сообщения с целью устранения конфликтов. Сеть Бенеша с n входами и n выходами имеет симметричную структуру, в каждой половине которой (верхней и нижней) между входными и выходными БКЭ расположена такая же сеть Бенеша, но с n/2 входами и n/2 выходами.

Литература
• Lenfant J. «Parallel Permutations of Data: A Benes Network Control Algorithms for Frequently Used Permutations», IEEE Transactions on Computers, C-27, № 7, 1978, 637-647.
• Nassimi D. «A Self-Routing Benes Network and Parallel Permutation Algorithms», IEEE Transactions on Computers, C-30, № 5, 1981, pp. 332-340.
• Цилькер Б.Я. Организация ЭВМ и систем: учебник для вузов / С.А. Орлов, Б.Я. Цилькер. - СПб.: Питер, 2011. - 688 с.

Ключевые термины, связанные с термином : "Топология Бенеша":

1. Динамическая топология [ru]
2. Многоступенчатая сеть [ru]
3. Неблокирующая топология [ru]
4. Реконфигурируемая топология [ru]
5. Топология Клоза [ru]

Литература

Основная

1. Орлов С. А., Цилькер Б. Я. Организация ЭВМ и систем: Учебник для вузов. 2-е изд. — СПб.: Питер, 2011. — 688 с.: ил. - ISBN 978-5-49807-862-5.

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

© 2013-2024, Евразийский национальный университет им. Л.Н.Гумилева, Астана © 2007-2024, Новосибирский государственный университет, Новосибирск © 1998-2024, Институт вычислительных технологий СО РАН, Новосибирск © 1998-2024, Федотов А.М.

ФИТ НГУ       НГУ ЕНУ им.Гумилева ИВТ СО РАН