Устройство для связи процессоров в вычислительной системе Советский патент 1989 года по МПК G06F13/14 

СП ел

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

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

На фиг.1 приведена блок-схема предлагаемого устройства; на фиг.2 - функциональная схема блока регистров приоритета; на фиг. 3 - то же, узла ком- мутации соединения; на фиг.4 - схема узла выбора процессора; на фиг.5- . то же, узла приоритетов; на фиг.6 - то же, узла коммутации.

Устройство (фиг.1) содержит шины 1 стандартного интерфейса связи, IH- терфейсные блоки 2 усилителей, узел 3 коммутации соединения, блок 4 регистров приоритета, шины 5 передачи, шины 6 приема, линии 7 запросов, шины 8 запросов, шины 9 группы выходов блока 4 регистров приоритета.

Блок 4 регистров приоритета (фиг.2) содержит коммутатор 10 и группу регистров 11 приоритета.

Узел 3 коммутации соединения (фиг.З) содержит группу управляющих регистров 12, первую группу элементов И 13, узел 14 выбора процессора, синхровход 15, вход 16 управ- ления, группу управляющих входов 17, группу запросных входов 18 и группу выходов 19 узла 14, буферный регистр 20 запросов, первую группу формирователей 21 импульса (дифференцирующих элементов), узел 22 приоритета процессоров, второй узел 23 приоритета активного процессора, первую группу блоков элементо И 24, третью группу элементов И 25, первую группу управляющих триггеров 26, первый элемент ШШ 27, вторую группу формирователей 28 импульса, первый элемент 29 задержки, третий элемент 30 задержки, триггер 31 уп- равления, четвертьй элемент ИЛИ 32, третий элемент И 33, вторую группу элементов И 34, второй элемент И 35 буферный регистр 36 готовности, вторую группу блоков элементов И 37, второй элемент ИЛИ 38, группу элементов 39 сравнения, первый элемент И 40, триггер 41 пуска, третий элемент 1Ш11 42, первый узел 43 приори

Q

-с

20

25

30

дО 45 CQ

55

тета активного процессора, второй элемент 44 задержки, вторую группу управляю1цих триггеров 45, узел 46 коммутации, выходы 47 триггеров 26 (первые адресные входы узла 46),группу ВЫХОДОВ 48 формирователей 21 (первые входы сброса узла 46), выход 49 элемента 44 задержки (вход стробиро- вания узла 46), группу выходов 50 формирователей 28 (вторые входы сброса узла 46), выходы 51 триггеров 45 (вторые адресные входы узла 46), первый 52 и второй 53 управляющие входы устройства, выходы 54 регистра 20 и .генератор 55 импульсов.

Узел 14 выбора процессора (фиг.4) содержит вторую группу элементов ИЛИ 56, первую 57 и вторую 58 группы элементов И соответственно и первую группу элементов ИЛИ 59.

Узел 22 приоритетов процессоров (фиг.5) содержит группу дешифраторов 60, группу элементов ИЛИ 61, группу элементов И 62, шифратор 63 и группу элементов 64 сравнения.

Узел 46 коммутации (фиг.6) содержит каналы 65, каждьй из которых включает в сеРя первую 66 и вторую 67 группы элементов И, регистр 68 и коммутатор 69 и группу элементов ИЛИ 70.

Устройство работает следующим об разом.

При организации процессов в вычислительной системе каждому из них вьщеляется необходимое число процессоров. На этапе планирования вычислений операционной системой для определения последовательности орга- 1шзации межпроцессорных связей внутри созданных процессов каждому из них устанавливается приоритет двоичными кодами натурального ряда чисел, причем наивысшим приоритетом обладает процесс с меньшим приоритетным кодом. Каждому процессору одного процесса задаются двоичный код приоритета данного процессора и одинаковый номер задачи (процесса). Это дает возможность при организации обменов сигналы запросов и готовности сопровождать номером процесса. В каждом процессе ряд процессоров (активные) формируют сигналы запросов, а остальные его процессоры (пассивные) - .сигналы г отовности. Эти сигналы сопровождаются номером процесса и фик5

сируются в соответствующем регистре 12 (фиг.З).

Каждый управляющий регистр 12 содержит два триггера, хранящих сигналы запроса и готовности, и регистр для хранения двоичного кода номера процесса.

Функцию присвоения приоритетов может взя-Л) на себя любой из процессоров, входящих в вычислительную систему, который в данный момент является центральным. При этом блок 4 рассматривается как абонент для процессора, присваивающего приоритеты. Процессор выдает код приоритета, который через соответствуюсщй интерфейсный блок 2 поступает по шинам 5 на вход коммутатора 10 (фиг.1 и 2) и далее в соответствующий регистр 11 по управляющему сигналу на линиях 7.

Межпроцессорньш обмен начинается с фазы установления связи между процессорами, выделенными процессу. Установление связи происходит в соответствии с присвоенными приоритетами процессам. Выбор приоритетного процесса происходит следующим образом.

Исходное состояние устройства характеризуется тем, что триггеры 31 и 41, регистры 20 и 36, триггеры 26 и 45 (фиг.З), регистры 68 каналов 65 (фиг.6) установлены в состояния О (цепи установки не показаны).

При необходимости установления связи актигзными процессорами по шинам 8 в регистры 12 заносится сигналы запросов и коды номеров процессов а пассивными процессорами по шинам 8 сигналы готовности и коды номеров процессов, а по входу 53 подается сигнал запуска, устанавливающий триггер 41 в состояние 1.

Так как триггеры 31, 26 и 45 находятся в нулевых состояниях, то в регистрах 20 и 36 с помощью открытых элементов И 13 и 34 производится отслеживание состояния триггеров Т, и Т регистра 12. При наличии в регистрах 20 и 36 единичных сигналов через соответствующие элементы ИЛИ 27 и 38 открывается элемент И 40, и первым импульсом генератора 55 триггер 31 устанавливается в состояние 1. При этом элементы И 13 и 14 закрьшаются, чем фиксируются сигналы в регистрах 20 и 36 в цикле установления межпроцессорных связей.

151706

Единичные сигналы с выходов регистра 20 поступают в узел 22 по входам 54, а единичным сигналом с единичного выхода триггера 31 открываются элементы И второго узла 23 приоритета активного процесса. В узле 22 (фиг.5) коды приоритетов посредством открытых по соответствующим входам Q 54 де1Ш1фраторов 60 преобразуются в унитарные. Одноименные выходы дещиф- ратора объединяются одноименными элементами ИЛИ 61. С помощью элементов И 62, включенных с выходами злемен- 5 тов ИЛИ 61 по приоритетной схеме,

производится выделение приоритетной . младшей единицы и формирование унитарного кода на входах шифратора 63, преобразующего его в двоичный. 20 Посредством элементов 64 сравнения определяется позиционньй код числа активных процессоров приоритетного процесса. При этом номера возбужденных выходов 18 узла 22 соответству- 25 ют номерам активных процессоров, а их количество - числу активных процессоров, требующих установления связи внутри приоритетного процесса. С помощью узла 23 приоритетного актив- 30 ного процесса из нескольких запросов приоритетного процесса производится вьщеление краШ-.его левого единичного сигнала из позиционного кода с рыхо- ДОН 18. Этим сигналом открьшаются элементы И блоков 24 и на объединенных выходах блоков 24 формируется двоичный код номера приоритетного процесса. Этот код поступает на входы элементов 39 сравнения. На другие д0 входы элементов 39 сравнения через соответствующие открытые сигналами готовности регистра 36 блоки 37 поступают коды номеров процессов, пассивные процессоры которых выставили д5 сигналы готовности к обмену.

При этом возможны два случая: сигналы готовности приняты в регистр 36 от пассивных процессоров, не относящихся к выделенному приоритетному 50 процессу, в регистре 36 зафиксированы сигналы готовности пассивных процессоров, относящихся к вьщеленно- му приоритетному процессу.

В первом случае на выходах элемен- сг тов 39 сравнения установлен нулевой код, которым через элемент ILTIi 42 закрыты элементы И 25, а по инверсным входам открыты элемент И 33 и элементы И 58 в узле 14 (фиг.З и 4).

35 Г

71515

ерез некоторое время, определяемое лементом 29 задержки, устанавливаютя в состояния О все триггеры реистра 20, относящиеся к вьщеленному риоритетному процессу, посредством зла 14 выбора процессора следующим образом. Пусть к приоритетному процессору относятся сигналы в Т 20 и 20. При этих условиях на выходах , 18 и 18 узла 22 присутствуют единичные сигналы, образующие позиционный код: 10...01. С помощью узла 23 формируется унитарньш код на выходах 17 : 10.-..СО. В узле 14 еди- . ничным сигналом с входа 1 открыты элементы И 57 по первому входу, элемент И- 58, по третьему прямому входу и через элементы ИЛИ 56 - по третьим прямым входам элементы Н 58, начиная с второго. По входу 18„ по первому прямому входу открыт элемент И 58п-) . Таким образом, при поступлении сигнала по синхровходу 15 в узле 14 единичные сигналы формируются на выходе 25 элемента И 57, и на выходе элемента ИЛИ 59л., поступающих с выхода элемента И 58 f, 4, Сигналами с выходов 19, и 19|, триггеры 20, и 20п устанавливаются в нулевые состояния. При этом, если в регистре 20 имеются сигналы запросов, то на выходе элемента ИЛИ 27 удерживается единичный сигнал, которым элементы И 33 и 35 закрыты по инверсным входам. Вследствие этого триггер 31 остается в единичном 35 состоянии и по второму импульсу генератора 55 организуется очередной такт работы устройства.

Во втором случае единичным сигналом с выхода элемента ИЛИ 42 откры- ваются элементы И 25 и закрьшаются по инверсным входам элементы И 58 в узле 14. Одновременно при наличии нескольких единичных сигналов на выходах элементов 39 сравнения с помощью узла 43 вьщеляется крайняя левая единица из позиционного кода выходных сигналов элементов 39 сравнения. Задержанным сигналом с выхода элемента 29 задержки устанавливаются в состо- 50 яние 1 соответствующие триггеры 26 и 45 в состояние О - через соответствующий элемент И 34 одноименный разряд регистра 36 и соответствующий разряд регистра 20. Пусть к 55 приоритетному процессу в данном случае относятся Т 20.j и Т 20}. При этих условиях на входах 182, 18 з и 172.

30

5

0 5

0

1708

узла 14 присутствуют единичные сигналы. Единичным сигналом с входа 18 открыт элемент И 57 по первому входу, л элементы И 58 закрыты по ин- верслым входам. Поэтому импульсом с синхровхода 15 только на выходе элемента И 57 формируется единичный сигн;ш, поступающий через элемент ИШ1 59I на выход 19 узла 14. Этим сигналом устанавливается в состояние О триггер 20 регистра 20. Если после установки в состояние О разряда регистра 36, вьщеленного для межпроцессорной связи, в нем нет сигналов готовности от пассивных процессоров, единичный сигнал с выхода элемента ИЛИ 42 снимается. При этом элемент И 33 открьшается по инверсному входу нулевым сигналом с выхода элемента ИЛИ 42, а единичным сигналом с выхода элемента ИЛИ 27 по прямому входу он удерживается в закрытом состоянии. Кроме того, элемент И 35 открыт по прямому входу единичным сигналом с выхода элемента ИЛИ 27 и по инверсному входу нулевым сигналом с выхода элемента ИЛИ 38. Поэтому дополнительно задержанным импульсом, элементом 30 задержки триггер 31 устанавливается в нулевое состояние, разрешая прием сигналов запросов и готовности соответственно в регистры 20 и 36 через открытые элементы И 13 и 34.

Аналогичным образом триггер 31 устанавливается в нулевое состояние, когда после установления связи между активным и пассивным процессорами регистры 20 и 36 оказываются в нулевых состояниях, через элемент И 33.

Если же после установки в состояние О разряда регистра 36, выделенного для межпроцессорной связи, в нем имеются сигналы готовности процессоров, не относящихся к приоритетному процессу, о чем свидетельствует сигнал на выходе элемента ИЛИ 42, элементы И 33 и 35 закрыты по инверсным входам единичными сигналами соответственно с выходов элементов ИЛИ 38 и ИЛИ 27. Поэтому триггер 31 остается в единичном состоян ш.

Элемент И 40 удерживается в открытом состоянии единичными сигналами с выходов элементов ИЛИ 27 и 38, поэтому импульсом генератора 55 рассмотренным выше образом устанавлиto

f5

20

25

вается в состояние О разряд регистра 20 приоритетного про.цесса. Тем самым обеспечивается установка межпроцессорных связей для очередного по приоритету процесса при наличии сигналов запросов и готовности в регистрах 20 и 36.

Выходные сигналы триггеров 26 И 45 испол1.зуются для коммутации входов и выходов активного и пассивного процессоров в узле 46 коммутации.

Пусть в единичное состояние установлены триггеры 26, и 45ц. Это означает, что по сигисшу запроса выходы первого процессора должны быть ском- мутированы с входами п-го процессора, выходы которого, в свою очередь, должны быть подключены к входам первого процессора. Эта задача выполняется узлом 46 следующим образом. Единичным сигналом с входа 47( (фиг.6) открыты элементы И 67 в канале 65, и элемент И 66, в канапе 65f,. Единичным сигналом с входа 51 открыт элемент И 67 f,., в канале 65, и элементы И 66 в канале 65,. Через время задержки, определяемое элементом 44 (фиг.З), триггеры 68 „, в канале 65, и 68. в канале 65„ устанавливаются в единичные состояния. При этом шины 5, первого процесса коммутатором 69 подключаются к шинам 6„, а шины 5 коммутатором 69, подключаются к шинам 6., чем обеспечивается двухсторонняя связь первого процессо- 35 ра с п-нь2.

Период повторения импульсов генератора 55 выбирается с учетом параметров элементов 29 и 44 задержки.

По окончании обмена сигналы запро сов и готовности снимаются. При этом соответствующие триггеры регистра 12 устанавливаются в состояние О. Перепады потенциалов на нулевых выходах дифференцируются соответствующими элементами 21 и 28, положительными сигналами с выходов которых ус танавливаются в нулевые состояния соответствующие триггеры 26 и 45 и в узле 46 триггеры 68 соответствующих каналов 65 через элементы ИЛИ 70.

При необходимости создания новых процессов, перераспределение приоритетов процессам или в других случаях когда надобность в установке межпроцессорных связей исключена, то по входу 52 подается сигнал останова, по которому триггер 41 пуска уста50-

30

-40

45

55

to

f5

20

25

35

151517010

навливается в состояние О, чем прекращается подача импульсов генератора 55.

Для использования вновь устройства, оно приводится в исходное состояние. После этого по входу 52 подается импульс запуска.

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

30

40

45

55

групп - к инверсным выходам разрядов запроса и готовности управляющих регистров групп, прямые выходы разрядов запросов которого подключены к первым входам элементов И первой группы, а выходы разрядов кода номера - к информационным входам блоков элементов И первой и второй групп, выходы которых подключены соответственно к первым и вторым входам схем сравнения группы, выход первого элемента задержки соединен с вторыми входами элементов И третьей группы, с синхронизируюциья входами первого узла приоритета активного процесса и узла выбора процесса и через второй элемент задержки - с входом стробирования узла коммутации, выходы элементов И третьей и первой групп подключены соответственно к единичньп- входам управляющих триггеров первой группы и буферного регистра запросов, группа выходов которого соединена с группой разрешающих входов узла приоритета процессоров и с группой входов первого элемента ИЛИ, первый вход группы управляющих выходов узла выбора процессора подключен к нулевому входу первого разряда буферного регистра запросов, единичный вход триггера управления подключен к входу первого элемента задержки и выходу первого элемента И,первый, второй и третий входы которого соединены соответственно с выxoдcl - генератора импульсов, первого и второго элементов ИЛИ, группа входов которого соединена с управляющими входами блоков элементов И второй группы и группой выходов буферного регистра готовности, группа единичных входов которого соединена с выходами элементов И второй группы, первые входы которых подключены к единичным выходам разрядов готовности управляющих регистров группы,первые выходы управляющих ч риггеров первой и второй групп соединены с вторыми входами элементов И соответственно первой и второй групп, треть ими входами подключенных к нулевому выходу триггера управления, третьи входы элементов И третьей группы поц ключены к выходу третьего элемента ИЛИ, группа входов которого соединена с выходами схем сравнения группы и с группой запросных входов первого узла приоритета активного пропес10

15

20

25

са, группа БЬ1Ходов которого подключена к единичным входам управляющих триггеров второй группы и группе нулевых входов буферного регистра ГОТОВНОСТИ, отличающее ся тем, что, с целью расцирения функциональных возможностей за счет коммутации процессов при реализации сильно связанных параллельных алгоритмов, в узел коммутации соединения введены триггер пуска, входы которого являются укравляюцр ми входами устройства, четвертой элемент ИПИ, третий элемент задержки, второй и третий элементы И, второй узел приоритета активного процесса, синхро- низирую1дий вход которого подключен к единичному выходу триггера управления, группа выходов узла приоритета процессов соединена с группами запросных входов узла выбора процессора и второго узла приоритета активного процесса, группа выходов которого подключена к управляющим входам блоков элементов И первой группы, к первым входам элементов И третьей группы и к группе управляющих входов уз.ча выбора процессора, вход управления котсрого соединен с выхо- дом третьего элемента ИЛИ и инверсным входам третьего элемента И, прямой вход которого соединен с выходом третьего элемента задержки, входом подключенлого ;; выходу первого элемента задержки, и с порвьам прямым входом второго элемента И, инверсный вход которого подключен к выходу второго элемента И, а второй прямой вход соединен с выходами первого элемента tLTHi и с вторым инверсным входом третьего слемента И, выход которого подкггючен к первому входу четвертого элемента Ш1И, вторым входом соединенного с выходом второго элемента И, а вьссодом - с нулевым входом триппера управления, единичный выход триггера пуска подключен к четвертом входу первого элемента И.

2. Устройство по п. 1, о т л и - -50 чающееся тем, что узел выбора процессора дополнительно содержит вторую группу элементов И и две группы .элементов ИЛИ, вход синхронизации лс дключен к вторым прямым вхо- 55 дам элементов И второй группы, инверсные входы которых coeдIiнeны с пходим управления узла выбора профессора, первый вход группы управ30

35

40

45

Ve

Фиг.3

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

ФигЛ

54

ft

Фиг. 5