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

 

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

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

РЕСПУБЛИК

09) ацл G 06 F 9/46

ply>,1

ОСУДАРСТВЕННОЕ ПАТЕНТНОЕ едОмстВО сссР

ГОСПАТЕНТ СССР) АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1) 4702656/24

2) 08.06.89

6) 30,08.93, Бюл. М 32

2) В.А;Титов, Ш.Т.Азанчеев, В,Я.Аронов и .Б.Петровский

6) Авторское свидетельство СССР

964643, кл. G 06 F 9/46, 1980.

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

1126963, кл, G 06 F.9/46, 1982.

4) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

АДАНИЙ ПРОЦЕССОРАМ

7) Изобретение относится к области выислительной техники и может быть испольовано в разработках аппаратного испетчера при обработке пакета задач в

Изобретение относится к области выислительной техники и может быть испольовано в разработках аппаратного испетчера при обработке пакета задач в ногопроцессорной или многомашинной

ычислительной системе.

Цель изобретения — расширение функиональных воэможностей за счет органиации распределения пакета задач с рерываниями.

На фиг.1 представлена структурная схеа устройства для распределения заданий роцессорам; на фиг.2 — структурная схема лока управления; на фиг,3 — структурная хема коммутатора, на фиг.4 — структурная хема сумматора.

Устройство содержит(см. фиг.1) блок упавления 1, элемент ИЛИ 2, счетчик 3, регитры 4 и 5, счетчик 6, коммутатор 7, схему равнения 8, элемент ИЛИ 9, регистр 10, лок регистров 11<.„11„, мультиплексор 12, локи элементов И-ИЛИ 13 и 14, сумматор микропроцессорной или многомашинной вычислительной системе. Цель изобретения— расширение функциональных воэможностей за счет обеспечения распределения заданий и с учетом прерываний задач, Устройство содержит группу регистров, второй. третий, четвертый, пятый и шестой регистры, мультиплексор, первый и второй блоки элементов И-ИЛИ, первый и второй счетчики, коммутатор, первую и вторую схемы сравнения, первый и второй элементы

ИЛИ, сумматор, третий блок элементов ИИЛИ, блок элементов И. элемент задержки, блок деления, блок управления. 1 з,п. ф-лы, 4 ил.

15, блок элементов И-ИЛИ 16, регистр 17, схему деления 18, регистр 19, схему сравнения 20, элемент задержки 21, блок элементов И 22, вход 23>, на который подается сигнал запуска, входные шины 23z, на которые подается код числа процессоров, входные шины 23з, на которые подается код числа заданий, входы 24,...,24 для записи кодов "весов" задач, выход 25, с которого выдается сигнал останова, выходные шины.

26, с которого выдается код задания в процессоры.

Блок управления 1 (см. фиг.2) содержит формирователь импульса 27, элемент ИЛИ

28, триггер 29, генератор импульсов 30, элемент ИЛИ 31, постоянное запоминающее устройство (ПЗУ) 32, элемент ИЛИ 33, счетчик 34, триггер 35, элемент ИЛИ 36, дешифратор 37, элемент ИЛИ 38, элементы И 39, 40 и 41, вход 42, вход 43, на который поступает сигнал со схемы сравнения 20 (см. фиг.1), вход 44, на который поступает сигнал

1837287 са схемы сравненил 8 (см. фиг.1), выход 45, rlo которому подается сигнал сброса, выходные шины 46, по которым выдаются управляющие сигналы 1...20.

Коммутатор 7 (см. фиг.3) содержит элемент И-ИЛИ 47„элементы 481...48I<, И

491...49л. дЕШИфратар 50, ЭЛЕМЕНТЫ И

51;...51и, выходные шины 521...52л, на которые выдается код "веса" задания, код номера процессора, код номера задания, синхрониз11ру ощий1 импульс, вход 53 синхроимпуньса, входные шины 54, по которым подается номер процессора, входные шины

55, по которым подается номер задания, входные шины 56, по которым поступает код

"веса" задания с выхода буферного регистра 10, вход 57, по которому поступает разрешающий импульс, с выхода ПЗУ 31 (15), входные шины 59, па которым поступает код

"веса" задания, с выхода буферного регистра 17, вход 58, по которому поступает разрешающий импульс с выхода ПЗУ 32 (17), входные шины 60, па которым поступает код

"веса" задания с выхода мультиплексора 12, вход 61, по которому поступает разрешающий импульс с вь1хада ПЗУ 32 (18).

Сумматор 15 (см. фиг,4) содержит блок элементов И 62, схему сложения 63, блок элемент И-НЕ 64, блок элементов И-ИЛИ 65, элемент HE 66,.входные шины 67, по которым поступает код первого операнда, входные шины 68, llo которым поступает код второго операнда, вход 69, по которому поступает синхранизирующий импульс с ПЗУ

32, вход 70, по которому поступает кад oilGрации с ПЗУ 32, выходные шины 71, по которым выдается код результата.

В исходном состоянии все счетчики, регистры и триггеры находятсл в нулевом состоянии (входы установки в нуль на рисунках не показаны). По входам 241...24л заносится "веса" решаемых задач, на реГистр 4 llo входу 233 заносится числа задач в пакете. по входу 237. на регистр 5 заносится код числа процессоров.

Работа устройства начинается после подачи сигнала запуска по входу 231 блока

1 (вход 42 бл.1, см. фиг.2), после чего устанавливается и единицу триггер 29, единичный сигнал с выхода которого поступает на вход формирователя импульсов 27, Сформированный единичный сигнал с выхода формирователя 27 (выход 45 блока 1 сбрасывает в нуль счетчики 3, 6, регистры t0, 17 (cM. фиг.1). Кроме того единичным сигналом с выхода триггера 29 запускается генератор

30 блока ",. Сдиничным сигналом с выхода формирователя 27 устанавливается в нуль счетчик 34 и в едичицу триггер 35 через элемент ИЛИ 33. После занесения информации в регистр 4 на выходе схемы сравнения

8 (выход несравненил) будет сигнал логической диницы, который по входу 44 поступает в блок 1. Единичный сигнал с выхода триггера 35 переводит счетчик 34 в режим счета. Следователь1<о, по первому импульсу с выхода генератора 30, счетчик 34 переходит и состояние 00001, после чего выбирается первая строка матрицы ПЗУ, в результате чего на шинах 2 и 8 (выхад 46) матрицы 32 появляются сигналы логической

1 и к содержимому счетчика 3 прибавляется единица, а сумматор 15 переводитсл в режим сложения. Выходы сче1чика 3 падсае15 динены к адресным входам мультиплексора

12, на выходе которого появится код, зафиксированный на регистре !1, Далее, по второму импульсу генер«30 выбирается вторал строка матрицы 32 и сип алы лагиче20 ской единицы появятся на ее шинах 3, 4, 7, 8, 9, 12. Информация с регистра 111 через мультиплексор 12 поступает на первый вход элемента И-ИЛИ 13 и после подачи стробирующего сигнала по шине 3 блока 1 поступает на вход А первого слагаемого сумматора 15. Одновреме1н<о на первый вход элемента И-ИЛИ 14 поступает код, выхода регистра 17 через открытый блок элементов И 22 (вначале эта будет нулевой кад)

30 и по страбирующему сигналу по шине 4 блока 1 пасгупает на вход Б второго слагаемого. Па сигналам с шины 7, 8 блока 1 сумматор выполняет операци|о сложения и через элементы И-ИЛИ 16 по стробирующе35 му сигналу с шины 9 блока 1 результат суммирования записывается в регистр 17, причем запись асуществляетсл па единичному сигналу, поступающему по шине 12 блока 1 через элемент -адержки 21. Необхо 10 димасть применения элементов 21, 22 обусловлена тем, что возникает необходимость закрытия шины с выходов регистра 17 для правильной работы сумматора. По третьему импульсу, с выхода генератора 30 считыва45 ется третья строка матрицы 32, к содержимому счетчика 3 прибавляется единица, при этом никаких других преобразований в устройстве нс производится. Теперь на выходе счетчика 34 хранится кад 00011, который

50 поступает на вход дешифратара 37, на третьем выходе которого формируется си<нал логической единицы. Этот сигнал проходит через открытый элемент И 39, элемент

ИЛИ 36 и сбрасывает триггер 35 в нуль, тем самым счетчик 34 переводится в режим записи информации. Кроме того, единичный сигнал с выхода элемента 39 через элемент

ИЛИ 31 обеспечивает запись в счетчик 34 кода 00010, Далее суммирование кодов происходит аналоги гно, пока на выходе схемы

1837287

: 8 не появится нулевой сигнал, и триггер 35, останется в состоянии логической единицы, на счетчике 34 сформируется код 0100 и ! будет далее выбрана четвертая строка мат, рицы 32, Далее, сигналом логической еди: ницы по шине 13 блока 1 запускается схема

: деления 18, где происходит деление суммы

, "весов" заданий, которые поступают на пер, . вый вход А схемы 18, на значение числа, процессоров, которое хранится на регистре

: 5. С приходом очередного импульса на счет,чик 34 из матрицы 32 считывается пятая

; строка, после чего единичный сигнал по ши: не 14 блока 1 переписывает частное из блока 18 на регистр 19. При считывании из

:, матрицы 32 шестой строки единичный сиг, :нал по шине 1 блока 1 через элемент ИЛИ 9, устанавливает в нуль регистры 10 и 17, а

; через элемент ИЛИ 2 — счетчик 3. После

; считывания седьмой строки матрицы 32

: единичным сигналом по шине 2 блока 1 в

;: счетчик 3 заносится вновь код единицы. Од; новременно с этим единица заносится и в

: : счетчик 6 по сигналу логической единицы с

: шины 20 блока 1. После считывания вось,, мой строки матрицы 32 единичными сигна:лами по шинам 3 и 4 блока 1 производятся

; следующие действия. Код с регистра 11 че: рез мультиплексор 12, открытый единичным сигналом по шине 3 блока 1 элемент И-ИЛИ 13 поступает на вход А сумматора 15 (пер,вый операнд), на вход В второго операнда :поступает с выхода регистра 17 (в начале

,,код нулей) через открытый блокирующий

|элемент И 22 и через открытый единичный сигналом по шине 4 блока 1 элемент И—

:;ИЛИ 14.

По сигналам логических единиц по ши;:нам 7 и 8 блока 1 сумматор 15 выполняет ,операцию сложения, результат с выхода сумматора 15 через открытый единичным

,сигналом по шине 9 блока 1 элемент И-ИЛИ

16 поступает на вход регистра 17 и по еди ничному сигналу по шине 12 через элемент задержки 21 блока 1 записывается на него. осле считывания девятой строки матрицы

2, содержащей во всех разрядах только ули, никаких операций в устройстве не бует происходить, При этом на выходе схемы равнения 20 будет вырабатываться сигнал огического нуля, который поступает по вхоу 43 в блок 1, закрывая элемент И 40, если начение суммы на регистре 17 меньше треуемого времени загрузки одного процессоа или сигнал логической единицы в ротивном случае. В первом случае сигнал входа 9 дешифратора 37 через элемент И

0 не будет сбрасывать триггер 35 в нуль, на четчике 34 зафиксируется код числа 10 и. удет считана десятая строка матрицы 32.

После считывания десятой строки матрицы

32 сигналы логических единиц, поступающие на шины 16 и 18 блока 1 открывают элемент И-ИЛИ 47 блока 7 и информация с мультиплексора 12, счетчика 3, счетчика 6 по разрешающему сигналу по шине 16 блока 1 поступит в блок 7, а затем на выход 26 устройства. Далее аналогично будет выбрана одиннадцатая строка матрицы 32, При этом единичный сигнал поступает по шине

2 блока 1 и к содержимому счетчика 3 прибавляется единица. После считывания двенадцатой строки матрицы 32, содержащей все нули в устройстве никаких действий не производится. Если текущий номер задачи меньше, чем общее количество заданий М, то на выходе схемы сравнения 8 будет присутствовать сигнал логической единицы, поступающий на вход 44 блока 1, в результате открывается элемент И 41 и единичный сигнал через элемент ИЛИ 36 сбрасывает в нуль триггер 35, после чего счетчик 34 переводится в режим записи, и в счетчик 34 записывается код 01000 и после выбора восьмой строки матрицы 32 с выхода 8 дешифратора 37 сигнал логической единицы через элемент ИЛИ 38, элемент ИЛИ 33 поступает на установочный в единицу вход триггера 35, переключая его в состояние логической единицы, Тем самым счетчик 34 переводится опять в режим счета, и описанный выше процесс повторяется до тех пор пока на выходе схемы сравнения 8 не появится сигнал логического нуля. Этим сигналом закрываются элементы 39 и 41 после чего будет выбрана тринадцатая строка матрицы 32 и на шине 19 блока 1 появится единичный сигнал. Если же на выходе схемы сравнения 20 (см. фиг.21 по входу 43 блока 1 будет сформирован сигнал логической единицы, то единичный сигнал с выхода 9 дешифратора 37 проходит через элемент И 40, элемент ИЛИ 36 и устанавливает триггер 35 в нуль, разрешается запись информации в счетчик 34, куда заносит" я код 01110, Этот код появляется на выходах счетчика 34 и поступает на вход дешифратора 37, после чего единичный сигнал с выхода 14 дешифратора, проходя через элемент ИЛИ 33 и вновь устанавливает s единичное состояние триггер 35, по которому счетчик 34 переводится в режим счета. Далее выбирается четырнадцатая (нулевая) строка матрицы 32, в результате чего никаких действий в устройстве не происходит, По следующему импульсу с выхода генератора 30 на счетчике

34 фиксируется код числа 15 и выбирается пятнадцатая строка матрицы 32. Единичные сигналы по шинам 5 и 6 блока 1 разрешают работу элементов И-ИЛИ 13 и 14 и инфор1837287 мация с выходов регистров 17 и 19 поступает на входы А и В сумматора 15, Сигналами логической единицы па шине 7 блока 1 на сумматоре 15 осуществляется операцил вычитания, т.к. на шине 8 блока 1 будет нуле- 5 вой сигнал, ll результат такого сложения через элемент И-ИЛИ 16 па сигналу логической единицы па шине 9 блока 1 поступает на входы буферных регистров 10 и 17, а по сигналу логической единицы по шинам 11 10 записываетсл на регистр 10, а по сигналу логической единицы по шине 12 через элемент задержки 21 запитываетсл на регистр

17, По следующему импульсу с выхода генератора 30 будет выбрана шестнадцатал 15 строка матрицы 32, после чего сигналами логических единиц с шин 3 и 4 блока 1 информация с мультиплексора 12 и буферного регистра 17 через элементы И-ИЛИ 13 и 14 подается на входы А и В сумматора 15. По 20 сигналу логической единицы с шины 7 и и ри нулевом сигнале с шины 8 блока 1 сумматора 15 выполняет операцию вычитания. Результат этой операции сигналам логической единицы по шине 9 блока 1 передается че- 25 рез элемент И-ИЛИ 16 и по сигналу логической единицы на шине 12 блока 1 через элемент 21 записывается на регистр 17. Далее аналогично выбирается семнадцатал строка матрицы 32, после чего сигналам ло- 30 гических единиц на шинах 16 и 17 блока 1 информация с буферного регистра 17 со счетчиком 6 и 3, поступает в блок 7 для выдачи номера задачи; времени ее решенил и номера процессора на выходы устройства, 35 после чего считываетсл восемнадцатая строка матрицы 32. По единичному сигналу с шины 20 блока 1 а счетчик 6 прибавляется единица. Далее считывается девятнадцатая строка матрицы 32. Единичными сигналами 40 по шинам 15 и 16 блока 1 информация с регистра 10 поступает о блок 7 для выдачи очередного номера активного процессора на выход 26 устройства, Далее оыбираетсл двадцатал строка матрицы 32 и сигналом 45 логической единицы па шине 10 блока 1 информация с выхода буферного регистра

10 через элемент И-ИЛИ 16 поступает на вход регистра 17. Единичный сигнал с выхода 20 дешифратора 37 через элемент ИЛИ 50

36 сбрасывает триггер 35 в нуль, разрешается запись информации о счетчик 34. В счетчик 34 заноситсл код 01011,после чего будет считана одиннадцатая строка матрицы 32 и работа устройства будет продал- 55 жаться да тех пор, пока на выходе схемы сравнения 8 не сформируется сигнал логи-. ческого нуля, по которому закрывается элемент И 41, благодаря чему далее будут последовательчо считаны двенадцатая и тринадцатая строки матрицы 32, После считывания тринадцатой строки матрицы 32 единичным сигналом по шине 19 блока 1 триггер 29 сбрасывается в нуль, запрещая работу генератора 30, Сигнал на шине 19 (выход 40) блока 1 лоляется сигналом окончания работы устройства.

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

Формула изобретения

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

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

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

30

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

ыходы блока управления подсоединены к ервому и второму входам блока элементов

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

ыход блока управления подсоединен к вхоу управления режимом блока деления, втоой группа входов которо: о подсоединена к руппе выходов четвертого регистра, группа

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

20 равления подсоединен к счетному входу второго счетчика, группа выходов которого подсоединена к группе адресных входов коммутатора, выход второй схемы сравнения подсоединен к второму входу блока управления, вход запуска устройства соединен с третьим входом блока управления, двадцать первый выход которого явл.":ется выходом готовности устройства, группа информационных выходов которого соединена с группой выходов коммутатора. первая и вторая группы кодовых входов которого соединены cooTBGTGTBGHHoс группой информационных входов третьего регистра и с группой информационных входов четвертого регистра, каждая группа информационных входов устройства соединена с группой информационных входов одноименного регистра группы.

2. Устройство по п,1, от л и ч а ю щ е ес я тем, что блок управления содержит генератор импульсов, формирователь импульсов, с первого по пятый элементы ИЛИ, первый и второй триггеры, первый, второй и третий элементы И, счетчик, дешифратор и постоянную память, первый выход которой подсоединен к нулевому входу первого триггера, прямой выход которого подсоединен к входу генератора импульсов и через формирователь импульсов — к входу установки E "0" счетчика и к первому входу первого элемента ИЛИ, выход которого подключен к единичному входу второго триггера, прямой выход которого подсоединен к управляющему входу счета счетчика, а инверсный выход — к управляющему входу записи счетчика, группа выходов которого подсоединен к адресным входам постоянной памяти и к входам дешифратора, первый, второй, третий и четвертый выходы которого подсоединены к соответствующим входам второго элемента ИЛИ, выход которого подсоединен к второму входу первого элемента ИЛИ, пятый выход дешифратора подсоединен к первому входу первого элемента И, выход которого подсоединен к первому входу третьего элемента ИЛИ и к первому входу четвертого элемента ИЛИ, выход которого подсоедин:и к нулевому входу второго триггера, шестой выход дешифратора подсоединен к первому входу второго элемента И, выход которого подсоединен к второму входу четвертого элемента ИЛИ. к третьему информационному входу третьего элемента ИЛИ и к первому входу пятого элемента ИЛИ, выход которого подсоединен к четвертому инфор;лационному входу счетчика, седьмой выход дешифратора подссединен к первому входу третьего элемента И, выход которого подсоединен к

1837287

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

1837287

Guz. У

Фг4

Составитель В.Титов

Техред М.Моргентал

Корректор С.Пекарь Редактор Н.Коляда

Производственно-издательский комбинат "Патент", r, Ужгород, ул.Гагарина, 1Î1

: Заказ 2065 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Рауыская наб., 4/5