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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) 966 А

4(51) С 06 F 9/46

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЬП ИЙ (21) 3670991/24-24 (22) 02 ° 12.83 (46) 23.04.85. Бюл. К- 15 (72) С.Н.Ткаченко, В.И.Ярмонов, В.С.Харченко, Г.Н.Тимонькин и Т.E.Ñåìåíîâà (53) 684.325(088.8) (56) 1. Авторское свидетельство СССР

У 629538, кл. G 06 Г 9/00,. 1977.

2. Авторское свидетельство СССР

Р 866560, кл. 6 06 Р 9/46, 1981 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОПЕССОРАИ, содержащее группу регистров хранения, регистр сдвига, регистр готовности процессоров элемент ИЛИ, группу блоков элементов

И, блок элементов И, первый элемент

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

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

Известно устройство для распреде- 5 ления заданий процессорам, содержащее регистр готовности процессоров, группу элементов Ц, блок управления, регистр сдвига, процессоры, элементы

ИЛИ (11.

Ю

Недостатками этого устройства являются низкая надежность вследствие существования высокой вероятности потери заявки на решение задачи, вызванной отказом устройства от 15

BbIIIoJIHPHHH r1 HHR, B слУчае, когДа число свободных процессоров меньше количества потребных процессоров; ограниченные функциональные возможности, проявляющиеся в том, что в . 20 устройстве отсутствует воэможность организации очереди заданий.

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

I нака номера задачи первого регистра хранения группы, группу входов признака числа потребных процессоров первого регистра хранения группы, первую и вторую группы элементов И, элемент И„ регистр сдвига, информационный вход регистра сдвига, элемент ИЛИ, блох элементов ИЛИ, группу процессоров, регистр готовности процессоров, блок управления, первый вход которого соединен с входом пуска устройства, группа выходов регистра готовности процессоров соеди« иена с первыми входами элементов И первой группы, вторые входы которых соединены с группой выходов регистра сдвига и с группой входов элемента

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

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

М щего элемента И этой группы, первыи g0 вход последнего элемента И второй группы соединен с вторым выходом блока управления (21 .

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

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

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

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

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

И-ИЛИ группы соединена с группой информационных входов одноименного регистра обслуживания группы, группа выходов каждого регистра обслуживания группы, кроме последнего, соединена с второй группой выходов сле3 1151 дуннцего блока элементов И-ИЛИ группы, группа выходов последнего регистра обслуживания группы соединена с второй группой входов первого блока элементов И-ИЛИ группы, группа 5 выходов каждого регистра обслуживания группы соединена с. группой входов одноименного дешифратора группы и с группой входов одноименного блока элементов И группы, каждый выход группы выходов регистра готовности процессоров соединен с вторым.входом одноименного блока элементов И группы, третий вход каждого блока элементов И группы соединен с выхо- 15 дом одноименного дешифратора группы, вход сброса каждого регистра обслуживания группы соединен с выходом одноименного элемента ИЛИ группы, вход пуска устройства соединен 20 с единичным входом триггера, выход последнего разряда регистра сдвига соединен с его первым информационным входом, На фиг. 1 представлена функцио- 25 нальная схема предлагаемого устройства; на фиг. 2 — схема алгоритма функционирования устройства.

Устройство (фиг. 1) содержит группу информационных входов 1 устрой- 30 ства, вход 2 пуска устройства, сигнальный выход 3 устройства, элементы

И 4-6, элемент ИЛИ-ИЕ 7, элемент ИЛИ

8, блок 9 элементов И, группу блоКоВ 10 1-10. N элементов И, группу

11.1-11.N блоков элементов И-ИЛИ, группу 12.1..12N элементов ИЛИ, группу

13.1-13.И дешифраторов, триггер 14, одновнбратор 15, генератор 16 импульсов, выходы 17 и 18 генератора 16 . щ импульсов, группу 19. 1-19.L регистров хранения, регистр 20 сдвига, группу

21. 1-21 ° N регистров обслуживания, регистр 22 готовности процессоров, группу 23.1-23.5 процессоров, группу

24 выходов элементов блока 9 элемен-. тов И, 24.1-24.N-первый, Я-й разряды группы 24 выходов блока 9, группы выходов 25.1-25.N регистров .21 1-Zt N, выходы 26.1-26.L признаков наличия 1О заявки регистров 19. 1-19А.

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

966 6

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

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

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

После этого по такту с выхода 17 генератора 16 на выход 3 устройства через элемент И б выдается квитанция а записи заявки в очередь. Продвижение заявки в регистрах 19 осуществляется до того момента, пока заявка не записана в последний регистр 19, Во время продвижения заявки в регистрах 19 на входы 1. устройства могут подаваться очередные заявки, которые также записываются в регистры 19.

Таким образом в регистрах. 19.1-19.L образуется очередь заявок на решение задач.

После записи заявки в последний регистр 19 на выходе 26.1 последнего

21.N, и для этих регистров через блоки 11.1-11.N формируются цепи для циклического сдвига содержимого регистров 21. 1-2t.N от первого к последнему, а выход последнего регистра

21.N подключается к входу первого регистра 21.1.

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

20 подключен к входу первого разряда.

Это позволяет осуществлять многократную попытку распределения процессоров задаче.

Кроме того, при изменении выходного потенциала элемента ИЛИ 8 с нулевого на единичный одновибратором

15 формируется импульс, по которому последний регистр 19.L устанавливается в нулевое состояние. При этом разрешается прохождение тактовых импульсов генератора 16 через элемент

И 5, которые управляют записью и продвижением заявок в регистрах

19. 1-19.N.

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

При этом целесообразно рассматривать работу устройства в два этапа: первоначального назначения процессоров; последующего назначения процессоров.

Первоначальное назначение процессоров осуществляется следующим образом.

С выходов регистра 22 готовности процессоров сигналы готовности поступают на входы 10,1-10.N элементов И. На эти же блоки поступают сиг-. налы с выходов регистра 20 и сигналы кодов номера задачи с выходов 25. 125.N регистров 21. Сигналы с шин

25. 1-25.N, определяющие коды доступности процессоров, поступают на со ответству ацие дешифраторы 13.1-13.N.

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

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

Выбор заявки на обслуживание из 10 регистра 19.L осуществляется всякий раз, когда в очереди есть заявки и устройство не занято обслуживанием.

Сигнал о том, что устройство не занято обслуживанием заявки, форми- 15 руется на выходе элемента ИЛИ 8, если в регистре 20 все разряды установлены в нулевое состояние.

В начале работы устройства регистр

20 находится в нулевом состоянии и, 20 поэтому, нулевым потенциалом с выхода . элемента ИЛИ 8 открыт блок 9 элементов И. После записи заявки в .регистр

19.Ь на выходах блока 9 устанавливается код заявки, определяющий код 25 количества процессоров, необходимых для решения задачи (на выходах 24) и коды номера задачи и доступности процессоров. Так как на входе разрешения сдвига регистра 20 установлен, з0 нулевой потенциал, то под управлением тактовых импульсов с выхода .18 генератора 16, поступающих на вход разрешения записи регистра 20, осуществляется запись параллельного кода с выходом 24 блока 9 в регистр 20.

Кроме того, тактовые импульсы с выхода 18 генератора 16 поступают на тактовые входы регистров 21.121.0. При этом к информационным 40 входам этих регистров через блоки

11. 1".11.И осуществляется подключение входов 24 только для тех регистров, которым соответствует единичное состояние соответствующего разряда 4S

24.1-24.N. Таким образом, по очередному. тактовому импульсу с выхода 18 генератора 16 происходит запись кода количества процессоров в регистр 20, а в регистры 21.1-21.N — запись ко- 0 дов номера задачи и доступности процессоров.

После записи кода количество процессоров в регистр 20 на выходе элемента ИЛИ 8 устанавливается единичный5 потенциал, яо которому закрывается блок 9 элементов И, отключаются вы- ходы 24 от входов регистров 21. 19 1151 вий на входах блоков 10.1-10.N элементов И с их выходов снимаются сиг. налы назначения процессоров, по которым через элементы ИЛИ 12.1-12.N обнуляются соответствующие разряды, в регистре 20 и соответствующие регистры 21.1-21Л. После этого в соответствующие блоки 10.1-10.N

:элементов И закрываются.

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

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

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

В регистре 20 не все разряды обнулены, поэтому на выходе элемента

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

966 10 импульсам с выхода 18 генератора 16 °

Этими же импульсами осуществляется управление кольцевым циклическим сдвигом содержимого регистров 21.121.N. При этом после каждого очередного такта сдвига производится попыт-. ка распределения процессоров задаче, . аналогично вышеуказанному. Этот процесс продолжается до тех пор, пока не все требуемые процессоры 23.12З.N назначены задаче. Как только распределение процессоров будет завершено, на выходе элемента ИЛИ 8 устанавливается нулевой потенциал и новая. заявка выбирается на обслуживание из очереди.

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

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

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

1151966

1151966

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4

БНИИПИ

Тираж 710

Заказ 2325/38

Подписное