Устройство коммутации Советский патент 1992 года по МПК G06F9/02 G06F1/00 

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

Цель изобретения расширение области применения за счёт исключения блокировочных состояний при параллельной настройке плоской коммутационной структуры.

На фиг. 1 представлена функциональная схема устройства коммутации; на фиг. 2

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

Устройство коммутации (фиг. 1) содержит вход 1 кода настройки, два информационных входа. 2 и 3, два входных регистра 4 и 5, четыре ключа 6-9, два информационных выхода 10 и 11, четыре триггера 12-15, четыре схемы сравнения 16-19, два элемента НЕ-И 20 и 21; регистр 22 настройки, два элемента НЕ 23 и 24, три элемента И 25-27, четыре элемента ИЛИ 28-31, вход 32 сброса и два входа 33 и 34 синхронизации устройства, элемент 35 задержки, третий вход 36 синхронизации устройства.

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

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

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

Рассмотрим работу устройств коммутации в плоской коммутационной структуре при. параллельной неблокирующей настройке в ней произвольных неодинарных подстановок между внешними полюсами eiе4 и ei - е4 на фиг. 3. Предполагается при .этом, что множество полюсов ei - е4 являются выходными, а множество полюсов ei 64 считаются входными при передаче коммутируемой информации через плоскую коммутационную структуру 51. Очевидно, что за N шагов, где в данном случае, процессоры 47-50 сформируют на своих управляющих выходах указанную на фиг. 4 временную диаграмму импульсов. Например, сформируем прежде всего импульс 3733 на первый вход 33 синхронизации устройства 37 коммутации первый процессор 47, который формирует импульсы также и на другие входы синхронизации устройств 37 и 38 коммутации по шинам, показанным

на фиг. 3. При этом импульс с последнего управляющего выхода процессора 47 попадает на управляющий вход процессора 48, который далее сформирует импульсы на

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

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

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

ei е2 ез е4

еа е2 ei ei

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

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

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

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

5 последовательным, либо параллельным кодом. Так как этЪт процесс не отражает сущности работы устройств 37-46 коммутации в процессе параллельной настройки на приведенную неодинарную подстановку, то на

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

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

5 соответственно коды Х2 и Хз, которые при наличии сигналов на первом входе 33 синхронизации записываются в первый и второй входные регистры 4 и 5. Аналогичным образом, после вторичной подачи на вход 33 синхронизации импульсов буДут возбуждены входы синхронизации первого и второго входных регистров 4 и 5 и с них считаются коды Х2 и Хз, которые должны пройти на информационные выходы 10 и 11 и поступить в плоской коммутационной структуре на информационные входы 2 и 3 других устройств коммутации, связанных в строке и столбце с предыдущим аналогичным устройством коммутации. Проталкивание кодов Х2 и Хзна информационные выходы 10 и 11 зависит от их соотношения между собой, т.е. Х2 Хз. Ха-Хз или Ха Хз, а также от сравнения кодов Х2 , Хз,с кодом Xt в регистре 22. В зависимости от этих соотношений в устройстве коммутации может быть зафиксировано восемь состояний (фиг.2), что определяется включением соответствующих триггеров 12-15 через их входы установки в Г (обозначены через S на фиг. 1). Подача сигнала на входы установки в 1 триггеров 12-15 происходит с элементов ИЛИ 28-31, а переключение триггеров 1215 осуществляется в момент формирования сигнала на третьем входе 36 синхронизации устройства, который связан с их входами синхронизации. Высокий потенциал с единичных выходов триггеров 12-15 подается на соответствующие управляющие входы ключей 6-9 и открывает их для проталкивания через них кодов Ха и Хз.

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

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

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

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

5 состояние, что обеспечивает соединение информационного входа 2 с информационным выходом 10 через открытый ключ 6.

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

Пусть Х2 О, Хз Хг и Хз О (см.строку в в таблице на фиг.2). Тогда на выходе элемента НЕ-И 20 высокий потенциал, а на

0 выходе НЕ-И 21 низкий. В данном случае

этими потенциалами через элемент НЕ 24

открывается элемент И 27, Rotopый подготавливает четвертую схему 19 сравнения,

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

Пусть , Хз Хг,, Хз О (см. строку

5 г в таблице на фиг. 2). Тогда во включенной

четвертой схеме 19 сравнения происходит

возбуждение выхода Больше, потенциал с

которого через четвертый элемент ИЛИ 31

включает четвертый триггер 15, что обеспечивает соединение информационного входа 3 с информационным выходом 11 через открытый ключ 9.

Пусть Х2 0 и Хз 5 0. а Х2 5 Хз (см.строки д и е в таблице на фиг. 2). На выходах

5 элементов НЕ-И 20 и 21 присутствуют низкие потенциалы, по которым через элементы НЕ 23 и 24 открывается элемент И 26, подготавливающий к работе вторую схему 17 сравнения, на группы информационных

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

Если код Х2 Хз, то происходят возбуждение выхода Больше во второй схеме сравнения, срабатывание второго и третьего элементов ИЛИ 29 и 30 и при подаче сигнала на третий выход 36 синхронизации устройства - включение триггеров 13 и 14, что обеспечивает соединение информационного входа 2 с информационным выходом 11 через ключ 7, а информационного входа 3 с информационным выходом 10 через ключ 8.

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

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

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

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

В соответствии с указанным функционированием одиночного устройства коммутации нетрудно понять его работу при взаимодействии с другими аналогичными

устройствами в плоской коммутационной структуре 51 на фиг. 3 при организации параллельной настройки на неодинарную подстановку. Такого типа подстановка предположим реализуетс я перед обменом

информации между процессорами , которые должны автоматически настроить плоскую коммутационную структуру 15 на соответствующую программу соединений. Таким образом, в многопроцессорной вычислительной системе на фиг. 3 организация одновременных, всегда неблокирующих ветвящихся связей между процессорами 47-50 ведется со стороны выходных полюсов, на которые одновременно выставляются последовательные коды входных полюсов 61 -64. 3 соответствии с подстановкой процессоров 47 выставляет код полюса 82, процессор 48 - код полюса е2, процессоры 49 и 50 - код полюса ei. Причем эти коды

настройки выбираются длиною iog2 N, где N - число процессоров в системе.

Одновременно с этим соответствующий процессор по диагонали плоской коммутационной структурь- 51 с помощью подачи

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

устрО,сгву (оммутации плоской структуры. р которых данные коды сравниваются как между собой, так и с кодом настройки XT в регистрах 22 настройки.

Нетрудно оценить время настройки на

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

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

коммутации, так как его второй так;т используется для сообщения остальным процессорам об окончании настройки каналов. Учитывая, что в данном случае время проталкивания кодов настройки пропорционально на каждом устройстве коммутации log2N, то общее время неблокирующей настройки N неодинарных и одинарных соединений не превышает оценку

TH (2N-1)log2N тактов.

Формула изобретения Устройство коммутации, содержащее с первого по четвертый ключи, с первого по четвертый триггеры, первый и второй входные регистры, с первого по третий элементы И, с первого по четвертый элементы ИЛИ, причем первый информационный вход устройства подключен к информационным входам первого входного регистра, первого и второго ключей, второй информационный вход устройства - к информационным входам второго входного регистра, третьего и четвертого ключей, вход сброса устройства соединен с входами установки в О с первого по четвертый триггеров, первый вход синхронизации устройства подключен к входам синхронизации первого и второго входных регистров, выходы с первого по четвертый триггеров соединены с управляющими входами соответственно с первого по четвертый ключей, выходы первого и третьего ключей образуют первый информационный выход устройства, выходы второго и четвертого ключей образуют второй информационный выход устройства, отличаю щ и и с я тем, что, с целью расширения области применения за счет исключения блокировочных соединений при параллельной настройке плоской коммутационной структуры, оно дополнительно содержит регистр настройки, лервый и второй элементы НЕ-И, первый и второй элементы НЕ, с первой по четвертую схемы сравнения, элемент задержки, причем второй вход синхронизации устройства подключен к первым входам стробирования первой, второй и четвертой схем сравнения, к входу элемента задержки, выход которого соединен с первым входом стробирования трет.ьей схемы сравнения, выход Равно которой соединен с первым входом первого и третьего элементов ИЛИ, выходы которых соединены соответственно с .входами установки в 1 первого и третьего триггеров, вход кода настройки устройства подключен к инфор мационному входу регистра настройки, выход которого соединен с первым

информационным.входом четвертой схемы сравнения, выход первого регистра - с перВ1 ми информационными входами с первой по третью схем сравнения и входами первого элeмeнta НЕ-И, выход которого соединен с первым входом третьего элемента И и с входом первого элемента НЕ, выход которого соединен с первыми входами первого и второго элементов И, выходы которых со единены с вторыми входами стробирования первой и второй схем сравнения, выход второго входного регистра соединен с вторыми информационными входами второй и четвертой схем сравнения и с входами втррого элемента НЕ-И, выход которого соединен с вторым входом первого элемента И и с входом второго элемента НЕ, выход которого соединен с вторыми входами второго и третьего элементов И, выход последнего соединен с вторым входом стробирования четвертой схемы сравнения, выход Больше третьей схемы сравнения соединен с первыми входами второго и четвертого элементов ИЛИ, выход Больше четвертой схемы сравнения - с вторым входом четвертого элемента ИЛИ, выходы Равно первой и четвертой схем сравнения соединены с вторыми входами соответственно первого и третьего элементов ИЛИ, выход Меньше второй схемы сравнения соединен с третьими входами первого и четвертого элементов ИЛИ, выход которого соединен с входом установки в 1 черветого триггера, выход Равно второй схемы сравнения соединен с вторым входом стробирования третьей схемы сравнения, выход Больше первой схемы сравнения - с вторым входом второго элемента ИЛИ, выход которого соединен с входом в 1 второго триггера, выход регистра настройки соединен с вторыми информац1лонными входами первой и третьей схем сравнения, выход Больше второй схемы сравнения соединен с третьими входами второго и tpeTbero элементов ИЛИ, третий вход синхронизации устройства соединен с входами синхронизации с первого по четвертый триггеров.

:7iiH

Фиг2

фиг.З

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