Устройство для формирования маршрута сообщения в однородной вычислительной системе Советский патент 1989 года по МПК G06F15/177 

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

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

Сущность изобретения заключается в следующем.

Вычислительная система представляет собой матрицу однотипных элементов вычислительных модулей, обменивающихся сообщениями. Вычислительный

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

00 Ьд tsd

оо

транзитной передачи в направлении совпадения номеров (адресов) передатчика и приемника. Кроме сообщений, поступающих от соседних модулей системы, от супервизора системы поступают сообщения об отказах отдельных модулей, Эти сообщения заносятся в специальный рег истр отказов. В блоке ассоциативной памяти на-jQ 24.1-24.К. блок элементов И 25.1-25.К,

тов И, элемент ИЛИ 16, элемент И 17, управляющий вход 1.8 устройства, информационные входы 19.1-1.9.9 и выходы 20.1-20.9 устройства.

БПС l.i имеет демультиплексор 21, блок регистров 22.1-22.К (где К - глубина очереди), группу элементов ИЛИ 23.1-23.К-1, блок элементов И

24.1-24.К. блок элементов И 25.1-25.К

тов И, элемент ИЛИ 16, элемент И 17, управляющий вход 1.8 устройства, информационные входы 19.1-1.9.9 и выходы 20.1-20.9 устройства.

БПС l.i имеет демультиплексор 21, блок регистров 22.1-22.К (где К - глубина очереди), группу элементов ИЛИ 23.1-23.К-1, блок элементов И

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

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

Расширение области применения устройства достигается путем динамического изменения маршрута передачи сообщений в случае отказа отдельных модулей системы за счет естественной избыточности (или вводимой), обусловленной, во-первых тем, что часть ресурсов повторяется в несколь30

35

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

На фиг. 1 представлена функциональная схема устройства для формирования маршрута сообщений в однородной вы- 40

числительной системе-, на фиг. 2 -

функциональная схема i-ro (1 1,9 блока памяти сообщений (БПС); на фиг. 3 - функциональная схема коммутатора опроса (КОП), на фиг. 4 - функциональная схема блока выбора направления передачи (БВНП); на фиг.5- функциональная схема блока синхронизации (БС) .

Устройство для формирования марш- рута сообщений в однородной вычислительной системе содержит первьй - 1 девятый БПС 1.1-1.9, блок 2 ассо- ц.иативной памя.ти БВНП 3, блок 4 памяти константы, мультиплексор 5, КОП 6,. р€1гистр 7 отказов, буферной регистр 8, ЕС 9, счетчик JО, дешифратор М , демультиплексорь 12 и 13, триггер 14 запуска, блок 15 элемен 45

50

55

5

0

5

0

5

0

5

0

5

блок элементов ИЛИ 26.1-26.К, элемент И 27 и элемент И-НЕ 28.

КОП 6 образуют элемент И 29, блок элементов И 30.1-30.9, блок триггеров 31.1-31.9, дешифратор 32, шифратор 33, элемент 34 И и блок 35.1- 35.9 одновибраторов.

БВНП 3 (фиг. 4) содержит две схемы 36 и 37 сравнения и элемент И 38.

Блок 9 синхронизации состоит из генератора 39 тактовых импульсов, счетчика 40, дешифратора 41 и триггера 42.

Первый - -девятый БПС 1.1-1.9 предназначены для организации очередей сообщений, поступающих от восьми соседних устройств и собственно про- цессорного элемента.

Блок 2 ассоциативной памяти формирует код адресной части сообщения : в зависимости от состояния вычислительной системы (отказов отдельных модулей).

БВНП 3 предназначен для выбора и модификации направления передачи поступивших сообщений в зависимости от адреса получателя сообщения и кода адреса устройства.

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

Мультиплексор 5 коммутирует входные сообщения.

Регистр 7 отказов предназначен для хранения кода состояния вычислительной системы. Буферньй регистр 8 для хранения кода сообщения на время анализа и обработки.

Блок 9 синхронизации используется для задания последовательности синхронизирующих импульсов.

Коммутатор 6 опроса предназначен для последовательного формирования кодов номеров блоков памяти сообщений содержащих информацию.

Счетчик 10 совместно с дешифратором 11 служит для опроса БПС 1.1-1.9.

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

Демультиплексор 13 коммутирует импульс синхронизации на один из девяти выходов устройства.

Синхронизация работы устройства происходит по импульсам, которые фор- . мируются: на первом - шестом выходах БС 9 и представляют собой шесть импульсных последовательностей. Такт (цикл) работы состоит из шести фаз. Каждая фаза работы устройства начинается тактовым импульсом соответствующей импульсной последовательности.

По первому тактовому импульсу происходит запись кода состояния БПС 1.1-1.9 в коммутатор 6 опроса.

По второму тактовому импульсу происходит обращение к соответствующему 25 выбора направления передачи опредеблоку памяти сообщений путем записи кода состояния блоков памяти в счетчик 10.

По третьему тактовому импульсу производится запись сообщения в буфер ный регистр 8.

По четвертому тактовому импульсу происходит обращение к блоку 4 памяти констант.

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

По шестому тактовому импульсу про- 40 Щем модуле системы в зависимости от

изводится сдвиг информации в блоке памяти сообщений, из которого было сосчитано сообщение на обработку. Далее цикл работы устройства пов50

торяется путем обращения к очередно- 45 записан код адреса (код строки и му блоку памяти сообщений.

Рассмотрим работу устройства для формирования маршрута сообщения в регулярных однородных структурах.

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

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

При отсутствии сообщений в БПС на их управляющих выходах присутствуют нулевые сигналы, которые не изменяют выходное состояние элемента ИЛИ 16. Нулевой сигнал с выхода элемента ИЛИ 55 16 не изменяет нулевого состояния триггера 14 запуска.

При поступлении .сообщений от соседних ПЭ однородной структуры на управляющих выходах соответствчтощих

щий местоположение устройства в системе (номер строки и номер столбца i в матрице процессорных элементов) Передаваемое сообщение состоит из двух частей - адресной и операцион- ной. Адресная часть представляет код адреса ПЭ, которому предназначена данная операционная часть передаваемого сообщения.

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

0

0

ляется таблицей.

В свою очередь, исполнительный адрес ПЭ-источника информации определяется на основе анализа адресной части сообщения, поступающего с, выхода первого поля буферного регистра 8 на вход блока 2 ассоциативной памяти, а кода состояния системы, поступающего с выхода регистра 7 от- 5 казов.

I

Блок 2 ассоциативной памяти формирует исполнительную часть сообщения при появлении отказа в соответствуюадреса ПЭ приемника информации.

Перед началом работы элементы памяти устройства находятся в нулевом состоянии. В блоке 3 памяти констан50

45 записан код адреса (код строки и

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

При отсутствии сообщений в БПС на их управляющих выходах присутствуют нулевые сигналы, которые не изменяют выходное состояние элемента ИЛИ 16. Нулевой сигнал с выхода элемента ИЛИ 55 16 не изменяет нулевого состояния триггера 14 запуска.

При поступлении .сообщений от соседних ПЭ однородной структуры на управляющих выходах соответствчтощих

10

15

20

7 1508228

БПС 1.1-1.9 появляется единичный сигнал который через элемент ИЛИ 16 устанавливает триггер 14 запуска в единичное состояние. Сигнал 1 на прямом выходе триггера 14 поступает на упраззляющий вход БС 9, разрешая формирование тактовых импvльcoв на его выходах для синхронизации работы устройства.

Первый тактовый импульс -с выхода блока 9 синхронизации, поступает на правляющий вход КОП 6. Так как реистр состояния, построенный на основе триггеров 3J.1-3J.9, находится в нулевом состоянии, то на выходе элемента И 34 присутствует сигнал 1. Этот сигнал поступает на вход элемента 29 И и разрешает прохождение тактового импульса на управляюие входы элементов И 30.1-30.9.

Информация о состоянии соответствующих БПС 1.1-1.9 (о наличии поступивших сообщений) заносится в блок триггеров 31.1-31.9. Его состояние отлично от нулевого и на выхое элемента И 34 появляется сигнал о,запрещающий поступление тактового импульса через элемент И 29 на запись информации в блок триггеров 31 .1-31 .9. Дешифратор 32 преобразует позиционный ход состояния в унитарный код, определяющий последовательно начиная с первого в каком БПС находится поступившая информация. На соответствующем выходе дешифратора 32 появляется сигнал 1. Этот сигнал на выходе шифратора 33 образует позиционный ход, который поступает с выхода коммутатора 6 опроса на информационный вход счетчика 10. По второму тактовому импульсу с выхода БС 9 код опроса заносится в счетчик 10. На выходе дешифратора 11 и инициируется единичный сигнал соответствующего БПС 1.1 (i 1,9). Информация с соответствующего блока памяти сообщений l.i через мультиплексор 5 подается на. информационный вход буферного регистра 8 и по третьему тактовому импульсу, поступающему с выхода ЕС 9, сообщение заносится в буферньй регистр 8. Поступившее сообщение состоит из двух частей - адресной части и операционной.

Выбор направления передачи сообщения осуществляется в зависимости от адресной части, хранимой в первв о в с ч о м н

ж и х к л

25 д с н в о м н в с пл н в и с

х ны ни п .щи вы щи

50 си та БС из ин по ди

30

35

40

45

55

10

5

0

8228

8

вом поле буферного регистра 8 и состояний отдельных модулей, хранимых в регистре 7 отказов. Информация об отказах модулей, например, от супер- визорного устройства вычислительной системы, подается на вход 18 устройства j-й (J -I,N-I, где N - количество модулей в системе)триггер регистра 7 определяет состояние соответствующего модуля системы. Если модуль, которому необходимо передавать сообщение, находится в состоянии отказа, то адресная часть сообщения модифицируется блоком 2 ассоциативной памяти.

Блок 2 ассоциативной памяти может быть выполнен в виде программируемой логической матрицы и хранит информацию о модулях, которым необходимо передавать информацию при отказах основных модулей. При отсутствии- отказа соответствующего модуля адресная часть сообщения без мо5 дификации поступает на вход БВНП 3. Направление передачи информации осуществляется по минимальному физическому пути между модулями системы на основе сравнения кодов из адресов в матри1,е процессорных элементов в однородной вычислительной среде. После анализа кодов адресов на схемах 36 и 37 сравнения образуется код направления, поступающий с выхода ББНП 3 на адресный (управляющий) вход демультиплексора 12. Информация с информационного входа демультиплексора 12 в зависимости от кода направления поступает на один из восьми выходов 20.1-20.8, к одному из соседних аналогичных устройств системы..

Очередной тактовый импульс с выхода БС 9 поступает на информационный вход демультиплексора 13 синхронизации и в зависимости от кода направления, поступающего на управляю- .щий вход демультиплексора 13, тактовый импульс выдается на соответствующий выход 20.1-20.9 устройства для

0 синхронизации записи сообщения в БПС 1 .1-1 .9 соседнего устройства.Очередной тактовый .имПульс поступает с выхода БС 9 на тактовый вход БПС сообщений, из которого производилась выборка информации для анализа. Этот импульс поступает через элемент И 27 БПС 1.i (на втором входе элементам 27 находится сигнал 1 с соответствующего

0

5

0

5

5

выхода дешифратора 11) через соответствующие элементы ИЛИ 26.1-26.К на синхронизирующие входы блока регистров 22.1-22.К. В БПС l.i производится сдвиг информации. Далее устройство функционирует аналогично: проводится обращение к очередному БПС, хранящему поступившие на обслуживание сообщения.

При совпадении кодов адресов модуля приемника информации с адресной частью принятого сообщения на выходах Равно первой 36 и второй 37 схем сравнения БВНП 3 формируются сигналы 1. На выходе элемента И 38 имеется сигнал 1. Этот сигнал с выхода блока 3 выбора направления передачи поступает на вход блок 15 элементов И, разрешая прохождение операционной части сообщения с выхода второго поля буферного регистра 8 на выход 20.9 устройства для дальнейшей его обработки собственным ПЭ.

При обнулении блока триггеров 31.1-31.9 КОП 6 на выходе элемента И 34 имеется сигнал 1. Этот сигнал поступает на вход элемента И 29, разренгая по первому импульсу очередной последовательности запись информации о состоянии блоков 1.1-1.9 памяти сообщений в коммутатор 6 опроса Далее устройство функционирует аналогично описанному.

Если очереди сообщений в БПС 1.1- 1.9 пусты, на выходе элемента ИЛИ 16 имеется сигнал О. Этот сигнал поступает на инверсный вход элемента И 17, разрешая при подаче последнего сообщения на соседнее устройство импульсом с выхода БС 9 обнуление триггера 14 запуска. На этом устройство завершает свою работу.

Запись информации от соседних аналогичных устройств или собственного ПЭ для анализа и дальнейшей передачи в вычислительной системе происходит следующим образом.

Сообщение от соседнего устройства поступает на информационный вход соответствующего БПС l.i (i 1,9), с информационного входа БПС сообщение поступает на информационный вход демультиплексора 21. В начальный момен

времени блок регистров 22.1-22.К нахо- дится в нулевом состоянии. На нулевых выходах j-ro (л 1,К) регист

10

15

08228И)

ра 22.j сигналы 1 поступают на вход соответствующего элемента И 24.

БПС 1.1 (i 1,9) реализует дисцип- ЛИНЫ обуслуживания по правилу Первым пришел - первым обслужен., Код, образованный выходами элементов И 24.1-24.К управляет процедурой запис11 поступающих сообщений в соответствующие регистры 22.1-22.К по мере их заполнения. Так при коде 1 1 ... 1 I , поступающем на адресньп т вход демульти- плексора 21, запись информации производится в регистр 22.1, при коде . 11...10 - во второй регистр 22.2 и т.д. Одновременно с поступлением сообщения в БПС l.i поступает тактовый импульс. Этот импульс через элементы И 25 . 1 -25 . К и элементы ИЛИ 26.1-26.К поступает на синхронизирующие входы регистров 22.1-22.К. Однако запись . поступивп его сообщения производится только в регистр 22.15 так как адрес- ный ход демультштлексора 21 разреша- прохождение информации через блок элементов ИЛИ 23.1 на информацион- ный вход регистра 22..1. .Состояние этого регистра отлично от нуля. Управляющий код на выходах блока элементов И 25.1-25.К изменяется и оче-- редное сообщение заносится во второй регистр 22.2 и т.д. При изменении состояния одного из. К регистров 22.1-22.К на выходе элемента И-НЕ 28 появляется сигнал 1, кото- рьй поступает на управляющий выход соответствующего БПС 1.1-1.9. Сиг20

30

35

нал 1 на управляющем выходе БПС 1.1-1.3 идентифицирует наличие информации, поступившей на обслуживание. По этому сигналу через элемент ИЛИ 16, триггер 14 запуска устанавливается в единичное состояние и устройство начинает функционирование аналогично описанному. Формула изобретения Устройство для формирования маршрута сообщения в однородной вычисли- .тельной системе, содержащее девять блоков памяти сообщений, блок выбора направления передачи информации, блок памяти константы, мультиплексор, буферный регистр,блок синхронизации;, счетчик, дешифратор, два демульти- плексора, триггер запуска,- блок эле- ментов И, элемент ИЛИ и элемент И, причем информационные входы с первого по девятый блоков памяти сообщений являются с первого по девятый

П I 508228

информационными входами устройства соответственно, первые управляющие входы с первого по девятый блоков памяти сообщений соединены с первого по девятый выходами дешифратора соответственно, вторые управляющие входы с первого по девятый блоков памяти сообщений соединены с первым выходом блока синхронизации, инфор- JQ ма;ционные выходы с первого по девятый блоков памяти сообщений соединены с первого по девятый информационными входами мультиплексора соответственно, управляющие выходы 15 с первого по девятый блоков памяти сообщений соединены с первого по девятый входами элемента ИЛИ соответственно, выход элемента ИЛИ подключен к входу установки в 1 триггера запуска и инверсному входу элемента И, выход которого соединен с входом установки в О триггера запуска, выход которого соединен с входом блока синхронизации, второй выход которого подключен к прямому входу элемента И и информационному входу первого демультиплексора, третий выход блока синхронизации соединен со счетным входом счетчика, которого соединен тора и управляющим входом мульти- плексора, выход которого соединен с информационным входом буферного регистра, вход синхронизации которого соединен с четвертым выходом блока синхронизации, пятый выход которого соединен с управляющим входом блока памяти констйнты, выход которого подключен к первому входу блока вы- 40 бора направления передачи информа- дни, первый выход которого соединен С управляницим входом второго демуль- типдексора и первой группой управ20

25

выход 30 с входом дешифра35

ля со пр не в и с м пл ж в п м в ю ш з ш в п н п в г в з

В, Д Б Д

в П

в Д

12

5 0

0

5

0

5

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

Влево вверх

Вверх

Вправо вверх

Влево вниз

Вниз

Вправо вниз

Влево Свой модуль

Вправо

И.

fltf

Sk

3

33