Лекция РИС 2018 Динамические топологии. Лекция по дисциплине Распределенные информационные системы Раздел
 Скачать 0.57 Mb.
|
|
Кафедра «Самолетостроение»" ИНСТИТУТ АВИАЦИОННЫХ ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ Ульяновск 2018/19 уч.год Два чувства дивно близки нам - В них обретает сердце пищу: Любовь к родному пепелищу, Любовь к отеческим гробам. А.С. Пушкин Алекса́ндр Серге́евич Пу́шкин (1799 - 1837) - русский поэт, драматург и прозаик, критик и теоретик литературы, историк, публицист; один из самых авторитетных литературных деятелей XIX века. *** Лекция по дисциплине «Распределенные информационные системы» Раздел: Топологии распределенных вычислительных систем Тема: Динамические топологии Введение В динамической топологии сети соединение узлов обеспечивается электронными ключами, управляя которыми можно менять топологию сети. В узлах динамических сетей располагаются устрой-ства, обменивающиеся сообщениями (прцессоры, банки памяти, устройства ввода/вывода и др.). Они подключа-ются к входам и выходам этой сети. Выделяют два класса сетей с динамической топо-логией; - сети на основе шины; - сети на основе коммутаторов. Рассмотрим топологии на основе шины. . Одношинная топологияОдношинная топология Сети на основе шины — наиболее простой и деше-вый вид динамических сетей. Рис. 1 иллюстрирует систему на базе одношинной топологии. Рис. 1. Пример системы с одной шиной Система состоит из k процессоров, каждый из кото-рых подключен к общей шине. Процессоры взаимодей-ствуют через общую память. Узлы при одношинной топологии имеют степень d = 1. Как недостаток отмечается, что одношинная техноло-гия допускает одновременную передачу только одного сообщения. Может быть полезной, когда число узлов невелико, то есть когда трафик шины мал по сравнению с ее пропускной способностью. Размер подобных систем изменяется в диапазоне от 2 до 50 процессоров (ядер). Используется для объеди-нения нескольких узлов в группу (кластер), Из класте-ров образуют сеть на базе других видов топологии. Многошинная топологияМногошинная топология Многошинная топология является развитием идеи одношинной топологии. Используется для объединения множества процес-соров и множества модулей памяти с помощью парал-лельных шин. Процессоры, как правило, подключаются к каждой из шин, а подключение модулей памяти производится по четырем схемам: - с подключением ко всем шинам; - с подключением к одной из шин; - с подключением к части шин; - с подключением по классам. Топология «Множественные шины с подключением банков памяти ко всем шинам» показана на рис. 2-а. Рис. 2-а. Множественные шины с подключением банков памяти ко всем шинам Топология «Множественные шины с подключением банков памяти к одной из шин» показана на рис. 2-б. Рис. 2-б. Множественные шины с подключением банков памяти к одной из шин Топология «Множественные шины с подключением банков памяти к части шин» показана на рис. 2-в. Рис. 2-б. Множественные шины с подключением банков памяти к части шин Топология «Множественные шины с подключением банков памяти по классам системы» показана на рис. 2-г. Рис. 2-г. Множественные шины с подключением банков памяти по классам системы Топология «Множественных шин с подключением к банкам памяти» используется в высокопроизводи-тельных ВС. Пропускная способность возрастает пропорционально числу шин. Управление сетью с несколькими шинами сложнее из-за необходимости предотвращения конфликтов. Кроме того, с увеличением степени узлов сложнее становится их техническая реализация. Блокирующие, неблокирующие иБлокирующие, неблокирующие и реконфигурируемые топологии В динамических сетях на основе коммутаторов тракты между терминальными узлами формируются с использованием коммутирующих устройств. Требованием к сети с коммутацией является под-держка соединения любого входа с любым выходом. Для этого в сети с n входами и n выходами система управле-ния обязана предоставить n! вариантов коммутации и поддерживать nn вариантов перестановок. С этих позиций все топологии сетей с коммутацией разделяются на три типа: блокирующие, неблокирующие и реконфигурируемые. Блокирующие сети В блокирующих сетях установление соединения между входом и выходом возможно не всегда, что связано с другим, уже установленным соединением. Для минимизации числа коммутаторов в сети жела-тельно создавать единственный путь между каждой парой вход - выход. Для уменьшения числа конфликтов и повышения отказоустойчивости в сети могут предусматриваться множественные обходхные пути. Такие блокирующие сети известны как сети с обходными путями. Неблокирующие сети В неблокирующих сетях любой входной порт может быть подключен к любому свободному выходу без влияния на существующие соединения. Такие сети, как правило, являются многоступенча-тыми. В многоступенчатых динамических сетях коммута-торы группируются в так называемые ступени коммутации. Наличие более чем одной ступени коммутации позволяет обеспечить множественность путей между любыми парами входов и выходов. Реконфигурируемые сети В реконфигурируемых сетях возможна такая уста-новка коммутаторов, при которой допустима одновре-менная передача сообщений без взаимного блокирова-ния сообщений. Для этого все тракты передачи должны формироваться одновременно. В реконфигурируемых сетях обеспечивается множе-ственность путей между каждой парой вход-выход. Сети данного типа используются для построения матричных ВС. Топология полносвязной коммутаци- онной матрицы «кроссбар» Топология полносвязной коммутационной мат-рицы (кроссбар) представляет собой пример односту-пенчатой динамической сети, в которой любой входной порт может быть связан с любым выходным портом. Коммутатор представляет собой матрицу, строки которой входы, а столбцы - выходы. На пересечении линий и столбцов находятся переключатели, которые замыкают соединение строки на столбец. Для управления переключателями используют контроллер, который управляет переключателями на основе информации об адресе назначения. Кроссбар n×l способен соединить n входных и l выходных процессоров, банков памяти и т. п. Обмен могут вести одновременно min(n,l) пар терминальных узлов. Конфликты при работе не возникают. Новое соединение может быть установлено для любых свободных входных и выходных портов. Достоинство топологии состоит том, что сеть полу-чается неблокируемой. Обеспечивается меньшая задержка в передаче сообщений. Рис. 3. Сеть кроссбар 8×8 На рис. 3 показано состояние кроссбара при одновременном соедине-нии каждого из 8 процессоров (ПР,) со своим банком памяти (БП). Показаны два возможных состояния переключающего элемента - это прямое соединение (рис. 3-а), и диагональное соединение (рис.3-б). Коммутирующие элементы сетей с динамической топологией Для изучения многоступенчатых топологий коммута-ции рассмотрим используемые в них типы коммутиру-ющих элементов. Ранее был рассмотрен кроссбар n×l со своими элементами коммутации. В дальнейшем будет использован базовый коммутирующий элемент (БКЭ). Сигналы управления для него формируются исходя из адресов узла-источ-ника и узла-получателя. Возможные состояния БКЭ показаны на рис. 3. Рис. 3 Состояния БКЭ: а – прямое; б – перекрестное; в – широк-вещательное с верхнего входа; г – широковещательное с нижнего входа Конструктивно базовые коммутирующие элементы достаточно просты, что позволяет реализовать их на базе интегральных микросхем. Многоступенчатые динамические сети Многоступенчатые динамические сети соединяют входные устройства с выходными посредством нескольких ступеней коммутации, построенных из базовых коммутирующих элементов (БКЭ). Количество ступеней и способ их соединения опреде-ляют возможности маршрутизации в сети. Многоступенчатые динамические сети МДС состоит из g ступеней G0-Gg-1. Kаждая ступень, скажем Gi, содержит wi коммутаторов. Таким образом, ступень Gi имеет pi входов и qi выходов. Рис. 5. Многоступенчатая сеть с n входами, l выходами и g ступенями6 а – общая структура; б – детельное представление ступени Gi Блокирующие многоступенчатые сети Среди блокирующих многоступенчатых сетей наиболь-шее распространение получили баньяноподобные (индийская смоковница) сети. В Баньян-сети возможен только единственный путь. На рис. 6 показаны несколько вариантов дельта-сетей. Представленные топологии различаются тем, какие функции маршрутизации использованы между ступенями сети и на ее входе. Эти функции указаны в верхней части каждой схемы. Отметим, что по отношению к произволь-ному трафику все сети обеспечивают эквивалентную производительность. Рис. 6. Примеры сетей класса Дельта размерности 16х 16 с топологией: а — базисной линии; б — баттерфляй; в — обобщенного куба; г — Омега Достоинством рассматриваемых схем является свойство самомаршрутизации. Чтобы доставить сооб-щение к узлу-получателю, используется адрес этого узла, содержащийся в заголовке пакета. Этот адрес не только определяет маршрут сообще-ния к нужному узлу, но и используется для управления прохождением сообщения по этому маршруту. Каждый БКЭ, куда попадает пакет, просматривает один бит адреса и в зависимости от его значения направляет сообщение на верхний или нижний выход. На примере сети «Омега» 8x8 показан процесс маршрутизации сообщения с входного терминала 210 (0102) на выходной терминал с номером 610 (1102). Старший бит адреса назначения управляет коммутато-рами нулевой ступени, средний бит — первой ступени, младший бит — второй ступени. Рассмотрим процесс блокирования для ситуации одновременной передачи с входного терминала 010 (0002) на выходной терминал 110 (0012) и с входного терминала 510 (1012) на выходной терминал 210 (0102). Аналогичная ситуация возникает в другом варианте дельта-сети при попытке одновременной передачи пакетов с входного терминала 110 (0012) на выходной терминал 510 (1012) и с входного терминала 310 (0112) на выходной терминал 410 (1002). Неблокирующие многоступенчатые сетиСеть Клоза содержит r1 кроссбаров во входной ступени, т кроссбаров в промежуточной ступени и r2 кроссбаров в выходной ступени. У каждого коммутатора входной ступени есть n1 входов и т выходов - по одному на каждый кроссбар промежуточной ступени. Коммутаторы промежуточной ступени имеют r1 входов по числу кроссбаров входной ступени и r2 выходов, что соответствует количеству переключателей в выходной ступени сети. Выходная ступень сети строится из кроссбаров с т входами и n2 выходами. Отсюда числа n1, n2, r1, r2 и т полностью определяют сеть. Число входов сети N = r1n1 а выходов — М = r2n2 Клоз доказал, что подобная сеть является неблоки-рующей, если количество кроссбаров в промежуточной ступени т удовлетворяет условию: т > n1 + n2 - 1. Если n1 = n2 = n, то матричные переключатели в промежуточ-ной ступени представляют собой «полный кроссбар» и критерий неблокируемости приобретает вид: т > 2n - 1. СПАСИБО ЗА ВНИМАНИЕ Задание на самостоятельную работу: - повторить учебный материал лекции. - планируется проведение автоматизированного контроля знаний обучаемых. |