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

 

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

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

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

РЕСПУБЛИК,. SU„„1462344 А1 (5D 4 G 06 F 15/16

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

IlO ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4284146/24-24 (22) 13.07.87 (46) 28.02.89. Бюл. У 8 (72) В.А.Мельников, В.С.Харченко, Г,Н,Тимонькин и С.Н.Ткаченко (53) 681.325(088 ° 8) (56) Авторское свидетельство СССР

В 1179364, кл. G 06 F 15/16, 1984.

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

У 1287172, кл. G 06 F 15/16, 1986. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

МАРШРУТА СООБЩЕНИЯ В ОДНОРОДНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ (57) Изобретение относится к вычислительной технике и может быть использовано при построении высокопроизводительных матричных, конвейерных, систолических, векторных и других процессоров, в которых в процессе обработки информации происходит движение данных в вычислительной среде. Цель изобретения — повышение быстродействия устройства при одновременном сокращении аппаратурных затрат. Для достижения указанной цели в устройство дополнительно . введен блок 3 считывания информации ° что позволяет организовать обращения только к тем буферным запоминающим блокам 1.1.. ° 1.9 устройства, которые содержат сообщения, поступившие для обслуживания и таким образом исключить "пустые" циклы. 2 s.n. ф-лы. 6 ил.

1462344

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

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

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

Устройство для формирования мар- 30 шрута сообщения в однородной вычислительной системе (фиг.1) содержит группу буферных запоминающих блоков 1.1 - 1.9, блок 2 памяти констант, блок 3 считывания информации, регистр 4, демультиплексор 5, первый блок 6 сравнения, второй блок

7 сравнения, блок 8 элементов И, блок 9 элементов ИЛИ, элемент ИЛИ 10„ блок 11 синхронизации, элемент И 12,, ) 40 группу входов 13.1-13.9 устройства и группу выходов 14:1-14.9 устройст-. ва.

Буферный запоминающий блок 1.i 45 (i = 1,9) (фиг.2) содержит блок регистров 15.1-15.К (rpe К вЂ” глубина. очереди), блок коммутаторов 1616 (К-1),второй блок элементов И 17. 1

17.К, демультиплексор 18, элемент 5<

И-НЕ 19, триггер 20, элемент ИЛИ

21, одновибратор 22, первый блок 23 элементов И, Блок считывания информации (фиг.3) содержит блок триггеров 24.1-24.9, первый блок элемен- 55 тов И 25.1-25.9, второй блок элементов И 26.1-2619, блок одновибраторов

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

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

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

1.9. Регистр 4 предназначен для хранения адресной и операционной (смысловой) частей информации во время анализа и выбора направления передачи информации.

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

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

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

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

16.1-16,(К-1) предназначен для коммутации информации поступающих сообщений для записи их в соответствующий регистр блока регистров 15.1 з

14

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

Элемент И-HE 19 предназначен для формирования управляющего сигнала о наличии в блоке буферной памяти сообщения для его анализа и выдачи либо соседним устройствам системы, либо на обслуживание "закрепленному" процессорному элементу. Триггер 20 предназначен для управления процессом записи и сдвига информации в блоке регистров 15 ° 1-15.К.

Одновибратор 22 предназначен для формирования импульса на обнуление триггера 20 после организации сдвига информации в блоке регистров 15.1

15.К.

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

Блок триггеров 24.1-24.9 предназначен для хранения кода, определяющего в i-м разряде кода наличие сообщения в соответствующем блоке буферной памяти. Первый блок элементов И 25.1-25.9 предназначен для разрешения записи очередного кода состояний группы блоков 1 1-1 ° 9 6vферной памяти в блок триггеров 24.1

24.9. Второй блок элементов И 26.1

26.9 предназначен для последовательного формирования сигналов на опрос соответствующих блоков буферной памяти; i-й одновибратор (i = 1,9) бло ка одновибраторов 27.1-27.9 предназначен для формирования импульса на обнуление соответствующего тригге-. ра 24.i после считывания сообщения из соответствующего блока буферной памяти.

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

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

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

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

ПЭ. Выбор направления передачи сообщения определяется по следующему правилу:

55 л

С - А = D В, 62344

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

ro устройства.

Поступающая информация (сообщения) по любому иэ направлений заносится в соответствующий буферный запоминающий блок 1.i (i = 1,9) (фиг.1).

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

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

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

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

4О направлений (одно — на обработку дан« ному ПЭ и восемь других — на соседние ПЭ).

Пусть А — код номера строки приемника информации;  — код номера

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

44 - 25 = (4 ) 2) ti (4 (5) — вверх вправо

- 35 25 = (3 ) 2) Л (5 = 5) - вверх

-« 25 25 = (2 = 2) Л (5 = 5) - стоп

ЗО

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

5 (СП) и устройством-приемником (АВ) информации.

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

= А —. стой.

62 25 = (6 2) h (2

53 25 = (5 ) 2) М (3

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

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

Кроме адресной и операционной (смыс- 40 ловой) информации на. соответствующий вход 13.i (i = 1,9) поступает от соседних ПЭ тактовый импульс, по которому сообщение заносится в один из регистров 15.1-15.К блока (фиг.2) 45

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

-16 (К-1) иразрешает,тем самым,прохож- 55 дение информации с выходов демульти-, плексора 18 через соответствующие коммутаторы 16. 1-16.(К-1) на инфор.мационные входы регистров.

Перемещение по горизонтали определяется по правилу: если D > В— влево; если D ( — вправо; если

D = В - стой.

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

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

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

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

Сигнал логической единицы на управляющем входе блока 11 синхронизации (фиг.4) разрешает формирование импульсов на выходе генератора 29 для синхронизации работы устройства.

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

1462344 пии (фиг.3) через элемент И 28 разрешает запись информации о состоянии буферных запоминающих блоков

1.1-1.9 через блок элементов И 25.1—

25.9 в блок триггеров 24 ° 1-24.9.

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

24 ° 1"24.9 до окончания процедуры обслуживания записанного кода. Пред- 15 положим, что в блок триггеров 24.1

24.9 записан код 010100000, что соответствует наличию сообщений во втором и четвертом буферных запоминающих блоках 1.1-1.9 группы. Так 20 как на прямом выходе триггера 24.1 блока 3 считывания информации (фиг.3) находится сигнал логическоjro нуля, то первый тактовый импульс очередной импульсной последовательности с блока 11 синхронизации через элемент И 26,1 на считывание ин— формации из первого блока 1.1 пройдет. Этот импульс, поступая на входы

I блока элементов И 26.1-26.9, пройдет 30 через элемент И 26.2 на выход блока

3 считывания информации и с его выхода на управляющий вход буферного запоминающего блока 1 ° 2 (фиг.2). Импульс, поступающий на управляющий вход блока 1,2, разрешает выдачу информации через блок элементов И 23 с выхода регистра 15.1, в котором находится первое сообщение. Кроме того, управляющий импульс устанавли- 40 вает триггер 20 в единичное состояние сигнал с прямого выхода которого разрешает сдвиг информации в блоке регистров 15.1-15.К через коммутаторы 16.1-16.(К-1).

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

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

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

6 и 7 сравнения поступает идентификатор (код), определяющий местоположение данного устройства в матрице процессорных элементов.

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

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

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

В случае другой комбинации сравнения кодов (сигналы с выходов блоков

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

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

1.2 на выходе одновибратора 27.2 блока 3 считывания информации фор1462344

10 мируется импульс, устанавливающий триггер 24 ° 2 в нулевое состояние и разрешающий тем самым опрос наличия информации в других буферных запоми нающих блоках. Поэтому первый тактовый импульс очередной последовательности, поступая на тактовый вход блока 3 считывания информации, вы" ! ,дает импульс на считывание информа:ции из четвертого буферного запоми:нающего блока 1.4, поскольку хранимый

,в блоке триггеров 24.1-24.9 код ! ,: будет 000100000. Далее устройство функционирует аналогично описанно.MV

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

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

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

Сигналы логического нуля с управляющих выходов буферных запоминающих блоков 1.1-1.9 на выходе элемента

ИЛИ 10 образуют логический нуль.

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

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

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

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

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

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

И, соответственно, выход элемента

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

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

2. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что буфернык запоминающий блок содержит К регистров (где К вЂ” глубина очереди), (К-1) коммутаторов, К элементов И, . демультиплексор, блок элементов И, триггер, одновибратор, элемент ИЛИ ,и элемент И-НЕ, причем информационный вход демультиплексора является информационным входом блока i-й выход демультиплексора (i = 1,К-1) соединен с первым информационным входом i-ro коммутатора, К-й выход демультиплексора соединен с информационным входом К-го регистра, выход

j-го регистра (j = 2,К) соединен с вторым информационным входом (j-1)го коммутатора, выход i-го коммутатора соединен с информационным входом i-ro регистра, выход первого регистра соединен с первым

-входом блока элементов И, выход ко-! торого является информационным выходом блока, выход m-го регистра (m = 1,К) соединен с входом ш-го элемента И, выходы К элементов И соединены с управляющими входами демультиплексора и входами элемента

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

15 3. Устройство по п.1, о т л ич а ю щ е е с я тем, что блок считывания информации содержит блок триггеров, первый и второй блоки элементов И, блок одновибраторов

20 и элемент И, причем информационные входы блока считывания информации соединены с первыми входами первого блока элементов И, выходы которых соединены с входами установки блока триггеров, прямые выходы которого соединены с первыми входами ,соответствующего элемента И второго блока элементов И, выходы которых соединены с соответствующими выходами блока считывания информации и входами блока одновибраторов, выходы которых соединены с соответствующими входами сброса блока триггеров, инверсный .выход i-ro триг35 гера блока триггеров (х = 1 ° ...,9) с входами с (i+1)-го по девятый элементов И второго блока элементов

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

45 элементов И.

1462344

1462344

Фиг. б