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

ООЭ СОВЕТСКИХ ОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН 0 С 5 4 С 06 Р 15/1 ВИ 50 ИИ"1 ЛяТВЕ- -: .ЛЫ 1 Б;Б : . А ОПИСАНИЕ ИЗОБРЕТЕНИР Харченко,редставых элемен- обмениГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР А ВТОРСНОМУ СВИДЕТЕЛЬСТ(56) Авторское свидетельство СССР В 1249524, кл. С 06 Р 5/16, 1984. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ МАРШРУТА СООБЩЕНИЯ В ОДНОРОДНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ(57) Изобретение относится к вычислительной технике и может быть использовано при построении высокопроизводительных матричных и вектор ных процессоров, в которых в процес се обработки информации происходит Изобретение относится к вычислительной технике и может быть использовано при построении высокопроизводительных матричных, конвейерных,систолических, векторных и другихпроцессоров, в которых в процессе обработки информации происходит движение данных в вычислительной среде,при построении вычислительных системс динамической архитектурой.Цель изобретения - расширение фунциональных возможностей устройстваза счет динамического изменения маршрута продвижения сообщения.Сущность изобретения заключаетсяв следующем,Вычислительная система иляет собой матрицу однотипнтов вычислительных модулей,вающихся сообщениями. Вычислительный движение данных в вычислительнойсреде, при построении вычислительныхсистем с динамической архитектурой.Цель изобретения - расширение функциональных возможностей устройстваза счет динамического изменения маршрута продвижения сообщения. Это достигается тем, что в устройство дополнительно введены блок ассоциативной памяти, коммутатор опроса и регистр отказов. Введение указанныхэлементов и порождаемых ими связейпозволяет осуществлять динамическиеизменения маршрутов продвижения сообщения в системе, порождаемые отказами отдельных элементов системы.5 ил. 1 табл. модуль может быть выполнен на процессорном (операционном),управляющем и коммутационном элементах. Коммутационный элемент служит для связи с соседними коммутационными элементами, а через них с процессорными или управляющими элементами. Каждому модулю (элементу) вычислительной системы присваивается определенный номер (адрес), идентифицирующий его местоположение в матрице модулей вычислительной системы (номер строки и номер столбца). Передаваемое сообщение состоит из адресной и смысловой (операционной частей). Адресная часть при поступлении сообщения в 1-й (д = ,И) модуль систе,мы сравнивается с его номером и в зависимости от отношения этих номе, ров осуществляется выбор дальнейшей,транзитной передачи в направлениисовпадения номеров (адресов) передатчика и приемника, Кроме сообщений, поступающих от соседних модулей системы, от супервизора системыпоступают сообщения об отказах отдельных модулей, Эти сообщения заносятся в специальный регистр отказов, В блоке ассоциативной памяти находится информация о модулях-дублерах, которая модифицирует адреснуючасть передаваемого сообщения. Возможность динамического изменениямаршрута передачи сообщений при отказе отдельных модулей системы ипередачи сообщения модулям-дублерампозволяет повысить отказоустойчивость системы, а следовательно, расширить область применения предложенного устройства.Расширение области примененияустройства достигается путем динамического изменения маршрута передачи сообщений в случае отказа отдельных модулей системы за счет естественной избыточности (или вводимой),обусловленной, во-первых тем, чточасть ресурсов повторяется в несколь-,ких модулях в целях оптимизации и, 30во-вторых, тем, что при закреплениипрограмм между модулями остаетсясвободной часть памяти. Свободноепространство памяти используетсядля хранения дублей, по которым35производится вычисления при отказахосновных модулей системы .На фиг. 1 представлена функциональная схема устройства для формированиямаршрута сообщений в однородной вычислительной системе; на фиг. 2 -функциональная схема -го (ь = 1,9)блока памяти сообщений (БПС); нафиг. 3 - функциональная схема коммутатора опроса (КОП)1 на фиг. 4 - 45функциональная схема блока выборанаправления передачи (БВНП) на фиг.5 Функциональная схема блока синхронизации (БС).устройство для формирования марш. рута сообщений в однородной вычислительной системе,- содержит первый - .девятый БПС 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,1 имеет демультиплексор 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 опроса предназначендля последовательного формированиякодов номеров блоков памяти сообщений содержащих информацию.1508228 30 35 5 10 15 20 25 40 45 50 55 щий местоположение устройства в системе (номер строки и номер столбца в матрице процессорных элементов). Передаваемое сообщение состоит из двух частей - адресной и операцион- ной. Адресная часть представляет код адреса ПЭ, которому предназначена данная операционная часть передаваемого сообщения.Выбор направления передачи сооб- щения происходит на основе анализа исполнительного адреса и кода адреса данного устройства. По номерам строк и столбцов определяется одно из девяти возможных направлений передачи (восемь направлений - на соседние ПЭ, девятое - на обработку собственному ПЭ) по следующему правилу. Пусть А и В коды адресов ПЭ-источника сообщения соответственно по вертикали и горизонтали размещения в матрице ПЭ, а С и Д коды адресов ПЭ-приемника сообщения, Процедура выбора направления передачи определяется таблицей. В свою очередь, исполнительный адрес ПЭ-источника информации определяется на основе анализа адресной части сообщения, поступающего с выхода первого поля буферного регистра 8 на вход блока 2 ассоциативной памяти, а кода состояния системы, поступающего с выхода регистра 7 отказов. Блок 2 ассоциативной памяти формирует исполнительную часть сообщения при появлении отказа в соответствующем модуле системы в зависимости от адреса ПЭ приемника информации.Перед началом работы элементы памяти устройства находятся в нулевом состоянии. В блоке 3 памяти константы записан код адреса (код строки и код столбца) данного устройства относительно других устройств в регулярной однородной структуре вычислительной системы.При отсутствии сообщений в БПС на их управляющих выходах присутствуют нулевые сигналы. которые не изменяют выходное состояние элемента ИЛИ 16. Нулевой сигнал с выхода элемента ИЛИ 16 не изменяет нулевого состояния триггера 14 запуска.При поступлении сообщений от соседних ПЗ однородной структуры на управляющих выходах соответствующих1508228 40 БПС 1,1-1,9 появляется единичный сигнал, который через элемент ИЛИ 16устанавливает триггер 14 запуска вединичное состояние. Сигнал "1" на5прямом выходе триггера 14 поступаетна управляющий вход БС 9, разрешаяформирование тактовых импульсов наего выходах для синхронизации работы устройства.10Первый тактовый импульс с выхода блока 9 синхронизации., поступает на управляющий вход КОП 6. Так как регистр состояния, построенный на основе триггеров 31,1-31 .9, находится в нулевом состоянии, то на выходеэлемента И 34 присутствует сигнал "1". Этот сигнал поступает на вход элемента 29 И и разрешает прохождение тактового импульса на управляющие входы элементов И 30.1-30.9.Информация о состоянии соответствующих БПС 1.1-1,9 (о наличии поступивших сообщений) заносится в блок триггеров 31,1-31.9, Его состо яние отлично от нулевого и на выходе элемента И 34 появляется сигнал 0",запрещающий поступление тактового импульса через элемент И 29 на запись информации в блок триггеров 3031,1-31.9. Дешифратор 32 преобразу-ет позиционный ход состояния в унитарный код, определяющий последовательно начиная с первого в каКом БПС находится поступившая информа 35 ция. На соответствующем выходе дешифратора 32 появляется сигнал "1". Этот сигнал на выходе шифратора ЗЗ образует позиционный ход, который поступает с выхода коммутатора 6 опроса на информационный вход счетчика 10. По второму тактовому импульсу с выхода БС 9 код опроса заносится в счетчик 10. На выходе дешифратора 11 и инициируется единичный сигнал опроса соответствующего БПС 1 . (1 = 1,9). Информация с соответствующего блока памяти сообщений 1,1 через мультиплексор 5 подается на информационный вход буферного регистра 8 и по третьему50 тактовому импульсу, поступающему с выхода БС 9, сообщение заносится в буферный регистр 8, Поступившее сообщение состоит из двух частей -55 адресной части и операционной.Выбор направления передачи сообщения осуществляется в зависимости от адресной части, хранимой в пер 8вом поле буферного регистра 8 и состояний отдельных модулей, хранимыхв регистре 7 отказов. Информация оботказах модулей, например, от супервизорного устройства вычислительнойсистемы, подается на вход 18 устройства 1-й Ц =1,Б, где Б - количество модулей в системе)триггеррегистра 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.1(на втором входе элемента И 27 находится сигналс соответствующеговыхода дешифратора 11) через соответствующие элементы ИЛИ 26.1-26.К на синхронизирующие входы блока регистров 22.1-22.К. В БПС 1.1 произ 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.1- 1.9 пусты, на выходе элемента ИЛИ 16 имеется сигнал О". Этот сигнал поступает на инверсный вход элемента 40 И 17, разрешая при подаче последнего сообщения на соседнее устройство импульсом с выхода БС 9 обнуление триггера 4 запуска. На этом устройство завершает свою работу.Запись информации от соседних аналогичных устройств или собственного ПЭ для анализа и дальнейшей передачи в вычислительной системе происходит следующим образом.Сообщение от соседнего устройства поступает на информационный вход соответствующего БПС 1, (. =1,9), с информационного входа БПС сообщение поступает на информационный вход демультиплексора 2. В начальный момент55времени блок регистров 22.1-22,К нахо дится в нулевом состоянии. На нулевых выходах 1-го (1 =1,К) регистра 22. сигналы "1" поступают на вход соответствующего элемента И 24.БПС 1,1. (1 1,9) реализует дисциплины обуслуживания по правилу Первым пришел - первым обслужен., Код, образованный выходами элементов И 24.1-24.К управляет процедурой эаписр поступающих сообщений в соответствующие регистры 22,1-22.К по мере их заполнения. Так при коде 1111, поступающем на адресный вход демультиплексора 21, запись информации производится в регистр 22.1, при коде .1110 - во второй регистр 22.2 и т.д. Одновременно с поступлением сообщения в БПС 1 поступает тактовый импульс. Этот импульс через элементы И 25. 1-25. К и элементы ИЛИ 26, 1-26. Кпоступает на синхронизирующие входырегистров 22.1-22.К. Однако записьпоступившего сообщения производитсятопько в регистр 22.1, так как адресный ход демультиплексора 21 разреша 4 ет прохождение информации через блокгэлементов ИЛИ 23,1 на информационный вход регистра 2".1, Состояниеэтого регистра отлично от нуля. Управляющий код на выходах блока элементов И 25,1-25,К изменяется и очередное сообщение заносится во второй регистр 22,2 и т.д. При измекении состояния одного из, К регистров 22.1-22.К на выходе элементаИ-НЕ 28 появляется сигнал "1", который поступает на управляющий выходсоответствующего БПС 1.1-1.9. Сигнал "1" на управляющем выходе БПС1.1-1.3 идентифицирует наличие информации, поступившей на обслуживание, По этому сигналу через элементИЛИ 16, триггер 14 запуска устанавливается в единичное состояние иустройство начинает функционированиеаналогично описанному,формула изобретенияУстройство для формирования маршрута сообщения в однородной вычислительной системе, содержащее девятьблоков памяти сообщений, блок выбора направления передачи информацииблок памяти константы, мультиплексор,буферный регистр, блок синхронизации,счетчик, дешифратор, два демультиплексора, триггер запуска, блок элементов И, элемент ИЛИ и элемент И,причем информационные входы с первого по девятый блоков памяти сообщений являются с первого по девятый1508228 12 Соотношение кодов Код на- правления Направление передачи сообщения 11 000 001 101 100 011 110 010 Влево вверхВверхВправо вверхВлево внизВнизВправо внизВлевоСвой модульВправо ВтДВ=ДВ ДВДВ=0ВДВ ДВ=ДВД А= С А: С А С А С А "-.С АСС С А=С информационными входами устройства соответственно, первые управляющие входы с первого по девятый блоков памяти сообщений соединены с первого по девятый выходами дешифратора5 соответственно, вторые управляющие входы с первого по девятый блоков памяти сообщений соединены с первым выходом блока синхронизации, информационные выходы с первого по девятый блоков памяти сообщений соединены с первого по девятый информационными входами мультиплексора соответственно, управляющие выходы с первого по девятый блоков памяти сообщений соединены с первого по девятый входами элемента ИЛИ соответственно, выход элемента ИЛИ подключен к входу установки в "1" триг гера запуска и инверсному входу элемента И, выход которого соединен с входом установки в 0 триггера запуска, выход которого соединен с входом блока синхронизации, второй вы ход которого подключен к прямому входу элемента И и информационному входу первого демультиплексора, третий выход блока синхронизации соединен со счетным входом счетчика, выход 30 ,которого соединен с входом дешифратора и управляющим входом мульти. плексора, выход которого соединен с информационным входом буферного ресгистра, вход синхронизации которого35 соединен с четвертым выходом блока синхронизации, пятый выход которого соединен с управляющим входом блокапамяти константы, выход которого подключен к первому входу блока выбора направления передачи информации, первый выход которого соединен с управляющим входом второго демульъпщеКдора и первой группой управ.по вертикали по горизонтали ляющих входов первого демультиплексора, второй выход блока выбора направления передачи информации соединен с второй группой управляющих входов первого демультиплексора и управляющим входом блока элементов И, информационный вход которого соединен с первой группой выходов буферного регистра и с первой группой информационных входов второго демультиплексора, с первого по восьмой выхо- . ды второго демультиплексора, а также выход блока элементов И образуют с первого по девятый информационные выходы устройства, соответственно, с первого по девятый выходы первого демультиплексора образуют с первого по девятый управляющие выходы устройства соответственно, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет динамического изменения маршрута продвижения сообщения, в него введены блокассоциативной памяти, коммутатор опроса и регистр отказов, причем вторая группа выходов буферного регистра соединена с информационным входом блока ассоциативной памяти, выход которого подключен к второму входу блока выбора направления передачи информации и второй группе информационных входов второго демультиплексора, шестой выход блока синхронизации соединен с управляющим входом коммутатора опроса, инФормационный вход которого соединен с входом элемента ИЛИ, выход коммутатора опроса соединен с информационным входом счетчика, выход регистра отказов соединен с управляющим входом блока ассоциативной памяти, информационный вход и вход синхронизации регистра отказов являются уп-равляющим входом устройства.1508228 ФОР, ЮСоставитель Л.ПоливодаРедактор Л. Пчолинская , Техред А,Кравчук Корректор И.Куска Заказ 5542/51 Тираж 668 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям113035, Москва, Я, Раушская наб., д. 4/5 КНТ ССС Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101