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

It

- (fntf.t

т/

5

I

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

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

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

Устройство для формирования мар- шрута сообщения в однородной вычислительной системе (фиг.1) содержит группу буферньк запоминающих блоков 1.1 - 1.9, блок 2 памяти констант, блок 3 считывания информации, регистр 4, демультиплёксор 5, первый блок 6 сравнения, второй блок 7 сравнения, блок 8 элементов И, блок 9 элементов ИЛИ, элемент ИЛИ Ю блок 11 синхронизации,элемент И 12,, j группу входов 13.1-13.9 устройства и группу выходов 14.-1-14.9 устройства.

Буферный запоминающий блок 1.1 (i f7 (фиг.2) содержит блок регистров 15.1-15.К Хгде К - глубина очереди), блок коммутаторов 16 -.

.16(К-1),второй блок элементов И 17.1 17.К, демультиплёксор 18, элемент И-НЕ 19, т риггер 20, элемент ИЛИ 21, одновибратор 22, первый блок 23 элементов И. Блок считывания информации (фиг.З) содержит блок триггеров 24.1-24.9, первый блок элемен- тов И 25.1-25.9, второй блок элементов И 26., блок одновибраторов

27.1-27.9, элемент И 28. Блок 11 синхронизации (фиг.4) содержит генератор 29 тактовых импульсов, счетчик 30, дешифратор 31.

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

Группа буферных запоминающих блоков 1.1-1.9 предназначена для организации очередей данных, поступающих от восьми соседних устройств к собственного процессорного элемента (ПЭ) для передачи информации соседним устройствам. Блок 2 памяти констант предназначен для хранения кода (идентификатора), определяющего местоположение устройства в матрице процессорных элементов (однородной вычислительной систе-. ме). Блок 3 считьгаания информации предназначен для циклического опроса и выборки информации из группы буферных запоминающих блоков 1.1 - 1.9. Регистр 4 предназначен для хранения адресной и операционной (смысловой) частей информации во время анализа и выбора направления передачи информации.

Демультиплёксор 5 предназначен для коммутации сообщения в одном из восьми направлений к соседним устройствам (процессорным элементам). Первый 6 и второй 7 блоки сравнения предназначены для анализа адресной части поступившего на обслуживание сообщения. Блок 8 элементов И предназначен Для разрешения записи (передачи) операционной (смысловой) части сообщения, при совпадении адресных частей устройства и поступившего сообщения. Блок 11 синхронизации предназначен для задания последовательностей импульсов дпя синхронизации работы устройства,

Назначение элементов i-ro буфер- ного запоминающего блока (i 1,9) (фиг.2) состоит в следующем.

Блок регистров 15.1-15.К предназначен для хранения и организации очереди поступивших на обслуживание сообщений; j-й элемент И (j 1.К) блока элементов И 17.1-17.К предназначен для формирования управляюще- ,гр сигнала, идентифицирующего нулевое состояние соответствующего регистра 15.1. Блок коммутаторов 16.1-16.(К-1) предназначен для KOMJ мутации информации поступающих сообщений для записи их в соответствующий регистр блока регистров 15.1

15.К. Демультиплексор 18 предназначен для коммутации (распределения) поступающих на обслуживание сообщений в порядке их поступления в блок регистров 15.1-15.К в зависимости от занятости очереди.

Элемент И-НЕ 19 предназначен для формирования управляющего сигнала о наличии в блоке буферной памяти сообщения для его анализа и выдачи либо соседним устройствам системы, либо на обслуживание закрепленному процессорному элементу. Триггер 20 предназначен для управления процессом записи и сдвига информации в блоке регистров 15.1-15.К. Одновибратор 22 предназначен для формирования импульса на обнуление

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

ТО массива, например по восьми возможн направлениям с помощью предлагаемо го устройства.

Поступающая информация (сообщени по любому из направлений заносится

15 в соответствующий буферный запоминающий блок 1.1 (i 1,9) (фиг.О. Информация о передаваемом сообщении заносится как от восьми соседних аналогичных устройств системы.

триггера 20 после организации сдвига 20 гз собственного процессорного

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

информации в блоке регистров 15.1 - 15.К.

Назначение элементов блока считывания информации 3 (фиг.З) состоит в следующем.

Блок триггеров 24.1-24.9 предназначен для хранения кода, определяющего в i-M разряде кода наличие сообщения в соответствующем блоке

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

буферной памяти. Первый блок элемен- 30 тификатором по отнощению к другим

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

массива, например по восьми возможным направлениям с помощью предлагаемо- го устройства.

Поступающая информация (сообщения) по любому из направлений заносится

в соответствующий буферный запоминающий блок 1.1 (i 1,9) (фиг.О. Информация о передаваемом сообщении заносится как от восьми соседних аналогичных устройств системы.

гз собственного процессорного

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

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

тов И 25.1-25.9 предназначен для разрешения записи очередного кода состояний группы блоков 1.1-1.9 буферной памяти в блок триггеров 24.1 24.9. Второй блок элементов И 26.1 - 26.9 предназначен для последовательного формирования сигналов иа опрос соответствующих блоков буферной памяти; i-й одновибратор (i 1,9) блока одновибраторов 27.1-27.9 предна- значен для формирования импульса на обнуление соответствующего триггера 24.1 после считывания сообщения из соответствующего блока буферной памяти.

Элемент И 28 предназначен для формирования сигнала о нулевом состоянии блока триггеров 24.1-24.9 и разрешения записи очередного кода состояния группы буферных запоминающих блоков 1.1-1.9.

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

b исходном состоянии элементы па- мяти устройства находятся в нулевом состоянии.

Модульная вычислительная система представляет собой регулярную од

5 0

g

устройствам вычислительной системы.

Выбор направления передачи посту- пивЩего сообщения в предлагаемом устройстве происходит следующим образом.

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

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

С - А D - В,

т.е выбор направления передачи соощения определяется минимальным физическим расстоянием между устройством-передатчиком информации (CD) и устройством-приемником (АВ) информации.

Тогда передача сообщения в вертикальном направлении определяется следующим образом: если С А - вверх; если С - А - вниз; если С - А -, стой.

62

25 (6 7 2) Л (2 5)

-5.3 - 25 (5 2) Л (3 : 5)

- 44 - 25 (4 2) / (4 г 5)

-35 - 25 (3 2) Л (5 5)

- 25

25 (2 2) / (5 5)

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

Информация от соседних ПЭ од- норЪдной структуры (например, при передаче данных между процессорными элементами в систолическом массиве) поступает на предлагаемое устройство для ее анализа и транзитной выдачи в соответствующий канал (направление) устройства. Данная информация поступает на входы 13.1-13, устройства для занесения ее в буферные запоминающие блоки 1.1-1.9. Кроме адресной и операционной (смысловой) информации на.сооТветствую- щий вход 13.1 (1 1,9) поступает от соседних ПЭ тактовый импульс, по которому сообщение заносится в один из регистров 15.1-15.К блока (фиг.2) В буферном запоминающем блоке 1.1 (1 1,9) по мере поступления сообщения начинают заполнять регистры, начиная с первого, следующим образом. Так как триггер 20 находится в нулевом со стоянии, то сигнал логической единицы с инверсного выхода триггера 20 поступает на управляющие входы блока коммутаторов 16.1 - ; 16 (К-1) и разрешает, тем самым, прохождение информации с выходов демульти- плексора 18 через соответствующие коммутаторы 16.1-16.(К-1) на информационные входы регистров.

Перемещение по горизонтали определяется по правилу: если D В - йлево; если D i В - вправо; если D В - стой.

Например, требуется осуществить передачу сообщения от устройства, имеющего адрес в матрице ПЭ 62 (фиг.6), к устройству с адресом 25,

Процедура выбора направления передачи сообщения может быть представлена следующим образом:

вправо вправо вправо

25

30

В начальный .момент времени блок регистров 15.1-15.К находится в нулевом состоянии, и на выходе элементов И 17.1-17.К находятся сигналы логической единицы. Эти сигналы (код) поступают на управляющий вход демультиплексора 18 и разрешают.за-, пись поступившего сообщения в регистр 15о1о Состояние этого регистра отли чно от нулевого, что изменяет код, поступающий на управляющий 35 вход демультиплексора 1В и подготавливает его выход для записи очередкого сообщения в регистр 15,2 и т.д.

При занесении информации в ферные запоминающие блоки на выходе элемента И-НЕ 19 (фиг.2) соответствующего блока появляется сигнал логической единицы. Этот сигнал (сигналы) с выходов буферных запоми- 5 нающих блоков поступают, во-первых, через элемент ИЛИ 10 (фиг.1) на управляющий вход блока 11 синхронизации, во-вторых, на информационные входы блока считывания информации. 50 Сигнал логической единицы на управляющем входе блока 11 синхронизации (фиг.4) разрешает формирование импульсов на выходе генератора 29 для синхронизации работы устройства.

55 Так как триггеры 24.1-24.9 находятся в нулевом состоянии, то первый тактовый импульс, поступающий с выхода блока 11 синхронизации на вход блока 3 считывания информч

НИИ (фиг.З) через элемент И 28 разрешает запись информации о состоянии буферных запоминающих блоков 1,1-1.9 через блок элементов И 25.1 25.9 в блок триггеров 24.1-24.9.

При записи информации в блок триггеров 24.1-24.9 его состояние отлично от нулевого и поэтому на выходе элемента И 28 сигнал логиче- ского нуля, который запрещает запись информации с входов блока 3 считывания информации в блок триггеров 24.1-24.9 до окончания процедуры обслуживания записанного кода. Пред- положим, что в блок триггеров 24.1 - 24.9 записан код 010100000, что соответствует наличию сообщений во втором и четвертом буферных запоминающих блоках 1.1-1.9 группы. Так как на прямом выходе триггера 24.1 блока 3 считывания информации (фиг.З) находится сигнал логического нуля, то первый тактовый импульс очередной импульсной последователь- ности с блока 11 синхронизации через элемент И 26.1 на считывание информации из первого блока 1 о 1 пройдет. Этот импульс, поступая на входы блока элементов И 26.1-26.9, пройдет через элемент И 26.2 на выход блока 3 считывания информации и с его выхода на управляющий вход буферного запоминающего блока 1.2 (фиг.2.). Импульс, поступающий на управляющий вход блока 1.2, разрешает выдачу информации через блок элементов И 23 с выхода регистра 15.1, в котором находится первое сообщение. Кроме то- го управляющий импульс устанавли- вает триггер 20 в единичное состояние, сигнал с прямого выхода которого разрешает сдвиг информации в блоке регистров 15.1-15.К через коммутаторы 16.1-16,(К-1),

Информация с выходов регистра 15 буферного запоминающего блока 1.2 через блок элементов И 23 (фиг.2) через блок 9 элементов ИЛИ (фиг.1) поступает на информационный вход регистра 4. По тактовому импульсу с выхода блока 11 синхронизации поступившая информация заносится в регистр Л. После записи информации в регистр 4 по срезу импульса,по- ступившего на управляющий вход блока 1о2, происходит сдвиг информации в блоке регистров 15.1-15.К (фиг.2). На выходе однрвибратора

22 формируется импульс, который устанавливает триггер 20 в исходное (нулевое) состояние и тем самым разрешается запись поступающих в буферный запоминающий блок- 1.2 сообщений.

Записанная по второму тактовому импульсу информация (фиг.5) содержит операционную (смысловую) часть и адресную часть. При этом адресная част содержит два поля, определяющих местоположение приемника информации в матрице ПЭ по вертикали и горизонтали. Адресная информация поступает на входы блоков 6 и 7 сравнения. По третьему тактовому импульсу последовательности с выхода блока 2 памяти констант на вторые входы блоков 6 и 7 сравнения поступает идентификатор (код), определяюпцсй местоположение данного устройства в матрице процессорных элементов.

В зависимости от соотношения этих двух кодов формируется направление

дальнейшей передачи сообщения. При совпгщении кодов как по вертикали, так и по горизонтали на выходах первого 6 и второго 7 блоков сравнения формируются сигналы Равно. Эти сигналы на выходе элемента И 12 образуют сигнал, идентифицирующий факт о том,что поступившее сообщение предназначено данному процессорному элементу. Этот сигнал, поступая на управляющий вход блока 8 элементов И одновременно с тактовым импульсом, разрешает прохождение смысловой информации на выход 14.1 устройства для записи, например, в ОЗУ процессорного элемента с целью последующей обработки поступившего сообщения

В случае другой комбинации сравнения кодов (сигналы с выходов блоков 6 и 7 сравнения поступают на управляющий вход демультиплексора 5) ре- шающее правило выбора направления дальнейшей передачи сообщения реализуется дешифратором демультиплексора 5. Сообщение с тактов ым импульсом через демультиплексор 5 и один из выходов 14.2-14.9 поступает к одному из соседних аналогичных устройств системы.

После выдачи управляющего сигнала на считывание информации из второго буферного запоминающего блока 1.2 на выходе одновибратора 27.2 блока 3 считывания информации формируется импульс, устанавливающий триггер 24.2 в нулевое состояние и разрешающий тем самым опрос наличия информации в других буферных запоминающих блоках. Поэтому первьй тактовый импульс очередной последовательности, поступая на тактовый вход блока 3 считывания информации, вы дает импульс на считывание информа- ции из четвертого буферного запоминающего блока 1.4, поскольку хранимы b блоке триггеров 24.1-24.9 код Ьудет 0001000СГО. Далее устройство гфункционирует аналогично описанноJMV.

При обнулении блока-триггеров 2Л.1-24.9 блока 3 считывания информации (фиг.З) очередной тактовый им- пульс через элемент И 28 поступает на управляющие входы элементов ;И 25.1-25.9 и разрешает запись оче- |редного кода на обслуживание тех буферных запоминающих блоков 1.1- 1.9, в которых имеются сообщения для :передачи. Далее устройство функционирует аналогично описанному.

При вьщаче сообщений соседним устройствам и собственному ПЭ регистры 15.1-15.К буферных запоми- .блоков 1.1-1.9 находятся в нулевом состоянии. На выходах элементов И 17.1-17.К находятся сигналы логической единицы, которые поступают на вход элемента И-НЕ 19 и образуют сигнал-логического нуля, идентифицирующий отсутствие сообщения в соответствующем буферном запоминающем блоке .1.i (i - 1.9), Сигналы логического нуля с управляющих, выходов буферных запоминающих блоков 1.1-1.9 на выходе элемента ИЛИ 10 образуют логический нуль. Этот сигнал запрещает формирование тактовых импульсов на выходах бло- : ка l l синхронизации, и устройство заканчивает работу.

Формула изобретения

.1 . Устройство для формирования

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

0

5

0

JQ

55

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

5 входа элементов И, выходы первой, второй и третьей групп регистра и третий выход блока синхронизации соединены с разрядами информационного входа демультиплексора, выход Боль0 ше, Меньше и Равно первого и - второго блоков сравнения соединены с первого по шестой управляющими входами демультиплексора соответст- венно, выходы Равно первого и

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

-входом блока элементов И, выход которого является информационным йыхо- дом блока, выход т-го регистра

(т 1,К) соединен с входом т-го элемента И, выходы К элементов И соединены с управляющими входами демультиплексора и входами элемента И-НЕ, выход которого является управляющим выходом блока, первый и второй входы элемента ШТИ являются первым и вторым управляющими входами ;блока соответственно, первый вход

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

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

О

ft

ш

«

8

ТТг

&1

Фив. 2

29

Фиг 3

t/

JO

:

J7

Фи&.

Codep ufioe регистра

Смысловая инфорпоцип

Фиг. 5

11

А I А I /ч I I УЧ I

5

21

Ж

12 1гЛ/5

13

22

Ж

8

И

2-5

15

16

24

/

26

хкю ахскг

- J/ - JZ - JJ - JV - 55 J5 -

:D

1

42

51

25

1Ъ

3

52

ЦЧ

53

45

5

6

55

56

:j jc3cj c3c:x

61

mjL

дЗ

Адрес устройства приемника инсрорг ации

Адрес приепни- па по Вертикали патриц ы ПЭ

5

И

15

16

24

/

26

ЦЧ

45

6

55

56

6

65

66