Устройство коммутации

 

Изобретение относится к вычислительной технике и позволяет на его основе создавать параллельные процессоры, многомодульные вычислительные и мультитранспьютерные системы, обра6ать1вающие параллельные графы семантических сетей. Цель изобретения - расширение области применения за счет исключения блокировочных состояний при параллельнойнастройке плоской коммутационной структуры. Устройство^ коммутации, содержащее четыре ключа, четыре тригге^Е», два вёхрдных регистра, три элемента И, четыре элемента ИЛИ, причем первый информациойный вход устройства-подхлючен к инфо|эмацйонным входам первого входного регистра, первого и второго ключей, второй информационный вход - к информационным входам второго входного регистра, третьего и четвертого ключей, вход cfipocf, входы синхронизации и два информационных выхода, дополнительно содержит регистр настройки, первый и второй элементь! НЕ-И. первый и второй элементы НЕ, с первой по четвертую схемы сравнения, элемент задержки. Введение указанных элементов позволяет вести в плоской коммутационной структуре на данных устройствах параллельное отображение программы с неодинарными соединениями, что исключает блокировочные состояния и •реализациювсех выставленных заявок на соединения. 4 ил.'' s.*-иVI о ю со

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5!>5 6 06 F 9/02, 1/00

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР т

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4764056/24 (22) 05.12.89 (46) 30.01.92, Бюл. N. 4 (71) Днепродзержинский индустриальный институт им.M.È.Àðñåíè÷åâà и МГТУ им.Н.Э;Баумана (72) Н.И.Витиска и Э,Н.Витиска (53) 681.3 (08 8,8) (56) Фет Я.Н. Параллельные процессоры для управляющих систем. М.: Энергоиздат, 1981, с. t 2.6 — 144.

Авторское свидетельство СССР

N. 444466005599, кл. 6 06 F 9/02 (прототип). (54) УСТРОЙСТВО КОММУТАЦИИ (57) Изобретение относится к вычислительной технике и позволяет на его основе создавать параллельные процессоры,, многомодульные вычислительные и мультитранспьютерные системы, обрабатывающие параллельные графы семантических сетей. Цель изобретения — расширение области применения за счет исключения блокировочных состоянйй при параллельной

Изобретение относится к вычислительной технике и предназначено для построения параллельных процессоров, многомодульных вычислительных систем и мультитранспьютерных систем. Цель изобретения — расширение области применения за счет исключения блокировочных состояний при параллельной настройке плоской коммутационной структуры;

На фиг. 1 представлена функцио нальная схема устройства коммутации; на фиг. 2. SU,, 1709311 А1 настройке плоской коммутационной структуры. Устройство коммутации, содержащее . четыре ключа, четыре триггера, два входних регистра, три элемента И, четьгре элемента

ИЛИ, причем первый информационный вход устройства.подключен:к информационным входам первого входного регистра, первого и второго ключей, второй информационный вход — к информационным входам второго входного регистра; третьего и четвертого ключей; вход сброса, входы синхронизации и.два информационных выхода, дополнительно содержит регистр настройки, первый и второй элементы НЕ-И, первый и второй элементы НЕ, с первой по четвертую схемы сравнения, элемент задержки, Введение указанных элементов позволяет вести в плоской коммутационной структуре на данных устройствах параллельное отображение программы с неодинарными соединениями, что исключает блокировочные состояния и реализацию— всех выставленных заявок на соединения. а

4 ил.

/ — перечень состояния устройства коммутации при реализации им на плоской коммутационной структуре неблокирующих неодинарных подстановок; на фиг.3 — при . мер многопроцессорной вычислительной системы, в которой плоская коммутационная структура для связи процессоров выполнена на 10 данных устройствах коммутации; на фиг. 4- временная диаграмма формирования тактируемых импульсов со стороны процессоров на фиг. 3 на устройства коммутации в плоской коммутацион 1709311 который далее сформирует импульсы на

5 входы синхронизации устройств 39-42 коммутации. С последнего управляющего выхода процессора 48 импульс поступает на управляющий вход процессора 49, который формирует соответственно импульсы синх10 ронизации на устройства 43-45 коммутации, а со своего последнего управляющего выхода подает сигнал на управляющий вход процессора 50, который далее подает импульсы синхронизации на соединитель 46 и

15 со своего последнего управляющего выхода сформирует сигнал на вторые управляющие входы процессоров 47-50, сообщая им тем самым об окончании цикла параллельной настройки всех связей в плоской коммута20 ционной структуре 51.

Предполагается, что в регистры 22 через входы 1 устройств 37-46 коммутации перед началом отображения программы неодинарных связей, представленной, напри25 мер, неодинарной подстановкой вида е1 ег ез е4! ! ег ег е е

50 фиг, 3 эти связи не показаны для входа 1 кода настройки.

Рассмотрим одиночную работу каждого устройства коммутации (фиг,1). На его информационные входы 2 и 3 могут поступить

55 ной структуре при параллельной настройке на программы неодинарных соединений.

Устройство коммутации .(фиг.1)-содержит вход 1 кода настройки, два информационных входа 2 и 3, два входных регистра 4 и 5, четыре ключа 6-9, два информационных выхода 10 и 11, четыре триггера 12-15; четыре схемы сравнения 16-19, два элемента

НŠ— И 20 и 21, регистр 22 настройки, два элемента НЕ 23 и 24, три элемента И 25-21, четыре элемента ИЛИ 28-31, вход 32 сброса и два входа 33 и 34 синхронизации устройства, элемент 35 задержки, третий вход 36 синхронизации устройства;

Как видно из фиг. 2 устройство 1 коммутации может быть настроено в плоской коммутационной структуре на восемь различных состояний, которые обозначены а-з.

Причем через Хг и Хз обозначены последовательные коды на информационных входах

2 и 3, а через Хт- код настройки, записанный в регистре 22 настройки, Показанный на фиг.3 пример многопро- цессорной вычислительной системы выполнен с плоской коммутационной структурой, в которой объединены десять устройств 3746 коммутации в треугольную сортирующую сеть типа У. Каутца, и содержит также процессоры 47-50, которые для организации управления настройкой и передачи данных подключены к устройствам коммутации в плоской коммутационной структуре 51.

Как видно из фиг.4, в одном столбце по ординате указывается номер входа синхронизации 33, 34 или 36 устройства 3 коммутации 37-46, а в другом столбце— номер устройства коммутации, на который подается в соответствующий момент времени указанный на диаграмме импульс.

Рассмотрим работу устройств комму- 4 тации в плоской коммутационной структуре при параллельной неблокирующей, настройке в ней произвольных неодинарных подстановок между внешними полюсами е е4 и е) — е4 на фиг. 3. Предполагается при 4 этом, что множество полюсов e> — е4 являются выходными, а множество полюсов e>— е4 считаются входными при передаче коммутируемой информации через плоскую коммутационную структуру 51. Очевидно, что за .

Nшагов,,где N=4 в данном случае, процессоры 47-50 сформируют на своих управляющих выходах указанную на фиг, 4 временную диаграмму импульсов. Например, сформируем прежде всего импульс 37ЗЗ на первый вход 33 синхронизации устройства 37 коммутации первый процессор 47, который формирует импульсы также и на другие входы синхронизации устройств

37 и 38 коммутации по шинам, показанным на фиг. 3, При этом импульс с последнего управляющего выхода процессора 47 попадает на управляющий вход процессора 48, должны быть занесены коды соответствующих столбцов плоской коммутационной структуры 51. Так процессор 47 должен записать код первого столбца в регистры 22 устройств 37-42 коммутации, процессор

48 — код второго столбца в регистры 22 устройств в 39. 41, 44 коммутации, процессор

49 — код третьего столбца в регистры 22 устройств 43 и 45 коммутации, а процессор

50 — код четвертого столбца в регистр 22 устройства 46 коммутации. В качестве регистра 22 может быть использован как последовательный. так и параллельный регистр.

Поэтому запись может вестись в него либо последовательным, либо параллельным кодом. Так как этот процесс не отражает сущности работы устройств 37-46 коммутации в процессе параллельной настройки на приведенную неодинарную подстановку, то на соответственно коды Хг и Хз, которые при наличии сигналов на первом входе 33 синхронизации записываются в первый и второй входные регистры 4 и 5. Аналогичным образом, после вторичной подачи на вход 33 синхронизации импульсов будут возбужде1709311

10

25

35

55 ны входы синхронизации первого и второго входных регистров 4 и 5 и с них считаются коды Х2 и Хз, которые должны пройти на информационные выходы 10 и,11 и поступить в плоской коммутационной структуре на информационные входы 2 и 3 других устройств коммутации, связанных в строке и столбце с предыдущим аналогичным устройством коммутации. Проталкивание кодов Хг и Хз на информационные выходы 10 и 11 зависит от их соотношения между собой, т.е. Х2 > Хз, Хг-Хз или Хг с Хз, а также от сравнения кодов Xz, Хз с кодом Хт в регистре 22. В зависимости от этих соотношений в устройстве коммутации может быть зафиксировано восемь состояний (фиг.2), что определяется включением соответствующих триггеров 12-15 через их входы установки в "1" (обозначены через S на фиг. 1).

Подача сигнала на входы установки в "1" триггеров 12-15 происходит с элементов

ИЛИ 28-31, а переключение триггеров 12—

15 осуществляется в момент формирования сигнала на третьем входе 36 синхронизации устройства, который связан с их входами синхронизации. Высокий потенциал с единичных выходов триггеров 12 — 15 подается на соответствующие управляющие входы ключей 6 — 9 и открывает их для проталкивания через них кодов Xz и Хз.

В результате сравнения кодов на четырех схемах 16 — 19 сравнения формируются сигналы на четырех элементах ИЛИ 28 — 31.

Причем включение схем сравнения происходит в момент подачи сигнала на второй вход 34 синхронизации устройства, потенциал с которого включает первую, вторую и четвертую схемы 16, 17 и 19 сравнения непосредственно через их первые входы стробирования, а третью схему 18 сравнения через элемент 35 задержки и ее первый вход строби рован ия.

Проанализируем всевозможные ситуации по кодам Xz Хз и Х-, и очередность срабатывания элементов НЕ-И 30 — 27 и четырех схем 16-19 сравнения.

В случае, когда Xz--О, то на выходе элемента НЕ-И 20 формируетея высокий потенциал, и, наоборот, когда Хз=О, то на выходе элемента НЕ-И 21 появляется высокий потенциал. В зависимости от этих потенциалов через элементы НЕ 23 и 24 и элементы И 25-27 включаются через вторые входы стробирования первая, вторая и четвертая схемы 16, 17 и 19 сравнения. Формирование аналогичного сигнала включения для третьей схемы 18 сравнения на ее втором входе стробирования происходит при появлении сигнала на выходе "Меньше" второй схемы 17 сравнения.

Пусть Хг 4 О и Хз = О, а Х2 = Х",(см, строку а в таблице на фиг, 2), Тогда на выходе элемента НЕ-И 20 низкий потенциал, а на выходе НЕ-И 21 высокий. В данном случае этими потенциалами через элемент НЕ 23 открывается элемент И 25, который подготавливает первую схему 16 сравнения, срабатывание которой начинается после подачи сигнала на второй вход 34 синхронизации устройства. Так как коды Xz и Х;равны, то формируется высокий потенциал на выходе "равно" первой схемы 16 сравнения, который через первый элемент ИЛИ 28 включает первый триггер 12 в единичное состояние, что обеспечивает соединение информационного входа 2 с информационным выходом 10 через открытый ключ 6.

Пусть Xz ФО, Х2> Х? и Хз= О (см. строку б в таблице на фиг. 2). Тогда происходит возбуждение выхода "Больше" первой схемы 16 сравнения, потенциал с которого через второй элемент ИЛИ 29 включает триггер 13, что обеспечивает соединение информационного входа 2 с информационным выходом 11 через открытый ключ 7..

Пусть Хг = О, Хз = Хги Хз О (см.строку в в таблице на фиг.2). Тогда на выходе элемента НŠ— И 20 высокий потенциал, а на выходе НŠ— И 21 низкий. В данном случае этими потенциалами через элемент НЕ 24 открывается элемент И 27, который подготавливает четвертую схему 19 сравнения, срабатывание которой начинается после подачи сигнала на второй вход 34 синхронизации устройства. Так как .коды Хз и Х", равны, то формируется высокий потенциал на ее выходе "Равно", который через третий элемент

ИЛИ 30 включает третий триггер 14 в единичное состояние, что обеспечивает соединение информационного входа 3 с информационным выходом 10 через открытый ключ 8.

Пусть Xz=0, Хз > X-ð,,Хз A О (см. строку

r в таблице на фиг. 2). Тогда во включенной четвертой схеме 19 сравнения происходит возбуждение выхода "Больше", потенциал с которого через четвертый элемент ИЛИ 31 включает четвертый триггер 15, что обеспечивает соединение информационного входа

3 с информационным выходом 11 через открытый ключ 9. .Пусть Хг ФОи Хз WО, a Xz-/Хз(см.строки д и е в таблице на фиг. 2). На выходах элементов НŠ— И 20 и 21 присутствуют низкие потенциалы, по которым через элементы НЕ 23 и 24 открывается элемент И 26, подготавливающий к работе вторую схему

17 сравнения, на группы информационных

1709311 входов соответственно подаются коды Хг и

Хз. При подаче сигнала на второй вход 34 синхронизации устройства происходит срабатывание второй схемы 17 сравнения, что обеспечивает сравнение кодов Хг и Хэ.

Если код X2 > X3, то происходят возбуждение выхода "Больше" во второй схеме сравнения, срабатывание второго и третьего элементов ИЛИ 29 и 30 и при подаче сигнала на третий выход 36 синхронизации устройства — включение триггеров 13 и 14, что обеспечивает соединение информационного входа 2 с информационным выходом

11 через ключ 7, а информационного входа

3 с информационным выходом 10 через ключ 8.

Наоборот, происходит срабатывание, если код Хг < X3, т.е. происходит возбуждение выхода "Меньше" во второй, схеме 17 сравнения, потенциал с которого включает триггеры 12 и 15, что обеспечивает соединение информационного входа 2 с информационным выходом 10 через ключ 6, а информационного входа 3 с информационным выходом 11 через ключ 9.

Если код Хг=Хэ (см; строки ж и э в таблице на фиг. 2), то происходит возбуждение выхода "Равно" второй схемы 17 сравнения, потенциал с которого включает третью схему 18 сравнения через второй ее вход стробирования, После подачи сигнала на второй вход 34 синхронизации через элемент 35 задержки происходит срабатывание третьей схемы 18 сравнения, на группы информационных входов которой поданы коды Хг и Хг-, Если Хг = Х-, то возбуждается выход "Равно" третьей схемы 18 сравнения, потенциал с которого включает триггеры 12 и 14, и тем самым обеспечивает связь информационных входов 2 и 3 с информационным выходом 10 через открытые ключи 6 и

8, В другом случае, если Хг > Х <. то возбуждается выход "Больше" третьей схемы 18 сравнения, потенциал с которого проходит через элементы ИЛИ 29 и 31, включает триггеры 13 и 15 и тем самым обеспечивает связь информационных входов 2 и 3 с информационным выходом 11 через открытые ключи 7 и 9.

При необходимости разборки приложенных путей осуществляется подача сигнала на вход 32 сборки устройства, который поступает на входы установки в "0" с первого по четвертый триггеров 12 — 15, После этого на единичных выходах данных триггеров фиксируется нулевой потенциал, который закрывает все четыре ключа 6 — 9 устройства .коммутации, 10

В соответствии с указанным функционированием одиночного устройства коммутации нетрудно понять его работу при взаимодействии с другими аналогичными устройствами в плоской коммутационной структуре 51 на фиг. 3 при организации параллельной настройки на неодинарную подстановку. Такого типа подстановка предположим реализуется перед обменом информации между процессорами 47-50, которые должны автоматически настроить плоскую коммутационную структуру 15 на соответствующую программу соединений.

Таким образом, в многопроцессорной вы-. числительной системе на фиг, 3 органиэация одновременных, всегда неблокирующих ветвящихся связей между процессорами 47-50 ведется со стороны выходных полюсов, на которые одновременно выставляются последовательные коды входных полюсов е< — е4. 3 соответствии с подстановкой процессоров 47 выставляет код полюса ег, процессор 48 — код полюса еg, процессоры

49 и 50 — код полюса е>, Причем зти коды настройки выбираются длиною1оцг N, где N — число процессоров в системе.

Одновременно с этим соответствующий процессор по диагонали плоской коммутационной структурь 51 с помощью подачи импульсов на входы 33, 34 и 36 синхронизации включает группу своих устройств коммутации; Благодаря этому ведется последовательное, неблокирующее проталкивание двоичных кодов настройки через устройс гв." оммутации плоской структуры, р которых данные коды сравниваются как между собой, так и с кодом настройки Х в регистрах 22 настройки.

Нетрудно оценить время настройки на приведенную и реализованную на фиг. 3 неодинарную подстановку. Так первый процессор 47 за два такта по диагонали включает последовательно устройства 37 и 38 коммутации, второй процессор 48 также за два такта включает по диагонали устройства

39, 40 и 41, 42 коммутации, третий процессор 49 — устройства 43 — 45 коммутации, а последнему процессору 50 требуется включить в первом такте только устройство 46 коммутации, так как его второй такт используется для сообщения остальным процессорам об окончании настройки каналов.

Учитывая, что в данном случае время проталкивания кодов настройки пропорционально на каждом устройстве коммутации

1оцгй, то общее время неблокирующей настройки N неодинарных и одинарных соединений не превышает оценку

Тн = (2N — 1)1ОЯг1Ч TBKTOB.

1709311

Формула изобретен ия.

Устройство коммутации, содержащее с первого по четвертый ключи, с первого по четвертый триггеры;-первый и второй входные регистры, с первого по третий элементы 5

И, с первого по четвертый элементы ИЛИ, причем первый информационный вход уст-.. ройства подключен к информационным входам первого входного регистра, первого и второго ключей; второй информационный 10 вход устройства — к информационным входам второго входного регистра, третьего и четвертого ключей, вход сброса устройства соединен с входами установки в "0" с первого по четвертый триггеров, первый вход 15 синхронизации устройства подключен к входам синхронизации первого и второго входных регистров, выходы с первого по четвертый триггеров соединены с управляющими входами соответственно с первого 20 по четвертый ключей, выходы первого и третьего ключей образуют первый информационный выход устройства, выходы второго и четвертого ключей образуют второй информационный выход устройства, о т л и ч а- 25 ю шийся тем, что, с целью расширения области применения за счет исключения блокировочных соединений при параллельной настройке плоской коммутационной структуры, оно дополнительно содержит ре- 30 гистр настройки, первый и второй элементы

HE-И, первый и второй элементы НЕ, с первой по четвертую схемы сравнения, элемент задержки, причем второй вход синхронизации устройства подключен к первым вхбдам 35 стробирования первой, второй и четвертой схем сравнения, к входу элемента задержки, выход которого соединен с первым входом стробирования третьей схемы сравнения, выход "Равно" которой соеди- 40 нен с первым входом первого и третьего элементов ИЛИ, выходы которых соединены соответственно с,входами установки в

"1" первого и третьего триггеров, вход кода настройки устройства подключен к инфор=. 45 мационному входу регистра настройки, выход которого соединен с .первым информационным. входом четвертой схемы сравнения, выхОд первого регистра — с первыми информационными входами с первой по третью схем сравнения и входами первого элемента НЕ-И, выход которого соединен с первым входом третьего элемента И и с входом первого элемента НЕ, выход которого соединен с первыми входами первого и второго элементов И, выходы которых соединены с вторыми входами стробирования первой и второй схем сравнения, выход второго входного регистра соединен с вторыми информационными входами второй и четвертой схем сравнения и с входами второго элемента НЕ-И, выход которого соединен с . вторым входом первого элемента И и с входом второго элемента НЕ, выход которого соединен с вторыми входами второго и третьего элементов И, выход последнего соединен с вторым входом стробирования четвертой схемы сравнения, выход "Больше" третьей схемы сравнения соединен с первыми входами второго и четвертого элементов

ИЛИ, выход "Больше" четвертой схемы сравнения — с вторым входом четвертого элемента ИЛИ, выходы "Равно" первой и четвертой схем сравнения соединены с вторыми входами соответственно первого и третьего элементов ИЛИ, выход "Меньше" второй схемы сравнения соединен с третьими входами первого и четвертого элементов

ИЛИ, выход которого соединен с входом установки в "1" черветого триггера, выход ,"Равно" второй схемы сравнения соединен с вторым входом стробирования третьей схемы сравнения, выход "Больше" первой схемы сравнения — с вторым входом второго элемента ИЛИ, выход которого соединен с входом установки в "1" второго триггера, выход регистра настройки соединен с вторыми информационными входами первой и третьей схем сравнения, выход "Больше" второй схемы сравнения соединен с третьими входами второго и третьего элементов

ИЛИ, третий вход синхронизации ycтройства соединен с входами синхронизации с первого по четвертый триггеров.

3709311

1709311

1709311

17093111

t.

Составитель H.Вутиска

Редактор И.Касарда Техред M.Ìîðãåíòýë Корректор М.Максимишинец

Заказ 426 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушскэя наб.. 4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101