Новосибирский государственный университет

Факультет информационных технологий

ICT SBRAS

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

Сеть Бэтчера-Баньяна

Синонимы: сеть бэтчера-баньяна; сеть бэтчера;

Сеть Бетчера - сортирующая сеть размером O(nlog2n) и глубиной O(log2n), где n количество элементов для сортировки.

Баньян-топология относится к блокирующим, то есть может приводить к конфликтам, если два сообщения пытаются выйти на один и тот же выход базовый коммутирующий элемент (БКЭ). В случае коллизии одно сообщение передается, а другое - отбрасывается. Однако если сообщения, поступающие на входы такой сети, упорядочены определенным образом, то конфликтов не происходит. В частности, баньян-сети n×n в состоянии передавать одновременно вплоть до n пакетов (при условии, что они предназначены разным получателям), если адреса назначения в пакетах, поступающих на входы сети с возрастающими номерами, также упорядочены в порядке возрастания. Такое упорядочение можно реализовать, если перед баньян-сетью поместить так называемую сортирующую сеть - сеть Бэтчера.
Сеть Бэтчера также состоит из стандартных БКЭ, но они работают несколько по-иному, чем аналогичные элементы баньян-сети. При получении двух пакетов коммутирующий элемент сравнивает хранящиеся в них адреса назначения и направляет пакет с большим адресом по стрелке, а пакет с меньшим адресом - в противоположном направлении. Если имеется только один пакет, то он посылается в направлении, противоположном указанию стрелки. Данный алгоритм иллюстрирует рисунок (см. дополнительно файл .pdf), в левой части которого показан порядок сортировки пакетов, одновременно направляемых на 4 выходных терминала.
С ростом числа входов n количество БКЭ в сети растет в соответствии с зависимостью nlog2n. При получении k сообщений сеть Бэтчера упорядочивает их в порядке возрастания адресов назначения и выдает на свои первые k выходов. Если теперь выходы сети Бэтчера по схеме полного тасования соединить с входами баньян-сети типа, то образовавшаяся сеть становится неблокирующей. Это относится ко всем вариантам баньян-сетей.


См. дополнительно: Сеть Бэтчера-Баньяна

Ключевые термины, связанные с термином "сеть бэтчера-баньяна":

  1. Неблокирующая топология
  2. Реконфигурируемая топология

Ключевые термины:  динамическая топология;   блокирующая топология;   неблокирующая топология;   многоступенчатая сеть;   топология «баньян»;   тасование;


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

|Список основных тем курса|
   
Федотова Ольга
[SBRAS]

НГУ
ФИТ НГУ
ИВТ СО РАН
© 2012-2024, Новосибирский государственный университет, Новосибирск
© 2004-2024, Институт вычислительных технологий СО РАН, Новосибирск
© 2004-2024, Федотов А.М.
    Дата последней модификации: 14.08.2013