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

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

УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАМ, содержащее группу регистров хранения, регистр сдвига, регистр готовности процессоров элемент ИЛИ, группу блоков элементов И, блок элементов И, первый элемент И, группу элементов ИЛИ, причем группа информационных входов устройства соединена с группой информационных входов первого регистра хранения группы, группа выходов каждого регистра хранения группы - с группой входов следующего регистра хранения группы, группа выходов последнего регистра хранения группы - с группой входов блока элементов И, группа выходов каждого блока элементов И соединена с группой входов одноименного элемента ШIIi группы и является соответствующей группой выходов устройства, выходы элементов ИЛИ группы соединены с группой входов сброса регистра сдвига и с группой входов сброса регистра готовности процессоров, каждьй разрядньй выход регистра сдвига соединен с первым входом одньименного блока элементов И группы. выходы регистра сдвига соединены с входами элемента ИЛИ, каждый сигнальный вход устройства соединен с одноименным информационным входом регистра готовности процессоров, отличающееся тем, что, с целью повышения быстродействия, устройство содержит триггер, генератор импульсов, группу блоков элементов И-ИЛИ, группу дешифраторов, группу регистров обслуживания, одновибратор, второй и третий элементы И и элемент ИЛИ-НЕ, выход которого соединен с первым входом первого элемента И, выход которого соединен с нулевым входом триггера, выход элемента ИЛИ соеди(Л нен с первыми управляющими входами блоков элементов И-ИЛИ группы, с с первым входом элемента ШМ-НЕ, с инверсным входом блока элемента И, с входом раэрешения сдвига регистра сдвига и с входом одновибратора, выход которого соединен с нулевым входом последнего регистра хранения :л группы, выходы признаков наличия заявки регистров хранения группы со соединены соответственно с входами Од О) элемента ИЛИ-НЕ, выход признака наличия заявки последнего регистра хранения группы соединен с инверсным входом второго элемента И, выход признака наличия заявки первого регистра хранения группы соединен с первым входом третьего элемента И, выход которого является сигнальным выходом устройства, первый выход генератора импульсов соединен с вторыми входами первого и третьего элементов И, второй выход генератора импульсов соединен с входом разрешения записи регистра

Изобретение относится к вычислительной технике и может быть использовано для построения многопроцессор ных вычислительных систем. Известно устройство для распределения заданий процессорам, содержащее регистр готовности процессоров, группу элементов И, блок управления регистр сдвига, процессоры, элементы ИЛИ l . Недостатками этого устройства являются низкая надежность вследствие существования высокой вероятности потери заявки на решение задачи, вызванной отказом устройства от выполнения задания, в случае, когда число свободных процессоров меньше количества потребных процессоров; ограниченные функциональные возможности, проявляющиеся в том, что в устройстве отсутствует возможность организации очереди заданий. Наиболее близким к изобретению является устройство для распределения заявок по процессорам, содержащее группу регистров хранения, группу выходов признака числа потребных процессоров последнего регистра хранения группы, группу входов признака номера задачи первого регистра хранения группы, группу входов признака числа потребных процессоров первого регистра хранения группы, первую и вторую группы элементов И, элемент И, регистр сдвига, информационный вход регистра сдвига, элемент ИЛИ, блок элементов ИЛИ, группу процессоров, регистр готовности процессоров, блок управления, первый вход которого соединен с входом пуска устройства, группа выходов регистра готовности процессоров соединена с первыми входами элементов И первой группы, вторые входы которых соединены с группой выходов регистра сдвига и с группой входов элемента ИЛИ выход которого соединен с вторым входом блока управления и первым входом элемента И, второй вход которого соединен с выходом старшего разряда группы выходов регистра сдвига, выход элемента И соединен с входом сдвига регистра сдвига, вход сброса которого соединен с выходом блока элементов ИЛИ и с входом сброса регистра готовности процессоров, группа информационных входов которого соединена с выходами процессоров группы, выходы которых соединены с выходами элементов И первой группы и с входами блока элементов ИЛИ, управляющий вход регистра сдвиг соединен с первым выходом блока уп- равления, группа информационных входов первого регистра хранения группы соединена с группой входов заявок устройства, управляющий вход каждого регистра хранения группы соединен с выходом соответствующего элемента И второй группы, группа информационных вькодов каждого реги-стра хранения группы, кроме последнего, соединена с группой информационных входов прследукяцего регистра хранения группы, первьш вход каждого элемента И второй группы, кроме последнего, соединен с выходом последую4щего элемента И этой группы, первый вход последнего элемента И второй группы соединен с вторьм выходом блока управления i2j . Недостатком известного устройства является низкое быстродействие. Цель изобретения - повышение быстродействия устройства. , . Поставленная цель достигается тем, что в устройство для распределе ния заданий процессорам, содержащее группу регистров хранения, регистр сдвига, регистр готовности процессор группу прюцессоров,элементИ1Ш,труппу блоков элементов И, блок элементов И, первый элемент И, группу элементов ИЛИ, причем группа информационных входов устройства соединена с группой информационных входов первог регистра хранения группы, группа выхо дов каждого perHcjrpa хранения группы с группой входов следующего регистра хранения группы, группа выходов последнего регистра хранения группы сое динена с группой входов блока элемен тов И, группа выходов каждого блока элементов И группй) соединена с группой входов одноименного элемента ИЛИ группы и является соответствующей пой выходов устройства, выходы элементов ИЛИ группы соединены с группой вхо-г дов сброса регистра сдвига и с группой входов сброса регистра готовност процессоров, каждый разрядный выход регистра сдвига соединен с первым входом одноименного блока элементовИ группы, выходы регистра сдвига соединены с входами элемента ИЛИ, каждый сигнальный вход устройства соединен с одноименным информационным входом регистра готовности процессоров, введены триггер, генератор импульсов, группа блоков элементов И-ИЛИ, группа дешифраторов, группа регистров обслуживания, одновибратор, второй и третий элементы И и элемент ШШ-НЕ, выход которого соединен с первьм входом первого элемента И, выход которого соединен с нулевым входом.триггера,выход элемента ИЛИ соединен с первыми управляющими входами блоков элементов И-ИЛИ группы, с первьм входом элемента ИЛИ-НЕ, с инверсным входом блока элементов И, с входом разрешения сдвига регистра сдвига и с входом одновибратора, выход которого соединен с нулевьм входом последнего регистра хранения группы, выходы признаков наличия заявки регистров хранения группы соединены соответственно с входами элемента ИЛИ-НЕ, выход признака наличия заявки последнего регистра хранения группы соединен с инверсным входом второго элемента И, выход признака наличия заявки первого регистра хранения группы соединен с первым входом третьего элемента И, выход которого является сигнальным выходом устройства, первый выхдд генератора импульсов соединен с вторьв1и входами первого и третьего элементов И, второй выход генератора импульсов соединен с входом разрешения записи регистра сдвига, с тактовьми. входами регистров обслуживания группы и с вторым входом второго элемента И, выход которого соединен с тактовьми входами регистров хранения группы, группа выходов блока элементов И соединена с группой информационных входов регистра сдвига, с первыми группами входов блоков элементов И-ИЛИ группы, второй управлякш ий вход каждого блока элементов И-ИЛй группы соединен с соответствующим выходом группы выходов блока элементов И, группа выходов кавдого блока элементов И-ИЛИ группы соединена с группой информационных входов одноименного регистра обслзтживания группы, группа выходов каждого регистра обслуживания группы, кроме последнего, соединена с второй группой выходов еле51

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

На фиг. 1 представлена функциональная схема предлагаемого устройства; на фиг. 2 - схема алгоритма функционирования устройства.

Устройство (фиг. 1) содержит группу информационных входов 1 устройства, вход 2 пуска устройства, сигнальный выход 3 устройства, элементы И 4-6, элемент ИЛИ-НЕ 7, элемент ИЛИ 8, блок 9 элементов И, группу блоков 10.1-10. N элементов И, группу 11.1-11.N блокор элементов , группу 12.1.12N элементов ИЛИ, группу 13.1-13.N дешифраторов, триггер 14, одновибратор 15, генератор 16 импульсов , выходы 17 и 18 генератора 16 импульсов, группу 19.1-19.L регистров хранения, регистр 20 сдвига, группу 21.1-21.N регистров обслуживания регистр 22 готовности процессоров, группу 23.1-23.N процессоров, группу 24 выходов элементов блока 9 элемен-. тов И, 24.1-24.К-первьй, N-й разряда группы 24 выходов блока 9, группы выходов 25.1-25.N регистров 21.1-21.N, выходы 26.1-26.L признаков наличия заявки регистров 19.1-19.L.

На вход 2 устройства подается сигнал пуска, который приводит устройство в рабочее состояние. Выход 3 используется для вьщачи квитанции вкешнай системе о записи заявки в регистр 19.1 группы..

Группа регистров 19.1-19,L хранения устройства предназначена для организации очереди заявок на обслуживание. Запись заявок производится в первьй регистр 19.1 группы, а выбор заявки на обслуживание - из последнего 19.L регистра хранения группы в параллельном коде.

Регистры 21 обслуживания предназначены для хранения признаков номера задачи и доступных процессоров в процессе распределения процессоров задаче. Регистр 20 сдвига предназначен для хранения кода количества процессоров, который представляется в позиционном коде. Наличие единицы в этом коде свидетельствует о необхо-. димости распределения процессора . задаче. Регистр 22 готовности предназначен для регистрации сигналов готовности процессоров. Единичное состояние разряда регистра свидетельствует о том, что процессор свободен и может быть распределен.

В исходном состоянии все элементы памяти, кроме регистра 22 готовности процессоров, находятся в нулевом состоянии, а регистр 22 готовности процессоров находится в единичном cocтoянииj что свидетельствует о готовности процессоров 23.1-23.N к решению задачи. На вход 2 устройства поступает сигнал пуска, по которому триггер 14 устанавливается в единичное состояние и разрешает прохождение сигнала через элемент И 5 с выхода 18 генератора 16 на тактовые входы регистров 19.1-19. Ь, Одновременно с сигналом пуска на выходы 1 устройства поступает заявка, которая под воздействием сигнала с генератора 16 записывается в регистр 19.1. После этого по такту с выхода 17 генератора 16 на выход 3 устройства через элемент И 6 выдается квитанция о записи заявки в очередь. Продвижение заявки в регистрах 19 осуществляется до того момента, пока заявка не записана в последний регистр 19, Во время продвижения заявки в регистрах 19 иа входы 1 устройства могут подаваться очереднс заявки которые также записываются в регистры 19. . Таким образом в регистрах 19.1-19.L образуется очередь заявок нарешеиие задач.

После записи заявки в последний регистр 19 на выходе 26.1 последнего регистра 19.L устанавливается сигнал наличия заявки, который запрещает прохождение сигнала через элемент И 5, После записи первой заявки в регистр 19.L осуществляется выбор ее на обслуживание, сущность которого состоит в назначении определяемой заявкой задаче необходимого числа процессоров для решения. Выбор заявки на обслуживание из регистра 19,L осуществляется всякий раз, когда в очереди есть заявки и устройство не занято обслуживанием. Сигнал о том, что устройство не занято обслуживанием , формируется на выходе элемента ИЛИ 8, если в регистре 20 все разряды установлены в нулевое состояние. В начале работы устройства регист 20 находится в нулевом состоянии и, поэтому, нулевым потенциалом с выход элемента ИЛИ 8 открыт блок 9 элементов И. После записи заявки в регистр 1.9.L на выходах блока 9 устанавливается код заявки, определяющий код количества процессоров, необходимых для решения задачи (на выходах 24) и коды номера задачи и доступности процессоров, так как на входе разрешения сдвига регистра 20 установлен нулевой потенциал, то под управление тактовых импульсов с выхода-18 генератора 16, поступающих на вход разрешения записи регистра 20, осуществ ляется запись параллельного кода с выходом 24 блока 9 в регистр 20. Кроме того, тактовые импульсы с выхода 18 генератора 16 поступают на тактовые входы регистров 21.1- -21.N. При этом к инфо1Я4ационньм входам этих регистров черкез блоки 11.1-11,К осуществляется подктаочение входов 24 только для тех регистров, которым соответствует единичное состояние соответствующего разряда 24.1-24.N. Таким образом по очередному тактовому импульсу с выхода 18 генератора 16 происходит запись кода количества процессоров а регистр 20, а в регистры 21.1-21.N - запись ко дов номера задачи и доступности процессоров. После записи кода количество процессоров в регистр 20 на выходе элемента ИЛИ 8 устанавливается единичны

потенциал, но которому закрывается блок 9 элементов И, отковочаются выходы 24 от входов регистров 21.1т.е. код доступности процессора определен для соответствующего дешифратора 13. При выполнении всех уело21.N, и для этих регистров через блоки 11.1-11.N формируются цепи для циклического сдвига содержимого регистров 21.1-21.N от первого к последнему, а выход последнего регистра 21.N подключается к входу первого регистра 21.1. Поступая на вход разрешения сдвига регистра 20, единичный потенциал с выхода элемента ИЛИ 8 запрещает запись по информационным входам этого регистра и разрешает циклический сдвиг содержимого регистра 20 в направлении от первого разряда к последнему, причем выход последнего разряда регистра 20 подключен к входу первого разряда. Это позволяет осуществлять многократную попытку распределения процессоров задаче. Кроме того, при изменении выходного потенциала элемента ИЛИ 8 с нулевого на единичный одновибратором 15 формируется импульс, по которому последний регистр 19.L устанавливается в нулевое состояние. При этом разрешается прохождение тактовых импульсов генератора 16 через элемент И 5, которые управляют записью и продвижением заявок в регистрах 19.1-19.N. Рассмотрим работу устройства по назначению процессоров задаче, определяемой выбранной заявкой на обслуживание. При этом целесообразно рассматривать работу устройства в два этапа: первоначального назначения процессоров; последующего назначения процессоров. Первоначальное назначение процессоров осуществляется следукадкм образом. С выходов регистра 22 готовности процессоров сигналы готовности поступают на входы 10И-10.N элементов И. На эти же блоки поступают сигналы с выходов регистра 20 и сигналы кодов номера задачи с выходов .25.125.N регистров 21. Сигналы с шин 25.1-25.N, определяющие коды доступности процессоров, поступают на соответствующие дешифраторы 13.1-13.N. На выходе дешифратора 13 сигнал появляется в том случае, если соответствующий ему процессор может решить подзадачу распределяемой задачи.

9 ,

ВИЙ на входах блоков lO..N элементов И с их выходов снимаются сигналы назначения процессоров, по которым через элементы ИЛИ l2.1-t2.N обнуляются соответствующие разряды в регистре 20 и соответствующие регистры 21.1-21.N. После этого в соответствующие блоки 1О.1-1О.N элементов И закрьюаются.

Далее в работе устройства возможны две Ситуации: после первоначального распределения все необходимые процессоры назначены задаче; после первоначального распределения не все необходидигые процессоры назначены задаче.

В первом случае устройства завершает обслуживание рассматриваемой задачи и формируется сигнал считьтания из регистра 19.L аналагочно рассмотренному вьше. Устройство переходит к обслуживанию следзпощей заявки на решение задачи.

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

В регистре 20 не все разряды обнулены, поэтому на выходе элемента ИЛИ 8 сохраняется единичный потен циал, что соответствует разрешению кольцевого циклического сдвига содержимого регистра 20 по тактовым

5196610

импульсам с выхода 18 генератора 16. Этими же импульсами осуществляется управление кольцевым циклическим сдвигом содержимого регистров 21.15 21.N. При этом после каждого очередного такта сдвига производится попыт-ка распределения процессоров задаче, аналогично вьшеуказанному. Этот процесс продолжается до тех пор, пока

10 не вСе требуемые процессоры 23.123,N назначены задаче. Как только распределение процессоров будет завершено, на выходе элемента ИЛИ 8 устанавливается нулевой потенциал

15 и новая заявка выбирается на обслуживание из очереди. Работа устройства завершается в том случае, если в очереди нет заявок и устройство не занято обслуткиванием

20 заявки. В этом случае на выходе

элемента ИЛИ-НЕ 7 формируется единичный потенциал, который поступает на вход элемента И 4. По тактовому импульсу с выхода 17 генератора 16,

25 поступакядему на другой вход элемента И 4, триггер 14 переводится в нулевое состояние, запрещая генерацию тактовых импульсов генератором 16. В дальнейшем устройство готово к новому циклу

0 работы.

Применение изобретения позволяет повысить быстродействие устройства.

EEL

Sj

i ----(С. ....

- ё

d

f I g I

-

} g

№

т f I

1

ж

fg-illTIT ;