Микропрограммный диспетчер многопроцессорной вычислительной системы Советский патент 1989 года по МПК G06F9/50 

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

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

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

Устройство содержит блок 1 памяти микропрограмм, блок 2 очереди заявок, регистр 3 адреса микрокоманд, регистр 4 микрокоманд, регистр 5 ко да номера задачи, регистр 6 кода числа процессоров, группу регистров 7 дообслуживаемых заявок, регистр 8 готовности процессоров, триггер 9 пуска, группу триггеров 10 управления, мультиплексор 11 логических условий, мультиплексор 12 адреса, мультиплексор 13 дообслуживания, коммутатор 14, дешифратор 15 дообслуживания, дешифратор 16 управления очередью заявок, элемент И 17, группу элементов И 18, группу блоков элементов И 19, элемент И 20, элемент ИЛИ 21, группу элеменten

со ю

СО

го

о

тов ИЛИ 22, элемент ИЛИ 23, блок 24 формирования логических условий-, генератор 25 тактовых импульсов, группу входов 26 кодов операций, группу входов 27 кодов заявок первого типа, вход 28 пуска, группу входов 29 внешних логических условий, группы входов 30 кодов заявок второго типа, группу входов 31 сигналов готовности процессоров, группы выходов 32 кодов номеров задач, группу управляющих выходов 33, группу выходов 34 микроопераций, группу управляющих выходов 35, группу адресных выходов 36 блока 1 памяти микропрограмм, управляющий вы- |ход 37 устройства, первый 38 и второй 39 выходы генератора 25 тактовых импульсов, выход 40 завершения режима, группу выходов 41 сигналов управления очередью заявок, выход 42 управления коммутацией, группу выходов 43 управления дообслуживанием заявок регистра 4 микрокоманд, первый 44, второй 45 и третий 46 выходы дешифратора 16 управления очередью заявок, группу управляющих выходов 47 блока 2 очереди заявок, первый 47.1, второй 47.2, третий 48, четвертый 49, пятый 50.1, шестой 50„2 и третий 51 входы внут- :; ренних логических условий мультиплексора 11 логических условий. Причем блоки 11, 12, 3, 1, 4 и 16 образуют блок микропрограммного управления. Блок 2 очереди заявок содержит группу регистров 52 очереди заявок, первую 53 и вторую 54 группы элементов И, элемент И 55, элемент ИЛИ 56, элемент И 57, элемент И 58 и группу триггеров 59о

Блок 24 формирования логических условий состоит из группы элементов ИЛИ 60, элемента ИЛИ 61 и элемента И 62„

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

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

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

0

5

0

5

0

5

0

5

с временными диаграммами, приведенными на фиг о 4 о

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

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

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

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

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

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

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

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

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

51532

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

Описанные режимы работы устройства соответствуют дисциплине обслужи- вания очередей в соответствии с относительными приоритетами. Наряду с этим в устройстве возможно обслуживание очередей заявок в соответствии С дисциплиной абсолютных и смешанных приоритетов„

Предпочтительное обслуживание заявок второго типа (фиг05).

По тактовому импульсу с выхода 38 генератора 25 в регистр 3 записывается код операции соответствующей микропрограммы управления, который поступает с входа 26 устройства через муль

15 формируется сигнал на выходе 44, затем - на выходе 45, затем - на выходе 46 дешифратора 16. Выполнение микроопераций, определяемых перечисленными сигналами, осуществляется по так-

типлексор 12„ При этом настройка нуль-20 товым импульсам с выхода 38 генератора типлексора 12 определяется нулевым 25.

кодом на выходе 33 блока 1 „ Код one- Рассмотрим запись заявки с входа рации определяет начальный адрес мик- 27 блока 2 в регистр 52.1. По уста- ропрограммы управления. Считанная - новлении единичного потенциала на по этому адресу микрокоманда из блока 25 входе 44 блока 2 и тактовому импульсу

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

Код заявки с входа 26 блока 2 поступает на вход регистра 52.J, а признак наличия заявки - на вход элемента И 54.1. Так как регистр 52.1 находится в нулевом состоянии, то по ряется по логическому условию на вхо- сигналу с входа 45 и импульсу с входа де 50.1, а заявок первого типа - по « 2 ка записывается в

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

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

Наличие заявок второго типа провелогическому условию на входе 47.2 мультиплексора 11 „

1 -л

В случае вылолнения условия ЛУ50.1«ЛУ 51 1 () в устройстве реализуется процесс обслуживания заявок второго типа. Если же выполняется условие ЛУ50.ЬЛУ51-ЛУ47.1 1, (2) то в устройстве реализуется процесс , записи заявок первого типа в очередь блока 2о

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

38 блока 2 заявка записывается в регистр 5201« При этом на выходе признака наличия заявки этого регистра устанавливается единичный потенциал,

4Q запрещающий, запись заявки в этот регистр в очередном такте Поскольку триггер 59.1 установлен в нулевое состояние, обнуление регистра 52.1 по тактовому импульсу с входа 38 при на45 личии сигнала на входе 46 не происходит „

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

ЛУ50„1 ЛУ47.2 ЛУ51 - 1

(3)

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

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

ЛУ50,ЬЛУ47.2 ЛУ51 ЛУ48 1 . (4)

На начальной фазе работы устройства первым истинным условием из проверяемых является условие , ЛУ47.2 ЛУ4701 1. В соответствии с этим рассмотрим реализацию функции записи заявок первого типа в очередь блока 2„

В этом режиме функционирования

0 устройства на выходе 42 регистра 4 ус- установлен единичный потенциал, а на выходе 41 этого регистра последовательно формируются коды сигналов управления очередью. Причем вначале

формируется сигнал на выходе 44, затем - на выходе 45, затем - на выходе 46 дешифратора 16. Выполнение микроопераций, определяемых перечисленными сигналами, осуществляется по так-

0 товым импульсам с выхода 38 генератора 25.

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

38 блока 2 заявка записывается в регистр 5201« При этом на выходе признака наличия заявки этого регистра устанавливается единичный потенциал,

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

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

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

5 заявки.

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

установку триггера 59 .L в единичное состояние и в последующем обнуле- нИе регистра 52.L,

Если все регистры 52 блока 2 содер- заявки, то на выходе 47.1 эле- Цента И 55 устанавливается единич- я)ый потенциал, по которому запреща- е)тся запись заявок в очередь. 1 Если хотя бы в одном регистре 52.1 «|сть заявка на обслуживание, на выгоде 47.2 элемента ИЛИ 56 установлен единичный потенциал, по которому разрешается выборка заявок из очереди ,н|а обслуживание

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

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

При обслуживании заявок второго типа на выходе 42 регистра 4 устанавливается единичный потенциал, а на выходе 43 формируется последователь- ность кодов, управляющих настройкой гультиплексора 13 и дешифратора 15, Код заявки из одного регистра 7 через мультиплексор 13 поступает на вход коммутатора 14 и в дальнейшем записывается в регистры 5 и 6 под воздействием тактового импульса с выхода 38 генератора 25, после чего на соответствующем выходе дешифратора 15 формируется единичный импульс, устанавли - вающий соответствующий триггер 10 и регистр 7 в нулевое состояние„

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

5

0

5

0

5

0

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

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

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

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

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

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

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

После записи кода номера задачи в регистр 5 и кода числа процессоров в

задаче назначается одновременно

При последующих распределениях

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

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

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

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

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

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

Рассмотрим процесс формирования очереди заявок второго типа. По завершению решения задачи на первой фазе обслуживания заявок соответствующий К-й процессор выставляет код заявки на соответствующих входах 30„К устройства , а также формирует импульс сигнала готовности на входе. 30„К. При этом код заявки записывается в регистр 7„К и осуществляется восстановление единичного потенциа- ла готовности К-го разряда регистра 8. При наличии заявок в регистрах 7 на выходе 50„1 блока 24 устанавливается единичный потенциал, который является проверяемым логическим уело- вием 50.1 мультиплексора 11.

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

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

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

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

Фае. 1

rirTti

РЛ A/f П Ј

«

( Начало }

. I

I коп -+- к&з

-

0