SU1151966A1 - Устройство дл распределени заданий процессорам - Google Patents

Abstract

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

Description

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

Изобретение относитс  к вычислительной технике и может быть использовано дл  построени  многопроцессор ных вычислительных систем. Известно устройство дл  распределени  заданий процессорам, содержащее регистр готовности процессоров, группу элементов И, блок управлени  регистр сдвига, процессоры, элементы ИЛИ 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 группы..

66 .

Группа регистров 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 ;

Claims (1)

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

   9961SU соединены соответственно с входами элемента ИЛИ-HE, выход признака наличия заявки последнего регистра хранения группы соединен с инверсным входом второго элемента И, выход признака наличия заявки первого регистра хранения группы соединен с первым входом третьего элемента И, выход которого является сигнальным выходом устройства, первый выход генератора импульсов соединен с вторыми входами первого и третьего элементов И, второй выход генератора импульсов соединен с входом разрешения записи регистра >

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