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

(54) УСТРОЙСТВО АСПРЕДЕЛЕНИЯ ЗА 57) Изобретен ительной техн тносится к выч и может быть и ользовано в кач аспределения за ГОСУДАРСТВЕННЫЙ НОМИТЕТ СС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКР Н АВТОРСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свУ 1283764, кл. ОАвторское свидУ 1275464, кл. 0 стве диспетчера дляаний процессорам в многопроцессорной вычислительной системе класса ОНЯ при вертикальном распараллеливании последовательных программ. Цель изобретения - расширение класса решаемых задач за счет возможности распределения заданий процессорам в многопроцессорной вычислительной системе при вертикальном распараллеливании последовательных программ. Устройство для распределения заданий содержит блок выбора кода, четыре группы элементов И, две группы элементов ИСКЛ 10 ЧА 10 ЩЕЕ . ИЛИ, две группы элементов ИЛИ и блок памяти, Цель достигается введением двух групп элементов ИЛИ, двух групп элементов ИСКЛЮЧАЯЕЕ ИЛИ и блока памя( ти с соответствующими связями. 1 з.п. ф-лы, 3 ил.1444808 Рассмотрим более подробно работуустройства.В исходном состоянии в блоке 5памяти находится нулевая информация.На вход 10 устройства поступает об 40ратный,код адреса очередной команды, при наличии команды перехода вМВС происходит анализ состояния процессорного поля. Если хотя бы одинпроцессор требует выполнения перехо 45к- да н программе (-и элемент вектораконфигурации МВС равен единице), тов центральном процессоре МВС (насхеме не показано) формируется адрес первой команды участка программы которую необходимо выполнить .-муФпроцессору, Сформированный адрес команды в обратном коде поступает навход 12 устройства, Лдрес первой команды для -го процессора и адрес н очередной команды поступают на входы10 и 12 блока 1, на остальнь 1 е входь 1из блока 5 поступает нулевая информация Изобретение относится к вычислительной технике и может быть использовано н качестве диспетчера дляраспределения заданий процессорам вмно 1 опроцессорной вычислительнойсистеме (МВС) класса ОКМД при верти кальном распараллеливании последонательных программ.Цель изобретения - расширениекласса решаемых задач за счет возможности распределения заданий процессорам в многопроцессорной вычислительной системе при вертикальном распараллеливании последовательных программеНа фиг. 1 представлена структурная схема устройства для распределения заданий; на фиг, 2 - структурнаясхема блока выбора кода; на фиг, 3 -структурная схема блока памяти,Устройство (фиг. 1) содержитблок 1 выбора кода, группу из К (К -разрядность адреса команды) элементов И 2, две группы из К элементов И 3каждая, группу из К элементов ИЛИ 4,блок 5 памяти, две группы по р (р -число элементов вектора конфигурацииМВС) элементов ИСКЛ 10 ЧАЮЩЕЕ ИЛИ 6,группу из р элементов ИЛИ 7, группуиз р элементов И 8, информационныйвыход 9 устройства, информационныевходы 10-12 устройства, информационный выход 13 устройства, управляющиевходы 14, 15 устройства. Блок 5 памяти (фиг. 2) включает и групп из шэлементов И 16, группу из и элементов И 17, и регистров 18, и групп изр элементов И 19, группу из (и)элементов ИЛИ 20, группу из (и)элементов И-НЕ 21 и элемент ИЛИ 22.Блок 1 выбора кода (фиг. 3) включаетгруппу из К элементов ИЛИ-НЕ 23,группу из К ячеек 24 анализа разрядов, каждая ячейка состоит из и узлов 25 поразрядного переноса (и - масимальное число адресов, поступающихна блок 1), в состав каждого из которых входят элементы ИЛИ 26 и И 27,иэлемент И-НЕ 28.Устройство работает следующим образом.При выполнении последовательнойпрограммы на вход 10 устройства поступает адрес очередной командь 1 нобратном коде, Если предыдущей комадой была команда условного перехода,то по результатам анализа условияпроцессоры или остаются в активном состоянии (соответствующие процессорам элементы вектора конфигурацииМВС равны "1"), или переходят н пассивное состояние (соответствующиеэлементы вектора конфигурации МВСравны "0"), Если перехода н программе требует хотя бы один процессор,то адрес первой команды (н обратномкоде), вызванной переходом в программе, поступает на вход 12 устройства, в противном случае выполняетсяочередная команда. В результате наличия на входах 10 и 12 адресов команд блок 1 производит сравнение ихзначений и выбирает наименьшее значение адреса. В результате на информационном выходе блока 1 появляетсякод минимального адреса команды, предназначенного для выполнения, а больший но значению адрес команды запоминается в блоке 5 памяти и в соответствии с ним запоминается состояние процессоров, требующее выполне 25 ния данной команды, Как только значение адреса очередной команды, поступающей на вход 10, станет равным адресу хранимой в блоке 5 памяти, сблока 5 поступает значение вектора30 конфигурации МВС, В результате процессоры, требующие выполнения данной ко"манды, переводятся в активное состояние. Далее процесс выполнения программы продолжается аналогично,з 1444808 1 О 15 20 25 40 ЗО 35 45 50 55 Блок 1 работает следуюпим образом. В первый момент в блоке 1 анализируются старшие разряды всех кодов. Если хотя бы один из старших разрядов кодов равен единице, на выходе элемента ИЛИ-НЕ 23 к появляется низкий потенциал (код 0), который соответствует значению старшего разряда максимального кода и является одновременно сигналом вапрета при анализе остальных разрядов кодов, старшие разряды которых равны нулю. Эти сигналыформируются на выходах элементов ИЛИ26 и поступают на входы элементов И27, Те коды, старшие разряды которыхравны 1, проходят через элементы И27 ячейки 24. Если старшие разрядывсех чисел равны О, на выходе элемента ИЛИ-НЕ 23 к формируется "1",которая равна старшему разряду максимального кода и поступает на выход блока 1, Кроме того, она обеспечивает разрешение на прохождение остальных разрядов всех кодов через элементы ячейки 24. Аналогичным образом анализируются вторые по старшинству разряды всех кодов и т.д в результате чего на выходах узлов 25 2525 щ формируется позиционныйц ффкод номера максимального кода, на выходе блока 1 устанавливается позиционный номер или номера (в случае двух или более равных максимальных значений). Если на все входы блока 1 поступают только нули (низкие потенциалы), то с выходов элементов ИЛИНЕ 23 на входы элемента И-НЕ 28 подаются высокие потенциалы. В результате с выхода элемента И-НЕ 28 низкий потенциал поступает на вход элементовИ 27, следовательно, на выходе элемента И 27 будут низкие потенциалы,Сигналы с первого узла 25 блока 1поступают на управляющие входы элементов ИЗ,ИЗ, а с второго узла 25, - на управляющие входы элементов ИЗИЗк, Остальные сигналыс выходов блока 1 поступают на соответствующие входы элементов И 17,19 блока 5 памяти,Кроме того, с выходов элементовИЛИ-НЕ 23 на выход блока 1 поступаетзначение кода, который из блока 1поступает на выход 9 устройства.Припоступлении на входы блока 1 адресовкоманд на выход 9 устройства постуает адрес команды, которую необходимо выполнить. В зависимости от значения адресов команд на первом или втором выходе устройства появляется высокий потенциал, которьп поступаетна входы элементов И 3,3 илиИЗ. Зсоответственно, Если напервом выходе блока 1 высокий потенцйал, то адрес первой команды для-го процессора через элементы ИЛИ 4поступает на информационные входыэлементов И 16, 16 ,Одновременно с поступлением навходы устройства адресов команд через вход 11 устройства на элементыИСКЛЮЧАОЩЕЕ ИПИ 6 поступает значениевектора конфигурации МВС.Высокий потенциал с первого выходаблока 1 поступает на входы элементовИСКЛЮЧАИ 0 ЕЕ ИЛИ 6 Г, 6 21 В результате на входы элементов ИЛИ7,7 с выходов элементов ИСКЛЮЧАОЩЕЕ ИЛИ 6,,6 Р поступает инвертированное значенйе вектора конфигурации МВС.При наличии на входе 12 устройства адреса команды на вход 14 поступает сигнал записи, который поступаетна управляющие входы элементов И 16блока памяти.Блок 5 памяти работает следующимобразом,На входы элементов И 6 И 16 кпоступает адрес команды, на входыэлементов И 16. ,16, поступаетзначение векторА конфигурации МВС.При наличии адресов на 1-х (,)=1п,регистрах 18 на входы соответствующих элементов ИЛИ 20 поступают кодыадресов. В результате с выходов элементов ИЛИ 20высокие потенциалы по"ступают на соответствующие входыэлементов И-НЕ 21 (й=д,д,,2)регистров 18. В результате на выходахэлементов И-НЕ 21 появляются низкиепотенциалы, которые поступают на входы д-х групп элементов И 16, А таккак на регистре 18 отсутствует ин-Формация, то через элемент ИЛИ 20 навход элемента И-НЕ 21 поступаетнизкий потенциал. В результате с выхода элемента И-НЕ 21 высокий потенциал поступает на входы второйгруппы элементов И 16. Следовательно, при подаче на вход 1 Й устройствавысокого потенциала - сигнала записи, который поступает на входы эле"ментов И 6, происходит сдвиг информации с регистра 181 на регистр 8,состояние остальных регистров 18 пе144 ЭО 1, Устройство для распределениязаданий, содержащее блок выбора кода и четыре группы элементов И, причем выходы элементов И первой группыобразуют первый информационный выход 35 устройства о т л и ч а ю щ е е с яЭтем, что, с целью расширения классарешаемых задач эа счет воэможностираспределения заданий процессорам вмногопроцессорной вычислительной фО системе при вертикальном распараллеливании последовательных программ,в него введены две группы элементовИЛИ, две группы элементов ИСКЛРЧА 10- ЩЕЕ ИЛИ и блок памяти, причем первыевходы элементов И второй группы соединены с соответствующими разрядамипервого адресного входа команды блока выбора кода и образуют первый информационный вход устройства, пер О .вые входы элементов И третьей группысоединены с соответствующими разрядами второго адресного входа командыблока выбора кода и образуют второйинформационный вход устройства, вторые входы элементов И третьей группы соединены с первым управляющимвыходом блока выбора кода и первымивходами элементов ИСКЛЮЧИОШЕЕ ИЛИпервой группы, вторые входы которых изменяется из-за наличия низкого потенциала на входах элементов И 16, аинФормация, поступившая на входыпервой группы элементов И 16, поступает на регистр 18 . Для поиска требуемой информации с инверсных выходоврегистров 18 значения адресов командпоступают на выход блока 5 памяти.При считывании значения вектора конфигурации МВС на входы соответствующих элементов И 19 поступает сигналсчитывания, в результате на выходблока 5 памяти поступает значение вектора конфигурации МВС. Для сбросасчитанной информации на входы элементов И 17 поступает сигнал сброса. Врезультате с выхода элемента И 17высокий потенциал поступает на входсоответствующего регистра 18 и устанавливает его в нулевое состояние,При необходимости одновременного считывания более одного вектора конфигурации МВС одновременно на входы нескольких групп элементов И 19 поступают высокие потенциалы и происходитодновременное считывание несколькихвекторов конфигурации МВС. При поступлении на входы элементов И 17сигнала сброса происходит одновременный сброс считанной информации ссоответствующих регистров 18, В результате нескольких регистров 18 оказываются в нулевом состоянии. Принеобходимости записи очередной информации происходит сдвиг содержимыхрегистров 18 до первого свободногорегистра 18,Такам образом, при поступлении вблок 5 памяти на входы элементовИ 6. 16 адреса команды, а навходы элементов И 16,16значения вектора конфигурации МВС и приналичии сигнала. записи на входахэлементов И 16,16 происходитзапись поступившей информации на регистр 18. В процессе поступленияадресов очередных команд на вход 10устройства в блоке 1 происходит сравнение адреса команды, поступающей синверсного выхода регистра 18 блока5 памяти на вход блока 1, и адресаочередной команды. При совпадениизначений адресов команд на третьемвыходе блока 1 появляется высокийпотенциал, который поступает на входы элементов И 17 19,19 ь, Врезультате значение вектора конфигурации МВС с регистра 18, через эле 4808 6менты И 19,. ,19 р поступает на соответствующие входы элементов ИЛИ 7,на которые через вход 11 устройстваи элементы ИСКЛЮЧАЮШЕЕ ИЛИ брм,, 56 поступает значение вектора конгрфигурации МВС, соответствующее очередной команде. В результате на выходе элементов ИЛИ 7 появляется значение вектора конфигурации МВС, которое поступает на входы элементов И 8,При выборке очередной команды на вьгполение на вход 15 поступает сигналзапроса, который поступает на входы 15 элементов И 8 и 2, В результате навыход 9 устройства с блока 1 черезэлементы И 2 подается адрес очередной команды, а на выход 13 устройства через элементы И 8 поступает 20 значение вектора конфигурации МВС.Следовательно, процессоры, требующиевыполнения данного участка программы,активны. Процесс распределения заданий процессорам МВС продолжается 25 до окончания выполнения программы аналогичноФормула из о бретения7 14448 соединены с первыми входами элементон ИСКЛ 10 ЧА 10 ЩЕЕ ИЛИ второй группы и образуют третий информационный вход уатройства, вторые входы элементов ИСКЛ 10 ЧА 0111 ЕЕ ИЛИ второй группы соедине 5 ны с вторым управляющим выходом блока выбора кода и вторыми входами элементов И второй группы соответственно, выходы которых соединены соответ ственно с первыми входами элементов ИЛИ первой группы, вторые входы которых соединены с выходами элементов И третьей группы, информационные выхо; ды блока выбора кода соединены соответственно с первыми входами элементов И четвертой группы, вторые входы которых соединены с вторыми входами элементов И первой группы, входом сброса блока памяти и первым управля ющим входом устройства, второй управляющий вход которого соединен с входом записи блока памяти, выходы разрядов адреса команды которого соединены с соответствующими разрядами 25 третьего адресного входа команды блока выбора кода, управляющие выходы которого соединены соответственно с управляющими входами блока памяти, входы разрядов адреса команды которо го соединены соответственно с выходами элементов ИЛИ первой группы, выходы элементов ИСКЛ 1 ОЧА 10 ЩЕЕ ИЛИ первой группы соединены соответственно с входами значения вектора конфигурации блока памяти, вторые входы элементов И первой группы соединены соответственно с выходами элементов ИЛИ второй группы, первые входы которых соединены соответственно с выходами элементов ИСХЛ 10 ЧАНЦЕЕ ИЛИ второй группы, р входов которых соединены с информационными выходами данных соответствующих разрядов блока памяти (р - число элементов вектора конфигурации), выходы элементов И четвертой группы являются вторым информационным выходом устройства.2, Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок па- БО мяти содержит и регистров, ие ш элементов И первой группы (и - разрядность регистров), вторую группу из 08 8и элементов И, группу из иэлементов И-НЕ, р а и элементов И третьей группы, группу из иэлементов ИЛИ и элемент ИЛИ, причем вход записи блока соединен с первыми входами элементов И первой группы, входы адреса команды блока соединены соответственно с вторыми входами (1,1)-х элементов И первой группы (1=1К, разрядность адреса команды), входы значения вектора конфигурации блока соединены соответственно с вторыми входами (1,р)-х элементов И первой группы (р=К+1 ш), выходы элементов И первой группы соединены с соответствующими разрядами и регистров, инверсные выходы 1-х разрядов которых соединены с выходами адреса команды блока, вход сброса которого соединен с первыми входами элементов И второй группы, выходы которых соединены соответственно с входами сброса -х регистров =1,2и),прямые ныходы р-х разрядов которых соединены соответственно с первыми входами элементов И третьей группы, пря" мые выходы 1-х разрядов и регистрон соединены соответственно с вторыми входами (1,1)-х элементов И первой группы (1=2 и), прямые выходы 1-х разрядов г-го регистра (г=2 и) соединены с соответствующими входами д-го элемента ИЛИ группы (д= =1и), прямые выходы 1-х разрядов и-го регистра соединены с соответствующими входами элемента ИЛИ, прямой выход которого соединен с первыми входами элементов И-НЕ группы, а инверсный выход - с третьими входами (и,ш)-х элементов И первой группы, третьи входы (г,ш)-х элементов И первой группы соединены соответственно с выходами Ь-х элементов И-НЕ группы, выходы д-х элементов ИЛИ группы соединены с соответствующими входами й-х элементов И-НЕ (й=д,д, д2), управляющие входы блока соединены соответственно с вторыми входами элементов И второй и третьей групп, выходы элементов И третьей группы соединены с информационными выходами данных блока.