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

СОЮЗ СОВЕТСНИСОЦИА ЛИСТ ИЧЕСНРЕСПУБЛИК(504 С 06 Г 15/ ГОСУДАРСТВЕННЫЙПО ИЗОБРЕТЕНИЯМ ИПРИ ГКНТ СССР ИТЕТРЫТИЯМ ИЗ ПИС ЕНИЯ К АВТОРСКО ИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССР 11 с 1179364, кл. С 06 Г 15/16, 1984Авторское свидетельство СССР У 1287172, кл. С 06 Р 15/16, 1986 (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ МАРШРУТА СООБЩЕНИЯ В ОДНОРОДНОЙ ВЫ ЧИСЛИТЕЛЬНОЙ СИСТЕМЕ(57) Изобретение относится к вычи тельной технике и может быть использовано при построении высокопроизводительных матричных, ксиве 801462 ных, систолических, векторных идругих процессоров, в которых в процессе обработки информации происходитдвижение данных в вычислительнойсреде. Цель изобретения - повышениебыстродействия устройства при одновременном сокращении аппаратурных за.трат, Для достижения указанной целив устройство дополнительно .введенблок 3 считывания информациичтопозволяет организовать обращениятолько к тем буферным запоминающимблокам 1.11.9 устройства, которые содержат сообщения, поступившиедля обслуживания и таким образомисключить "пустые" циклы. 2 з.п.ф-лы, 6 ил,Изобретение относится к вычислительной технике и может быть исполь" зовано при построении высокопроизводительных матричных, конвейер 5 ных, систолических, векторных и других процессоров, в которых в процессе обработки информации происходит движение данных в вычислительной среде. 1 ОЦелью изобретения является повышение быстродействия устройства при одновременном сокращении аппаратурных затрат.На фиг.1 представлена функцио" 15 нальная схема предлагаемого устройства для формирования маршрута сообщения в однородной вычислительной- системе; на фиг.2 - Функциональная схема буферного запоминающего бло- , 20 ка; на фиг.З - функциональная схема блока считывания информации; на фиг.4 - Функциональная схема блока синхронизации; на фиг.5 - формат сообщения; на фиг.6 - пример путей 25 прохождения данных между процессорными элементами (ПЭ) модульной вычислительной системы для известного и предложенного технических решений.Устройство для формирования мар шрута сообщения в однородной вычислительной системе (фиг.1) содержит группу буферных запоминающих блоков 1.1 - 1.9, блок 2 памяти констант, блок 3 считывания информации, 35 регистр 4, демультиплексор 5, первый блок 6 сравнения, второй блок 7 сравнения, блок 8 элементов И, блок 9 элементов ИЛИ, элемент ИЛИ 10 блок 11 синхронизации, элемент И 12 ) 40 группу входов 13.1-13.9 устройства и группу выходов 14:1-14.9 устройст-, ва. Буферный запоминающий блок 1.1 45 И = Г,9) (Фиг,2) содержит блокрегистров 15.1-15.К (где К - глубина очереди), блок коммутаторов 16- .16(К),второй блок элементов И 17.1 17.К, демультиплексор 18, элемент И-НЕ 19, триггер 20, элемент ИЛИ 21, одновибратор 22, первый блок 23 элементов И, Блок считывания информации (фиг.З) содержит блок триггеров 24.1-24.9, первый блок элемен тов И 25.1-25.9, второй блок элементов И 26.1-2619, блок одновибраторов 2. 1-27.9, элемент И 28. Блок 11 синхронизации (фиг.4) содержит гене" ратор 29 тактовых импульсов, счетчик 30, дешифратор 31.Назначение основных функциональных элементов устройства состоит вследующем.Группа буферных запоминающихблоков 1.1-1.9 предназначена дляорганизации очередей данных, поступающих от восьми соседних устройстви собственного процессорного элемента (ПЭ) для передачи информациисоседним устройствам. Блок 2 памяти констант предназначен для хранения кода (идентификатора), определяющего местоположение устройствав матрице процессорных элементов(однородной вычислительной систе-.ме), Блок 3 считывания информациипредназначен для циклического опроса и выборки информации из группыбуферных запоминающих блоков 1.11.9. Регистр 4 предназначен для хранения адресной и операционной (смыс. ловой) частей информации во времяанализа и выбора направления передачи информации.Демультиплексор 5 предназначен для коммутации сообщения в одном из восьми направлений к соседним устройствам (процессорным элементам), Первый 6 и второй 7 блоки сравнения предназначены для анализа адресной части поступившего на обслуживание сообщения. Блок 8 элементов И предназначен для разрешения записи (передачи) операционной (смысловой) части сообщения, при совпадении адресных частей устройства и поступившего сообщения. Блок 11 синхронизации предназначен для задания последовательностей импульсов для синхронизации работы устройства.Назначение элементов -го буферного запоминающего блока (1 = 1,9) (фиг,2) состоит в следующем.Блок регистров 15,1-15.К предназначен для хранения и организации очереди поступивших на обслуживаниесообщений; 3"й элемент И ( = 1.К) блока элементов И 17.1-17,К предназначен для формирования управляющего сигнала, идентифицирующего нулевое состояние соответствующего регистра 15 Блок коммутаторов16,1-16,(К) предназначен для коммутации информации поступающих сообщений для записи их в соответствующий регистр блока регистров 15.1з1415.К. Демультиплексор 18 предназна"чен для коюутации (распределения)поступающих на обслуживание сообщений в порядке их поступления в блокрегистров 15 .1-15 .К в зависимостиот занятости очереди.Элемент И-НЕ 19 предназначен дляформирования управляющего сигнала оналичии в блоке буферной памяти сообщения для его анализа и выдачилибо соседним устройствам системы,либо на обслуживание "закрепленному" процессорному элементу. Триггер 20 предназначен для управленияпроцессом записи и сдвига информации в блоке регистров 151-15.К.Одновибратор 22 предназначен дляформирования импульса на обнулениетриггера 20 после организации сдвигаинформации в блоке регистров 15.115.К.Назначение элементов блока считывания информации 3 (фиг.3) состоит в следующем.Блок триггеров 24.1-24.9 предназначен для хранения кода, определяющего в -м разряде кода наличиесообщения в соответствующем блокебуферной памяти. Первый блок элементов И 25.1-25.9 предназначен дляразрешения записи очередного кодасостояний группы блоков 1,1-19 бчферной памяти в блок триггеров 24.124.9. Второй блок элементов И 26,126.9 предназначен для последовательного формирования сигналов на опроссоответствующих блоков буферной памяти; х-й одновибратор (1 = 1,9) блока одновибраторов 27.1-27.9 предназначен для формирования импульса наобнуление соответствующего тригге-.ра 24.ь после считывания сообщенияиз соответствующего блока буфернойпамяти.Элемент И 28 предназначен для фор"мирования сигнала о нулевом состоянии блока триггеров 24,1-24.9 и разрешения записи очередного кода состояния группы буферных запоминающих блоков 11-1,9,Рассмотрим работу устройства дляформирования маршрута сообщения воднородной вычислительной системе,В исходном состоянии элементы памяти устройства находятся в нулевомсостоянии.Модульная вычислительная системапредставляет собой регулярную оджения устройства в столбце матрицыПЭ. Выбор направления передачи сообщения определяется по следующемуправилу: л С -е- А = В - В, 623444нородную структуру, каждый процессорный элемент которой соединен повосьми направлениям с соседними процессорными элементами, Передачаинформации между любыми ПЭ вычислительной системы осуществляется транзитным способом по минимальномуфизическому пути через другие ПЭмассива, например по восьми возможнымнаправлениям с помощью предлагаемо -го устройства.Поступающая информация (сообщения)по любому иэ направлений заноситсяв соответствующий буферный запоминающий блок 1.1 (д = 1,9) (фиг.1).Информация о передаваемом сообщении заносится как от восьми соседних аналогичных устройств системы,так и "собственного" процессорногоэлемента (ПЭ) вычислительной системы, Каждому ПЭ вычислительной системы (предлагаемому устройству) присваивается адрес, состоящий из 25 двух кодов, определяющих местоположение ПЭ, а следовательно, и устройства в матрице ПЭ, и соответствует .номеру строки и номеру столбца(фиг.6). Данный адрес является идентификатором по отношению к другимустройствам вычислительной системы.Выбор направления передачи поступившего сообщения в предлагаемомустройстве происходит следующим образом.Адресная часть поступившего сообщения (фиг.5) с адресом данного устройства по номерам строки и столбцаопределяет одно из девяти возможныхнаправлений (одно - на обработку данному ПЭ и восемь других - на соседние ПЭ).Пусть А - код номера строки приемника информации; В - код номера 45 столбца приемника информации. Тогдакод адресной части сообщения можетбыть представлен как А Ф В, где Фзнак конкатенации (сцепления) двухкодов. Соответственно, код адресаустройства (идентификатор) можетбыть представлен как С Ф Р, где С -код местоположения устройства в строке матрицы ПЭ, а Р - код местополо-1 25 - 25 = (2 = 2) Л (5 = 5) - стоп ЗО 5 14623 т.е. выбор направления передачи сообщения определяется минимальным фи. зическим расстоянием между устройством-передатчиком информации5 (СП) и устройством-приемником (АВ) информации.Тогда передача сообщения в вер-тикальном направлении определяется следующим образом: если С ) А - вверх; если С ( А - вниз; если С = = А - . стой. 62 - 25 = (62)(2 53 - 25 = (5 ) 2) М (3 Рассмотренная процедура передачи сообщения направлена на минимизацию физического пути между процес-, сорными элементами вычислительной системы.Информация от соседних ПЭ однородной структуры (например, при передаче данных между процессорными элементами в систолическом массиве) поступает на предлагаемое устройство для ее анализа и транзитной выдачи в соответствующий канал (направление) устройства. Данная ин- . формация поступает на входы 13.1-13.9 устройства для занесения ее в буферные запоминающие блоки 1.1-1.9. Кроме адресной и операционной (смыс О ловой) информации на. соответствующий вход 13.1 ( = 1,9) поступает от соседних ПЭ тактовый импульс, по которому сообщение заносится в один из регистров 15.1-15.К блока (фиг.2) 46 В буферном запоминающем блоке 1. ( = 1,9) по мере поступления сообщения начинают заполнять регистры,. начиная с первого, следующим обра" зом. Так как триггер 20 находится в нулевом состоянии, то сигнал логи.ческой единицы с инверсного выхода триггера 20 поступаетна управляющие входы блока коммутаторов 16,1 -16 (К) иразрешает,тем самым,прохож- бб дение информации с выходов демульти-, плексора 18 через соответствующие коммугаторы 16. 1-16,(К) на информационные входы регистров. Перемещение по горизонтали определяется по правилу; если 0 ) В - влево; если П ( В - вправо; если 0 = В - стой.Например, требуется осуществить передачу сообщения от устройства, имеющего адрес в матрице ПЭ 62 (фиг.6), к устройству с адресом 25.Процедура выбора направления передачи сообщения может быть представлена следующим образом: ( 5) - вверх вправо В начальный момент времени блок регистров 15.1-15.К находится в нулевом состоянии, и на выходе элементов И 171-17.К находятся сигналы логической единицы. Эти сигналы (код) поступают на управляющий вход демультиплексора 18 и разрешают,запись поступившего сообщения в регистр 15.1. Состояние этого регистра отлично от нулевого, что изменяет код, поступающий на управляющий вход демультиплексора 18 и подготавливает его выход для записи очередного сообщения в регистр 15.2 и т.д.При занесении информации в буферные запоминающие блоки на выходе элемента И-НЕ 19 (фиг.2) соответствующего блока появляется сигнал логической единицы, Этот сигнал (сигналы) с выходов буферных запоминающих блоков поступают, во-первых, через элемент ИЛИ 10 (фиг,1) на управляющий вход блока 11 синхронизации, во-вторых, на информационные входы блока считывания информации.Сигнал логической единицы на управляющем входе блока 11 синхройизации (фиг.4) разрешает формирование импульсов на выходе генератора 29 для синхронизации работы устройства.Так как триггеры 24.1-24.9 находятся в нулевом состоянии то первый тактовый импульс, поступающий с выхода блока 11 синхронизации иа вход блока 3 считывания информу.ции (фиг.3) через элемент И 28 разрешает запись информации о состоянии буферных запоминающих блоков 1.1-1.9 через блок элементов И 25.1 - 25.9 в блок триггеров 241-24,9,При запйси информации в блок триггеров 24.1-24,9 его состояние отлично от нулевого и поэтому на выходе элемента И 28 сигнал логиче ского нуля, который запрещает запись информации с входов блока 3 считывания информации в блок триггеров 241"24,9 до окончания процедуры обслуживания записанного кода, Пред положим, что в блок триггеров 24,1 24.9 записан код 010100000, что соответствует наличию сообщений во втором и четвертом буферных запоминающих блоках 1.1-1.9 группы, Так 20 как на прямом выходе триггера 24.1 блока 3 считывания информации (фиг.3) находится сигнал логического нуля, то первый тактовый импульс очередной импульсной последовательности с блока 11 синхронизации через элемент И 26.1 на считывание ин - формации из первого блока 1.1 пройдет. Этот импульс, поступая на входыблока элементов И 26.1-26.9, пройдет 30 через элемент И 26,2 на выход блока 3 считывания информации и с его выхода на управляющий вход буферного запоминающего блока 12 (фиг,2), Импульс, поступающий на управляющий вход блока 1,2, разрешает выдачу информации через блок элементов И 23 с выходарегистра 15.1, в котором находится первое сообщение. Кроме того, управляющий импульс устанавли вает триггер 20 в единичное состояние сигнал с прямого выхода которого разрешает сдвиг информации в блоке регистров 15.1-15.К через коммутаторы 16.1-16,(К).45Информация с выходов регистра 15.1 буферного запоминающего блока 1,2 через блок элементов И 23 (фиг.2) через блок 9 элементов ИЛИ (фиг.1) поступает на информационный вход регистра 4, По тактовому импульсу с выхода блока 11 синхронизации по-. ступившая информация заносится в регистр 4. После записи информации в регистр 4 по срезу импульсапоступившего на управляющий вход блока 1,2, происходит сдвиг информации в блоке регистров 1.5.1-15.К (фиг.2). На выходе одновибратора 22 формируется жпульс, который устанавливает триггер 20 в исходное (нулевое) состояние и тем самым разрешается запись поступающих в буферный запоминающий блок 1,2 сообщений.Записанная по второму тактовому импульсу информация (фиг.5) содержит операционную (смысловую) часть и адресную часть. При этом адресная часть содержит два поля, определяющих местоположение приемника информации в матрице ПЭ по вертикали и горизонтали. Адресная информация поступает на входы блоков 6 и 7 сравнения. По третьему тактовому импульсу последовательности с выхода блока 2 памяти констант на вторые входы блоков 6 и 7 сравнения поступает идентификатор (код), определяющий местоположение данного устройства в матрице процессорных элементов.В зависимости от соотношения этих двух кодов формируется направление 1дальнейшей передачи сообщения. При совпадении кодов как по вертикали, так и по горизонтали на выходах первого 6 и второго 7 блоков сравнения формируются сигналы "Равно". Эти сигналы на выходе элемента И 12 образу" ют сигнал, идентифицирующий факт о том,что поступившее сообщение предназначено данному процессорному элементу, Этот сигнал, поступая на управляющий вход блока 8 элементов И одновременно с тактовым импульсом, разрешает прохождение смысловой информации на выход 14.1 устройства для записи, например, в ОЗУ процессорного элемента с целью последующей обработки поступившего сообщения. В случае другой комбинации сравнения кодов (сигналы с выходов блоков 6 и 7 сравнения поступают на управляющий вход демультиплексора 5) ре-шающее правило выбора направления дальнейшей передачи сообщения реализуется дешифратором демультиплек-. сора 5. Сообщение с тактовым импульсом через демультиплексор 5 и один из выходов 14.2-14.9 поступает к од-, ному из соседних аналогичных устройств системы.После выдачи управляющего сигнала на считывание информации из второго буферного запоминающего блока 1.2 на выходе одновибратора 27.2 блока 3 считывания информации фор 1462344 1035 мируется импульс, устанавливающийтриггер 242 в нулевое состояние иразрешающий тем самым опрос наличияинформации в других буферных запоми нающих блоках. Поэтому первый тактовый импульс очередной последовательности, поступая на тактовый входблока 3 считывания информации, вы",дает импульс на считывание информа:ции из четвертого буферного запоми:нающего блока 1.4, поскольку хранимый,будет 000100000. Далее устройствофункционирует аналогично описанно.Му аПри обнулении блокатриггеров24.1-24.9 блока 3 считывания инфор:мации (фиг.3) очередной тактовый импульс через элемент И 28 поступаетна управляющие входы элементовИ 25.1-25.9 и разрешает запись очередного кода на обслуживание техбуферных запоминающих блоков 1.11.9, в которых имеются сообщения дляпередачи. Далее устройство функционирует аналогично описанному.При выдаче сообщений соседнимустройствам и "собственному" ПЗрегистры 15.1-15,К буферных запоминающих .блоков 1.1-1.9 находятся внулевом состоянии. На выходах элементов И 17,1-17.К находятся сигналы логической единицы, которые поступают на вход элемента И-НЕ 19и образуют сигнал логического нуля,идентифицирующий отсутствие сообщения в соответствующем буферномзапоминающем блоке . 1. (д = 1.9) .Сигналы логического нуля с управляющих выходов буферных запоминающихблоков 1.1-1.9 на выходе элементаИЛИ 10 образуют логический нуль.Этот сигнал запрещает формированиетактовых импульсов на выходах блока 11 синхронизации, и устройствозаканчивает работу,Формула изобретения;1. Устройство для формирования маршрута сообщения в однородной вы" числительной системе, содержащее девять буферных запоминающих блоков,блок памяти констант, регистр, де. мультиплексор, два блока сравнения, блок элементов И, блок элементов ИЛИ, элемент ИЛИ, блок синхронизации и элемент И, причем информационные входы с первого по девятый бу 10 15 20 25 30 40 45 50 55 ферных запоминающих блоков являются с первого по девятый информационными входами устройства соответственно, первые управляющие входы с первого по девятый буферных запоминающих блоков являются с первого по девятый управляющими. входами устройства соответственно, информационные выходы с первого по девятый буферных запоминающих блоков соединены с первого по девятый входами блока элементов ИЛИ, с первого по девятый управляющие выходы буферных запоминающих блоков соединены с первого по девятый выходами элемента ИЛИ соответственно, выход блока элементов ИЛИ подключен к информационному входу регистра, вход синхронизации которого соединен с первым выходом блока синхронизации, вход запуска которого подключен к выходу элемента ИЛИ, второй выход блока синхронизации соединен с входом синхронизации блока памяти констант, выход которого подключен к первым входам первого и второго блоков сравнения соответственно, выходы первой и второй группы регистра соединены с вторыми входами первого и второго блоков сравнения соответственно, выходы третьей группы регистра и третий выход блока синхронизации подключены к разрядам первого входа элементов И, вьгоды первой, второй и третьей групп регистра и третий выход блока синхронизации соединены с разрядами информационного входа демультиплексора, выход Больше, Меньше и Равно первого и второго блоков сравнения соединены с первого по шестой управляющими входами демультиплексора соответственно, выходы Равно первого и второго блоков сравнения соединены с первым и вторым входами элемента И, соответственно, выход элемента И подключен к второму входу блока элементов И выход которого является первым выходом устройства, с первого по восьмой выходы демультиплексора являются с второго по девятый выходами устройства соответственно, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия при одновременном сокращении аппаратурных затрат, в него введен блок считывания информации, с первого по девятый выходы которого со 1462344 12единены с вторыми управляющими входами с первого по девятый буферных запоминающих блоков соответственно, с первого по девятый информационные входы блока считывания информации соединены с управляющими выходами с первого по девятый буферных запоминающих блоков соответственно, синхронизирующий вход блока считывания информации соединен с четвертым выходом блока синхронизации.2. Устройство по п,1, о т л и - ч. а ю щ е е с я тем, что буфернык запоминающий блок содержит К регистров (где К - глубина очереди), (К) коммутаторов, К элементов И демультиплексор, блок элементов И, триггер, одновибратор, элемент ИЛИ ,и элемент И-НЕ, причем информационный вход демультиплексора является информационным входом блока д-й выход демультиплексора (д = 1,К) соединен с первым информационным входом -го коммутатора, К-й выход демультиплексора соединен с информационным входом К-го регистра, выход 3-го регистра (3 = 2,К) соединен с вторым информационным входом (3-1)- го коммутатора, выход -го коммутатора соединен с информационным вхоЯом д-го регистра, выход первого регистра соединен с первым входом блока элементов И, выход которого является информационным выходом блока, выход а-го регистра (ш = 1,К) соединен с входом ш-го элемента И, выходы К элементов И соединены с управляющими входами демультиплексора и входами элемента И-НЕ, выход которого является управляющим выходом блока, первый и второй входы элемента ИЛИ являются первьщ и вторым управляющими входами блока соответственно, первый вход элемента ИЛИ соединен с входом ус. тановки единицы триггера и с вторымвходом блока элементов И, выход элемента ИЛИ подключен к входам синхро,низации всех регистров, прямой выходтриггера соединен с вхопом одновибратора и с первыми управляющимивходами всех коммутаторов, инверсный выход триггера соединен с вторыми управляющими входами всех коммутаторов, выход одновибратора соединен с входом установки нуля триггера.15 3. Устройство по п.1, о т л ич а ю щ е е с я тем, что блок считывания информации содержит блоктриггеров, первый и второй блокиэлементов И, блок одновибраторов 20 и элемент И, причем информационныевходы блока считывания информациисоединены с первыми входами первого блока элементов И, выходы которых соединены с входами установкиблока триггеров, прямые выходы которого соединены с первыми входами,соответствующего элемента И второго блока элементов И, выходы которых соединены с соответствующими З 0 выходами блока считывания информации и входами блока одновибраторов, выходы которых соединены с соответствующими входами сброса блокатриггеров, инверсный .выход -го триг гера блока триггеров (х = 1,9)с входами с (+1)-го по девятый элементов И второго блока элементовИ и с входами элемента И, выход которого соединен с вторыми входами эле ментов И второго блока элементов И,синхронизирующий вход блока считывания информации соединен с тактовымвходом элемента И и соответствующимивходами элементов И второго блока 45 элементов И