Устройство для распределения заданий процессорам

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К ABTOPCKOMY СВИДЕТЕЛЬСТВУ

Союз Советскик

Социапистическик

Республик () )) 976442 (6l ) ДОполнительное к авт. свил-ву (5l)M. Кл.

G 06 F 9/00 (22) Заявлено 07.05.81(2I ) 3283537/18-24 с присоединением заявки М (23) Приоритет

Ваударстванаб квинтет

СССР ао явлаи нзебретеннй н вткрытнй

Опубликоваио23,11.82. Бюллетень J% 43 (5З) УДК681.325 (088.8) Дата опубликования описания 26.11.82 (72) Авторы изобретения

М. П. Вольнов и Ю. Н. Долгин (7I ) Заявитель (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОЦЕССОРАМ

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

Известно устройство для сопряжения процессов, содержащее блок коммутации, 5 блок настройки, блок управления и блок передачи, объединенные между собой внутренними шинами и предназначенное для сопряжения отдельных ЭВМ в единую однородную вычислительную систему (1). 10

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

Наиболее близким к изобретению по технической сущности и достигаемому результату является устройство для распределения заданий процессорам, содержащее

И процессоров, регистр сдвига, регистр готовности процессоров, первый блок из

20 групп элементов И н первый блок из И групп элементов ИЛИ (2), Недостатком устройства является низкая производительность, являющаяся след

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

Целью изобретения является увеличение пропускной способности устройства.

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

3. - 9764 готовности устройства, введены кодовый селектор, вторая группа из И блоков элементов И, вторая группа из И элементов

ИЛИ, элемент И, причем первые входы каждого блока элементов И второй груп пы соединены с первыми входами одноименных блоков. элементов первой группы .

И, выходы каждого блока элементов И второй группы - с соответствующими выходами группы информационных выходов устройства и с входами соответствующих элементов ИЛИ второй группы, выходы которьи.соединены с группой входов сброса регистра готовности процессоров, инверсный выход каждого 4-го (а 1... И) раз- ряда регистра готовности процессоров со-, единены с вторыми входами (1+1)-ro блока элементов И первой и второй групп, второй вход первого блока элементов И и третьи входы остальных блоков элементов

И первой группы соединены с первым вы ходом кодового селектора, второй вход первого и третьи входы остальных блоков элементов И соединены с вторым вьиодом кодового селектора, первый вход кбторого

2$ соединен с адресным входом устройства, второй вход кодового селектора соединен .с числовым входом устройства, группа входов кодового селектора соединена с. группой выходов регистра сдвига, вход которого соединен с тактовым входом устройства, сигнальный выход устройства соединен с выходом элемента И, входы которого соединены с прямыми выходами

Регистра готовности процессоров, 35

Кроме того, кодовый селектор содержит 2И регистров и треугольную матри цу элементов сравнения размерности (у-1) ° (и- 1), (гдето = !), каждый элемент сравнения которой в свою очередь содержит схему сравнения и два блока элементов И, причем первый вход каждого регистра, соединен с первым входом кодового селектора, второй вход каждого регистра соединен с вторым входом кодо 45 вого селектора, первый вьиод первого регистра соединен с первым входом каждой схемы сравнения первой строки треуголь-, ной матрицы элементов сравнения,:a первые выходы каждого j -го регистра, на- 50 чиная с второго, соединены с первым входом каждой схемы сравнения j -ой стро ки треугольной матрицы элементов сравнения и к второму входу каждой схемы сравнения а -го столбца треугольной мат- $$ рицы элементов сравнения, выход схемы сравнения каждого элемента сравнения треугольнои матрицы элементов сравнения соединен с первыми входами обоих блоков элементов И своего элемента сравнения треугольной матрицы элементов сравнения, вторые входы которых соедиI иены между собой и с соответствующим входом группы входов кодового селектора, вторые выходы первого регистра соединены с третьими входами каждого первого блока. элементов И первой строки треугольной матрицы элементов сравнения, а вторые выходы каждого 4-го регистра, начиная с второго, соединены с третьими входами каждого первого блока элементов

И q -ой строки треугольной матрицы элементов сравнения и с третьими выходами каждого второго блока элементов И i -ro столбца треугольной матрицы элементов сравнения, выходы первых блоков элемен тов g каждой строки треугольной матрицы элементов сравнения соединены с первым выходом кодового селектора, выходы вторых блоков элементов И каждой строки треугольной матрицы элементов сравнения соединены с вторым выходом кодового селектора.

На фиг. 1. приведена структурная схема устройства для распределения заданий процессорам; на фиг. 2 †. структурная схема кодового селектора. устройство содержит регистр 1 готовности процессоров, группы блоков элемен- . тов И 2 и 3, группы элементов ИЛИ 4 и 5, регистр 6 сдвига, кодовый селектор

7, элемент И 8, тактовый вход 9 устройства, сигнальный выход 10 устройства, адресный вход 11 устройства, числовой вход 12. устройства, выходы 13 и 14 кодового селектора 7, группу информационньи выходов 15 устройства, группу входов 16 готовности устройства, группу входов 17 кодового селектора 7 °

Кодовый селектор содержит регистр 18, треугольную матрицу 19 элементов сравнения. Элементы 20 сравнения матрицы

19 содержат схему 21 сравнения, блоки

22 и 23 элементов И.

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

42 6 ра 7 равно максимальному числу пар операндов, участвующих в работе.

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

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

4 и 5.

Первый операнд с выхода 13 селектора 7 поступает на входы каждого блока 2 а второй операнд с выходов 14 селектора 7 одновременно с первым подается на входы каждого блока 3. Прохождение операндов через блоки 2 и 3 обеспечивается разрешающим сигналом готовности процессоров, который подается с группы прямых выходов регистра 1, на входы соответству. юших блоков 2 и 3. Ва избежание назначения одного задания на несколько процес. соров в устройстве предусмотрен запрет назначения заданий на каждый последую- . щий процессор, если предыдущий готов к работе. Для этого инверсный выход каж.дого -го разряда регистра 1 готовности процессоров соединен с входами блоков 2 и 3, блоков 4 и 8 элементов И.

Таким образом, с выходов соответст вуюших пар блоков 2 и 3 каждая пара операндов поочередно поступает на входы готового к работе процессора.

Распределение заданий процессорам производится до тех пор, пока не будут получены сигналы готовности всех И процессоров. Эти сигналы подаются с прямых выходов регистра 1 готовности процессоров на входы элемента И 8, который по готовности всех И процессоров выдает на выход 10 устройства сигнал готовности к приему новой группы операндов.

Кодовый селектор 7 работает следующим образом.

Адресные признаки операндов, записанных в регистрах 18, с первой группы выходов поступают на схемы 21 сравнения.

При этом адресный признак операнда, записанного в первом регистре 18, подается на первые входы схем 21 сравнения строки треугольной матрицы 19 сравнения, адресный признак второго операнда, записанного во втором регистре 18, поступает на второй вход схемы 2 1 сравнения столбца треугольной матрицы 19 сравнения. Таким же образом подаются адрес5 97 64 дый операнд несет помимо числовой информации значение кода операций, выполняемых над данной парой, что исключает необходимость обращения к памяти. Указанное распределение обеспечивается парал-, 5 лельной работой группы блоков 2 совместно с группой элементов ИЛИ 4 и группы блоков 3 совместно с группой элементов

ИЛИ 5, которые осуществляют коммутацию выделенных пар операндов кодовым селек- 30 тором 7 на выходы 15.

Устройство работает следующим образом.

На выходы 11 и 12 устройства пода- 15 ется соответственно адресный признак и операнд с кодом операции. Эта информация заносится в регистры 18 кодового селектора 7. Она представляет собой множество операндов, реализуемых и данном цикле вычислений и соответствующие им адресные признаки.

Каждый операнд, подаваемый по входу

12, представляет собой двоичный код, часть разрядов которого определяет необ-25 ходимую для обработки числовую информацию, а другая часть — код операции, выполняемой над этим числом. Адресные признаки, подаваемые на входы 11, также. представляют собой двоичные коды, yg одинаковые для каждой пары взаимодействующих между собой операндов. Таким образом, в каждый иэ регистров 18 кодового селектора 7 записывается адресный признак и соответствующий ему операнд с кодом операции.

Кодовый селектор 7 при помощи треугольной матрицы 19 сравнения обеспечивает разделение множества операндов на пары, которые попарно через выходы 4й

13 и 14 кодового селектора 7 подаются на входы блоков 2 и 3.

Разделение пар операндов во времени обеспечивается за счет регистра 6. На вход регистра 6 через тактовый вход 9 устройства подается входная последовательность импульсов заданной частоты, которая осуществляет запись единицы и ее последующий поразрядный циклический сдвиг, за счет чего на выходах регистра

6 формируется тактовая сетка с временным сдвигом, равным периоду следования входной последовательности импульсов, которая через входы 17 кодового селектора 7 поступает на блоки 22 и 23 эле 55 ментов.20 треугольной матрицы 19 сравнения. Число разрядов регистра 6 также; как и число элементов 20 треугольной матрицы 19 сравнения кодового селекто7 976442 8 ные признаки со всех последующих регист-, ров, группа информационных входов которов 18 на элементы треугольной матрицы рого соединена с группой входов готовноссравнения. B общем случае с !-го регист- ти устройства, о т л и ч а ю щ е е с я ра 18 (2 < i< W>l) адресный признак тем, что, с целью увеличения пропускной

° ЮЮ поступает на вторые входы сравнения схем 5 способности, в устройство введены кодо21 сравненияэлементов20(-1)-гостол- Вый селектор, вторая группа из И блоков бцайнапервыевходысхем21сравнения элементов И, вторая группа элементов из

1 элементов 20 -ойстрокт1. Адресный приз-. И-элементов ИЛИ, элемент И, причем пернак последнего операнда поступает только Выв Входы каждого блока элементов И на вторые входы схем 21 сравнения эле- 10 Второй группы соединены с первыми вхоментов 20 последнего столбца матрицы, дами одноименных блоков элементов перТакимобразомподвергаютсяпопарному Вой 1 -Руппы И, Выходы каждого блока эле. сравнению адресные признаки всех участ- ментоВ И Второй группы - с соответствуВующих В вычислениях операндов. В слу- ющими Выходами группы информационных чае, если для какой-либо пары операндов >> выходов устройства и с входами соответимеет место общий адресный признак, то ствующих элементов ИЛИ второй группы, соответствующий элемент 21 сравнения Вь1ходы которых соединены с группой вхоформирует сигнал, который свидетельству- дов сброса регистра готовности процессоет о равенстве адресных признаков срав- Ров инверсный выход каждого 1-го (т = ниваемых операндов. Этот сигнал с выхо-20 1". 1 1) разряда регистра готовности ïðîда элемента 21 сравнения поступает на цессоров соединены с вторыми входами, первые входы блоков 22 и 23 элементов (1+1)-го блока элементов И первой и втоИ матрицы 19. рой групп, второй вход первого блока элеБлок 22 и блок 23 элементов И каж- ментоВ И и третьи входы остальных бло догоэлемента20треугольнойматрицы19 И ков элементов И первой группы соединесравнения попарно опрашиваются импуль- ны с первым выходом кодового селектосами, поступающими на группу входов 17 ра IITopot! Вхоц первого и третьи входы кодового селектора 7, и если схемы 21 остальных блокоВ элементов И соединены сравнения соответствующих элементов 20 с вторым выходом, кодового селектора, треугольной матрицы 19 сравнения при 30 первый вход которого соединен с адресэтом вьщают на блоки 22 и 23 элемен- HbI< входом устройства, второй вход котов И сигналы равенства адресных приз- . дового селектора соединен с числовым наков операндов, то соответствующие па- входом устройства, группа входов кодоворы операндов, поступающие с вторых вы- го селектора соединена с груйпой выхоходов регистров 18 на входы блоков 22 > aoH Регистра сдвига, вход которого соел и 23, проходят на выходы 13 и 14 ко, динен с тактовым входом устройства, сигдового селектора 7. нальный выход устройства соединен с выПрименение изобретения позволяет по- ходом элемента И, входы которого соедивь1сить пропускную cIIoco6HocTb устр@йст H88bf с IIPIIMbIMH выхоДами PeI HcTPB FQTCBва при распределении заданий процессорам. 46 НОСТИ ПРОЦЕССОРОВ.

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

1. Устройство для распределения заданий процессорам, содержащее регистр готовности процессоров,регистрсдвига,первую группу из И блоков элементов И (гдв

М - число процессоров} и первую группу из элементов ИДИ, .причем прямые выходы 0 регистра готовности процессоров соединены с первыми входами соответствующих блоков элементов И первой группы, выходы которых соединены с соответствующими выходами группы информационных выходов устройства и с входами соответст: вующих элементов ИЛИ первой группы, вы-. ходы которых соединены с группой входов сброса регистра готовности процвссо2. Устройство по п. l о т л и ч аю щ в е с я тем, что кодовый селектор содержит 2И регистров и треугольную матрицу элементов сравнения размерности (у1- 1) ° (Щ- 1) (где и1 И! ), каждый элемент сравнения которой в свою очередь содержит схему сравнения и.два блока элементов И, причем первый вход каждого регистра соединен с первым входом ко дового селектора, второй вход каждого регистра соединен с вторым входом кодово го селектора, первый выход первого регистра соединен с первым входом каждой схемы сравнения первой строки треугольной матрицы элементов сравнения, а первые выходы каждого 1-го регистра, начиная с второго, соединены с первым входом каждой схемы сравнения т -ой строки треугольg 976442 10 ной матрицы элементов сравнения и к вто- угольной матрицы элементов сравнения и рому входу каждой схемы сравнения 4-го с третьими входами каждого второго блостолбца треугольной матрицы элементов ка элементов И -го столбца треугольной сравнения, выход схемы сравнения каждо- матрицы элементов сравнения, выходы ларго элемента сравнения треугольно» мат- 5 вых блоков элементов И каждой строки рицы элементов сравнения соединен с пер треугольной матрицы элементов сравнения выми входами обоих -блоков элементов И соединены с первым выходом кодового сесвоего элемента сравнения треугольной лектора, выходы вторых блоков элементов матрицы. элементов сравнения, вторые вхо И каждой строки треугольной матрицы эледы которых соединены между собой и с и ментов сравнения соединены с вторым высоответствующим. входом группы входов ходом кодового селектора. кодового селектора, вторые выходы первого регистра. соединены с третьими входа- Иеточники информации, ми каждого первого блока элементов И принятые во внимание при экспертизе первой строки треугольной матрицы эле- 1. Авторское свидетельство СССР ментов сравнения, а вторые выходы каж- М 758128, кл. G 06 Р Ж/04, "l978. дого -го регистра, начиная с второго, со- 2. Авторское свидетельство СССР единены с третьими входами каждого пер- % 629539, кл. & 06 Р 9/00, 1978 (прового блока элементов И j -ой строки тре- тотип)., 20