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

(57) И тельнозованоных вычретени оГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГННТ СССР 4377001/24-2418.1 1.8730. 12.89. Вюл,С,Н,Ткаченко,озий, Г.Н.ТимоА,И,Просвирници681,325(088.8)Авторское свид6866, кл, С Обторское свидет1966, кл, 0 06 КРОПРОГРАИИНИЙ ДИСПЕТЧЕР МНО- ССОРНОИ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ обретение относится к вычисли- технике и может быть испольпри построении многопроцессорислительных систем. Цель изоб - расширение области примеИзобретение относится к вычислительной технике и может быть использовано при построении .многопроцесоор" ныл вычислительных систем.Цель изобретения - расширение об" ласти применения за счет воэможности перераспределения задач между процессорами.На Фиг.1 приведена Функциональная схема устройства на Фиг.2 " схема блока очереди заявок; на фиг.3 - схе"т ма блока формирования логических условий; на фиг,4 - временная диаграмма импульсов, Формируемых генератором тактовых импульсов; на фиг,5 - блок-схема алгоритма функционирования устройства. нения устройства за счет возможностиперераспределения задач между процессорами. Микропрограммный диспетчер .многопроцессорной вычислительной системы содержит блок микропрограммногоуправления, блок очереди заявок, регистр кода номера задачи, регистр кода числа процессоров, регистр дообслуживаемых заявок, регистр готовностипроцессоров, триггер пуска, группутриггеров управления, коммутатор, дешифратор управления, два элемента И,группу элементов И, группу блоковэлементов И, два элемента ИЛИ, дешифратор управления очередью, группу элементов ИЛИ, группу регистров дообслу-.живаемых заявок, мультиплексор дообслуживаемых заявок, блок Формированиялогических условий. 1 з.п, Ф-лы, 5 ил. Устройство содержит блок 1 памяти микропрограмм, блок 2 очереди заявок, регистр 3 адреса микрокоманд, регистр 4 микрокоманд, регистр 5 кода номера задачи, регистр 6 кода чис - ла процессоров, группу. регистров 7 дообслуживаемых заявок, регистр 8 г товности процессоров, триггер 9 пуска,группу триггеров 10 управления,мультиплексор 11 логических условий, мультиплексор 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 блока 1памяти микропрограмм, управляющий вы"ход 37 устройства, первый 38 и второй39 выходы генератора 25 тактовых импульсов, выход 40 завершения режима,группу выходов 41 сигналов управления 20очередью заявок, выход 42 управлениякоммутацией, группу выходов 43 управления дообслуживанием заявок регист,ра 4 микрокоманд, первый 44, второй,блок микропрограммного управления.35Блок 2 очереди заявок содержитгруппу регистров 52 очереди заявок,первую 53 и вторую 54 группы элемен, тов И, элемент И 55, элемент ИЛИ 56,элемент И 57, элемент И 58 н группутриггеров 59.40Блок 24 формирования логическихусловий состоит из группы элементовИЛИ 60, элемента ИЛИ 61 и элементаИ 62,Устройство работает следующим об-.разоо.м.В исходном состоянии регистры итриггеры устройства установлены внулевое состояние эа исключениемрегистра 8, который находится в единичном состоянии, что свидетельствует о готовности процессоров к ис -полнению задачи.По сигналу пуска, поступающему навход 28 устройства триггер 9 устаЭ55навливается в единичное состояние.При этом на выходах 38 и 39 генератора 25 разрешается формирование тактовой сетки импульсов в соответствии с временными диаграммами, приведенными на фиг,4.Одновременно с сигналом пуска навходы 26 и 27 устройства подаютсякод операции и код заявки соответственно,Код операции определяет начальныйадрес микропрограммы управления диспетчеризацией задач, а код заявки -номер соответствующей задачи и числопроцессоров для ее выполнения,В устройстве реализованы очередизаявок двух типов,Заявки первого типа - это заявки,впервые поступающие на обслуживаниекоды этих заявок хранятся в регистрах 52 блока 2,Заявки второго типа - это заявки,которые после получения кванта обслуживания на процессорах возвращаются на дообслуживание в устройство; коды этих заявок хранятся в регистрах 7.В зависимости от реализуемой микро"программы диспетчеризации возможныследующие дисциплины приоритетноговзаимодействия между очередями заявокпервого и второго типов.Приоритет обслуживания принадлежит заявкам первого типа,В этом случае, при наличии очередизаявок в блоке 2 устройства обслуживаются только заявки этой очереди, аобслуживание заявок второго типа возможно только в случае, когда в блоке2 очередь пуста. Этот режим целесообразно использовать в тех случаяхкогда интенсивность поступления зая"вок первого типа мала и они требуютнебольшого количества процессоров.Приоритет обслуживания принадлежитзаявкам второго типа, В этом случае 1если в регистрах 7 есть .заявки на до"обслуживание, то устройством обслужи"ваются только эти заявки, а заявкипервого типа обслуживаются, когда вустройстве нет заявок на дообслуживание, Этот режим целесообразно использовать в том случае, когда заявки второго типа требуют большогочисла процессоров, а интенсивностьпоступления заявок первого типа высока или они требуют большого временизанятия процессоров системы,В тех случаях, когда характеристи"ки потоков заявок первого и второготипа не определены, целесообразно использовать режим равноприоритетного1532926обслуживания очередей. При этом заявки из очередей выбираются на обслуживание попеременно.Описанные режимы работы устройства соответствуют дисциплине обслуживания очередей в соответствии с относительными приоритетами, Наряду сэтим в устройстве возможно обслуживание очередей заявок в соответствиис дисциплиной абсолютных и смешанныхприоритетов.- Предпочтительное обслуживание заявок второго типа (фиг.5).По тактовому импульсу с выхода 38генератора 25 в регистр 3 записывается код операции соответствующей микропрограммы управления, который поступает с входа 26 устройства через мультиплексор 12. При этом настройка мультиплексора 12 определяется нулевымкодом на выходе 33 блока 1. Код операции определяет начальный адрес микропРограммы управления. Считаннаяпо этому адресу микрокоманда из блока1 определяет выполнение следующихфункций в устройстве в соответствии с алгоритмом функционирования, приведенным на фиг.5.Определяющим условием функционирования устройства. в этом режиме является наличие заявок второго и первоготипов в соответствующих очередях,Наличие заявок второго типа проверяется по логическому условию на вхо-,де 50.1, а заявок первого типа - пологическому условию на входе 47.2мультиплексора 11,В случае выполнения условияЛУ 501 фЛУ 51 = 1 (1)в устройстве реализуется процесс обслуживания заявок второго типа,Если же выполняется условиеЛУ 50.1 ЛУ 51 ЛУ 47,1 = 1) (2)жо в устройстве реализуется процесс,записи заявок первого типа в очередьблока 2,При выполнении условия ЛУ 50,1 фЛУ 47,2 фЛУ 51 = 1 выполняется обслуживание заявок первого типа, одновременно с этим заявки первого типа, поступающйе на обслуживание со входа 27 устройства, записываются в очередь блока 2,Состоянию завершения работы устройства соответствует условие ЛУ 50,1ЛУ 47.2 ЛУ 51 ЛУ 48 = 1 . (4) На начальной фазе работы устройства первым истинным условием из проверяемых является условие (Г;3ЛУ 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 поступает на вход регистра 521, а при"знак наличия заявки - на вход элемента И 54.1, Так как регистр:52,1находится в нулевом состоянии, то посигналу с входа 45 и импульсу с входа38 блока 2 заявка записывается врегистр 52,1, При этом на выходе признака наличия заявки этого регистра.устанавливается единичный потенциал,40 запрещающий. запись заявки в этот регистр в очередном такте. Посколькутриггер 59.1 установлен в нулевое состояние, обнуление регистра 52.1 потактовому импульсу с входа 38 при на 5 личин сигнала на входе 46 не происходит.В.очередном цикле записи. заявокв очередь блока 2 заявка из регистра 52,1 переписывается в регистр50 52.2, если он не занят другой заяв".кой. При этом триггер 59.1 устанавливается в единичное состояние, чтообеспечивает вазможность обнулениярегистра 52.1 и уничтожение копии55 . заявкиВыбор заявки на обслуживание осуществляется иэ регистра 52,Ь, Приэтом на входе 42 блока 2 установленнулевой потенциал, что обеспечиваетустановку триггера 591. в единичноесостояние и в последующем обнуление регистра 52.Ь.Если все регистры 52 блока 2 содер 5явдат заявки, то на выходе 47,1 элеь 1 ента И 55 устанавливается единичый потенциал, по которому запрещатся запись заявок в очередь,Если хотя бы в одном регистре 521сть заявка на обслуживание, на вы"оде 47.2 элемента ИЛИ 56 установлендиничный потенциал, по которому разешается выборка заявок иэ очередиа обслуживание.15После завершения цикла записи заяви в очередь в устройстве осуществлятся последовательная проверка выполения условий (1)-(4).Пусть в очередном цикле провероклогических условий выполнялось услоие (1), По этому условию в устрой"тве реализуется процесс обслуживанияаявки второго типа.При обслуживании заявок второго .25ипа на выходе 42 регистра 4 устанавивается единичный потенциал, а наыходе 43 формируется последователь"ость кодов, управляющих настройкоймультиплексора 13 и дешифратора 15. 30Код заявки из одного регистра 7 черезмультиплексор 13 поступает на входкоммутатора 14 и в дальнейшем записывается в регистры 5 и 6 под воздействием тактового импульса с выхода 38 35;генератора 25 после чего на соответствующем выходе дешифратора 15 формируется единичный импульс, устанавли -вающий соответствующий триггер 10 ирегистр 7 в нулевое состояние. 40Одной из фаз обслуживания заявокпервого и второго типов являетсяраспределение их по процессорам вычислительной системы, Для заявок первого типа эта фаза имеет некоторые особенности,После записи кода номера задачи. в регистр 5 и кода числа процессоров в в регистр 6 на выходе 51 элемента ИЛИ 50 23 устанавливается единичный потенциал, запрещающий запись в регистры 5 и 6 и разрешающий выполнение сдвига содержимого регистра 6.Назначение К-го процессора задаче 55 осуществляется при выполнении следующего условия6.К 10,К 8,К = 1,т.е, если К-й разряд регистра 6 содержит единицу, К-й процессор свободени триггер 10.К установлен в нулевоесостояние.При выполнении перечисленных условий на выходах соответствующего бло"ка элементов И 19.К устанавливаетсякод номера задачи, который поступаетв процессорное поле с выходов 32.Кустройства. При выполнении перечисленных выше условий распределения возможно одновременное назначение, группы процессоров задаче.В том случае, когда произошло назначение К"го процессора, для решениязадачи на выходе соответствующегоэлемента ИЛИ 22.К устанавливаетсяединичный потенциал, по которому в ,нулевое состояние устанавливаются соответствующие К-е разряды регистров6 и 8. В дальнейшем соответствующийпроцессор не может быть назначен длярешения задачи до полного освобожде"ния. Одновременно с назначением К-гопроцессора для решения задачи из очереди заявок блока 2 в единичное со,стояние устанавливается соответствующий.триггер 1 О.К. Назначение этойфункции в устройстве поясняется приописании обслуживания заявок второготипа,Распределение задач по процессорам в устройстве осуществляется дотех пор, пока в системе есть свободные процессоры и в очередях блока 2и группе регистров 7 есть заявки нарешение.При распределении задач из очереди блока 2 имеются следующие особенности. Задача, определяющая системную управляющую программу, можетбыть распределена более чем на одинпроцессор, В силу того, что на начальном этапе работы устройства, когда все процессоры в системе свободны, требуемое число процессоров этойзадаче назначается одновременно.При последующих распределенияхзадач возможны следующие ситуации,После записи кода числа процессоровв регистр 6 назначение соответствующего процессора задаче невозможно попричине.занятого его состояния. Дляобеспечения возможности распределения задачи на другие процессоры осуществляется кольцевой сдвиг содержимого регистра 6 в целях поискасвободного процессора, Таким образом процесс распределения задачи по процессорам осуществляется до тех пор, пока все требуемые процессоры будут назначены. Завершается процесс распределения задач по обнулению всех разрядов регистра 6.При выполнении обслуживания заявок второго типа. в устройстве реализуют-ся следующие процессы: формирование очереди заявок второго типа в регистрах 7; освобождение процессоров; распределение задач из очереди. дообспуживаемых задач по процессорам,Рассмотрим процесс Формирования очереди заявок второго типа. По завершению решения задачи на первой фазе обслуживания заявок соответствующий К-й процессор выставляет код заявки на соответствующих входах ЗО,К 20 устройства , а также Формирует импульс сигнала готовности на входе ЗО.К. При этом код заявки записывает-. ся в регистр 7.К и осуществляется восстановление единичного потенциа ла готовности К-го разряда регистра 8. При наличии заявок в регистрах 7 на выходе 50.1 блока 24 устанавливается единичный потенциал, который является проверяемым логическим усло вием 50.1 мультиплексора 11.В том случае, если процессор завершил выполнение задачи и дообслу" живания заявки не требуется, то в соответствующий регистр 7 кода заявки не заносится, а готовность процессора к выполнению других задач восстанавливается в регистре 8 по сигналу готовностиЗавершается работа устройства при 40 выполнении условия (4), При этом из блока 1 считывается конечная микрокоманда, На выходе 40 регистра 4 этоймикрокоманды установлен единичный потенциал. В очередном такте по импуль су с выхода 38 генератора 25 на выхо-. де элемента.И 17 формируется единичный импульс, запрещающий Формирование тактовой сетки импульсов на выходах генератора 25.Формула изобретения1, Микропрограммный диспетчер мно гопроцессорной вычислительной системы, содержащий блок очереди заявок, регистр кода номера задачи, регистр кода числа процессоров, регистр до- обслуживаемых заявок, регистр готовности процессора, триггер пуска, группу триггеров управления, коммутатор,дешифратор управления, первый и второй элементы И, группу элементов И,группу блоков элементов И, первый ивторой элементы ИЛИ, дешифратор управления очередью, группу. элементовИЛИ, причем вход пуска диспетчера соединен с единичным входом триггера пуска, выход которого соединен с входом запуска генератора тактовых импульсов, группа выходов регистра кодачисла процессоров соединена с группой входов первого, элемента ИЛИ,выходы элементов ИЛИ группы соединеныс первыми входами соответсвуюшихэлементов И группы, группа входов готовности процессоров диспетчера соединена с группой единичных входов регистра готовности процессоров, группа входов кода зявок первого типа устройства соединена с группой входовблока очереди заявок, о т л и ч а ющ и й с я тем, что, с целью расширения области применения за счет возможности перераспределения задач между процессорами, в диспетчер введеныблокмикропрограммного управления,группа регистров дообслуживаемых заявок, мультиплексор . дообслуживаемыхзаявок, блок формирования логическихусловий, причем группа входов кодовопераций диспетчера соединена с первой группой информационных входовблока микропрограммного управления,выход завершения режима которого соединен с первым входом первого элемента И, группа выходов сигналов управления очерЕдью заявок блока микропрограммного управления соединена с группой входов дешифратора управленияочередью заявок, первый, второй итретий. выходы которого соединены соответственно с входами сброса, записии управления записи блока очередизаявок, выход управления коммутацией блока микропрограммного управления соединен с входом управлениясдвигом блока очереди заявок, с управляющим входом коммутатора и с вторыми входами элементов И группы, группа выходов управления дообслуживания заявок блока микропрограммногоуправления соединена с группой информационных входов дешифратора управления и с группой управляющих входовмультиплексора дообслуживания, группа.выходов которого соединена с первойгруппой информационных входов комиуттора, группа информационных выходфв блока очереди заявок соединена с второй группой информационных вхо 5 ДОВ коммутатора, группа выходов кода номера задачи которого соедине-. нЬ с группой информационных входов р гистра кода номера задачи, а групп выходов кода числа процессоров - 1 О с группой информации входов регистр кода числа процессоров, первый в лсод генератора тактовых импульсов с единен с первым входом синхроииэац и блока микропрограммного управлен я, входами синхронизации регистра к да номера задачи, регистра кода ч сла процессоров, блока очереди заявок, стробирующим входом дешифра" тора дообслуживания и вторым входом 20 первого элемента И, выход которого соединен с нулевым входом триггера пуска, второй выкрд генератора тактовых импульсов соединен с вторым входом синхронизации блока микро программного управления, первый и вто. рой выходы признаков заполнения блока очереди заявок соединены со" Оответственно с первым и вторым вхоами внутренних логических условий Зо лока микропрограммного управления, выход индикации записи заявки блоа очереди заявок соединен с сигнальным выходом диспетчера, выход пер- ВОГО элемента ИЛИ сОеДинен с ВхОДОм разрешения сдвига и входом разрешеЙия записи регистра кода числа проЙессоров с входом разрешения записи 1 егистра кода номера задачи и с третьим входом Внутренних логических 4 О условий блока микропрограммного управления, группа выходов регистра кода номера задачи соединена с группаии входов блоков элементов И группы, группы выходов которых соединены с со"45 ответствующими группами выходов кодов номеров задач диспетчера и с групПами входов соответствующих элементов ИЛИ группы выходы которых соеди 1 иены с соответствующими нулевыми входами регистра готовности процессоров, группа выходов регистра кода числа процессоров соединена с первымивходами блоков элементов И группы,группа выходов дешифратора управлениясоединена с нулевыми входами регистровдообслуживаеиых заявок группы и триггерон управления группы, инверсныевыходы которых соединены с вторымивходами соответствующих блоков элементов И группы, группа выходов регистра готовности процессоров соединенас третьими входами блоков элементовИ группы и с входами второго элемента ИЛИ и второго элемента И, выходкоторого соединен с четвертым входомвнутренних логических условий блокамикропрограммного управления, выходвторого элемента ИЛИ соединен с пятымвходом. внутренних логических условийблока микропрограммного управления,группы входов кодов заявок второготипа диспетчера соединены с группамивходов соответствующих регистров .дообслуживаемых заявок группы, группывыходов которых соединены с группамиинформационных входов мультиплексорадообслуживания и с группами входовблока формирования логических условий, первый и второй выходы которогосоединены соответственно с шестым иседьмым входами внутренних логических условий блока микропрограммногоуправления, группа входов внешних логических условий диспетчера соединенас вторым информационным входом блокамикропрограммного управления.2, Диспетчер по и. 1, о т л и ч аю щ и й с я тем, что блок формиро"вания логических условий содержитгруппу элементов ИЛИ, элементы И ИЛИвыходы которых являются соответственно первым и вторым выходами блока,группы входов которого соединены свходами элементов ИЛИ группы, выходыкоторых соединены с входами элементаИ и элемента ИЛИ,1532926 Составитель М,Сорочактор Л,Пчолинская Техред Л.Олийнык орректор О,Ципле роизводственно-издательский комбинат "Патент", г. Ужгород, у арина, 101 Заказ 8100/53 Тираж бб 8 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС113035, Москва, Ж, Раушская наб., д, 4/5