Модуль для обмена сообщениями
Изобретение относится к области вычислительной техники и может найти применение при построении коммутационных средств мультипроцессорных вычислительных и управляющих систем, абонентских систем связи с децентрализованным управлением и информационно-измерительных систем. Техническим результатом является расширение области применения устройства на основе включения в его состав блоков, обеспечивающих возможность динамической модификации маршрутов сообщений в зависимости от загрузки очередей как непосредственных, так и виртуальных соседей. Указанный результат достигается за счет того, что в модуль для обмена сообщениями, содержащий группу буферных блоков с первого по восьмой, блок коррекции направления, блок выбора направления, первую группу регистров, выходной регистр, первый дешифратор, мультиплексор, первый счетчик, группу коммутаторов с первого по восьмой, триггер запуска, первый и второй одновибраторы, элементы ИЛИ с первого по третий, первый и второй элементы И, генератор тактовых импульсов, введены буферный блок, вторая и третья группы регистров, второй дешифратор, группа демультиплексоров с первого по восьмой, второй счетчик, первая и вторая группы сумматоров, первая и вторая группы триггеров, третий одновибратор, первая и вторая группы элементов ИЛИ и четвертый и пятый элементы ИЛИ. 10 ил., 1 табл.
Изобретение относится к области вычислительной техники и может найти применение при построении коммутационных средств мультипроцессорных вычислительных и управляющих систем, абонентских систем связи с децентрализованным управлением и информационно-измерительных систем.
Известен модуль матричного коммутатора, содержащий три блока организации очередей сообщений, регистр идентификатора модуля, блок анализа очереди сообщений, мультиплексор, регистр, демультиплексор, триггер, блок синхронизации, два элемента сравнения, два дешифратора и элемент И (а.с. 1575167, СССР G 06 F 7/00, 15/16; опубл. 30.06.90, БИ №24).
Недостатком данного модуля является невозможность динамической модификации маршрутов передачи сообщений и, как следствие, узкая область применения.
Наиболее близким к предлагаемому модулю по технической сущности является устройство формирования маршрута сообщения в однородной вычислительной системе, содержащее группу блоков буферной памяти, три регистра, триггер, счетчик, блок сравнения, блок выбора направления, генератор тактовых импульсов, демультиплексор, мультиплексор, дешифратор, два элемента И, группу элементов И, три элемента ИЛИ, три одновибратора, два элемента задержки (а.с. 1287172, СССР G 06 F 15/16; опубл. 30.01.87, БИ №4).
Недостатком указанного устройства является невозможность динамической модификации маршрутов сообщений в зависимости от загрузки очередей модулей, находящихся на расстоянии 2 от текущего (виртуальных соседей). Это ведет к увеличению неравномерности нагрузки на коммутатор и возможным потерям сообщений, сужая область применения устройства.
Технической задачей, на решение которой направлено изобретение, является расширение области применения устройства на основе включения в его состав блоков, обеспечивающих возможность динамической модификации маршрутов сообщений в зависимости от загрузки очередей как непосредственных соседей, так и виртуальных соседей. Учет состояний очередей виртуальных соседей позволяет перенаправить сообщения по оптимальным направлениям и снизить общую нагрузку на коммутатор.
Техническая задача решается тем, что в модуль для обмена сообщениями, содержащий группу буферных блоков с первого по восьмой, блок коррекции направления, блок выбора направления, генератор тактовых импульсов, первую группу регистров с первого по второй, выходной регистр, первый дешифратор, мультиплексор, первый счетчик, группу коммутаторов с первого по восьмой, триггер запуска, с первого по третий одновибраторы, с первого по третий элементы ИЛИ, первый и второй элементы И, причем первый информационный вход блока выбора направления является входом адреса модуля, выход блока коррекции направления соединен со вторым информационным входом блока выбора направления, вход сброса модуля подключен ко входам сброса всех буферных блоков группы, ко входу сброса выходного регистра, ко входам сброса всех регистров первой группы, выходы первого дешифратора со второго по девятый соединены с управляющими входами буферных блоков группы с первого по восьмой соответственно, первые выходы которых соединены с информационными входами мультиплексора со второго по девятый соответственно, выход первого счетчика соединен с управляющим входом мультиплексора и со входом первого дешифратора, выход мультиплексора соединен с информационными входами всех регистров первой группы, выход первого одновибратора соединен со входом установки триггера запуска, выходы всех регистров первой группы соединены с первыми информационными входами всех коммутаторов группы, выход второго регистра первой группы соединен с информационным входом выходного регистра, выход которого является первым выходом приема модуля, выходы всех коммутаторов группы подключены к соответствующим выходам модуля, выход первого элемента ИЛИ подключен ко входам первого и второго одновибраторов, дополнительно включены буферный блок, вторая и третья группы регистров, второй дешифратор, группа демультиплексоров, второй счетчик, первая и вторая группы сумматоров, первая и вторая группы триггеров, первая и вторая группы элементов ИЛИ, четвертый и пятый элементы ИЛИ, причем выход первого регистра первой группы соединен с третьим информационным входом блока выбора направления, вход сброса модуля подключен ко входу сброса буферного блока, ко входам сброса всех триггеров первой и второй групп, всех регистров второй и третьей групп, к первым входам второго, третьего и пятого элементов ИЛИ, первый выход первого дешифратора соединен с управляющим входом буферного блока, первый выход буферного блока соединен с первым информационным входом мультиплексора, старшие разряды входов модуля с первого по восьмой соединены с первыми входами элементов ИЛИ первой и второй групп с первых по восьмые соответственно и входами синхронизации регистров третьей группы с первого по восьмой соответственно, младшие разряды входов модуля с первого по восьмой соединены со вторыми входами элементов ИЛИ первой группы с первого по восьмой соответственно и первыми входами синхронизации буферных блоков группы с первого по восьмой соответственно, вторые разряды входов модуля с первого по восьмой соединены со вторыми входами элементов ИЛИ второй группы с первого по восьмой соответственно, выходы элементов ИЛИ первой группы с первого по восьмой подключены к счетным входам триггеров первой группы с первого по восьмой соответственно, выходы элементов ИЛИ второй группы с первого по восьмой подключены ко входам синхронизации регистров второй группы с первого по восьмой соответственно, прямые выходы триггеров первой группы с первого по восьмой соединены с управляющими входами демультиплексоров группы с первого по восьмой соответственно, входы модуля с первого по восьмой подключены к информационным входам демультиплексоров группы с первого по восьмой соответственно, первые выходы которых соединены с информационными входами регистров второй группы с первого по восьмой соответственно, а вторые выходы подключены к информационным входам буферных блоков группы с первого по восьмой соответственно, выходы всех регистров второй группы соединены со входом блока коррекции направления, выход (i+1)-гo (i=0,1,...,7) регистра второй группы подключен ко входам ((i+3)mod 8+1)-гo, ((i+4)mod 8+1)-го и ((i+5)mod 8+1)-го сумматоров первой группы, выходы сумматоров первой группы с первого по восьмой соединены с первыми входами сумматоров второй группы с первого по восьмой соответственно, выходы которых соединены с информационными входами регистров третьей группы с первого по восьмой соответственно, вторые выходы буферных блоков группы с первого по восьмой соединены со вторыми входами сумматоров второй группы с первого по восьмой соответственно и со вторыми информационными входами коммутаторов группы с первого по восьмой соответственно, первый выход генератора тактовых импульсов через третий одновибратор соединен со входом синхронизации блока выбора направления, первый выход генератора тактовых импульсов соединен со вторыми входами синхронизации всех буферных блоков, со входами синхронизации всех регистров первой группы и с первыми входами всех элементов И, выход блока выбора направления соединен со входами установки всех триггеров второй группы, информационный вход буферного блока является входом приема модуля, первый вход синхронизации буферного блока является входом синхронизации модуля, девятый выход первого дешифратора подключен ко второму входу первого элемента И, второй выход буферного блока является вторым выходом приема модуля, третьи выходы всех буферных блоков подключены ко входу первого элемента ИЛИ, выход второго одновибратора соединен со вторым входом второго элемента ИЛИ, выход которого соединен со входом сброса триггера запуска, прямой выход которого соединен со входом генератора тактовых импульсов, второй выход которого подключен к счетному входу первого счетчика, вход сброса которого соединен с выходом пятого элемента ИЛИ, ко второму входу которого подсоединен выход первого элемента И, второй выход генератора тактовых импульсов соединен со счетными входами всех триггеров второй группы, третий, четвертый и пятый выходы генератора тактовых импульсов подсоединены к первому, второму и третьему входам четвертого элемента ИЛИ соответственно и к выходам модуля с первого по восьмой, выход четвертого элемента ИЛИ соединен со счетным входом второго счетчика, выход третьего элемента ИЛИ соединен со входом сброса второго счетчика, выход второго элемента И соединен со вторым входом третьего элемента ИЛИ, выход второго счетчика соединен со входом второго дешифратора, первый выход которого соединен с первыми управляющими входами всех коммутаторов группы, второй выход второго дешифратора соединен со вторыми управляющими входами всех коммутаторов группы, третий выход второго дешифратора соединен с третьими управляющими входами всех коммутаторов группы, а также со вторым входом второго элемента И, выходы регистров третьей группы с первого по восьмой соединены с третьими информационными входами коммутаторов группы с первого по восьмой соответственно, прямые выходы триггеров второй группы с первого по восьмой соединены с четвертыми управляющими входами коммутаторов группы с первого по восьмой соответственно, а прямой выход девятого триггера второй группы соединен со входом синхронизации выходного регистра.
На фиг.1 приведена функциональная схема модуля для обмена сообщениями, на фиг.2 приведена структурная схема коммутатора на базе предлагаемого модуля; на фиг.3 схематично показан процесс формирования кодов загруженности для одного сектора направлений; на фиг.4 приведена структура сообщения; на фиг.5 приведена граф-схема алгоритма обработки сообщения; на фиг.6 схематично изображен тракт коррекции направлений выдачи и формирования кодов длин очередей для одного сектора направлений; на фиг.7-9 приведены функциональные схемы буферного блока, блока выбора направления и блока коррекции направления соответственно; на фиг.10 изображены временные диаграммы работы модуля в режимах выдачи и приема информации.
Коммутатор на базе предлагаемого модуля имеет вид 8-регулярной решетки (матрицы) с незамкнутыми границами (каждый модуль имеет связи со своими восемью соседями, а крайние модули в строках и крайние модули в столбцах матрицы не имеют непосредственного соединения) (фиг.2). Обмен сообщениями выполняется в параллельном коде через транзитные модули. Каждый модуль имеет свой адрес, который определяется его координатами относительно других модулей. Направление выдачи сообщения на каждом шаге определяется динамически в секторе возможных направлений, сориентированном на приемник. При этом учитываются загруженность очередей трех соседей и загруженность очередей виртуальных соседей в секторе (фиг.3). Сообщение идет в том направлении, где меньше суммарная загрузка очередей. Сектор выбирается из 8 возможных вариантов в зависимости от взаимного расположения источника и приемника.
Адрес каждого модуля задается парой координат А.В, где А - номер столбца модуля в матрице, а В - номер строки модуля (А - координата модуля по оси X, а В - координата модуля по оси Y). Левый нижний "угол" матрицы имеет координаты 1.1, а правый верхний - координаты N.M (фиг.2).
Способ задания маршрутов сообщений определяется следующими обозначениями:
R - направление "вправо";
L - направление "влево";
U - направление "вверх";
D - направление "вниз";
RU - "вправо-вверх";
RD - "вправо-вниз";
LU - "влево-вверх";
LD - "влево-вниз".
Выбор направления выдачи сообщения организуется в зависимости от взаимного расположения приемника и источника. Пусть X.Y - это адрес приемника а X1.Y1 - адрес текущего модуля (в котором находится сообщение). Тогда направление выдачи сообщения в модуле X1.Y1 можно определить по таблице.
Чтобы задать маршрут передачи сообщения между модулями с учетом его возможной динамической модификации, пространство коммутатора (фиг.2) разбивается на секторы. Сектор - это группа направлений, в которых возможна передача сообщения на приемник. В каждом секторе три направления: одно из них основное, а два других - второстепенные. Маршрутизация в основном направлении идет согласно таблицы. Сектор можно определить так. Основное направление "вправо" (R), второстепенные - "вправо-вниз" (RD) и "вправо-вверх" (RU). Тогда, если сообщение должно передаваться вправо, в зависимости от загрузки очередей сообщений возможна его модификация на направления RU и RD. Точно также можно задать и другие секторы и направления передачи:
RU.R.RD - сектор направлений RU, R (основное направление), RD;
R.RD.D - сектор направлений R, RD (основное направление), R;
RD.D.LD - сектор направлений RD, D (основное направление), LD;
D.LD.L - сектор направлений D, LD (основное направление), L;
LD.L.LU - сектор направлений LD, L (основное направление), LU;
L.LU.U - сектор направлений L, LU (основное направление), U;
LU.U.RU - сектор направлений LU, U (основное направление), RU;
U.RU.R - сектор направлений U, RU (основное направление), R.
Модули получают информацию о загруженности очередей соседей в секторе, а также о загруженности очередей виртуальных соседей следующим образом. Код длины очереди хранится в специальном регистре-счетчике, который будет увеличиваться на 1 с каждым поступлением сообщения и уменьшаться на 1 с каждым уходом сообщения. Передать этот код соседям можно так же, как передаются обычные сообщения в виде параллельного слова по тактовому импульсу. Чтобы не вводить лишних каналов связи для обмена кодами длины очередей, эти коды передаются по основным каналам (по которым идут сообщения), но в мультиплексном режиме. Например, в первом такте выдается сообщение, а потом - коды длин очередей. Коды должны одновременно выдаваться всем соседям: каждому соседу код длины соответствующей ему очереди.
Чтобы передача сообщений велась не только с учетом состояния загруженности очередей трех соседей в секторе, но и виртуальных соседей, нужен обмен и кодами длин очередей виртуальных соседей. Сделать это можно аналогично описанному выше по основным каналам связи в режиме мультиплексирования. Например, в первом такте идет сообщение, во втором такте - коды длин соседей, а в третьем - коды длин виртуальных соседей.
Так как направление выдачи сообщения выбирается только из трех вариантов (основное и два второстепенных), но надо учитывать загруженность большего числа очередей, необходимо объединить коды длин каждого соседа с кодами соответствующих ему виртуальных соседей, например, путем суммирования. Тогда каждому направлению будет соответствовать суммарный код загруженности, по которому можно организовать выбор направления (фиг.3).
На фиг.3 через L1-L12 обозначены длины очередей сообщений виртуальных и непосредственных соседей. Модуль 2.2 на основании этих длин вычисляет 3 суммарных кода длин очередей: для направления U (LU), для направления RU (LRU) и для направления R (LR). Формулы для вычисления этих кодов выглядят следующим образом:
LU=L+L2L3+L10;
LRU=L4+L5+L6+L11;
LR=L7+L8+L9+L12.
Точно также вычисляются суммарные коды длин очередей для других секторов.
На основе вычисленных суммарных кодов длин очередей организуется динамическая модификация выбранных направлений передачи сообщений в секторе. Сначала выбирается основное направление согласно таблице. Затем это направление корректируется в соответствии с соотношением между суммарными кодами длин очередей. На выбор маршрута влияет состояние не только непосредственных соседей, но и виртуальных соседей. С такой маршрутизацией можно заранее определить наиболее загруженные сообщениями фрагменты коммутатора и оптимизировать время передачи сообщений путем их доставки "в обход". Если рассматривать весь трафик коммутатора, то можно обеспечить хороший баланс загрузки очередей и тем самым снизить требования к их предельной длине.
Алгоритм обработки сообщений модулем включает следующие этапы:
1. Считывание сообщения из очереди.
2. Формирование кода основного направления выдачи сообщения.
3. Коррекция кода направления выдачи сообщения.
4. Выдача сообщения на нужный выход.
Считывание сообщения из очереди включает выбор одной из очередей (всего 9 очередей по числу входов у модуля). Формирование кода направления происходит согласно таблице в зависимости от соотношения адресов текущего модуля и приемника сообщения. Коррекция кода направления включает расчет суммарных кодов длин очередей (LU, LRU и т.д.) и изменение кодов направлений с учетом результатов расчета (по минимуму суммарной длины). Выдача сообщения включает передачу информационной части или всего сообщения в скорректированном направлении (на нужный выход). Чтобы обеспечить корректность доставки сообщения приемнику, следует запретить коррекцию направления выдачи, когда до приемника остался лишь один шаг передачи, т.е. |Х-Х0|=1 и/или |Y-Y0|=1. В противном случае сообщение может "зациклиться" и не дойти до приемника.
Граф-схема алгоритма обработки сообщения показана на фиг.5. Условие Х=Х1 и Y=Y1 в алгоритме проверяет, доставлено ли сообщение в приемник или нет. Если оно ложно, то сообщение следует выдать соседу текущего модуля. Иначе информационная часть сообщения принимается модулем для передачи в обслуживаемое им операционное устройство. Условие |Х-Х1|=1 или |Y-Y1|=1 индицирует необходимость коррекции направления выдачи сообщения. Если оно истинно, то коррекция не нужна, так как сообщение будет передано модулю-приемнику. Если же оно ложно, то требуется коррекция направления по суммарным кодам длин очередей.
Модуль для обмена сообщениями (фиг.1) содержит группу буферных блоков 1.1-1.8, буферный блок 2, блок 3 коррекции направления, блок 4 выбора направления, генератор 5 тактовых импульсов, первую группу регистров 6.1, 6.2, вторую группу регистров 7.1-7.8, третью группу регистров 8.1-8.8, выходной регистр 9, первый дешифратор 10, второй дешифратор 11, мультиплексор 12, группу демультиплексоров 13.1-13.8, первый счетчик 14, второй счетчик 15, первую группу сумматоров 16.1-16.8, вторую группу сумматоров 17.1-17.8, группу коммутаторов 18.1-18.8, первую группу триггеров 19.1-19.8, вторую группу триггеров 20.1-20.9, триггер 21 запуска, первый 22, второй 23 и третий 24 одновибраторы, первую группу элементов ИЛИ 25.1-25.8, вторую группу элементов ИЛИ 26.1-26.8, с первого по пятый элементы ИЛИ 27-31, первый 32 и второй 33 элементы И, причем первый информационный вход блока 4 выбора направления является входом 34 адреса модуля, выход блока 3 коррекции направления соединен со вторым информационным входом блока 4 выбора направления, выход регистра 6.1 соединен с третьим информационным входом блока 4 выбора направления, вход 36 сброса модуля подключен ко входам сброса буферных блоков 1.1-1.8 и 2, выходного регистра 9, триггеров 19.1-19.8 и 20.1-20.9, регистров 6.1,6.2, 7.1-7.8 и 8.1-8.8, к первым входам элементов ИЛИ 28, 29 и 31, выходы дешифратора 10 с первого по девятый соединены с управляющими входами буферных блоков 2 и 1.1-1.8 соответственно, первые выходы буферных блоков 2 и 1.1-1.8 соединены с информационными входами мультиплексора 12 с первого по девятый соответственно, выход счетчика 14 соединен с управляющим входом мультиплексора 12 и со входом дешифратора 10, выход мультиплексора 12 соединен с информационными входами регистров 6.1 и 6.2, выход одновибратора 22 соединен со входом установки триггера 21 запуска, выходы регистров 6.1 и 6.2 соединены с первыми информационными входами коммутаторов 18.1-18.8, выход регистра 6.2 соединен с информационным входом выходного регистра 9, выход выходного регистра 9 является первым выходом приема 40.1 модуля, выходы коммутаторов 18.1-18.8 подключены к выходам 39.1-39.8 модуля соответственно, старшие разряды входов 35.1-35.8 модуля соединены с первыми входами элементов ИЛИ 25.1-25.8, 26.1-26.8 и входами синхронизации регистров 8.1-8.8 соответственно, младшие разряды входов 35.1-35.8 модуля соединены со вторыми входами элементов ИЛИ 25.1-25.8 и первыми входами синхронизации буферных блоков 1.1-1.8 соответственно, вторые разряды входов 35.1-35.8 модуля соединены со вторыми входами элементов ИЛИ 26.1-26.8 соответственно, выходы элементов ИЛИ 25.1-25.8 подключены к счетным входам триггеров 19.1-19.8 соответственно, выходы элементов ИЛИ 26.1-26.8 подключены ко входам синхронизации регистров 7.1-7.8 соответственно, прямые выходы триггеров 19.1-19.8 соединены с управляющими входами демультиплексоров 13.1-13.8 соответственно, входы 35.1-35.8 модуля подключены к информационным входам демультиплексоров 13.1-13.8 соответственно, первые выходы демультиплексоров 13.1-13.8 соединены с информационными входами регистров 7.1-7.8 соответственно, вторые выходы демультиплексоров 13.1-13.8 соединены с информационными входами буферных блоков 1.1-1.8 соответственно, выходы регистров 7.1-7.8 соединены со входом блока 3 коррекции направления, выход регистра 7.i+1 (i=0,1,...,7) подключен ко входам 16.((i+3)mod 8)+1-го, 16.((i+4)mod 8)+1-го и 16.((i+5)mod 8)+1-го сумматоров, выходы сумматоров 16.1-16.8 соединены с первыми входами сумматоров 17.1-17.8 соответственно, выходы сумматоров 17.1-17.8 соединены с информационными входами регистров 8.1-8.8 соответственно, вторые выходы буферных блоков 1.1-1.8 соединены со вторыми входами сумматоров 17.1-17.8 соответственно и со вторыми информационными входами коммутаторов 18.1-18.8 соответственно, первый выход генератора 5 тактовых импульсов через одновибратор 24 соединен со входом синхронизации блока 4 выбора направления, первый выход генератора 5 тактовых импульсов соединен со вторыми входами синхронизации буферных блоков 1.1-1.8 и 2, со входами синхронизации регистров 6.1, 6.2 и подсоединен к первым входам элементов И 32 и 33, выход блока 4 выбора направления соединен со входами установки триггеров 20.1-20.9, информационный вход буферного блока 2 является входом 37 приема модуля, первый вход синхронизации буферного блока 2 является входом 38 синхронизации модуля, девятый выход дешифратора 10 подключен ко второму входу элемента И 32, второй выход буферного блока 2 является вторым выходом приема 40.2 модуля, третьи выходы буферных блоков 2 и 1.1-1.8 подключены ко входу элемента ИЛИ 27, выход элемента ИЛИ 27 подключен ко входам одновибраторов 22 и 23, выход одновибратора 23 соединен со вторым входом элемента ИЛИ 28, выход элемента ИЛИ 28 соединен со входом сброса триггера 21 запуска, прямой выход триггера 21 запуска соединен со входом генератора 5 тактовых импульсов, второй выход генератора 5 тактовых импульсов подключен к счетному входу счетчика 14, вход сброса счетчика 14 соединен с выходом элемента ИЛИ 31, ко второму входу которого подсоединен выход элемента И 32, второй выход генератора 5 тактовых импульсов соединен со счетными входами триггеров 20.1-20.9, третий, четвертый и пятый выходы генератора 5 тактовых импульсов подсоединены к первому, второму и третьему входам элемента ИЛИ 30 соответственно и к выходам 39.1-39.8 модуля, выход элемента ИЛИ 30 соединен со счетным входом счетчика 15, выход элемента ИЛИ 29 соединен со входом сброса счетчика 15, выход элемента И 33 соединен со вторым входом элемента ИЛИ 29, выход счетчика 15 соединен со входом дешифратора 11, первый выход дешифратора 11 соединен с первыми управляющими входами коммутаторов 18.1-18.8, второй выход дешифратора 11 соединен со вторыми управляющими входами коммутаторов 18.1-18.8, третий выход дешифратора 11 соединен с третьими управляющими входами коммутаторов 18.1-18.8, третий выход дешифратора 11 соединен со вторым входом элемента И 33, выходы регистров 8.1-8.8 соединены с третьими информационными входами коммутаторов 18.1-18.8 соответственно, прямые выходы триггеров 20.1-20.8 соединены с четвертыми управляющими входами коммутаторов 18.1-18.8 соответственно, прямой выход триггера 20.9 соединен со входом синхронизации выходного регистра 9.
Каждый буферный блок 1.1-1.8 и 2 (фиг.7) соответствует прототипу и содержит группу регистров 41.1-41.n (где n - максимальная длина очереди сообщений), реверсивный счетчик 42 загрузки, первую и вторую группы ключей 43.1-43.n и 44.1-44.n, группу блоков элементов ИЛИ 45.1-45.n-1, первую и вторую группы элементов ИЛИ 46.1-46.n и 47.1-47.n, группу элементов И 48.1-48.n, с первого по четвертый элементы И 49-52.
Блок 4 выбора направления (фиг.8) соответствует прототипу и содержит узел 53 памяти константы, первый и второй вычитатели 54 и 55, с первой по четвертую схемы 56-59 сравнения, а также дешифратор, выполненный на первой и второй группах элементов И 60.1-60.9 и 61.1-61.8, группе блоков элементов И 62.1-62.8, группе элементов ИЛИ 63.1-63.8, с первого по третий элементах И 64-66, элементе ИЛИ 67 и элементе 68 задержки.
Блок 3 коррекции направления (фиг.9) соответствует прототипу и содержит группу схем 69.1-69.16 сравнения, первую и вторую группы элементов ИЛИ 70.1-70.16 и 71.1-71.8.
Процесс работы модуля включает несколько этапов: 1) установка исходного состояния; 2) запуск модуля; 3) обработка потоков сообщений; 4) завершение работы. В свою очередь, третий этап состоит из трех фаз. Первая фаза - выдача сообщения в выбранном направлении. Вторая фаза - синхронная передача кодов длин очередей сообщений всем восьми соседям. Третья фаза - выдача суммарных кодов длин очередей восьми соседям. На этом этапе асинхронно по отношению к выдаче сообщений и кодов длин очередей происходит прием сообщений и кодов длин очередей от соседей. Этот процесс также включает три фазы. Первая - прием сообщений в буферные блоки 1.1-1.8 и 2. Вторая - запись кодов длин очередей. И третья - прием суммарных кодов длин очередей.
В исходном состоянии все элементы памяти модуля (регистры 6.1, 6.2, 7.1-7.8 и 8.1-8.8, выходной регистр 9, счетчики 14 и 15, триггеры 19.1-19.8 и 20.1-20.9 и триггер 21 запуска) находятся в нулевом состоянии; на всех входах 34, 35.1-35.8, 37 и 38 и выходах 39.1-39.8 и 40.1, 40.2 модуля находятся нулевые сигналы. Приведение модуля в это состояние происходит подачей внешнего единичного сигнала достаточной длительности на вход 36 сброса (фиг.1).
Модуль продолжает находиться в исходном состоянии до тех пор, пока на один из буферных блоков 1.1-1.8 и 2 не поступит сообщение. В буферный блок 2 сообщение поступает от операционного устройства, которое обслуживается данным модулем, а в остальные буферные блоки 1.1-1.8 от восьми соседей текущего модуля в коммутаторе (фиг.2). После поступления сообщения в буферный блок, оно появляется на его первом выходе. При этом на втором выходе формируется ненулевой код длины очереди сообщений, а на третьем - единичный сигнал присутствия сообщений. Единица с третьего выхода буферного блока 1.1-1.8 и 2 через элемент ИЛИ 27 и одновибратор 22 воздействует на триггер 21 запуска и устанавливает его в единичное состояние. В результате генератор 5 тактовых импульсов начинает генерировать импульсные последовательности τ1-τ5. Модуль приступает к обработке сообщений (этап 3).
Обработка сообщений, как отмечалось выше, представляет собой многофазный процесс, в который отдельно входят выдача информации и ее прием.
Код выбора буферных блоков с выхода счетчика 14 поступает на управляющий вход мультиплексора 12 и коммутирует сообщение из буферного блока 1.1-1.8 или 2 в регистры 6.1 и 6.2. По импульсу τ1 с генератора 5 тактовых импульсов в регистр 6.1 записывается адресная часть сообщения, а в регистр 6.2 - информационная часть (фиг.4). Одновременно по импульсу τ1 происходит сдвиг очереди сообщений в выбранном буферном блоке. После записи сообщения в регистры 6.1 и 6.2 начинается анализ его адресной части и определяется код направления его выдачи согласно таблице.
Код направления формируется в блоке 4 выбора направления согласно правилам получения основного направления (см. таблицу) и его коррекции с учетом суммарных кодов длин очередей соседей в секторе (фиг.6). Сам процесс коррекции выполняется не просто по длинам очередей непосредственных соседей, а по суммарным кодам, учитывающим также состояние очередей виртуальных соседей в соответствующем секторе направлений (фиг.3).
Полученный код с выходов блока 4 выбора направлений подается на триггеры 20.1-20.9 и фиксируется в них по заднему фронту импульса τ2 с генератора 5 тактовых импульсов. Далее этот код поразрядно "распределяется" между выходными коммутаторами и настраивает нужный коммутатор на выдачу сообщения. Например, если выбрано направление U, то будет открыт только коммутатор 18.1 и сообщение из регистров 6.1 и 6.2 пойдет на выход U. Если текущий модуль является приемником сообщения, то ни один из коммутаторов 18.1-18.8 не пропустит сообщение; оно пойдет в операционное устройство через выходной регистр 9. После того как сообщение прошло через коммутатор на нужный выход модуля, на третьем выходе генератора 5 тактовых импульсов появляется импульс τ3. Он поступает на тот же выход, куда передано сообщение, и синхронизирует его прием в соседнем модуле.
Этот же импульс τ3 через элемент ИЛИ 29 проходит на вход второго счетчика 15 и переключает его в состояние "01". В результате на выходах второго дешифратора 11 образуется унитарный код "0010", который поступает на коммутаторы 18.1-18.8 и настраивает их на выдачу кодов длин очередей из буферных блоков 1.1-1.8. Текущие коды длин очередей из буферных блоков 1.1-1.8 сразу же проходят на соответствующие выходы модуля к соседям. По импульсу τ4 с генератора 5 тактовых импульсов эти коды будут одновременно приняты всеми восемью соседями.
По тому же самому импульсу τ4 происходит переключение счетчика 15 в очередное состояние "10". На выходах второго дешифратора 11 образуется унитарный код "0100". Этот код подается на выходные коммутаторы 18.1-18.8 и коммутирует через них на выходы модуля суммарные коды длин очередей соседей из регистров 8.1-8.2. По следующему импульсу τ5 с генератора 5 тактовых импульсов эти коды фиксируются соседними модулями. Одновременно этот импульс переключает второй счетчик 15 в состояние "11", на выходах второго дешифратора 11 появляется код "1000". Этот код блокирует все коммутаторы, но подготавливает счетчик 15 к сбросу в нулевое состояние, открывая элемент И 33. По очередному импульсу τ1 счетчик 15 будет сброшен в исходное состояние.
Принимаемая информация поступает от восьми соседей с входов 35.1-35.8 модуля на входы демультиплексоров 13.1-13.8 соответственно. Как уже говорилось выше, сначала поступают сообщения, потом коды длин очередей, а потом - суммарные коды (три фазы).
Сообщение проходит через демультиплексор 13.1-13.8 в соответствующий буферный блок 1.1-1.8, где фиксируется импульсом τ*3, поступающим от генератора тактовых импульсов соседа, передавшего это сообщение (далее звездочка в обозначении импульса говорит о том, что импульс передается от соседнего модуля). Запись сообщения в буферный блок происходит по стандартному алгоритму, который без изменений взят из прототипа. После записи сообщения очередь сообщений в буферном блоке увеличивается на 1, что сразу же индицируется кодом длины очереди сообщений на втором выходе данного буферного блока. Импульс τ*3 кроме записи сообщения в буферный блок решает другую задачу: он задним фронтом переводит соответствующий триггер 19.1-19.8 в единичное состояние. В результате вход соответствующего демультиплексора 13.1-13.8 коммутируется с его первым выходом и информация от соседа теперь пойдет не в буферный блок, а в соответствующий регистр 7.1-7.8.
Сразу после исчезновения импульса τ*3 на вход соответствующего демультиплексора от соседа поступает код длины его очереди сообщений. Этот код проходит на информационный вход соответствующего регистра 7.1-7.8, где фиксируется по переднему фронту очередного импульса τ*4. После записи кода в соответствующий регистр 7.1-7.8 начинается пересчет кода коррекции направления в блоке 3 коррекции направления и, спустя некоторое время, в блок 4 выбора направления выдается новый код коррекции. Одновременно осуществляется суммирование кодов длин очередей на сумматорах первой и второй группы сумматоров 16.1-16.8 и 17.1-17.8. Суммарный код, полученный из кодов от трех соседей в секторе, суммируется с кодом длины очереди текущего модуля и подается в соответствующий регистр третьей группы регистров 8.1-8.8 для последующей выдачи соседу.
После этого на входе модуля появляется импульс τ*5. Этот импульс завершает три фазы приема информации модулем от одного соседа. Импульс одновременно решает следующие задачи. Во-первых, он фиксирует в регистрах 8.1-8.8 суммарные коды длин очередей для соответствующих секторов направлений, вычисленные сумматорами соседей. Во-вторых, по нему от соседа переписывается суммарный код длины очередей, вычисленный аналогично этим соседом. И в-третьих, этот же импульс возвращает соответствующий триггер 19.1-19.8 в исходное нулевое состояние; так что очередное сообщение от соседа снова пойдет в буферный блок. Для обеспечения временного согласования описанных действий с действиями соседних модулей первые два из них возбуждаются передним фронтом импульса τ*3, а последнее - задним фронтом этого импульса.
Аналогично модуль принимает информацию от семи остальных соседей, фиксирует коды длин очередей от них, пересчитывает собственные коды, включая суммарные. Причем "работа" с разными соседями происходит асинхронно по импульсам от этих соседей, функционирование которых взаимно не синхронизировано.
Так как правильность работы модуля тесно связана с правильностью временных соотношений между различными сигналами в модуле и его соседях, необходим их анализ. Для этого на фиг.10 изображены упрощенные временные диаграммы работы модуля в описанных режимах выдачи и приема информации.
Из анализа диаграмм и функциональной схемы на фиг.1 вытекает правильность функционирования модуля во взаимосвязи с другими аналогичными модулями коммутатора.
Модуль заканчивает работу тогда, когда ни в одном из буферных блоков 1.1-1.8 и 2 не остается сообщений. В этом случае на третьих выходах буферных блоков 1.1-1.8 и 2 формируются нулевые сигналы. Триггер 21 запуска сбрасывается в нулевое состояние. В результате происходит выключение генератора 5 тактовых импульсов и модуль прекращает обработку сообщений. Для того чтобы модуль успел выдать последнее сообщение и обновить информацию о своих длинах очередей у соседей, выключение генератора 5 тактовых импульсов должно происходить только после выхода импульса τ5. Это легко сделать в схеме генератора 5 тактовых импульсов, используя кольцевой счетчик импульсов.
Работа модуля возобновляется как только в один из буферных блоков 1.1-1.8 или 2 снова поступает сообщение.
Таким образом, как следует из описания, включение в состав модуля блоков, обеспечивающих возможность динамической модификации маршрутов сообщений в зависимости от загрузки очередей как непосредственных соседей, так и виртуальных соседей, позволило значительно расширить область применения устройства за счет возможности перенаправления сообщений по оптимальным направлениям и снижения общей нагрузки на коммутатор.
| Таблица 1 | |
| Соотношение X.Y и X1.Y1 | Основное направление выдачи сообщения |
| X>X1, Y>Y1 | RU |
| X>X1, Y=Y1 | R |
| X>X1, Y<Y1 | RD |
| X<X1, Y>Y1 | LU |
| X<X1, Y=Y1 | L |
| X<X1, Y<Y1 | LD |
| X=X1, Y>Y1 | U |
| X=X1, Y<Y1 | D |
| X=X1, Y=Y1 | прием сообщения |
Модуль для обмена сообщениями, содержащий группу буферных блоков с первого по восьмой, блок коррекции направления, блок выбора направления, генератор тактовых импульсов, первую группу регистров с первого по второй, выходной регистр, первый дешифратор, мультиплексор, первый счетчик, группу коммутаторов с первого по восьмой, триггер запуска, с первого по третий одновибраторы, с первого по третий элементы ИЛИ, первый и второй элементы И, причем первый информационный вход блока выбора направления является входом адреса модуля, выход блока коррекции направления соединен со вторым информационным входом блока выбора направления, вход сброса модуля подключен ко входам сброса всех буферных блоков группы, ко входу сброса выходного регистра, ко входам сброса всех регистров первой группы, выходы первого дешифратора со второго по девятый соединены с управляющими входами буферных блоков группы с первого по восьмой соответственно, первые выходы которых соединены с информационными входами мультиплексора со второго по девятый соответственно, выход первого счетчика соединен с управляющим входом мультиплексора и со входом первого дешифратора, выход мультиплексора соединен с информационными входами всех регистров первой группы, выход первого одновибратора соединен со входом установки триггера запуска, выходы всех регистров первой группы соединены с первыми информационными входами всех коммутаторов группы, выход второго регистра первой группы соединен с информационным входом выходного регистра, выход которого является первым выходом приема модуля, выходы всех коммутаторов группы подключены к соответствующим выходам модуля, выход первого элемента ИЛИ подключен ко входам первого и второго одновибраторов, отличающийся тем, что в него дополнительно включены буферный блок, вторая и третья группы регистров, второй дешифратор, группа демультиплексоров, второй счетчик, первая и вторая группы сумматоров, первая и вторая группы триггеров, первая и вторая группы элементов ИЛИ, четвертый и пятый элементы ИЛИ, причем выход первого регистра первой группы соединен с третьим информационным входом блока выбора направления, вход сброса модуля подключен ко входу сброса буферного блока, ко входам сброса всех триггеров первой и второй групп, всех регистров второй и третьей групп, к первым входам второго, третьего и пятого элементов ИЛИ, первый выход первого дешифратора соединен с управляющим входом буферного блока, первый выход буферного блока соединен с первым информационным входом мультиплексора, старшие разряды входов модуля с первого по восьмой соединены с первыми входами элементов ИЛИ первой и второй групп с первых по восьмые соответственно и входами синхронизации регистров третьей группы с первого по восьмой соответственно, младшие разряды входов модуля с первого по восьмой соединены со вторыми входами элементов ИЛИ первой группы с первого по восьмой соответственно и первыми входами синхронизации буферных блоков группы с первого по восьмой соответственно, вторые разряды входов модуля с первого по восьмой соединены со вторыми входами элементов ИЛИ второй группы с первого по восьмой соответственно, выходы элементов ИЛИ первой группы с первого по восьмой подключены к счетным входам триггеров первой группы с первого по восьмой ее ответственно, выходы элементов ИЛИ второй группы с первого по восьмой подключены ко входам синхронизации регистров второй группы с первого по восьмой соответственно, прямые выходы триггеров первой группы с первого по восьмой соединены с управляющими входами демультиплексоров группы с первого по восьмой соответственно, входы модуля с первого по восьмой подключены к информационным входам демультиплексоров группы с первого по восьмой соответственно, первые выходы которых соединены с информационными входами регистров второй группы с первого по восьмой соответственно, а вторые выходы исключены к информационным входам буферных блоков группы с первого по восьмой соответственно, выходы всех регистров второй группы соединены со входом блока коррекции направления, выход (i+1)-гo (i=0,1,...,7) регистра второй группы подключен ко входам ((i+3)mod 8+1)-го, ((i+4)mod 8+1)-го и ((i+5)mod 8+1)-го сумматоров первой группы, выходы сумматоров первой группы с первого по восьмой соединены с первыми входами сумматоров второй группы с первого по восьмой соответственно, выходы которых соеденены с информационными входами регистров третьей группы с первого по восьмой соответственно, вторые выходы, буферных блоков группы с первого по восьмой соединены со вторыми входами сумматоров второй группы с первого по восьмой соответственно и со вторыми информационными входами коммутаторов группы с первого по восьмой соответственно, первый выход генератора тактовых импульсов через третий одновибратор соединен со входом синхронизации блока выбора направления, первый выход генератора тактовых импульсов соединен со вторыми входами синхронизации всех буферных блоков, со входами синхронизации всех регистров первой группы и с первыми входами всех элементов И, выход блока выбора направления соединен со входами установки всех триггеров второй группы, информационный вход буферного блока является входом приема модуля, первый вход синхронизации буферного блока является входом синхронизации модуля, девятый выход первого дешифратора подключен ко второму входу первого элемента И, второй выход буферного блока является вторым выходом приема модуля, третьи выходы всех буферных блоков подключены ко входу первого элемента ИЛИ, выход второго одновибратора соединен со вторым входом второго элемента ИЛИ, выход которого соединен со входом сброса триггера запуска, прямой выход которого соединен со входом генератора тактовых импульсов, второй выход которого подключен к счетному входу первого счетчика, вход сброса которого соединен с выходом пятого элемента ИЛИ, ко второму входу которого подсоединен выход первого элемента И, второй выход генератора тактовых импульсов соединен со счетными входами всех триггеров второй группы, третий, четвертый и пятый выходы генератора тактовых импульсов подсоединены к первому, второму и третьему входам четвертого элемента ИЛИ соответственно и к выходам модуля с первого по восьмой, выход четвертого элемента ИЛИ соединен со счетным входом второго счетчика, выход третьего элемента ИЛИ соединен со входом сброса второго счетчика, выход второго элемента И соединен со вторым входом третьего элемента ИЛИ, выход второго счетчика соединен со входом второго дешифратора, первый выход которого соединен с первыми управляющими входами всех коммутаторов группы, второй выход второго дешифратора соединен со вторыми управляющими входами всех коммутаторов группы, третий выход второго дешифратора соединен с третьими управляющими входами всех коммутаторов группы, а также со вторым входом второго элемента И, выходы регистров третьей группы с первого по восьмой соединены с третьими информационными входами коммутаторов группы с первого по восьмой соответственно, прямые выходы триггеров второй группы с первого по восьмой соединены с четвертыми управляющими входами коммутаторов группы с первого по восьмой соответственно, а прямой выход девятого триггера второй группы соединен со входом синхронизации выходного регистра.
