Новосибирский государственный университетФакультет информационных технологий |
Сеть Бетчера - сортирующая сеть размером O(nlog2n) и глубиной O(log2n), где n количество элементов для сортировки.
Баньян-топология относится к блокирующим, то есть может приводить к конфликтам, если два сообщения пытаются выйти на один и тот же выход базовый коммутирующий элемент (БКЭ). В случае коллизии одно сообщение передается, а другое - отбрасывается. Однако если сообщения, поступающие на входы такой сети, упорядочены определенным образом, то конфликтов не происходит. В частности, баньян-сети n×n в состоянии передавать одновременно вплоть до n пакетов (при условии, что они предназначены разным получателям), если адреса назначения в пакетах, поступающих на входы сети с возрастающими номерами, также упорядочены в порядке возрастания. Такое упорядочение можно реализовать, если перед баньян-сетью поместить так называемую сортирующую сеть - сеть Бэтчера.
Сеть Бэтчера также состоит из стандартных БКЭ, но они работают несколько по-иному, чем аналогичные элементы баньян-сети. При получении двух пакетов коммутирующий элемент сравнивает хранящиеся в них адреса назначения и направляет пакет с большим адресом по стрелке, а пакет с меньшим адресом - в противоположном направлении. Если имеется только один пакет, то он посылается в направлении, противоположном указанию стрелки. Данный алгоритм иллюстрирует рисунок (см. дополнительно файл .pdf), в левой части которого показан порядок сортировки пакетов, одновременно направляемых на 4 выходных терминала.
С ростом числа входов n количество БКЭ в сети растет в соответствии с зависимостью nlog2n. При получении k сообщений сеть Бэтчера упорядочивает их в порядке возрастания адресов назначения и выдает на свои первые k выходов. Если теперь выходы сети Бэтчера по схеме полного тасования соединить с входами баньян-сети типа, то образовавшаяся сеть становится неблокирующей. Это относится ко всем вариантам баньян-сетей.
Ключевые термины: динамическая топология; блокирующая топология; неблокирующая топология; многоступенчатая сеть; топология «баньян»; тасование;
Федотова Ольга |
НГУ ФИТ НГУ ИВТ СО РАН |