Системы коммутации

15. Системы коммутации Существует большое число разнообразных способов соединений компонентов вычислительных систем [1]. Тип организации таких соединений зависит не только от требовании к их пропускной способности, но и от таких количественных характеристик ВС как число процессоров, модулей памяти, каналов ввода вывода, а также и от особенностей структурной организации самих ВС. Например, существенным является то каким компонентам необходимо связываться друг с другом (процессор-процессор, процессорпамять). Так для систем класса ОКМД основной задачей параллельных вычислений на множестве процессоров является параллельная доставка данных (разных операндов) из общей памяти в локальную память каждого процессора. Чтобы связь между множеством процессоров и памятью была гибкой и достаточно быстродействующей, необходимо иметь большое число параллельно функционирующих линий связи со сложной системой их коммутации (СК). Как правило, для такого рода ВС прибегают к созданию специализированных СК на основе так называемых многоступенчатых коммутаторов, соответствующих их конкретному назначению. С одной стороны это приводит к значительному удорожанию ВС, а с другой стороны к обеспечению высокой пропускной способности СК. Для систем класса МКМД важным вопросом при построении СК является то, как организована память таких ВС, т.е. это организация с общей памятью или с распределѐнной памятью. Так для систем с общей памятью, обладающей физически единым адресным пространством, и являющейся разделяемым ресурсом ВС, СК строится, как правило, с использованием одной или нескольких шин и соответствующих коммутаторов, встроенных в процессоры и модули памяти, а сам обмен данными осуществляется с помощью выполнения команд «записи» «считывания».Для систем с распределѐнной памятью характерно то, что обмен данными осуществляется по схеме «обмен сообщениями» и, следовательно, существует огромное число видов построения СК, начиная от применения общей шины, одноступенчатых и многоступенчатых коммутаторов и заканчивая построением сложных сетей коммутации, таких, как например, гиперкуб большой размерности. Компоненты системы коммутации бывают 2-х типов: 1) активные (контроллеры шин, адаптеры, коммутаторы) 2) пассивные (магистрали, шины) Таким образом, рассматривая СК и абстрагируясь от типа ВС, можно сделать вывод о том, что основными компонентами СК являются активные компоненты. (Коммутаторы иногда являются пассивными). Коммутаторы могут быть реализованы с одной стороны как распределѐнные, например в системах с общей памятью, так и сосредоточенные, например в системах ОКМД, а с другой стороны как одноступенчатые, так и многоступенчатые. 82 Пропускную способность системы чаще всего определяют пассивные компоненты. 15.1 Шинные структуры Шинной структурой (ШС) называется такая организация системы коммутации, при которой для передачи данных между компонентами вычислительной системы используются одна или несколько общих (а в частном случае и индивидуальных) информационных магистралей. Самым простым случаем организации ШС является одношинная структура - общая шина, к которой подсоединены компоненты ВС, как это показано на рис. 15.1. P1 PBB P2 Pn П1 Пm Рис. 15.1 Структура «общая шина» В этой ВС - n процессоров P, m модулей памяти П и процессор вводавывода PВВ объединены общей шиной ОШ. Системы коммутации, использующие шинные структуры, могут применяться как для ВС с общей памятью, так и для ВС с распределѐнной памятью. Сами шины представляют собой пассивные элементы, а управлением передачей данных по шинам занимаются либо передающие и принимающие устройства компонент ВС, либо специализированное устройство управления шиной, называемое контроллером шины, при этом часть функций управления остаѐтся за передающими и принимающими устройствами (адаптеры шины). Основной трудностью при организации обмена данными между устройствами системы по одной общей магистрали является состязание за право использования общего ресурса - самой шины, которое приводит к возникновению конфликтов при одновременном запросе на передачу данных от нескольких устройств системы. Для разрешения конфликтов 83 используются такие приѐмы, как назначение каждому устройству уникального приоритета, постановка запросов в очередь с различными дисциплинами обслуживания, например. FIFO - "первый пришел, первый вышел", соединение устройств в цепь или в кольцо и, следовательно, физической фиксацией их взаимных приоритетов. Следует отметить однако, что возможна организация логического кольца при физическом подсоединении каждого устройства к общей шине. Как правило, информационная магистраль (шина) состоит из 3-х групп линий - линии управления, линии адреса (шина адреса) и линии данных (шина данных). При этом в большинстве случаев достаточно 4-х линий управления: линия запроса шины (ЗШ), линия занятости шины (зан. Ш), линия предоставления шины (ПШ) и линия готовности получателя (ГП). Число линий шины данных (ШД) и шины адреса (ША) определяется техническими характеристиками ВС: числом параллельно передаваемых разрядов информационного слова, размером адресного пространства памяти, числом процессоров и другими компонентами системы. На следующем рис. 15.2 представлена типичная схема организации системы коммутации "общая шина". P1 P2 Pn П1 PBB Пm Рис.15.2 Схема организации системы коммутации "общая шина" Иногда адреса и данные передаются по одной шине с разделением времени. В этом случае необходим специальный механизм их различения. 84 Например, вводится ещѐ одна линия управления. Функционирование системы коммутации "общая шина" заключается в том, что по заявкам от устройств, желающих передать данные тому или иному адресату, арбитр шины (специальное устройство, входящее в состав контроллера шины при централизованном еѐ управлении) в соответствии с принятой дисциплиной обслуживания при незанятой шине, предоставляет еѐ одному из отправителей данных. После этого отправитель должен установить связь с получателем, который распознаѐт свой адрес, установленный отправителем на шине адреса. В случае готовности получателя к приѐму данных (о чѐм он сообщает по линии готовности), отправитель выставляет данные на шине данных, которые и принимаются адресатом. После завершения обмена шина освобождается. Основным недостатком СК с общей шиной является то, что она является общим критическим ресурсом как с точки зрения пропускной способности, так и надѐжности СК. В случае, когда пропускной способности одной шины не хватает для организации обменов данными между компонентами ВС или требуется более высокая надѐжность системы коммутации, может быть введено ещѐ несколько шин. В этом случае каждая компонента должна иметь в своѐм составе коммутатор, позволяющий соединять передающее и принимающее устройства по одной из свободных шин системы (см. рис. ниже). 85 P1 PBB P2 Pn П1 Пm Рис.15.3 Схема организации системы с несколькими шинами В качестве примера можно привести организацию многошинной системы коммутации многопроцессорного вычислительного комплекса (МВК) "Эльбрус-2" (см. рис. ниже). Данный комплекс относится к классу МКМД с общей памятью. В его состав может входить до 10 центральных процессоров (P), до 4-х периферийных процессоров (PP) и 8 секций общей памяти (СП). 86 P1 P10 PP1 PP4 Рис.15.4 Многошинная система коммутации МВК "Эльбрус-2" Таким образом, каждый из 14 процессоров имеет в своѐм составе коммутатор на 8 направлений, а каждая секция памяти имеет коммутатор на 14 направлений. При этом система коммутации считается 8-мишинной с распределѐнным однокаскадным коммутатором. Иногда такую СК называют полносвязной. Как видно из представленных на рисунках структурных схем, рассматривались ВС с общей памятью. Для систем с распределѐнной памятью организация СК с шинной структурой с точки зрения построения физического канала принципиально не отличается от такой же СК для систем с общей памятью. Следует однако напомнить, что сам механизм обмена данными в системах с распределѐнной памятью основан на принципе обмена сообщениями, а в качестве компоненты ВС выступает процессор (или группа 87 процессоров) со своей локальной памятью, т.е. вычислительный модуль (ВМ). В качестве примера приведѐм два способа организации полносвязной СК для ВС с распределѐнной памятью: с распределѐнным коммутатором коммутация каждый с каждым (см. рис. ниже) Рис.15.5 Полносвязная СК с распределѐнным коммутатором (коммутация каждый с каждым) и центральным коммутатором (ЦК) - соединение типа "звезда" (см. рис. ниже). Рис.15.6 Полносвязная СК с центральным коммутатором (соединение типа "звезда") 88 Первый случай более надѐжен, т.к. отсутствует общий ресурс, а второй случай более простой, но менее надѐжен из-за присутствия общего ресурса - ЦК. Рассматривая шинные структуры, приведѐнные выше, можно сделать один главный вывод - при обеспечении высокой пропускной способности СК вычислительной системы с большим числом процессоров приходится вводить большое число коммутируемых линий связи и сложные коммутаторы, что резко усложняет и повышает стоимость ВС. Поэтому шинные структуры применяются в ВС с небольшим числом процессоров, обычно не более 16-ти. 15.2 Матричные структуры Системы коммутации матричных структур основаны на использовании множества распределенных одноступенчатых коммутаторов в ВС с высокой степенью распараллельности и с большим числом однородных процессоров. Исторически матричные структуры впервые были использованы в матричных процессорах, относящихся к классу ОКМД. Основное преимущество матричных структур – однородность элементов обработки и регулярность системы коммутации, что дает существенный экономический эффект при реализации матричных процессоров на кристалле. Применение матричных процессоров обычно связано с решением задач цифровой обработки сигналов и изображений и поэтому они рассматриваются как специализированные процессоры в составе мощной высокопроизводительной системы. Базовое соединение элементов процессорной матрицы происходит так, как это показано на рис. 15.7. Иногда такое соединение называют 2-мерный тор. Каждый узел данной матрицы представляет собой процессор со своей локальной памятью и коммутатором на 4 направления. Коммутатор может быть как встроенным в процессор, так и внешним по отношению к процессору и может быть реализован в виде специального связного процессора. В матричных структурах обмен данными между соседними процессорами происходит с большой скоростью, которая обуславливается однокаскадным их соединением. Однако, соединение между любыми двумя удалѐнными процессорами матрицы требует большего числа каскадов по каналу от источника к приѐмнику. В редких случаях, когда требуется высокая пропускная способность СК, применяется так называемая сильносвязная матрица процессоров с магистральным принципом обмена данными, которая изображена на рис. 15.9. Преимуществом, хотя и дорогостоящим, такой структуры является возможность организации обмена между любыми двумя процессорами, в том числе и в разных строках и столбцах, за один цикл магистрального обмена. 89 Рис 15.7 2-мерный тор. Структура элемента матрицы показана ниже, на рис. 15.8. ПР Локальная память магистраль для обмена данными с внешним миром и получения команд Коммутатор каналы для осуществления внутриматричного обмена Рис.15.8 Структура элемента матрицы. Как было отмечено выше, матричные структуры по своей сущности являются специализированными. Но ещѐ большая специализация достигается в систолических структурах, в которых соединение между процессорами выбираются исходя из особенностей параллельного представления конкретной прикладной задачи, для которой и проектируется данная система обработки данных. (Термин «систолический» заимствован у физиологов. Им обозначается ритмичное сокращение сердца, необходимое для нормальной циркуляции крови в организме животного). Узел систолической структуры, содержащий процессор, ведѐт циклическую обработку данных перед тем как 90 циклически же передать результат обработки одному или нескольким соседям в соответствии с программой решения заданной прикладной задачи. Рис.15.9 Магистральная матрица. Таким образом, матричные структуры, применяемые, как правило, в системах ОКМД, дают высокие показатели производительности на узком классе задач. Расширение этого класса требует усовершенствования матричных структур. Главной особенностью такого усовершенствования является их применение в ВС, строящихся по принципу МКМД. Например, российская многопроцессорная система МВС-1000 разработана как масштабируемый (легко расширяемый) массив процессорных узлов. Каждый узел содержит процессор с локальной памятью и коммуникационный процессор, имеющий 4 внешних канала (линка). Процессорные узлы связаны между собой по оригинальной схеме, сходной с топологией двумерного тора, представленной на рис. 15.10. Данная структура представляет собой модуль системы, состоящий из 16 узлов. При этом 4 угловых узла матрицы соединяются через линки по диагонали попарно. Оставшиеся 12 линков предназначаются для подсоединения внешних устройств – 4 угловых линка и 8 для соединения с себе подобными модулями Характерной особенностью такого соединения в структурном модуле 4х4 является то, что максимальная длина пути (число каскадов) от одного узла матрицы к другому равна трѐм. 91 для внешних связей для связи с аналогичной матрицей (расширение матрицы) Рис.15.10 Структура МВС-1000. В качестве примера матричной структуры можно также привести кластер МГУ, структура которого показана на следующем рис. На схеме показан вывод для расширения матрицы. В каждом узле – 2 процессора Pentium III с общей локальной памятью. Рис.15.11 Кластер МГУ. 15.3 Кубические структуры Кубические структуры предназначены для организации ВС с РП, состоящих из большого числа узлов. Они основаны на гиперкубах, организуемых либо в булевском, либо в евклидовом пространстве. В случае булевского пространства n-мерный куб образуется как декартово пространство кубов меньшей степени. Таким образом, гиперкуб nго порядка представляет собой два гиперкуба (n-1)-го порядка, соединенных одноименными вершинами. Рассмотрим вычислительную систему состоящую из большого числа вычислительных модулей (ВМ) (процессор со своей локальной памятью). На рис. 15. 12 показана условная схема ВС на примере гипер-куба 4 порядка. В 92 этой схеме ВМ располагаются в вершинах многомерного куба и соединяются с соседями ребрами этого куба. Для 4-х мерного куба ВС состоит из 16 ВМ (16 вершин), для 12 –и мерного куба из 4096 ВМ (4096 вершин). Соответственно, в первом случае из вершины исходит 4 ребра, во втором – 12 рѐбер. Очевидно, что К- мерный куб может включать 2 в степени К ВМ, а максимальный длины путь прохождения сообщений между двумя любыми ВМ составит К рѐбер. Рассмотрим более подробно принцип коммутации в схеме соединений типа гипер-куб. Каждый куб следующей размерности строится на основе двух кубов предыдущей размерности соединением двух одноимѐнных вершин куба предыдущей размерности. Таким образом, каждый раз увеличивая размерность куба на единицу, увеличивается число вершин в 2 раза. Поэтому такой куб называют «булев-К-куб». Булев-К-куб представляет собой очень удобную структуру по следующим причинам. Во-первых, если ВМ располагаются в вершинах 12 –куба, то ни один вычислительный модуль не отстаѐт более чем на 12 рѐбер куба (т.е. линий связи) ни от какого другого ВМ, что значительно облегчает задачу создания эффективных коммуникаций в системе. Гиперкубы: 0го порядка: 1 узел; 1-го порядка: 2 узла; 2-го порядка: 4 узла; 3-го порядка: 8 узла; 4-го порядка: 16 узлов; 0111 0000 и т.д. Рис. 15.12 Принцип образования К-куба 93 Во-вторых, структура соединений в К-кубе хорошо согласуется с двоичной логикой ЭВМ. Как было отмечено выше, каждый куб в К-кубе имеет два подкуба предыдущей размерности. Если их обозначить значениями булевой переменной 0 и 1, то в результате такого представления каждая вершина имеет единственный, отличный от других, двоичный адрес разрядности К. В-третьих, одно из ценных свойств К-куба состоит в том, что между любой парой ВМ есть сразу несколько с одинаковым числом рѐбер путей коммутации. Например, если мы имеем дело со структурой 12-куб, то каждая вершина имеет 12 разрядный адрес, первый разряд которого указывает какой из двух 11-кубов содержит данную вершину, второй разряд указывает на соответствующий 10-куб и т.д. до последнего разряда адреса. Этими двоичными адресами можно воспользоваться для того, чтобы направлять сообщение в сеть адресуясь к приѐмнику. Получив сообщение, маршрутизатор источника анализирует старший разряд адреса для определения подкуба и, если канал свободен, отправляет сообщение по этому каналу. Если канал занят, маршрутизатор анализирует следующий по старшинству разряд и так до тех пор пока не обнаруживается свободный канал. Так действуют все маршрутизаторы вершин куба по пути от источника к приѐмнику. СМ1- первая система, имеющая процессор кубической архитектуры 12-й 12 степени, состоящий из 4096 узлов (2 = 4096). Это система с распределенной памятью. Сколько степеней, столько должно быть и коммутационных выводов у каждого процессора. В этой машине впервые был использован router на 12 выходов. ВС такого типа уже имеет сетевую архитектуру. Одним из преимуществ такой схемы коммутации является простота адресации: каждому узлу соответствует определенный 12-разрядный адрес. Каждый разряд соответствует подкубу по старшинству. При передаче данных существует большое количество альтернативных путей. Вычислительный модуль системы показан на следующем рис. 15.13. Р Маршрутизатор ... 1 2 12 Рис.15.13 Вычислительный модуль системы СМ1. К кубическим структурам тесно примыкают многомерные торы (в одномерном случае это кольцевая структура, в двумерном – матрица, которые были рассмотрены выше). Торы образуются из n-мерных кубов 94 путѐм введения рѐбер между соответствующими вершинами граничных областей по некоторым или всем координатам, как это показано на рис. 15.14. Адресация происходит по координатам. Например, сначала по Y, потом по X и в конце по Z. X эти связи образуют тор Y Z Cray T3e/900 serial Number 6702 3-х мерный тор Рис.15.14 Трѐхмерный тор Используется принцип коммутации каналов. Обычно шина двунаправленная. Для того, чтобы уменьшить значение максимального числа каскадов, соединяющих любые два узла тора, используется так называемое соединения узлов с чередованием. (Если узлов много, то чередование через одного) Соединение узлов с чередованием Рис.15.15 Соединение с чередованием