Устройство для связи процессоров в вычислительной системе

 

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

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

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

РЕСПУБЛИК (5D 4 G 06 F 13/ 4

, г1, сца - йм

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

К А BTOPCHOIVIY СВИДЕТЕЛЬСТВУ

С:

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

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

IlPH ГКНТ СССР (21) 4363089/24-24 (22) 12.01.88 (46) 15.10.89. Бюп. В 38 (72) А.Х.Ганитулин и В.Г.Попов (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Ф 1130855, кл. G 06 F 13/14, 1982.

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

К 1332327, кл. С 06 F 13/14, 1985. (54) УСТРОЙСТВО ДЛЯ СВЯЗИ 11РОЦЕССОРОВ В ВЪЯИСЛИТЕЛЬНОЙ СИСТЕМЕ

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

Цель изобретения — расширение функциональных воэможностей за счет коммутации процессоров при реализации сильно связанных параллельных алгоритмов. Устройство содержит группу, интерфейсных блоков 2 усилителей, „„80„„15151 0 А1

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

ИЛП1, элемеHT И, триггер управления, генератор импульсов и узел выбора процесса, состояший из группы элементов И. Новым в устройстве является введение в узел коммутации соединения триггера пуска, элемента ИЛИ, элемента задержки, двух элементов И, второго узла приоритета активного процесса, а в узел выбора процесса— группы элементов И и двух групп элементов ИЛИ. 1 з.п. ф-лы, 6 ил.

1515170

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

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

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

Устройство (фиг.1) содержит шины, 1 стандартного интерфейса связи, ин-

20 терфейсные блоки 2 усилителей, узел

3 коммутации соединения, блок 4 регистров приоритета, шины 5 передачи, шины 6 приема, линии 7 запросов, шины 8 запросов, шины 9 группы Bbl ходов блока 4 регистров приоритета.

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

Узел 3 коммутации соединения (фиг.3) содержит группу управляющих регистров 12, первую группу элементов И 13, узел 14 выбора процессора, синхровход 15, вход 16 управления, группу управляющих входов

17, группу запросных входов 18 и группу выходов 19 узла 14, буферный регистр 20 запросов, первую гРуппу формирователей 2 1 импульса (дифференцирующих элементов), узел 22 приоритета процессоров, второй узел 23 приоритета активного процессора, первую группу блоков элементов

И 24, третью группу элементов И 25, первую группу управляющих триггеров

26, первый элемент KIH 27, вторую группу формирователей 28 импульса, первый элемент 29 задержки, третий элемент 30 задержки, триггер 3 1 управления, четвертый элемент ИЛИ 32, третий элемент И 33, вторую группу элементов И 34, второй элемент И 35, буферный регистр 36 готовности, вторую группу блоков элементов И 37, второй элемент ИЛИ 38, группу элементов 39 сравнения, первый элемент

И 40, триггер 4 1 пуска, третий элемент ИЛИ 42, первый узел 43 приори30

55 тета активного процессора, второй элемент 44 задержки, вторую группу управляющих триггеров 45, узел 46 коммутации, выходы 47 триггеров 26 (первые адресные входы узла 46),группу выходов 48 формирователей 2 1 (первые входы сброса узла 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 коммутации (фиг.б) содержит каналы 65, каждый из которых включает в себя первую 66 и вторую

67 группы элементов И, регистр 68 и коммутатор 69 и группу элементов

ИЛИ 70.

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

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

12 (фиг .3) .

Каждый управляющий регистр 12 содержит два триггера хранящих сигФ

5 налы запроса и готовности, и регистр для хранения двоичного кода номера процесса °

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

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

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

Исходное состояние устройства ха- 30 рактеризуется тем, что триггеры 31 и

41, регистры 20 и 36, триггеры 26 и

45 (фиг.З), регистры 68 каналов 65 (фиг.6) установлены в состояния "0" (цепи установки не показаны).

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

Так как триггеры 31, 26 и 45 на- 45 ходятся в нулевых состояниях, то в регистрах 20 и 36 с помощью открытых элементов И 13 и 34 производится отслеживание состояния триггеров Т„ и

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

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

Единичные сигналы с выходов регистра 20 поступают в узел 22 по входам 54, а единичным сигналом с единичного выхода триггера 31 открываются элементы И второго узла 23 приоритета активного процесса. В узле 22 (фиг.5) коды приоритетов посредством открытых по соответствующим входам

54 дешифраторов 60 преобразуются в унитарные. Одноименные выходы дешифратора объединяются одноименными элементами ИЛИ 61. С помощью элементов

И 62, включенных с выходами элементов ИЛИ 6 1 по приоритетной схеме, производится вьделение приоритетной младшей единицы и формирование унитарного кода на входах шифратора

63, преобразующего его в двоичный.

Посредством элементов 64 сравнения определяется позиционный код числа активных процессоров приоритетного процесса. При этом номера возбужденных выходов 18 узла 22 соответствуют номерам активных процессоров, а

Ф их количество — числу активных процессоров, требующих установления связи внутри приоритетного процесса. С помощью узла 23 приоритетного активного процесса из нескольких запросов приоритетного процесса производится вьделение крайнего левого единичного сигнала из позиционного кода с выходов 18. Этим сигналом открываются элементы И блоков 24 и на объеди-! ненных выходах блоков 24 формируется двоичный код номера приоритетного процесса. Этот код поступает на входы элементов 39 сравнения. На другие входы элементов 39 сравнения через соответствуюцие открытые сигналами готовности регистра 36 блоки 37 поступают коды номеров процессов, пассивные процессоры которых выставили сигналы готовности к обмену.

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

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

i 515170 Через некоторое время, определяемое элементом 29 задержки, устанавливаются н состояния "0 нсе триггеры регистра 20, относящиеся к выделенному приоритетному процессу, посредством узла 14 выбора процессора следующим образом. Пусть к приоритетному процессору относятся сигналы в Т 20, и

Т 20 „. При этих условиях на выходах

18, и 18„ узла 22 присутствуют единичные сигналы, образующие позиционный код: 10...01. С помощью узла

23 формируется унитарный код на выходах 17 : 10;.;00. В узле 14 единичным сигналом с входа 17, открыты элементы И 57 по первому входу, элемент И 58, по третьему прямому входу и через элементы ИЛИ 56 — по третьим прямым входам элементы И 58, начиная с второго. По входу 18„ по первому прямому входу открыт элемент И 58>, .

Таким образом, при поступлении сигнала по синхровходу 15 в узле 14 единичные сигналы формируются Hcl вьмоде 25 элемента И 57< и на выходе элемента

ИЛИ 59 „,, поступающих с выхода элемента И 58 „ Сигналами с выходов

19„ и 19„ триггеры 20, и 20 устанавливаются в нулевые состояния. При этом, если в регистре 20 имеются сиг30 налы запросов, то на выходе элемента

ИЛИ 27 удерживается единичный сигнал, которым элементы И 33 и 35 закрыты по инверсным входам. Вследствие этого триггер 31 остается н единичном состоянии и по второму импульсу генератора 55 организуется очередной такт работы устройства.

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

oTKp IT элемент И 57 по первому нхоz ду, а элементы И 58 закрыты по инверсным входам. Поэтому импульсом с синхронхода 15 только на выходе элемента И 57 формируется единичный сигнал, поступающий через элемент

ИЛИ 59 < на выход 19 узла 14. Этим сигналом ус тананливается н с ос тояние "0" триггер 20 регистра 20.

Если после установки в состояние "0" разряда регистра 36, выделенного для межпроцессорной связи, в нем нет сигналов готовности от пассивных процессоров, единичный сигнал с выхода элемента ИЛИ 42 снимается. При этом элемент И 33 открывается по инверсному входу нулевым сигналом с выхода эле— мента ИЛИ 42, а единичным сигналом с выхода элемента ИЛИ 27 по прямому входу он удерживается в закрытом состоянии. Кроме того, элемент И 35 открыт по прямому входу единичным сигналом с выхода элемента ИЛИ 27 и по инверсному входу нулевым сигналом с выхода элемента ИЛИ 38. Поэтому дополнительно задержанным импульсом, элементом 30 задержки триггер 3 1 устанавливается в нулевое состояние, разрешая прием сигналов запросов и готонности соответственно в регистры

20 и 36 через открытые элементы И 13 и 34.

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

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

1 входам единичными сигналами соответственно с выходов элементов ИЛИ

38 и ИЛИ 27. Поэтому триггер 31 остается в единичном состоянии.

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

10 вается в состояние "0" разряд ре- навливается в состояние "0" чем и егйстра 20 приоритетного процесса. кращается подача импул импульсов генератоТем самым обеспечивается установка ра 55. межпроцессорных связей для очеред- ования вновь устройства, Для использования ного по приоритету процесса при оно приводи о о приводится в исходное состояние ° наличии сигналов запросов и готовнос- После этого ого по входу 52 подается имти в регистрах 20 и 36. пульс запуска.

Выходные сигналы триггеров 26 .и Формула изобретения

45 используются для коммутации входов 1 1. Устройство для связи процесdî- и выходов активного и пассивного про- ров в вычислительной ьн ой сис теме, с одерцессоров в узле 46 коммутации. жащее группу интерфейсных блоков

Пусть в единичное состояние уста- усилителей, входы-выходы которых явновлены триггеры 26, и 45„. Это озна- ляются группой входов-выходов устчает, что по сигналу запроса выходы 15 ройства для подключения к входампервого процессора должны быть ском- выходам соответствующих процесс х процессоров мутированы с входами и-го процессора, вычислительной системы, блок региствыходы которого, в свою очередь, ров приоритета, группа информациондолжны быть подключены к входам пер- ных и группа синхровходов которого вого процессора. Эта задача выполня- соединены соответственно с нф

20 о с информается узлом 46 следующим образом. Еди- ционными выходами и выходом сигнала ничным сигналом с входа 47 (фиг.6) запроса интерфейсных блоков усилиоткрыты элементы И 67 в канале 65, телей группы, узел коммутации соедин элемент И 66, в канале 65>, Единич- нения, включающий узел коммутапии, ным сигналом с входа 51„ открыт эле- 25 информационные входы группы и выходы мент И 67

67, в канале 651 и элемен- которого подключены соответственно к ты И 66 в канале 65<. Через время за- информационным выходам группы и входержки, определяемое элементом 44 дам интерфейсных бл ок ов усилителей (фиг.З), триггеры 68 „, в канале группы, узел приоритетов процессов, 5, и 681 в канале 65„ устанавли- группа информационных входов котороваются в е диничные состояния. При

30 го соединена с группои выходов блока этом шины 5, первого процесса комму- регистров приоритета, группу управтатором 69 подключаются к шинам 6„, ляющих регистров, три группы элемент а шины 5 коммутатором 69„ подклю- тов И, первый узел приоритета активчаются к шинам 6, чем обеспечивается ного процесса, две группы формировадвухсторонняя связь первого процессо- З5 телей импульсов, буферный регистр запросов, буферный регистр готовности, Период повторения импульсов гене- две группы блоков элементов И две

У ратора 55 выбирается с учетом пара- группы управлякщих триггеров, группу метров элементов 29 и 44 задержки. элементов сравнения первый и второй

IIQ oKoH HHH o MeH H H 3anpo- элементы задержки, первый, второй

40 сов и готовности снимаются. При этом и третий элементы ИЛИ, первый элесоответствующие триггеры регистра 12 мент И, триггер управления, узел выустанавливаются в состояние "0 . Пе- бора процесса, состоящий иэ первой репады потенциалов на нулевых выхо- группы элементов И, вторые входы кодах дифференцируются соответствую- торых подключены к синхровходу этого

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

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

1515170

12 групп — к инверсным выходам разрядов запроса и готовности управляющих регистров групп, прямые выходы разрядов запросов которого подключены к первым входам элементов И первой группы, а выходы разрядов кода номера задачи — к информационным входам блоков элементов И первой и второй групп, выходы которйх подключены соответственно к первым и вторым входам схем сравнения группы, выход первого элемента задержки соединен с вторыми входами элементов И третьей группы, с синхронизируюцими входами первого узла приоритета активного процесса и узла выбора процесса и через второй элемент задержки — с вхсдом стробирования узла коммутации, выходы элементов И третьей и первой групп подключены соответственно к единичным входам управляющих триггеров первой группы и буферного регистра запросов, группа выходов которого соединена с группой разрешающих вхо- 2» дов узла приоритета процессоров и с. группой входов первого элемента ИЛИ, первый вход группы управляющих выходов узла выбора процессора подключен к нулево у входу первого разряда 30 буферного регистра запросов, единичный вход триггера управления подключен к входу первого элемента задерж— ки и выходу первого элемента И,первый, второй и третий входы которого соединены соответственно с выход, и

3» генератора импульсов, первого и второго элементов ИЛИ, группа входов которого соединена с управляющими входами блоков элементов И второй группы и группой выходов буферного

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

45 единичным выходам разрядов готовности управляющих регистров группы,первые выходы управляющих триггеров первой и второй гругп соединены с вторыми входами элементов И соответственно первой и второй групп, треть-ими входами подключенных к нулевому выходу триггера у"правления, третьи входы элементов И тречьей группы попключены к выходу третьего элемента

ИЛИ, группа входов которого соедин"-на с выходами схем сравнения группы и с группой запросных входов первого узла приоритета активного процесса, группа выходов которого подключена к единичным входам управляюцих триггеров второй группы и группе нулевых входов буферного регистра готовности, о т и и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет коммутации процессов при реализации сильно связанных i араллельных алгоритмов, в узел коммутации соединения введены триггер пуска, входы которого являются управляющими вхоцами устройства, четвертый элемент ИЛИ, третий элемент задержки, второй и третий элементы И, второй узел приоритета активного процесса, синхронизируюпий вход которого подключен к единичному выходу триггера управления, группа выходов узла приоритета процессов соединена с группами запросных входов узла выбора процессора и второго узла приоритета активного процесса, группа выходов которого подключена к управляющим входам блоков элемен ов И первой группы, к первым входам элементов И третьей группы и к группе управляющих входов узла ьыбvpа процессора, вход управ ения кот рого соединен с выходом тре-; его элемента ИЛИ и инверсным входам третьего элемента И, прямой вход которого соединен с выходом гретьего элеме".та задержки, входом по;.ц,лючeниоrо:.: выходу первого элемента задержки, и с первым -.рямым входом втс рого элемента И., инверсный вход которого и;дключен к выходу второ о элемента И, а второй прямой вход соединен с выходами первого элемента ИЛИ и с вторым инверсным входом третьего ."лемента И, выход которого подключен к первому входу четвертого элемента ИЛИ, вторым входом с.оединенного с выходом второго элемента И, à BbL oäoì — с нулевым ьходом три1 "cpa управления, единичный выход григгера пуска подключен к четвертому входу первого элемента И.

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

1515170

14 ляющих входов соединен с первым и третьим прямым входами соответственно элементов И первой и второй групп и с первыми входами элементов ШП1 второй группы, второй вход группы управляющих кодов подключен к первому входу второго элемента И первой группы и вторым входам элементов ИЛИ второй группы, i-й вход группы управляющих входов (i = Э, 4,...,n, n— число процессоров) соединен с первым входом i-го элемента И первой группы и с i-м входом (i-1)-ro, i-ro,..., (и-2)-го элементов ИЛИ второй группы, j é вход группы запросных входов () = 2, 3, ..., и) подключен к первому прямому входу (j-1)-го элемента И второй группы, выход которо5 го соединен с вторым входом (j-1)-го элемента ИЛИ первой группы, первый вход которого подключен к выходу

j -го элемента И первой группы, выход (i-2)-ro элемента ИЛИ второй группы соединен с третьим прямым входом (i-1)-го элемента И второй группы, выход первого элемента И первой группы и выходы элементов ИЛИ первой группы являются группой выхо,дов узла выбора процессора.

1515170

1515170

Ъь

М