Микропрограммный диспетчер многопроцессорной вычислительной системы

 

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

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

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

РЕСПУБЛИК (19) (Н) (50 4 С 06 F 46

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

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГННТ СССР

1 (21) 4377001/24-24 t (22) 18.11,87 (46) .30.12.89. Вюл. У. 48 (72) С.Н.Ткаченко, В.И.Ярмонов, С.П,Козий, Г.Н,Тимонькин, В.С,Харченко и А,И.Просвирницин (53) 681,325(088.8) (56) Авторское свидетельство СССР

11 1196866а кл, G 06 F 9/46, 1984.

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

Ф 1151966, кл, 0 06 F 9/46, 1983. (54) МИКРОПРОГРАММНЫЙ ДИСПЕТЧЕР NHO-

ГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ (57) Изобретение относится к вычислительной технике и может быть использовано при построении многопроцессорных вычислительных систем. Цель изобретения — расширение области примеИзобретение относится к вычислительной технике и может быть использовано при построении .многопроцесоор" ныл(вычислительных систем.

Цель изобретения — расширение об" ласти применения за счет воэможности перераспределения задач между процессорами.

На фиг.l приведена функциональная схема устройства; на фиг.2 " схема блока очереди заявок; на фиг.3 — схе-т ма блока формирования логических условий; на фиг.4 — временная диаграмма импульсов, формируемых генератором тактовых импульсов; на фиг,5— блок-схема алгоритма функционирования устройства.

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

Устройство содержит блок 1 памяти микропрограмм, блок 2 очереди за- ф 1 явок, регистр 3 адреса микрокоманд, © регистр 4 микрокоманд, регистр 5 ко- Я ) да номера задачи, регистр 6 кода чис— ла процессоров, группу. регистров 7 дообслуживаемых заявок, регистр 8 готовности процессоров,- триггер 9 пуска,группу триггеров 10 управления,мультиплексор ll логических условий, мультиплексор 12 адреса, мультиплексор

13 дообслуживания, коммутатор 14, дешифратор 15 дообслуживания, дешифратор

16 управления очередью заявок, элемент.И 17, группу элементов И 18, .группу блоков элементов И 19, элемент.

И 20, элемент ИЛИ. 21, группу элемен1532926 тов ИЛИ 22, элемент ИЛИ 23, блок 24 формирования логических условий; генератор 25 тактовых импульсов, группу входов 26 кодов операций, группу входов 27 кодов заявок первого типа, вход 28 пуска, группу входов 29 внешних логических условий, группы входов 30 кодов заявок второго типа, группу входов 31 сигналов готовности процессоров, группы выходов 32 кодов номеров задач, группу управляющих выходов 33, группу выходов 34 микроопе раций, группу управляющих выходов 35, группу адресных выходов 36 блока l памяти микропрограмм, управляющий вы" ход 37 устройства, первый 38 и второй

39 выходы генератора 25 тактовых импульсов, выход 40 завершения режима, группу выходов 41 сигналов управления 20 очередью заявок, выход 42 управления коммутацией, группу выходов 43 управления дообслуживанием заявок регист,ра 4 микрокоманд, первый 44, второй

; 45 и третий 46 выходы дешифратора 16 ,управления очередью заявок, группу управляющих выходов 47 блока 2 очере ди заявок, первый 47.1, второй 47.2, третий 48, четвертый 49, пятый 50.1, шестой 50.2 и третий 51 входы внут- 30 ренних логических условий мультиплек,сора 11 логических условий. Причем блоки 11, 12, 3, 1, 4 и 16 образуют

;блок микропрограммного управления.

Блок 2 очереди заявок содержит группу регистров 52 очереди заявок, первую 53 и вторую 54 группы элемен, тов И, элемент И 55, элемент ИЛИ 56, элемент И 57, элемент И 58 н группу триггеров 59.

Блок 24 формирования логических условий состоит из группы элементов

ИЛИ 60, элемента ИЛИ 61 и элемента

И 62, Устройство работает следующим обр азо.м.

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

По сигналу пуска, поступающему на вход 28 устройства триггер 9 устаЭ

55 навливается в единичное состояние.

При этом на выходах 38 и 39 генерато. ра 25 разрешается формирование тактовой сетки импульсов в соответствии с временными диаграммами, приведенными на фиг.4.

Одновременно с сигналом пуска на входы 26 и 27 устройства подаются код операции и код заявки соответственно.

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

В устройстве реализованы очереди заявок двух типов.

Заявки первого типа — это заявки, впервые поступающие на обслуживание. коды этих заявок хранятся в регистрах 52 блока 2.

Заявки второго типа - это заявки, которые после получения кванта обслуживания на процессорах возвращаются на дообслуживание в устройство; коды этих заявок хранятся в регистрах 7.

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

Приоритет обслуживания принадлежит заявкам первого типа .

В этом случае, при наличии очереди заявок в блоке 2 устройства обслуживаются только заявки этой очереди, а обслуживание заявок второго типа возможно только в случае, когда в блоке

2 очередь пуста. Этот режим целесообразно использовать в тех случаях, когда интенсивность поступления зая" вок первого типа мала и они требуют небольшого количества процессоров.

Приоритет обслуживания принадлежит заявкам второго типа. В этом случае если в регистрах 7 есть .заявки на до" обслуживание, то устройством обслужи" ваются только эти заявки, а заявки первого типа обслуживаются, когда в устройстве нет заявок на дообслуживание. Этот режим целесообразно использовать в том случае, когда заявки второго типа требуют большого числа процессоров, а интенсивность поступления заявок первого типа высока или они требуют большого времени занятия процессоров системы.

В тех случаях, когда характеристи" ки потоков заявок первого и второго типа не определены, целесообразно использовать режим равноприоритетного

1532926 обслуживания очередей. При этом saявки из очередей выбираются на обслуживание попеременно.

Описанные режимы работы устройства соответствуют дисциплине обслуживания очередей в соответствии с относительными приоритетами, Наряду с этим в устройстве возможно обслуживание очередей заявок в соответствии с дисциплиной абсолютных и смешанных приоритетов.Предпочтительное обслуживание заявок второго типа (фиг.5).

По тактовому импульсу с выхода 38 генератора 25 в регистр З.записывается код операции соответствующей микропрограммы управления, который поступает с входа 26 устройства через мультиплексор 12. При этом настройка муль - 20 типлексора 12 определяется нулевым кодом на выходе 33 блока 1. Код операции определяет начальный адрес микроп3 ограммы управления. Считанная по этому адресу микрокоманда из блока

1 определяет выполнение следующих функций в устройстве в соответствии с алгоритмом функционирования, приведенным на фиг.5.

Определяющим условием функционирования устройства. в этом режиме является наличие заявок второ о и первого типов в соответствующих очередях, Наличие заявок второго типа проверяется по логическому условию на вхо-, де 50.1, а заявок первого типа - по

-логическому условию на входе 42.2 мультиплексора 11.

В случае выполнения условия

ЛУ50,1 ЛУ 51 = 1 (1) в устройстве реализуется процесс об» служивания заявок второго типа.

Если же выполняется условие

ЛУ50.1ЛУ51 ЛУ47.1 = 1, (2)

m в устройстве реализуется процесс, записи заявок первого типа в очередь блока 2.

При выполнении условия

ЛУ50,1 ЛУ47,2 ЛУ51 = 1 выполняется обслуживание заявок первого типа, одновременно с этим sassки первого типа, поступающйе на обслуживание со входа 27 устройства, записываются в очередь блока 2.

Состоянию завершения работы устройства соответствует условие

ЛУ50,1 ° ЛУ47.2 ЛУБ) ЛУ48 = 1 . (4) На начальной фазе работы устройства первым истинным условием из проверяемых является условие 5 7 .

° ЛУ47,2 ЛУ47.1=1, В соответствии с этим рассмотрим реализацию функции записи заявок первого типа в очередь блока 2.

В этом режиме функционирования устройства на выходе 42 регистра 4 усустановлен единичный потенциал, а ча выходе 41 этого регистра последовательно формируются коды сигналов управления очередью. Причем вначале формируется сигнал.на выходе 44, затем - на выходе 45, затем " на выходе 46 дешнфратора 16. Выйолнение микроопераций, определяемых перечисленными сигналами, осуществляется по тактовым импульсам с выхода 38 генератора

25, Рассмотрим запись заявки с входа

27 блока 2 в регистр 52.1. По установлении единичного потенциала на входе 44 блока 2 и тактовому, импульсу с входа 38 блока 2 осуществляется установка в нулевое состояние триггеров

59, Это обеспечивает сохранение заявок в очереди и уничтожение.их дублей.

Код заявки с входа 26 блока 2 поступает на вход регистра 52„31 а признак наличия заявки — на вход элемента И 54.1. Так как регистр:52.1 находится в нулевом состоянии, то по сигналу с входа 45 и импульсу с входа

38 блока 2 заявка записывается в регистр 52о1, При этом на выходе признака наличия заявки этого регистра„устанавливается единичный потенциал, 40 запрещающий. запись заявки в этот регистр в очередном такте. Поскольку триггер 59.1 установлен в нулевое состояние, обнуление регистра 52.1 по тактовому импульсу с входа 38 при на 5 личин сигнала на входе 46 не происходит.

В.очередном цикле записи. заявок в очередь блока 2 заявка из регистра 52,1 переписывается в регистр

5р 52.2, если он не занят другой заяв-... кой. При этом триггер 59. l устанавливается в единичное состояние, что обеспечивает вазможность обнуления регистра 52.1 и уничтожение копии

Выбор заявки на обслуживание осуществляется из регистра 52.L. При этом на входе 42 блока 2 установлен нулевой потенциал, что обеспечивает

1532926 установку триггера 59.L в единичное состояние и в последующем обнуление регистра 52.L, Если все регистры 52 блока 2 содер5 явдат заявки, то на выходе 47.1 элемента И 55 устанавливается единичый потенциал, по которому запрещатся запись заявок s очередь, Если хотя бы в одном регистре 52 ° 1 сть заявка на обслуживание, на вы" оде 47.2 элемента ИЛИ 56 установлен диничный потенциал, по которому разешается выборка заявок иэ очереди а обслуживание.

После завершения цикла записи заяви в очередь в устройстве осуществлятся последовательная проверка выпол.ения условий (1)-(4). !

Пусть в очередном цикле проверок логических условий выполнялось услоие (1), По этому условию в устройтве реализуется процесс обслуживания

1 аявки второго типа.

При обслуживании заявок второго .25 ипа на выходе 42 регистра 4 устанавивается единичный потенциал, а на

ыходе 43 формируется последовательость кодов, управляющих настройкой мультиплексора 13 и дешифратора 15. 30

Код заявки из одного регистра 7 через мультиплексор 13 поступает íà вход

:коммутатора 14 и в дальнейшем записывается в регистры 5 и 6 под воздействием тактового импульса с в ода 38 35

; генератора 25 после чего на соответ1 ствующем выходе дешифратора 15 форми руется единичный импульс, устанавли—

1 вающий соответствующий триггер 10 и регистр 7 в нулевое состояние. 40

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

После записи кода номера задачи в регистр 5 и кода числа процессоров в в регистр 6 на выходе 51 элемента ИЛИ 50

23 устанавливается единичный потенциал, запрещающий запись в регистры 5 и 6„ и разрешающий выполнение сдвига содержимого регистра 6.

Назначение К-го процессора задаче 55 осуществляется при выполнении следующего условия

6.К 10.K 8.Ê = 1, т.е. если К-й разряд регистра 6 содержит единицу, К-й процессор свободен и триггер 10.К установлен в нулевое состояние.

При выполнении перечисленных условий на выходах соответствующего бло" ка элементов И 19.К устанавливается код номера задачи, который поступает в процессорное поле с выходов 32.K устройства. При выполнении перечисленных выше условий распределения возможно одновременное назначение, группы процессоров задаче.

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

6 и 8. В дальнейшем соответствующий процессор не может быть назначен для решения задачи до полного освобожде" ния. Одновременно с назначением К-ro процессора для решения задачи из очереди заявок блока 2 в единичное со--. стояние устанавливается соответствующий.триггер 10.К. Назначение этой функции в устройстве поясняется при описании обслуживания заявок второго типа.

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

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

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

После записи кода числа процессоров в регистр 6 назначение соответствующего процессора задаче невозможно по причине.занятого его состояния. Для обеспечения возможности распределения задачи на другие процессоры осуществляется кольцевой сдвиг содержимого регистра 6 в целях поиска свободного процессора. Таким обра1532926, 10 зом процесс распределения задачи по процессорам осуществляется до тех пор, пока все требуемые процессоры будут назначены. Завершается процесс распределения задач по обнулению всех разрядов регистра 6.

При выполнении обслуживания заявок второго типа. в устройстве реализуют- ся следующие процессы: формирование очереди заявок второго типа в регистрах 7; освобождение процессоров; распределение задач из очереди. дообспуживаемых задач по процессорам, Рассмотрим процесс формирования очереди заявок второго типа. По завершению решения задачи на первой фазе обслуживания заявок соответствующий К-й процессор выставляет код заявки на соответствующих входах ЗО.К 20 устройства, а также формирует импульс сигнала готовности на входе

ЗО.К. При этом код заявки записывает-. ся в регистр 7.К и осуществляется восстановление единичного потенциа- 25 ла готовности К-го разряда регистра

8. При наличии заявок в регистрах 7 на выходе 50.1 блока 24 устанавливается единичный потенциал, который является проверяемым логическим усло- 30 вием 50.1 мультиплексора 11.

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

Завершается работа устройства при 40 выполнении условия (4), При этом из блока 1 считывается конечная микрокоманда. На выходе 40 регистра 4 этой микрокоманды установлен единичный потенциал. В очередном такте по импуль- 45 су с выхода 38 генератора 25 на выхо-. де элемента. И 17 формируется единичный импульс, запрещающий формирование тактовой сетки импульсов на выходах генератора 25.

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

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

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

12 группой информационных входов комиутфтора, группа информационных выходфв блока очереди заявок соединена с второй группой информационных вхо5 дов коммутатора, группа выходов кода номера задачи которого соедине-. не с группой информационных. входов р гнстра кода номера задачи, а групп выходов кода числа процессоров — 1О с группой информации входов регистр кода числа процессоров, первый в гход генератора тактовых импульсов с единен с первым входом синхроииэац и блока микропрограммного управлен я, входами синхронизации регистра к да номера задачи, регистра кода ч сла процессоров, блока очереди заявок, стробирующим входом дешифра" тора дообслуживания и вторым входом первого элемента И, выход которого ! соединен с нулевым входом триггера пуска, второй выкрд генератора тактовых импульсов соединен с вторым входом синхронизации блока микро- 25 программного управления, первый и второй выходы признаков заполнения

1 блока очереди заявок соединены со" ответственно с первым и вторым вхо ами внутренних логических условий., ЗО лока микропрограммного управления, 1 выход индикации записи заявки бло а очереди заявок соединен с сигнальным выходом диспетчера, выход первогo элемента ИЛИ соединен с входом разрешения сдвига и входом разрешения записи регистра кода числа npodeccopoa„ с входом разрешения записи

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

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

2. Диспетчер по и. 1, о т л и ч аю шийся тем, что блок формиро" вания логических условий содержит группу элементов ИЛИ, элементы И ИЛИ выходы которых являются соответствен» но первым и вторым выходами блока, группы входов которого соединены с входами элементов ИЛИ группы, выходы которых соединены с входами элемента

И и элемента ИЛИ.

153292б

1532926

1532926

Составитель М,Сорочан

Редактор JI.Ï÷oëèíñêàÿ Техред Л,Олийнык Корректор О,Ципле

Заказ 8100/53 Тираж бб8 Подписное

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

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

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