Содержание к диссертации
Введение
Глава 1. Задачи обработки сообщений в параллельных системах 10
1.1. Архитектура современных параллельных и распределенных систем 10
1.2. Коммутационные особенности задач вМРР-системах 13
1.3. Архитектура коммутационной подсистемы параллельных и распределенных систем 20
1.4. Статические коммутационные подсистемы в МРР-системах 21
1.5. Процедура коммутации сообщений в МРР-системах 35
1.6. Выводы по главе 38
Глава 2. Параллельно-последовательные процедуры коммутации сообщений для МРР-систем 39
2.1. Содержательная характеристика задачи разработки процедуры коммутации сообщений 39
2.2. Параллельно-последовательная процедура коммутации 41
2.3. Параллельно-конвейерная процедура коммутации сообщений 44
2.4. Выводы по главе 47
Глава 3. Структура коммутаторов на основе предложенных процедур коммутации 49
3.1. Структурная схема параллельно-последовательного коммутатора 49
3.2. Пример работы параллельно-последовательного коммутатора 52
3.3. Структурная схема параллельно-конвейерного коммутатора 55
3.4. Пример работы параллельно-конвейерного коммутатора 58
3.5. Функциональная схема параллельно- последовательного коммутатора 60
3.6. Выводы по главе 95
Глава 4. Комплексная оценка разработанных процедур и коммутаторов на их основе 96
4.1. Аналитическая оценка аппаратной сложности коммутаторов 96
4.1.1. Аналитическая оценка аппаратной сложности последовательного и параллельно-последовательного коммутатора 96
4.1.2. Аналитическая оценка аппаратной сложности параллельно-конвейерного коммутатора 99
4.2. Аналитическая оценка пропускной способности разработанных коммутаторов 101
4.3. Экспериментальная оценка пропускной способности коммутаторов 107
4.4 Архитектура библиотеки классов моделирования коммутаторов 112
4.5. Q-схемы моделируемых коммутаторов 121
4.6. Выводы по главе 129
Заключение 131
Список литературы 133
- Статические коммутационные подсистемы в МРР-системах
- Параллельно-конвейерная процедура коммутации сообщений
- Структурная схема параллельно-конвейерного коммутатора
- Аналитическая оценка аппаратной сложности последовательного и параллельно-последовательного коммутатора
Введение к работе
Актуальность. Любая вычислительная система (будь то супер-ЭВМ или персональный компьютер) достигает своей наивысшей производительности благодаря использованию высокоскоростных элементов и параллельному выполнению операций. Возможность параллельной работы различных модулей является главным фактором увеличения производительности вычислительной системы (ВС),
Одной из отличительных особенностей современных ВС является наличие коммутационной подсистемы (КП), с помощью которой процессорные элементы (ПЭ) осуществляют обмен информацией, КП настолько важна для ВС, что многие характеристики ее производительности напрямую выражаются в терминах времени межпроцессорного обмена. Таким образом, для повышения производительности ВС необходимо решение задачи синтеза эффективной коммутационной подсистемы.
Объектом рассмотрения в диссертационной работе являются параллельные ВС с распределенной памятью (МРР-системы), подобные системам Cray ТЗЕ и Origin 2000. Задача синтеза эффективной КП стоит в МРР-системах весьма остро, так как решаемые ими проблемы характеризуются высокоинтенсивным межпроцессорным трафиком стохастического характера (нечеткая барьерная синхронизация, детектирование момента завершения коллективного вычисления, задачи математической физики, итерационные матричные задачи). В связи с тем, что в МРР-системах взаимодействие осуществляется только между соседними ПЭ, для передачи сообщений от одного ПЭ другому необходимо выполнить ряд коммутаций сообщений (передач через транзитные ПЭ). В ходе коммутации каждый ПЭ решает следующие задачи: 1) прием сообщений и их хранение в буферных блоках до
5 обработки; 2) обработка сообщений - определение направлений передачи; 3) выдача сообщений по соответствующим направлениям.
Отличительной особенностью коммутаторов МРР-систем является последовательное выполнение обработки транзитных сообщений, что резко ограничивает пропускную способность КП и класс задач, решаемых МРР-системами. Таким образом, актуальной задачей является разработка процедур коммутации и коммутаторов на их основе, обеспечивающих повышение пропускной способности КП.
Анализ особенностей процедуры обработки сообщений позволил выявить возможность повышения пропускной способности на основе выполнения параллельной обработки и выдачи подмножеств сообщений, которым соответствуют различные направления передачи. Для реализации параллельной обработки средства коммутации должны обеспечивать параллельное считывание сообщений, присутствующих на выходах различных буферных блоков (очередей), независимое формирование кодов направлений их передачи, анализ соотношения кодов направлений и выделение подмножеств сообщений, коды направлений передачи которых не совпадают. Указанные принципы были реализованы в двух процедурах коммутации сообщений, названных параллельно-последовательной процедурой коммутации (ППП) и параллельно-конвейерной процедурой коммутации (ПКП), и коммутаторах на их основе.
Целью диссертационной работы является повышение пропускной способности коммутационной подсистемы МРР-систем на основе разработки процедур коммутации и коммутаторов с параллельно-последовательным характером обработки транзитных сообщений.
Задачами диссертационной работы являются:
1. Исследование существующих процедур коммутации и коммутаторов в параллельных и распределенных системах.
Разработка процедуры коммутации, обеспечивающей параллельно-последовательный принцип обработки транзитных сообщений, и коммутатора на ее основе.
Проектирование процедуры коммутации, реализующей параллельно-конвейерный способ обработки транзитных сообщений, и коммутатора на ее основе.
Аналитическая оценка пропускной способности и аппаратной сложности разработанных коммутаторов.
Экспериментальное исследование динамических характеристик разработанных коммутаторов.
Методы исследования.
При решении поставленных задач использовались методы теории множеств, теории графов, теории вероятности и математической статастики, а также теории параллельных и распределенных систем. Экспериментальные исследования проводились на основе библиотеки классов имитационного моделирования и визуальной среды программирования, разработанных под руководством доц. Зотова И.В.
Научная новизна результатов диссертационной работы:
Разработаны процедуры коммутации транзитных сообщений и коммутаторы на их основе, позволяющие повысить пропускную способность коммутационной подсистемы МРР-систем на основе принципа параллельно-последовательной обработки.
Получены аналитические оценки пропускной способности и аппаратной сложности для разработанных коммутаторов (повышение пропускной способности не менее чем в 2 раза при 2-х кратном увеличении аппаратной сложности).
Исследованы зависимости пропускной способности коммутаторов от характеристик потока сообщений и параметров коммутатора (выявлено
7 увеличение пропускной способности при высоких интенсивностях потоков по сравнению с существующими аналогами в 3 раза).
4. Определены условия возникновения потерь сообщений для разных йнтенснвностей потоков и параметров коммутатора. Установлено отсутствие потерь сообщений при средних значениях йнтенснвностей потоков (у известных аналогов потери имеются).
Практическая ценность работы заключается в следующем:
Создан параллельно-последовательный алгоритм коммутации сообщений, предназначенный для использования в условиях средней интенсивности потоков сообщений.
Разработан параллельно-конвейерный алгоритм коммутации сообщений, предназначенный для использования в условиях высокой интенсивности потоков сообщений.
Спроектирована функциональная схема коммутатора сообщений реализующего параллельно-последовательную процедуру.
Разработана библиотека классов имитационного моделирования коммутаторов и визуальная среда программирования для ее поддержки.
Технические решения защищены патентами РФ {№ 2166793, № 2178584).
Реализация и внедрение.
Результаты диссертационной работы были использованы в учебном процессе в Курском государственном техническом университете, в Курском институте менеджмента, экономики и бизнеса и внедрены на предприятии ЗАО мКентавр электронике", что подтверждается соответствующими актами.
Апробация работы.
Основные положения диссертационной работы докладывались и получили положительную оценку на всероссийской НТК (Computer-Based Conference) «Информационные технологии в науке, проектировании и
8 производстве» (г. Нижний Новгород, 2000), всероссийской ЭНТК
«Компьютерные технологии в науке, проектировании и производстве» (г. Нижний Новгород, 2000), межвузовской электронной НТК «Управляющие и вычислительные системы. Новые технологии» (Вологда, ВГТУ, 2001), МНТК «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (Курск, 2001), на научно-технических семинарах кафедры «Вычислительная техника» Курского государственного технического университета с 1999 по 2003 год.
Публикации.
Результаты диссертационной работы отражены в 11 публикациях, включая 3 статьи, 2 патента на изобретение, 6 тезисов и материалов докладов. В работах, опубликованных в соавторстве, лично соискателем предложено: в [1, 9] - параллельно-последовательная процедура коммутации; в [2, 3, 10] -организация коммутатора; в [4,5] - функциональные схемы параллельно-последовательных коммутаторов; в [6, 7, 8, 11] - процедуры выбора направлений ретрансляции сообщений.
На защиту выносятся:
Параллельно-последовательная и параллельно-конвейерная процедуры коммутации сообщений для МРР-систем.
Аналитическая оценка пропускной способности и аппаратной сложности коммутаторов.
Результаты экспериментального исследования динамических характеристик коммутаторов.
Структурные и функциональные схемы коммутаторов на, базе созданных процедур.
Объем и структура работы.
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 140 страниц текста и
9 поясняется 50 рисунками; список литературы включает 80 наименований; приложения содержат 40 страниц. Общий объем составляет 180 страниц.
Области возможного использования.
Результаты диссертационной работы могут быть использованы при создании коммутационных процессоров в однородных параллельных системах с распределенной памятью типа Cray ТЗЕ, Origin 2000, в глобальных и локальных сетях ЭВМ в коммутационных узлах, в абонентских системах, в системах сбора данных, а также в иных системах, для которых характерны интенсивные стохастические потоки сообщений.
Статические коммутационные подсистемы в МРР-системах
При создании ПС используют коммутаторы в составе коммутационной подсистемы с динамической коммутацией сообщений (ДКП) и со статической коммутацией сообщений (СКП).
Динамические коммутационные подсистемы (ДКП) [1,2] предполагают возможность непосредственного физического соединения всех процессорных элементов между собой. Информационное взаимодействие происходит на основе построения физических линий связи между взаимодействующими ПЭ. ДКП, как правило, используют централизованное управление, которое осуществляет специальное устройство. Устройство, в зависимости от расположения ПЭ, формирующих запрос на организацию обмена, вырабатывает управляющий код, который поступает на входы ДКП и обеспечивает формирование непосредственного физического соединения между ПЭ. Межпроцессорный обмен начинается после установления соответствующего физического канала.
Главной отличительной особенностью статических КП (СКП) является обеспечение непосредственной связи только между строго определенными ПЭ (находящимися рядом). Взаимодействие ПЭ, не имеющих общего канала, как правило, осуществляется через другие ПЭ, называемые в этом случае транзитными (либо ретрансляторами сообщений). Для осуществления информационного взаимодействия между такими ПЭ формируется виртуальный канал связи, создаваемый в момент начала обмена информацией и разрушаемый в момент его окончания. Статические КП в подавляющем большинстве случаев используют принцип децентрализованного управления; функции управления передачей информации распределяется между отдельными ПЭ и каждый элемент ВС осуществляет обработку информации на основании анализа некоторых признаков, содержащихся в формате сообщений (адрес ПЭ - приемника сообщения). В основном статические коммутационные системы работают по методу коммутации пакетов, заключающемся в том, что сообщение передается от передатчика к приемнику порциями (пакетами) фиксированного объема и через ряд ПЭ - ретрансляторов сообщений. В МРР-системах ввиду их большой размерности (количество процессоров достигает нескольких тысяч) реализация ДКП практически невозможна. Поэтому далее под КП понимаются статические подсистемы. В процессе анализа статические коммутационные подсистемы представляются структурно-топологическими моделями в виде пространственных графов, вершины которых соответствуют ПЭ, а ребра (дуги) отображают межпроцессорные каналы связи. В зависимости от сложности пространственного строения принято выделять простые и сложные СКП. Простые системы (к ним относятся одномерные и двумерные СКП), как правило, представляются плоскими графами и имеют небольшой пример наращивания. Сложные подсистемы (такими считаются СКП, допускающие химерные варианты построения) ориентированы на применение в системах значительной размерности и обеспечивают топологически простой механизм наращивания в теоретически произвольных пределах [3]. Для сравнительной оценки структур СКП используются следующие количественные характеристики [17]: т - время передачи сообщения от ПЭ-передатчика к ПЭ-приемнику или задержка сообщения (message delay); X - загрузка каналов связи (количество сообщений, приходящихся на канал связи в единицу времени) или плотность потока сообщений (message traffic density); с - удельная сложность СКП (число каналов связи в расчете на один ПЭ), Кроме количественных характеристик иногда вводят ряд вспомогательных параметров, а также качественные характеристики: коммутационная сложность системы, максимальные потери при выходе из строя произвольного ПЭ (определяется степенью нарушения межпроцессорных связей в системе или степенью ограничения количества обменных взаимодействий) [1]. Некоторые из простых топологий СКП систем изображены на рис. 1.7, Простейший вариант топологической организации СКП представляет собой одномерная цепочка (рис.17а) [71]. Удельная сложность с=2 и не зависит от размерности СКП N. Цепочка предоставляет достаточно простой механизм расширения структуры КП при добавлении ПЭ. Однако, использование такой топологии при построении ПС большой размерности нецелесообразно, поскольку средняя задержка сообщения т и загрузка каналов связи X зависят от N. Кроме того, выход из строя і-го ПЭ разрушает каналы взаимодействия пар ПЭ (m mi), = 0,1-1,/= J+1,N, хотя система в целом сохраняет работоспособность. При соединении линией связи первого и последнего ПЭ простой цепочки (то и mN_i) образуется кольцевая СКП [16]. На практике получили распространение две разновидности кольцевых ПС: двунаправленная (рис.1.76) и однонаправленная (рис.1.7в). В двунаправленной кольцевой ПС каждый i-тый ПЭ может непосредственно принимать и передавать сообщения как от ((i+l)mod N)-ro (т.е. соседнего справа), так и от ((i+N-1) mod N)-ro (т.е. соседнего слева) ПЭ, / = 0,ЛГ-1. В однонаправленной СКП направление, в котором осуществляется движение сообщений, фиксируется и і-й ПЭ непосредственно передает сообщения только ПЭ (i+1) mod N, принимая при этом сообщения только от ПЭ (i+N-1) mod N. Кольцевым КП независимо от направлений передачи информации присущи те же положительные свойства, что и одномерной цепочке (простота комплексирования, наращивания, малая удельная сложность, простота маршрутизации сообщений). Хотя значение т и X немного ниже, чем в простой цепочке, кольцевые СКП также не могут служить эффективной основой для построения систем значительной размерности (N 10 N - 20), поскольку зависимость т и X от N имеет порядок т = л= —. КП с кольцевой организацией обладают малой надежностью, так как отказ по меньшей мере одного ПЭ или канала связи существенно уменьшает возможное число обменных взаимодействий. Одним из возможных способов повышения надежности кольцевых СКП, причем при одновременной минимизации их диаметра (и, следовательно, значения т)5 является организация дополнительной связи между ПЭ mi и mj, где іє{0,2Д...,Д-2}5 j=(i+3)mod N, N - четное. В результате образуется хордо-кольцевая СКП (рис.1.9.г). Свойства хордо-кольцевых СКП были исследованы в работе [4].
Параллельно-конвейерная процедура коммутации сообщений
Усовершенствованным вариантом гиперкуба является «двухсвязный гиперкуб», аналогично полному гиперкубу, элементы СКП со структурно-топологической организацией «двухсвязный гиперкуб» располагаются в узлах d-мерного гиперкуба с длиной ребра q. Каждый ПЭ подключается к двум шинам, охватывающим два различных измерения, одним из которых является измерение условно называемое нулевым и ассоциированное с вертикальным направлением (этому направлению соответствует вертикальная, или первая шина СКП). Элементы СКП размещаются в гиперплоскостях, перпендикулярных основному направлению, и наряду с вертикальной шиной соединяются с шиной некоторого k-го направления (k = l,d-\) измерения (эта шина условно называется второй). При движении вдоль вертикального направления и последовательном переходе от одной гиперплоскости к другой направление второй шины изменяется на ортогональное предшествующему. Направления ориентации шин, лежащих в гиперплоскостях, расстояния между которыми в нулевом измерении равны d, совпадают. Наиболее простой вариант СКП с организацией типа двухсвязный гиперкуб представлен на рис. 1Л Об (здесь вертикальное направление показано стрелкой).
Сравнительный анализ двух описанных выше топологий показывает, что двухсвязный гиперкуб во многих отношениях является более эффективным по сравнению с полным гиперкубом. Весьма важной особенностью двухсвязного гиперкуба является низкая удельная сложность, с=4 (при использовании двунаправленных линий связи) и полная независимость величины с ни от длины ребра q, ни от числа измерений d. Последнее позволяет увеличивать число размерность СКП как за счет роста величины q, так и путем введения дополнительных измерений. При этом среднее время передачи сообщений и средняя загрузка каналов связи в полном и двухсвязном гиперкубах одинаковой размерности находятся в отношении \/L. Подробный анализ свойств КП с организацией типа гиперкуб дан в работе [10]. Эффективным способом структурно-топологической организации СКП представляется «куб циклов». Куб циклов представляет собой булев гиперкуб (q=2) размерности d, каждая из 2 вершин которого вместо одного элемента заменена циклом из d связанных ПЭ. Каждый из ПЭ имеет по три двунаправленных канала связи, два из которых подключаются к соседним ПЭ, принадлежащим общему с данным элементом циклу, а третий канал пересекает гиперкуб в одном из трех измерений и соединяет рассматриваемый элемент с соответствующим ПЭ другого цикла. Трехмерный куб циклов представлен на рисЛЛОв. Куб циклов в отношении пространственной и временной сложности соответствует двухсвязному гиперкубу и так же, как и последний весьма хорошо подходит для построения СКП значительной размерности (N 1000). Средняя длина пути рс проходимого сообщениями в d-мерном кубе циклов лишь незначительно меньше, чем соответствующая длина для d-мерного двухсвязного гиперкуба pk :pL = -d-3;ph = 2rf-3[ll]. В тоже время число измерений dc в кубе циклов, содержащем заданное число узлов N, превышает число измерений dh двухсвязного гиперкуба с таким же числом элементов всего в log2log2N раз. Топологические свойства куба циклов были исследованы в работе [12]. Положительные стороны использования СКП в МРР-системах включают: 1) малую сложность аппаратной реализации; 2) легкое масштабирование; 3) простую маршрутизацию при передаче сообщений. Процедура коммутации сообщений в СКП МРР-систем включает следующую последовательность фаз: Фаза 1. Прием сообщений от соседних ПЭ и запись в соответствующие входные очереди сообщений (процесс буферизации сообщений до момента их обработки коммутатором). Фаза 2. Считывание сообщений из очередей по определенным приоритетам (в порядке поступления, в зависимости от приоритетных направлений и т.д.). Фаза 3. Определение направлений выдачи сообщений. Данная фаза может выполняться, используя следующую информацию (в зависимости от алгоритма реализации): кратчайшее направление до ПЭ-приемника сообщения (минимальный путь), состояние загруженности буферных блоков соседних ПЭ с ним (загруженность направлений). Фаза 4. Выдача выбранных сообщений соседним ПЭ по определенным направлениям. Организация и, соответственно, пропускная способность средств коммутации сообщений существенно зависят от используемой процедуры обработки сообщений, В существующих МРР-системах наиболее широкое применение нашла последовательная процедура коммутации. Отличительной особенностью данной процедуры является - последовательное выполнение каждой из фаз обработки сообщений. Сообщения, формируемые или передаваемые соседними ПЭ, поступают на входы //, ..., 1 а сообщения, вырабатываемые текущим ПЭ, подаются на вход 10. Буферные блоки ББ0, ББЬ ,.., ББ обеспечивают прием, хранение и выдачу сообщений в порядке их поступления. Блок опроса (БО) осуществляет управление считыванием сообщений из ББ через мультиплексор MX в буферный регистр Рг, а также реализует требуемую дисциплину обслуживания ББ, БВНПС - блок выбора направлений выдачи сообщений - на основании адреса ПЭ-приемника сообщения осуществляет настройку демультиплексора DX на выдачу данного сообщения по соответствующему направлению. Выходы О/, ..., Ом осуществляют передачу обработанного сообщения по соответствующим направлениям, а О0 - направление передачи к текущему ПЭ (которому принадлежит коммутатор). Процедура опроса ББ, осуществляемая БО, может выполняться различными способами в зависимости от реализации. Наиболее часто используемые методы опроса:
Структурная схема параллельно-конвейерного коммутатора
После анализа способа размещения сообщений множества F выделяется подмножество = {MS5,MSb}. Процесс выдачи в целом завершается после считывания сообщений MS] и MS?. Всего, таким образом, потребовалось к -3 такта. (Следует отметить, что в общем случае существует множество способов формирования подмножеств F , порядок включения сообщений в эти подмножества может определяться из соображений минимизации аппаратно-алгоритмической сложности БАСР.)
Основная особенность параллельно-последовательного коммутатора, о чем упоминалось в главе 2 диссертации, - это разграничение по времени этапов заполнения MP и выборки групп совместных сообщений для их последующей выдачи по выбранным направлениям. При этом дополнительное заполнение (дозаполнение) матрицы MP вновь пришедшими сообщениями не осуществляется до тех пор, пока не закончится к тактов выборки сообщений из MP. Таким образом, в параллельно-последовательном коммутаторе не в полной мере решается задача оптимизации обработки сообщений.
Также можно выделить еще ряд особенностей, ограничивающих пропускную способность параллельно-последовательного коммутатора: 1) заложенная в параллельно-последовательном коммутаторе приоритетность столбцов матрицы регистров для поступающих от соседних ПЭ сообщений; 2) сообщения, идущие через такой коммутатор, отправляются только по физически кратчайшему пути. И если направление выдачи уже занято (в MP), то коммутатор по этому направлению перейдет в состояние ожидания. Таким образом, сочетание параллельно-последовательной процедуры коммутации с оптимальной организацией средств маршрутизации сообщений способно обеспечить более высокую пропускную способность коммутационной подсистемы. Указанные принципы были реализованы в параллельно-конвейерном коммутаторе. Основные отличительные особенности его функционирования перечислены ниже. 1. Дозапись сообщений в MP, не дожидаясь ее полного высвобождения. Для этого существует четкое разграничение последовательности фаз работы коммутатора, а именно этап дозаписи сообщений в MP с учетом направлений передачи сообщений (при этом учитываются и оптимальные пути передачи сообщения). 2, Выборка группы несовместных сообщений из MP. При этом оптимизирован механизм выборки, при котором направление просмотра сообщений, находящихся в MP, каждый раз меняется на противоположное (просмотр либо с первого элемента строки к последнему, либо наоборот - от последнего к первому). Тем самым существенно уменьшается возможность заблокирована менее приоритетных каналов, по которым приходят сообщения. Рассмотрим структурную схему параллельно-конвейерного коммутатора. 33. Структурная схема параллельно-конвейерного коммутатора. Параллельно-конвейерный коммутатор решает ряд ограничений параллельно-последовательного коммутатора, что позволяет его использовать в ПС, которым свойственна высокая интенсивность потоков межмодульных взаимодействий (1 сообщение на 3 такта по каждому входу). Структурная схема данного коммутатора представлена на рис. 3,3, В состав коммутатора входят следующие элементы и блоки: буферные блоки ББо, ББЬ, ББ ; блоки выбора направления передачи сообщений БВНПСо, БВНПСЬ ..., БВНПСЯ; матрица регистров (MP) размерности {р±1 )х(//+/); блок анализа способа размещения сообщений (БАСР), /Л-7 мультиплексоров, БУРОС - блок управления режимами обработки сообщений. БУРОС инициирует выполнение последовательностей фаз: 1) заполнение (и дозаполнение) MP сообщениями, взятыми из входных очередей ББ0, ББЬ, ББ ; 2) выдача выбранной группы несовместных сообщений блоком БАСР из MP с учетом порядка просмотра ячеек строк матрицы. Рассмотрим процесс обработки сообщений данным коммутатором. Сообщения, поступающие на входы коммутатора / /у, ..., 1 (далее эти сообщения обозначаются соответственно как MS(h MS], ..., MSM) последовательно размещаются в соответствующих ББ и затем считываются в порядке поступления. Запись сообщений в различные ББ производится асинхронно, а считывание осуществляется группами по s сообщений, ] S JJ+1 (сообщения пришедшие от соседних ПЭ и сообщения от ПЭ, который содержит данный коммутатор). БВНПС,- обеспечивают преобразование содержимого адресного поля А; сообщения MS( в код направления его выдачи K(MS1 ) т Коды {K(MSi)} используются для управления записью сообщений в регистры MP. Матрица регистров организована таким образом, что ее столбцы соответствуют входным каналам коммутатора, а строки — выходным каналам. Сообщение MSh і = 0,//, может быть записано либо в регистр столбца і который соответствует кратчайшему направлению выдачи либо, если кратчайшее занято, в существующее незанятое оптимальное направление выдачи сообщения, при этом номер строки, в которую помещается сообщение, определяется кодом KQAS . Запись s считанных сообщений в MP производится одновременно, при этом используется адаптированный механизм выборки. Процедуры размещения сообщений в MP ЇЇ их выдачи на выходы коммутатора разделены, и выполняются строго последовательно. Таким образом, каждый раз коммутатор либо осуществляет один процесс дозаписи либо процесс выдачи группы совместных сообщений. В ходе выполнения этой процедуры определяется способ размещения группы сообщений в MP.
Аналитическая оценка аппаратной сложности последовательного и параллельно-последовательного коммутатора
Кросс-коммутатор (рис3.7) предназначен для анализа поступающих сообщений на предмет установления направления их дальнейшей передачи и для перераспределения потоков сообщений между различными выходными каналами в зависимости от результатов анализа и содержит генератор 27 номера модуля, первую 28, вторую 29 и третью 30 схемы сравнения, первую 31.1-31.3 (31),вторую 32.1-32.3 (32) и третью 33.1-33.3 (33) группы регистров» генератор 34 тактовых импульсов, триггер 35 управления, счетчик 36, дешифратор 37, регистр 38, первый 39, второй 40 и третий 41 коммутаторы, первую 42.1-42.3, вторую 43.1-43.3 и третью 44.1-44.3 группы элементов И-НЕ, группу элементов запрета 45.1-45.3, группу элементов И 46.1-46.3, первый 47 и второй 48 элементы И-ИЛИ, первый 49 и второй 50 триггеры, блок элементов И 51, первый элемент запрета 52, первый 53 и второй 54 элементы И, второй элемент запрета 55, третий 56, первый 57 и второй 58 элементы ИЛИ и одновибратор 59, причем входы генератора 27 номера модуля являются входами настройки модуля, а выход подключен к первым входам схем сравнения 28-30, вторые входы которых подключены соответственно к первому, второму и третьему информационным входам кросс-коммутатора, первый, второй и третий информационные входы кросс-коммутатора соединены соответственно с информационными входами регистров 31,1, 32.1, 33.1, регистров 31.2, 32.2, 33.2 и регистров 31.3, 32,3, 33.3, управляющий вход кросс-коммутатора подключен к инверсному входу элемента запрета 52 и к входу установки три ггера 3 5 управления, прямой выход которого соеди йен с входом генератора 34 тактовых импульсов, выход которого подключен к счетному входу счетчика 36 и к управляющему входу (V) дешифратора 37, информационные входы с первого по третий которого соединены с соответствующими выходами счетчика 36, первый, второй и третий выходы схемы сравнения 28 подключены к входам разрешения (V) регистров 31.1, 32.1 и ЗЗЛ соответственно, первый, второй и третий выходы схемы сравнения 29 подключены к входам разрешения (V) регистров 31.2, 32.2 и 33.2 соответственно, первый, второй и третий выходы схемы сравнения 30 подключены к входам разрешения регистров 31.3, 32.3 и 33.3 соответственно, прямые выходы регистров 31.1, 31.2, 31.3 подключены соответственно к третьему, второму и первому информационным входам коммутатора 39, выход которого соединен с первым информационным выходом кросс-коммутатора, прямые выходы регистров 32.1, 32.2, 32.3 подключены соответственно к третьему, второму и первому информационным входам коммутатора 40, выход которого соединен с вторым информационным выходом кросс-коммутатора, прямые выходы регистров 33.1, 33.2, 333 подключены соответственно к третьему, второму и первому информационным входам коммутатора 41, выход которого соединен с третьим информационным выходом кросс-коммутатора, инверсные выходы регистров 31Л-31.3, 32.1-32.3, ЗЗД-33.3 подключены соответственно к входам элементов И-НЕ 42,1-42.3, 43Д-43.3 и 44.1-44.3, выход элемента И-НЕ 42.1 соединен с третьим входом элемента И 46.1, с третьим, шестым и седьмым входами элемента И-ИЛИ 47, а также с третьим, пятым и восьмым входами элемента И-ИЛИ 48, выход элемента И-НЕ 42.2 соединен с прямым входом элемента запрета 45Л, с первым входом элемента И 46.1, с вторым, четвертым и девятым входами элемента И-ИЛИ 47, а также с вторым, шестым и седьмым входами элемента И-ИЛИ 48, выход элемента И-НЕ 42.3 соединен с инверсным входом элемента запрета 45 Л, с вторым входом элемента И 46.1, с первым разрядом информационного входа регистра 38, с первым, пятым и восьмым входами элемента И-ИЛИ 47, а также с первым, четвертым и девятым входами элемента И-ИЛИ 48, выход элемента И-НЕ 43Л соединен с третьим входом элемента И 46,2, с двенадцатым, пятнадцатым и шестнадцатым входами элемента И-ИЛИ 47, а также с двенадцатым, четырнадцатым и семнадцатым входами элемента И-ИЛИ 48, выход элемента И-НЕ 43.2 соединен с прямым входом элемента запрета 45.2, с первым входом элемента И 46.2, с одиннадцатым, тринадцатым и восемнадцатым входами элемента И-ИЛИ 47, а также с одиннадцатым, пятнадцатым и шестнадцатым входами элемента И-ИЛИ 48, выход элемента И-НЕ 43.3 соединен с инверсным входом элемента запрета 45.2, с вторым входом элемента И 46,2, с четвертым разрядом информационного входа регистра 38, с десятым, четырнадцатым и семнадцатым входами элемента И-ИЛИ 47, а также с десятым, тринадцатым и восемнадцатым входами элемента И-ИЛИ 48, выход элемента И-НЕ 44Л соединен с третьим входом элемента И 463, с двадцать первым, двадцать четвертым и двадцать пятым входами элемента И-ИЛИ 47, а также с двадцать первым, двадцать третьим и двадцать шестым входами элемента И-ИЛИ 48, выход элемента И-НЕ 44,2 соединен с прямым входом элемента запрета 45.3, с первым входом элемента И 46,3, с двадцатым, двадцать вторым и двадцать седьмым входами элемента И-ИЛИ 47, а также с двадцатым, двадцать четвертым и двадцать пятым входами элемента И-ИЛИ 48, выход элемента И-НЕ 44.3 соединен с инверсным входом элемента запрета 45.3, с вторым входом элемента И 46.3, с седьмым разрядом информационного входа регистра 38, с девятнадцатым, двадцать третьим и двадцать шестым входами элемента И-ИЛИ 47, а также с девятнадцатым, двадцать вторым и двадцать седьмым входами элемента И-ИЛИ 48, первый выход дешифратора 37 подключен к входам синхронизации регистров 31Л-31.3, 32Л-32.3 и 33.1-33.3, а также к управляющему выходу кросс-коммутатора, второй выход дешифратора 37 подключен к первому входу элемента ИЛИ 57, а также к входам синхронизации триггеров 49 и 50, третий выход дешифратора 37 подключен к первому входу элемента
