Шинная топология

Блокирующие и неблокирующие многоуровневые сети

Минимальным требованием к сети с коммутацией является поддержка соединения любого входа с любым выходом. Для этого в сети с n входами и n выходами система ключей обязана предоставить n! вариантов коммутации входов и выходов (перестановок – permutations). Проблема усложняется, когда сеть должна обеспечивать одновременную передачу данных между многими парами терминальных узлов (multicast), причем так, чтобы не возникали конфликты (блокировки) из-за передачи данных через одни и те же коммутирующие элементы в одно и то же время. Подобные топологии должны поддерживать nⁿ перестановок. С этих позиций все топологии СМС с коммутацией делятся на три типа: неблокирующие, неблокирующие с реконфигурацией и блокирующие.

В неблокирующих сетях обеспечивается соединение между любыми пара-ми входных и выходных терминалов без перенастройки коммутирующих эле- ментов сети. В рамках этой группы различают сети строго неблокирующие (strictly non-blocking) и неблокирующие в широком смысле (wide sense non-blocking). В строго неблокирующих сетях возникновение блокировок принци-пиально невозможно в силу примененной топологии. К таким относятся мат-ричная сеть и сеть Клоша. Неблокирующими в широком смысле называются топологии, в которых конфликты при любых соединениях не возникают только при соблюдении определенного алгоритма маршрутизации.

В неблокирующих сетях с реконфигурацией также возможна реализация соединения между произвольными входными и выходными терминалами, но для этого необходимо изменить настройку коммутаторов сети и маршрут связи между соединенными терминалами. Примерами таких сетей служат сети Бенеша, Бэтчера, «Мемфис» и др.

В блокирующих сетях, если какое-либо соединение уже установлено, это может стать причиной невозможности установления других соединений. К блокирующим относятся сети «Баньян», «Омега», n-куб и др.

Сети с шинной архитектурой – наиболее простой и дешевый вид дина- мических сетей. При одношинной топологии, показанной на рис. 6.1, а,все уз- лы имеют порядок 1 (d = 1) и подключены к одной совместно используемой шине. В каждый момент времени обмен сообщениями может вести только одна пара узлов, то есть на период передачи сообщения шину можно рассматривать как сеть, состоящую из двух узлов, в силу чего ее диаметр всегда равен 1 (D = 1). Ширина бисекции (В) также равна единице, поскольку топология до- пускает одновременную передачу только одного сообщения. Одношинная кон- фигурация полезна, когда число узлов невелико, то есть когда трафик шины мал по сравнению с ее пропускной способностью. Одношинная архитектура ис-пользуется для объединения нескольких узлов в группу (кластер), после чего из таких кластеров образуют сеть на базе других видов топологии.

Рис. 6.1. Шинная топология: а – с одной шиной; б – со многими шинами

Многошинная топология предполагает наличие n независимых шин и подключение узлов к каждой из этих шин (рис. 6.1, б), что позволяет вести одновременную пересылку сообщений между n парами узлов. Такая топология вполне пригодна для высокопроизводительных ВС. Диаметр сети по-прежнему равен 1, в то время как пропускная способность возрастает пропорционально числу шин. По сравнению с одношинной архитектурой управление сетью с несколькими шинами сложнее из-за необходимости предотвращения конфлик-тов, возникающих, когда в парах узлов, обменивающихся по разным шинам, присутствует общий узел. Кроме того, с увеличением порядка узлов сложнее становится их техническая реализация.

3. Топология перекрестной коммутации (“кроссбар”)

Топология перекрестной коммутации мультипроцессорной системы (cross-bar switch system) на основе матричного (координатного) коммутатора представ-ляет собой классический пример одноступенчатой динамической сети. Кроссбар n × m (рис. 6.2) представляет собой коммутатор, способный соединить n входных и m выходных терминальных узлов с уровнем параллелизма, равным min(n, m). Главное достоинство рассматриваемой топологии состоит в том, что сеть полу-чается неблокирующей и обеспечивает меньшую задержку в передаче сообще-ний по сравнению с другими топологиями, поскольку любой путь содержит только один ключ. Тем не менее, из-за того, что число ключей в сети равно n × m, использование кроссбара в больших сетях становится непрактичным, хотя это достаточно хороший выбор для малых сетей. Для больших неблокирующих се- тей можно предложить иные топологии, требующие существенно меньшего ко-личества ключей.

Рис. 6.2. Матричный коммутатор n × m

В случае n = m имеем «полный кроссбар». Полный кроссбар на n входов и n выходов содержит n ²ключей. Диаметр сети равен 1, ширина бисекции – n /2. Этот вариант часто используется в сетях с древовидной топологией для объеди-нения узлов нижнего уровня, роль которых играют небольшие группы (кластеры) процессоров и модулей памяти.

Современные коммерчески доступные матричные коммутаторы способны соединять до 256 устройств. Топология используется для организации соедине-ний в некоторых серийно выпускаемых вычислительных системах, например в Fujitsu VPP 500 224 × 224.

Дата добавления: 2014-01-20