Устройство для формирования маршрута сообщения в однородной вычислительной системе

 

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

СО1ОЭ СОВЕТСКИХ

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

РЕСПУБЛИК

ВИ10ИИ"1Л

ЫПНЕ3- i -:::.ЛЫ!11Я

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

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

Б -,Б,!-1 . l,,!, ГОСУДАРСТВЕННЫЙ КОМИТЕТ

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

ПРИ ГКНТ СССР

f (21 ) 4390961/24-24 (22) 14. 01 . 88 (46) 15.09.89. Бюл. - 34 (72) В.А. Мельников, В.С. Харченко, П.И. Кныш и С.Б. Кальченко (53) 681 .325(088.8) (56) Авторское свидетельство СССР № 1249524, кл. G 06 F 15/16, 1984. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

МАРШРУТА СООБЩЕНИЯ В ОДНОРОДНОЙ

ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ (57) Изобретение относится к вычислительной технике и может быть использовано при построении высокопроизводительных матричных и векторных процессоров, в которых в процессе обработки информации происходит

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

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

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

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

„„Я0„„1508228 А 1

2 движение данных в вычислительной среде, при построении вычислительных систем с динамической архитектурой.

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

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

3 150822 ,транзитной передачи в направлении совпадения номеров (адресов) передатчика и приемника. Кроме сообщений, поступающих от соседних модулей системы, от супервизора системы поступают сообщения об отказах отдельных модулей, Эти сообщения заносятся в специальный регистр отказов. В блоке ассоциативной памяти на- 10 ходится информация о модулях-дублерах, которая модифицирует адресную

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

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

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

УсТроНсТВо для формирования марш- 50

- рута сообщений в однородной вычислительной системе,-. содержит первый — . девятый БПС 1.1-1.9, блок 2 ассоциативной памяти БВНП 3, блок 4 памяти константы, мультиплексор 5, КОП 6,. регистр 7 отказов, буферной регистр 8, БС 9, счетчик 10, дешифратор 11, демультиплексоры 12 и 13, триггер 14 запуска, блок 15 элемен-8 4 тов И, элемент ИЛИ 16 элемент И 17, управляющий вход 1.8 устройства, информационные входы 19.1-1.9.9 и выходы 20.1-20.9 устройства.

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

ИЛИ 23.1-23.К вЂ” 1, блок элементов И

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

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

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

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

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

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

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

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

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

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

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

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

508228

1О

Счетчик 0 совместно с дешифратором 11 служит для опроса БПС 1.! — 1.9.

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

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

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

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

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

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

1.1-1.9 в коммутатор 6 опроса.

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

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

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

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

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

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

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

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

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

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

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

ПЭ, девятое — на обработку собственному ПЭ) по следующему правилу.

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

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

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

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

Перед началом работы элементы памяти устройства находятся в нулевом состоянии. В блоке 3 памяти константы записан код адреса (код строки и код столбца) данного устройства относительно других устройств в регулярной однородной структуре вычислительной системы.

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

Нулевой сигнал с выхода элемента ИЛИ

16 не изменяет нулевого состояния триггера 14 залуска.

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

1508228

O

БПС 1.1-1.9 появляется единичный сигнал, который через элемент ИЛИ 16 устанавливает триггер 14 запуска в единичное состояние. Сигнал "1" на

5 прямом выходе триггера 14 поступает на управляющий вход БС 9, разрешая формирование тактовых имп льсов на его выходах пля синхронизации работы устройства.

Первый тактовый импульс с выхода блока 9 синхронизации., поступает на управляющий вход КОП 6. Так как регистр состояния, построенный на основе триггеров 3) .1 — 3) .9, находится в нулевом состоянии, то на выходе элемента И 34 присутствует сигнал

"1". Этот сигнал поступает на вход элемента 29 И и разрешает прохождение тактового импульса на управляющие входы элементов И 30.1-30.9.

Информация о состоянии соответствующих БПС 1.1-1.9 (о наличии поступивших сообщений) заносится в блок триггеров 31.1-31.9. Его состо- 25 яние отлично от нулевого и на выходе элемента И 34 появляется сигнал

О",запрещающий поступление тактового импульса через элемент И 29 на запись информации в блок триггеров 30

3I .1 -31 .9. Дешифратор 32 преобразу- ет позиционный ход состояния в унитарный код, определяющий последовательно начиная с первого в каКом

БПС находится поступившая информа35 ция. На соответствующем выходе дешифратора 32 появляется сигнал "1".

Этот сигнал на выходе шифратора ЗЗ образует позиционный ход, который поступает с выхода коммутатора 6 опроса на информационный вход счетчика 10. По второму тактовому импульсу с выхода БС 9 код опроса заносится в счетчик 10. На выходе дешифратора 11 и инициируется единичный сигнал опроса соответствующего БПС 1 .i (i = 1,9). Информация с соответствующего блока памяти сообщений I.i через мультиплексор

5 подается на информационный вход буферного регистра 8 и по третьему

50 тактовому импульсу, поступающему с выхода БС 9, сообщение заносится в буферный регистр 8. Поступившее сообщение состоит из двух частей—

55 адресной части и операционной.

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

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

Направление передачи информации осуществляется по минимальному физическому пути между модулями. системы на основе сравнения кодов из адресов в матрице процессорных элементов в однородной вычислительной среде.

После анализа кодов адресов на схемах 36 и 37 сравнения образуется код направления, поступающий с выхода

БВНП 3 на адресный (управляющий) вход демультиплексора 12. Информация с информационного входа демультиплексора 12 в зависимости от кода направления поступает на один из восьми выходов 20.1-20.8. к одному из соседних аналогичных устройств системы, Очередной тактовый импульс с выхода БС 9 поступает на информационный вход демультиплексора 13 синхронизации и в зависимости от кода направления, поступающего на управляющий вход демультиплексора 13, тактовый импульс выдается на соответствующий выход 20.1-20.9 устройства для синхронизации записи сообщения в БПС

1.1 — 1.9 соседнего устройства. Очередной тактовый имПульс поступает с выхода

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

508228

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

БПС, хранящему поступившие на обслуживание сообщения. !О

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

При обнулении блока триггеров

31.1-3!.9 КОП 6 на выходе элемента

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

Далее устройство функционирует ана35 логично описанному.

Если очереди сообщений в БПС 1.11.9 пусты, на выходе элемента ИЛИ 16 имеется сигнал 0". Этот сигнал поступает на инверсный вход элемента 40

И 17, разрешая при подаче последнего сообщения на соседнее устройство импульсом с выхода БС 9 обнуление триггера !4 запуска. На этом устройство завершает свою работу.

Запись информации от соседних аналогичных устройств или собственного

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

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

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

1 соответствующего элемента И 24.

БПС .i (i. 1,9) реализует дисциплины обуслуживания по правилу Первым пришел — первым обслужен .. Код, образованный выходами элементов И

24.1-24.К управляет процедурой эаписН поступающих сообщений в соответствующие регистры 22.1-22.К по мере их заполнения. Так при коде 11 11, поступающем на адресный вход демультиплексора 21, запись информации производится в регистр 22.1, при коде

11...10 — во второй регистр 22.2 и т.д. Одновременно с поступлением сообщения в БПС I.i поступает тактовый импульс. Этот импульс через элементы И 25. 1-25. К и элементы ИЛИ 26, 1-26. К поступает на синхронизирующие входы регистров 22. 1-22. К. Однако запись поступившего сообщения производится только в регистр 22.1, так как адресный ход демультиплексора 21 разреша4ет прохождение информации через блок

Т элементов ИЛИ 23.1 на информационt ный вход регистра 2 .1. Состояние этого регистра отлично от нуля. Управляющий код на выходах блока элементов И 25.1-25.Kизменяется и очередное сообщение заносится во второй регистр 22.2 и т.д- При измекении состояния одного из, К регистров 22.1-22.К на выходе элемента

И-HE 28 появляется сигнал "1", который поступает на управляющий выход соответствующего БПС 1.1-1.9. Сигнал "1" на управляющем выходе БПС

i .1 — 1.3 идентифицирует наличие информации, поступившей на обслуживание. По этому сигналу через элемент

ИЛИ 16, триггер 14 запуска устанавливается в единичное состояние и устройство начинает функционирование аналогично описанному. формула изобретения

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

1508228

Соотношение кодов

Код направления

Направление передачи сообщения

11!

001

101

011

010

Влево вверх

Вверх

Вправо вверх

Влево вниз

Вниз

Вправо вниз

Влево

Свой модуль

Вправо

В тД

В = Д

В Д

В)Д

B=D

В сд

В«Д

B=Д

B,Д

А= С

А =С .А )С А сС

А ..С

АсС

С

С

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

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

35 соединен с че тв ер тым выходом блока синхронизации, пятый выход которого соединен с управляющим входом блока памяти константы, выход которого подключен к первому входу блока вы- 40 бора направления передачи информации, первый выход которого соединен с управляющим входом второго демульÒàïðå îðà и первой группой управ. по вертикали по горизонтали ляющих входов первого демультиплексора, второй выход блока выбора направления передачи информации соединен с второй группой управляющих входов первого демультиплексора и управляющим входом блока элементов И, информационный вход которого соединен с первой группой выходов буферного регистра и с первой группой информационных входов второго демультиплексора, с первого по восьмой выхо- . ды второго демультиплексора, а также выход блока элементов И образуют с первого по девятый информационные выходы устройства, соответственно, с первого по девятый выходы первого демультиплексора образуют с первого по девятый управляющие выходы устройства соответственно, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет динамического изменения маршрута продвижения сообщения, в него введены блокассоциативной памяти, коммутатор опроса и регистр отказов, причем вторая группа выходов буферного регистра соединена с информационным входом блока ассоциативной памяти, выход которого подключен к второму входу блока выбора направления передачи информации и второй группе информационных входов второго демультиплексора, шестой выход блока синхронизации соединен с управляющим входом коммутатора опроса, информационный вход которого соединен с входом элемента ИЛИ, выход коммутатора опроса соединен с информационным входом счетчика, выход регистра отказов соединен с управляющим входом блока ассоциативной памяти, информационный вход и вход синхрони зации регистра отказов являются уп- равляющим входом устройства.

1508228

13f

1508228 фс/Р. 5

Составитель Л.Поливода, Техред А,Кравчук Корректор И.Муска

Редактор Л. Пчолинская

Заказ 5542/51 Тираж 668 Подписное

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

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

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