Устройство для распределения заданий процессорам Советский патент 1982 года по МПК G06F9/00 

Изобретение относится к вычислитель, ной технике и может быть использовано в многопроцессорньгх системах для обра- .ботки цифровой информации. Известно устройство для сопряжения процессов, содержащее блок коммутации, блок настройки, блок управления и блок передачи, объединенные между собой ьнут ренними шинами и предназначенное для сопряжения отдельных ЭВМ в единую однородную вычислительную систему f l. Недостатком указанного устройства является его существенная сложность и сравнительно невысокая производительност Наиболее близким к изобретению по технической сущности и достигаемому результату является устройство для распределения заданий процессорам, содержащее И процессоров, регистр сдвига, регистр готовности процессоров, первый блок из групп элементов И и первый блок из И групп элементов ИЛИ 2. Недостатком устройства является низкая гфоизводителыюсть, являющаяся след ствием простоев в работе устройства в случае, когда число свободных от работы процессоров меньше требуемого количества. Целью изобретения является увеличение пропускной способности устройства. Поставленная цель достигается тем, что в устройство для распределения заданий 1фоцессс рам, содержащее регистр готовности процессоров, регистр сдвига, первую группу из И блоков элементов И (где И- число гфоцессоров) и первую группу из элементов ИЛИ, причем -прямые выходы регистра готовности 1чюцесс ов соединены с первыми входами соответствукяцих блоков элементов И первой группы, выходы которых соединены с соответствующими выходами группы информгщионных выходов устройства и с входами соответс-гвующих элементов ИЛИ первой группы, выходы которых соединены с груш пой входов сброса регистров готовности 1фоцесссров, группа информационных входов которого соединена с группой входо; готовности устройства, введены кодовый селектор, вторая группа из И блоков элементов И, вторая группа из И элементов ИЛИ, элемент И причем первые входы каждого блока элементов И второй группы соединены с первыми входами одноименных блоков, элементов первой группы И, выходы каждого блока элементов И второй группы - с соответствующими выходами группы информационных выходов устройства и с входами соответствующих элементов ИЛИ второй группы, выходы ко торых .соединены с группой входное сброса .регистра готовности процессоров, инверсный выход каждого i-ro ( /i I... м) разряда регистра готовности процессоров со- единены с вторыми входами (i-H)-ro 6jjo ка элементов И первой и второй групп, второй вход первого блока элементов И и третьи входы остальных блоков элементов И первой группы соединены с первым вы° ходом кодового селектора, второй вход первого и третьи входы остальных блоков элементов И соединены с вторым выходом кодового селектора, первый вход которого соединен с адресным входом устройства, второй Вход кодового селектора соединен р числовым входом устройства, группа входов кодового селектора соединена с . группой выходов регистра сдвига, вход которогосоединен с тактовым входом устройства, сигнальный выход устройства со единен с выходом элемента И, входы которого соединены с прямыми выходами ореристра готовности процессоров. Кроме того, кодовый селектор содержит 2 И регистров и треугольную матрицу элементов сравнения размерности (yyi-l) ( VYV- l), (где/п ) каждыйэлемент сравнения которой в свою очередь содержит схему сравнения и два блока . элементов И, причем первый вход каждого регистра, соединен с первым входом ко дового селектора, второй вход каждого регистра соединен с вторым входом кодового селектора, первый вьбсод первого ре гистра соединен с первым входом каждой схемы сравнения первой строки феугольной матрицы элементов сравнения, .;а первые выходы каждого i -го регистра, начиная с второго, соединены с первым входом каждой схемы сравнения i -ой стр ки треугольной матрищы элементов сравнения и к второму входу каждой схемы сравнения Л-го столбца треугольной матрицы элементов сравнения, выход схемы сравнения каждого элемента сравнения треугольной матрицы элементов сравнеНИН соединен с первыми входами обоих блоков элементов И своего элемента сравнения треугольной матрицы элементов сравнения, вторые входы котсрых соединены между собой и с соответствующим Входом группы входов кодового селектора, вторые выходы первого регистра соединены с третьими входами каждого первого блока элементов И первой строки треугольной матрицы элементов сравнения, а вторые выходы каждого -i-ro регистра, начиная с второго, соединены с третьими входами каждого первого блока элементов И 4 -ой строки треугольной матрицы элементов сравнения и с третьими выходами каждого второго блока элементов И i -го столбца треугольной матрицы элементов сравнения, выходы первых блоков элементов И каждой строки треугольной матрицы элементов сравнения соединены с первым выходом кодового селектора, выходы вторых блоков элементов И каждой строки треугольной матрицы элементов сравнения соединены с вторым выходом кодового селектора. На фиг. 1- гфиведена структурная схема устройства для распределения заданий процессорам; на фиг. 2 - структурная схема кодового селектора. Устройство содержит регистр 1 готовности процессфов, группы блоков элемен- тов И 2 и 3, группы элементов ИЛИ 4 и 5, регистр 6 сдвига, кодовый селектор 7, элемент И 8, тактовый вход 9 устройства, сигнальный выход 10 устройства, адресйый вход 11 устройства, числовой вход 12 устройства, выходы 13 и 14 кодового селектора 7, группу информационных выходов 15 устройства, группу входов 16 готовности устройства, группу входов 17 кодового селектора 7. Кодовый селектор содержит регистр 18, треугольную матрицу 19 элементов сравнения. Элементы 2О сравнения матрицы 19 содержат схему 21 сравнения, блоки 22 п 23 элементов И. Принцип работы устройства основан на предварительном формировании заданий процессорам, заключающемся в том, что все множество операндов, предназначенное для решения в данном цикле вычислений, при помощи кодового селектора 7 разбивается по общему адресному ;призн акУ на пары операвдов, взаимодействующих между собой. Последующее распределение полученных таким образом ,пар операндов по процессорам 1д оизводится по мере готовности процессс ов к работе, причем каждый операнд несет помимо числовой информации значение кода операций, выполняемых над данной парой, что исключает необходимость обращения к памяти. Указанное распределение обеспечивается ;Парал-, лельной работой группы блоков 2 совместно с агруппой элементов ИЛИ 4 и группы блоков 3 совместно с группой элементов ИЛИ 5, которые осуществляюг коммутацию выделенных пар операндов кодовым селектором 7 на выходы 15.

I

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

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

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

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

Разделение пар операндов во времени обеспечивается за счет регистра 6, На вход регистра 6 через тактовый вход 9 устройства подается входная последовательность импульсов заданной частоты, которая осуществляет запись единицы и ее последующий поразрядный циклический сдвиг, за счет чего на выходах регистра 6 формируется тактовая сетка с временным сдвигом, равным периоду следования входной последовательности импульсов, которая через входы 17 кодового селектора 7 поступает на блоки 22 и 23 элементов 2 О треугольной матрицы 19 сравнення. Число разрядов регистра 6 также как и число элементов 2О треугольной матрицы 19 сравнения кодового селектора 7 равно максимальному числу пар one- равдов, участвующих в работе.

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

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

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

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

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

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

Адресные признаки операндов, записанных в регистрах 18, с первой группы выходов поступают на схемы 21 сравнения. При этом адресный признак операнда, записанного в первом регистре 18, подается на первые входы схем 21 сравнения строки треугольной чатрицы 19 сравнения, адресный признак второго операнда, записанного во втором регистре 18, поступает на второй вход схемы 21.сравнения столбца треугольной матр1щы 19 сранения. Таким же. образом подаются адресные признаки со всех последующих регист ров 18 на элементы треугольной матрицы сравнения. В общем случае с -го регист ра 18 (2 i Vvtr.l) адресный признак поступает на вторые входы сравнения схем 21 сравнения элементов 2О( -1)-го столбца и на первые входы схем 21 сравнения элементов2О -ойстроки. Адресный признак последнего операнда поступает только на вторые входы схем 21 сравнения элементов 20 последнего столбца матрицы. Таким образом подвергаются попарному сравнению адресные признаки всех участвующих в вычислениях операндов. В случае, если для какой-либо пары операндов имеет место общий адресный признак, то соответствующий элемент 21 сравнения формирует сигнал, который свидетельствует о равенстве адресных признаков сравниваемых операндов. Этот сигнал с выхода элемента 21 сравнения поступает на о первые входы блоков 22 и 23 элементов И матрицы 19. Блок 22 и блок 23 элементов И кажi дого элемента 2 О треугольной матрицы 19 сравнения попарно опрашиваются импульсами, поступающими на группу входов 17 кодового селектора 7, и если схемы 21 сравнения соответствующих элементов 20 треугольной матрицы 19 сравнения при этом вьщают на блоки 22 и 23 элементов И сигналы равенства адресных признаков операндов, то соответствующие пары операндов, поступающие с вторых регистров 18 на входы блоков 22 и 23, проходят, на выходы 13 и 14 ко. дового селектора 7. Применение изобретения позволяет повысить пропускную способность устрэйства при распределении заданий процессорам. Формула изобретения 1. Устройство для распределения задаНИИ процессорам, содержащее регистр готовности проиессоров,регистр сдвига, первую группу из У1 блоков элементов И (где ,У1 - число процессоров) и первую группу из элементов ЙЛЙ,1фичем прямые выходы регистра готовности щзоцессоров соединены с первыми входами соответствующих блоков элементов И первой группы, выходы которых соединены с соответствующиMVi выходами группы информационных выходов устройства и с входами соответствующих элементов ИЛИ первой группы, вы-f: ходы которых соединены с группой входов сброса регистра готовности процессоров, группа информационных входов которого соединена с группой входов готовности устройства, отличающееся тем, что, с целью увеличения пропускной способности, в устройство введены кодовый селектор, вторая группа из И блоков элементов И, вторая группа элементов из W элементов ИЛИ, элемент И, причем первые входы каждого блока элементов И втчрой группы соединены с первыми входами одноименных блоков элементов первой группы И, выходы каждого блока эле мейтов И второй группы - с соответствующими выходами группы информационных выходов устройства и с входами соответствующих элементов ИЛИ второй группы. Выходы которых соединены с группой входов сброса регистра готовности процессоров, инверсный выход каждого-i-го(1 1... и) разряда регистра готовности процессоров соединены с вторыми входами (t4l)-ro блока элементов И первой и второй групп, BTqjc вход первого блока элементов И и третьи входы остальных блоков элементов И группы соединены с первым выходом кодового селектора, второй вход первого и третьи входы остальных блокое элементов И соединены с вторым выходом, кодового селектора, первый вход которого соединен с адресным входом устройства, второй вход кодового селектора соединен с числовым входом устройства, rpjmna входов кодового селектора соединена с груйпой выходов регистра сдвига, вход которого соединен с тактовым входом устройства, сигнальный выход устройства соединен с выходом злемекга И, входы которого соединены с прямыми выходами регистра готовности процёсссфов. 2. Устройство по п. 1,отличаю щ е е с я тем, что кодовый селектор содержЕгт 2VJ регистров и треугольную матрицу элементов сравнения размерности (т- 1) ( т- 1) (где гм и), каждый эпамент- сравнения котсрой в свою очередь содержит схему сравнения и два блока элементов И, гфичем первый вход каждого регистра соединен с первым входом кодового селектора, второй вход каждого регастра соединен с втqpым входом кодового селектора, первый выход первого регистра соединен с первым входом каждой схемы сравнения первой строки треугольной матрицы элементов сравнения, а первые выходы каждого i-го регистра, начиная с второго, соединены с первым входом каждой схемы сравнения -ей строки треугольвой матрицы элементов сравнения в к второму входу каждой схемы сравнения .i -го столбца треугольной матрицы элементов сравнения, выход схемы сравнения каждого элемента сравнения треугольной матрицы элементов сравнения соединен с первыми входами обоих-блоков элементов И своего элемента сравнения треугольной матрицы элементов сравнения, входы которых соединены между собой и с соответствукяцим.входом tpyniibi входов кодового селектсфа, вторые выходы перво го регистра соединены с третьими входами каждого первого блока элементов И строки треугольной матрицы элементов сравнения, а вторые выходы каждого i-го регистра, начиная с второго, со единены с третьими входами каждого первого блока элементов И i гой строки тре-г угольной матрицы элементов сравнения и с третьими входами каждого второго блока элементов И i-ro столбца треугольной матрицы элементов сравнения, выходы Первых блоков элементов И каждой стрсжи треугольной матрицы элементов сравнения соединены с первым выходом кодового селектора, выходы вторых блоков элементов И каждой строки треугольной матрицы элементов сравнения соединены с вторым вьн ходом кодового селектсфа. Источники ивфсфмацви, хфинятые во внимание при экспертвэе 1.Авторское свидетельство СССР N 758128, кл. а Об F i3704,rl978. 2.Авторское свидетельство СССР № 629538, кл. QO6 F 9/ОО, 1978 (про тотип).|

4

./У

I