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

(19) 4(51) С 06 Г 9/46 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) 1. Авторское свидетельство СССРУ 629538, кл. С 06 Г 9/00,. 1977.2, Авторское свидетельство СССРР 866560, кл. 6 06 Р 9/46, 1981(54) (57) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯЗАДАНЫ ПРОЦЕССОРАМ, содержащее группу регистров хранения, регистр сдвига, регистр готовности процессоровэлемент ИЛИ, группу блоков элементовИ, блок элементов И, первый элементИ, группу элементов ИЛИ, причем группа информационных входов устройствасоединена с группой информационныхвходов первого регистра хранениягруппы, группа выходов каждого регистра хранения группы - с группойвходов следующего регистра хранениягруппы, группа выходов последнегорегистра хранения группы - с группойвходов блока элементов И, группавыходов каждого блока элементов Исоединена с группой входов одноименного элемента ИЛИ группы и являетсясоответствующей группой выходов устройства, выходы элементов ИЛИ группысоединены с группой входов сбросарегистра сдвига и с группой входовсброса регистра готовности нроцессоров, каждый разрядный выход регистрасдвига соединен с первым входом одноименного блока элементов И группы,выходы регистра сдвига соединены свходами элемента ИЛИ, каждый сигнальный вход устройства соединен с одноименным информационным входом регистра готовности процессоров, о т л ич а ю щ е е с я тем, что, с цельюповышения быстродействия, устройствосодержит триггер, генератор импульсов, группу блоков элементов И-ИЛИ,группу дешифраторов, группу регистровобслуживания, одновибратор, второйи третий элементы И и элемент ИЛИ-НЕ,выход которого соединен с первымвходам первого элемента И, выходкоторого соединен с нулевым входомтриггера, выход элемента ИЛИ соединен с первыми управляющими входамиблоков элементов И-ИЛИ группы, спервым входом элемента ИЛ-НЕ, с инверсным входом блока элемента И, свходом разрешения сдвига регистрасдвига и с входом одновибратора,выход которого соединен с нулевымвходом последнего регистра хранениягруппы, выходы признаков наличиязаявки регистров хранения группысоединены соответственно с входамиэлемента ИЛИ-НЕ, выход признака наличия заявки последнего регистрахранения группы соединен с инверснымвходом второго элемента И, выход признака наличия заявки первого регистрахранения группы соединен с первымвходом третьего элемента И, выходкоторого является сигнальным выходомустройства, первый выход генератора .импульсов соединен с вторыми входамипервого и третьего элементов И, второйвыход генератора импульсов соединен свходом разрешения записи регистра1151966 сдвига, с тактовыми входами регист-ров обслуживания группы и с вторымвходом второго элемента И, выходкоторого соединен с тактовыми входамирегистров хранения группы, группавыходов блока элементов И соединенас группой информационных входов регистра сдвига, с первыми группами входовблоков элементов И-ИЛИ группы, второйуправляющий вход каждого блока элементов И-ИЛИ группы соединен с соответствующим выходом группы выходовблока элементов И, группа выходовкаждого блока элементов И-ИЛИ группысоединена с группой информационныхвходов одноименного регистра обслуживания группы, группа выходов каждого регистра обслуживания группа,кроме последнего, соединена с второйгруппой выходов следующего блокаэлементов И-ИЛИ группы, группа выхоИзобретение относится к вычислительной технике и может быть использовано для построения многопроцессорных вычислительных систем.Известно устройство для распределения заданий процессорам, содержащее регистр готовности процессоров,группу элементов Ц, блок управления,регистр сдвига, процессоры, элементыИЛИ Я .10Недостатками этого устройстваявляются низкая надежность вследствие существования высокой вероятности потери заявки на решение задачи, вызванной отказом устройства от 15выполнения задания, в случае, когдачисло свободных процессоров меньшеколичества потребных процессоров;ограниченные функциональные возможности, проявляющиеся в том, что в 20устройстве отсутствует воэможностьорганизации очереди заданий,Наиболее близким к изобретениюявляется устройство для распределения заявок по процессорам, содержащее группу регистров хранения, группу выходов признака числа потребных.процессоров последнего регистрахранения группы, группу входов приздов последнего регистра обслуживаниягруппы соединена с второй группойвходов первого блока элементов И-ИЛИгруппы, группа выходов каждого регистра обслуживания группы соединенас группой входов одноименного дешифратора группы и с группой входоводноименного блока элементов И группы, каждый выход группы выходоврегистра готовности процессоров соединен с вторым входом одноименногоблока элементов И группы,. третийвход каждого .блока элемента И группысоединен с выходом одноименного деаифратора группы, вход сброса каждогорегистра обслуживания группы соединенс выходом одноименного элемента ИЛИгруппы, вход пуска устройства соединенс единичным входом триггера, выходпоследнего разряда сдвига соединен сего первым информационным входом. нака номера задачи первого регистрахранения группы, группу входов признака числа потребных процессоровпервого регистра хранения группы,первую и вторую группы элементов И,элемент И регистр сдвига, информационный вход регистра сдвига, элемент ИЛИ, блок элементов ИЛИ, группупроцессоров, регистр готовности процессоров, блок управления, первыйвход которого соединен с входомпуска устройства, группа выходов регистра готовности процессоров соединена с первыми входами элементов Ипервой группы, вторые входы которыхсоединены с группой выходов регистрасдвига и с группой входов элементаИЛИ, выход которого соединен с вторым входом блока управления и первымвходом элемента И, Второй Вход которого соединен с выходом старшегоразряда группы выходов регистрасдвига, выход элемента И соединенс входом сдвига регистра сдвига,вход сброса которого соединен с выходом блока элементов ИЛИ и с входомсброса регистра готовности процессоров, группа информационных входовкоторого соединена с выходами про 11519цессоров группы, выходы которых соединены с выходами элементов И первойгруппы и с входами блока элементовИЛИ, управляющий вход регистра сдвигасоединен с первьм выходом блока управления, группа информационныхвходов первого регистра хранениягруппы соединена с группой входовзаявок устройства, управляющий входкаждого регистра хранения группы 10 соединен с выходом соответствующего элемента И второй группы, группа информационных выходов каждого регистра хранения группы, кроме последнего, соединена с группой информацион ных входов последующего регистра хранения группы, первый вход каждого элемента И второй группы, кроме пос леднего, соединен с выходом последуючч 3 щего элемента И этой группы, первыи вход последнего элемента И второй группы соединен с вторым выходом блока управления 121 .Недостатком известного устройства 25 является низкое быстродействие. Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что в устройство для распределения заданий процессорам, содержащее группу регистров хранения, регистр сдвига, регистр готовности процессоров, группу процессоров,элементИЛИ,груп 35 пу блоков элементов И, блок элементов И, первый элемент И, группу элементов ИЛИ, причем группа информационных входов устройства соединена с группой информационных входов первого регистра хранения группы, группа выходов каждого регистра хранения группы с группой входов следующего регистра хранения группы, группа выходов последнего регистра хранения группы сое- динена с группой входов блока элементов И, группа выходов каждого блока элементов И группы соединена с группой входов одноименного элемента ИЛИ группы и является соответствующей груп" 50 пой выходов устройства, выходы элементов ИЛИ группы соединены с группой входов сброса регистра сдвига и с группой входов сброса регистра готовности процессоров, каждый разрядный выход регистра сдвига соединен с первым входом одноименного блока элементов И группы, выходы регистра сдвига бб 4соединены с входами элемента ИЛИ,каждый сигнальный вход устройствасоединен с одноименным информационным входом регистра готовности процессоров, введены триггер, генератор импульсов, группа блоков элементов И-ИЛИ, группа дешифраторов,группа регистров обслуживания,одновибратор, второй и третий элементы И и элемент ИЛИ-НЕ, выходкоторого соединен с первым входомпервого элемента И, выход которогосоедйнен с нулевым входом. триггера,выход элемента ИЛИ соединен с первымиуправляющими входами блоков элементовИ-ИЛИ группы, с первым входом элемента ИЛИ-НЕ, с инверсным входом блокаэлементов И, с входом разрешениясдвига регистра сдвига и с входомодновибратора, -выход которого соединен с нулевым входом последнегорегистра хранения группы, выходыпризнаков наличия заявки регистровхранения группы соединены соответственно с входамн элемента ИЛИ-НЕ,выход признака наличия заявки последнего регистра хранения группысоединен с инверсным входом второгоэлемента И, выход признака наличиязаявки первого регистра хранениягруппы соединен с первым входомтретьего элемента И, выход которогоявляется сигнальным выходом устройства, первый выход генератора импуль.сов соединен с вторыми входами первого и третьего элементов И, второйвыход генератора импульсов соединенс входом разрешения записи регистрасдвига, с тактовыми, входами регистров обслуживания группы и с вторымвходом второго элемента И, выход.которого соединен с тактовыми входамирегистров хранения группы, группа выходов блока элементов,И соединена сгруппой информационных входов регистра сдвига, с первыми группамивходов блоков элементов И-ИЛИ группы,второй управляющий вход каждого блокаэлементов И-ИЛИ группы соединен ссоответствующим выходом группывыходов блока элементов И, группавыходов каждого блока элементовИ-ИЛИ группы соединена с группойинформационных входов одноименногорегистра обслуживания группы, группавыходов каждого регистра обслуживания группы, кроме последнего, соединена с второй группой выходов сле 3 1151 дуннцего блока элементов И-ИЛИ группы, группа выходов последнего регистра обслуживания группы соединена свторой группой входов первого блока элементов И-ИЛИ группы, группа 5 выходов каждого регистра обслуживания группы соединена с группой входов одноименного дешифратора группы и с группой входов одноименного блока элементов И группы, каждый выход группы выходов регистра готовности процессоров соединен с вторым.входом одноименного блока элементов И группы, третий вход каждого блока элементов И группы соединен с выхо дом одноименного дешифратора группы, вход сброса каждого регистра обслуживания группы соединен с выходом одноименного элемента ИЛИ группы, вход пуска устройства соединен 20 с единичным входом триггера,. выход последнего разряда регистра сдвига соединен с его первым информационным входомНа фиг. 1 представлена функцио- .25 нальная схема предлагаемого устройства; на фиг. 2 - схема алгоритма функционирования устройства.Устройство (фиг, 1) содержит группу информационных входов 1 устрой- ЗО ства, вход 2 пуска устройства, сигнальный выход 3 устройства, элементы И 4-6, элемент ИЛИ-НЕ 7, элемент ИЛИ 8, блок 9 элементов И, группу блоков 10,1-10. И элементов И, группу 11.1-11.И блоков элементов И-ИЛИ, группу 12.112 И элементов ИЛИ, группу 13.1-13,И дешифраторов, триггер 14, одновнбратор 15, генератор 16 импульсов, выходы 17 и 18 генератора 16 . щ импульсов, группу 19,1-19 А регистров хранения, регистр 20 сдвига, группу 21, 1-21.И регистров обслуживания, регистр 22 готовности процессоров, группу 23.1-23,И процессоров, группу 45 24 выходов элементов блока 9 элемен-. тов И, 24.1-24.И-первый, Я-й разряды группы 24 выходов блока 9, группы вь- ходов 25.1-25.И регистров .21.1-21.И, выходы 26.1-26.Ь признаков наличия 5 О заявки регистров 19. 1-19.Ъ. На вход 2 устройства подаетсясигнал пуска, который приводит уст-.ройство в рабочее состояние. Выход Э 5используется для вьщачн квитанциивнешней системе о записи заявки врегистр 19.1 группы. 966 бГруппа регистров 19.1-19,Ь хранения устройства предназначена для организации очереди заявок на обслуживание, Запись заявок производится впервый регистр 191 группы, а выборзаявки на обслуживание - из последнего 19,Ь регистра хранения группыв параллельном коде.Регистры 21 обслуживания предназначены для хранения признаков номеразадачи и доступных процессоров впроцессе распределения процессоров -задаче. Регистр 20 сдвига предназначен для хранения кода количества процессоров, который представляется впозиционном коде. Наличие единицы вэтом коде свидетельствует о необхо-.димости распределения процессоразадачеРегистр 22 готовности предназначен для регистрации сигналовготовности процессоров. Единичноесостояние разряда регистра свидетельствует о том, что процессор свободени может быть распределен.В исходном состоянии все элементыпамяти, кроме регистра 22 готовностипроцессоров, находятся в нулевомсостоянии, а регистр 22 готовностипроцессоров находится в единичномсостоянии, что свидетельствует оготовности процессоров 23.1-23,Ик решению задачи. На вход 2 устройства поступает сигнал пуска, по кото"рому триггер 14 устанавливается вединичное состояние и разрешаетпрохождение сигнала через .элемент И 5с выхода 18 генератора 16 на тактовыевходы регистров 19.1-19. Ь, Одновременно с сигналом пуска на выходы 1устройства поступает заявка, котораяпод воздействием .сигнала с генератора 16 записывается в регистр 19,1После этого по такту с выхода 17 генератора 16 на выход 3 устройства через элемент И б выдается квитанцияа записи заявки в очередь. Продвижение заявки в регистрах 19 осуществляется до того момента, пока заявка незаписана в последний регистр 19,Во время продвижения заявки в регистрах 19 на входы 1. устройства могутподаваться очередные заявки, которыетакже записываются в регистры 19.Таким образом в регистрах, 19.1-19,Ьобразуется очередь заявок на решениезадач,После записи заявки в последнийрегистр 19 на выходе 26. 1 последнего21,М, и для этих регистров черезблоки 11.1-11.В формируются цепи дляциклического сдвига содержимого регистров 21. 1-21.И от первого к последнему, а выход последнего регистра21.М подключается к входу первогорегистра 21.1.Поступая на вход разрешения сдвигарегистра 20, единичный потенциал свыхода элемента ИЛИ 8 запрещает запись по информационным входам этогорегистра и разрешает циклический сдвигсодержимого регистра 20 в направленииот первого разряда к последнему, причем выход последнего разряда регистра20 подключен к входу первого разряда,Это позволяет осуществлять многократную попытку распределения процессоровзадаче,Кроме того, при изменении выходного потенциала элемента ИЛИ 8 снулевого на единичный одновибратором15 Формируется импульс, по которомупоследний регистр 19.Ь устанавливается в нулевое состояние, При этомразрешается прохождение тактовыхимпульсов генератора 16 через элементИ 5, которые управляют записью ипродвижением заявок в регистрах19,1-19.М.Рассмотрим работу устройства поназначению процессоров задаче, определяемой выбранной заявкой на обслуживание.При этом целесообразно рассматривать работу устройства в два этапа:первоначального назначения процессоров; последующего назначения процессоров.Первоначальное назначение процессоров осуществляется следующим образом.С выходов регистра 22 готовности процессоров сигналы готовности поступают на входы 10.1-10.К элементов И, На эти же блоки поступают сиг-.налы свыходов регистра 20 и сигналыкодов номера задачи с выходов 25. 125.0 регистров 21. Сигналыс шин25. 1-25,0, определяющие коды доступности процессоров, поступают на соответствуацие дешифраторы 13.1-13.Я.На выходе дешифратора 13 сигналпоявляется в том случае, если соответствующий ему процессор может решить подзадачу распределяемой задачи,т.е. код доступности процессора оределен для соответствующего дешифратора 13. При выполнении всех усло 7 1151966регистра 19,Ь устанавливается сигналналичия заявки, который запрещаетпрохождение сигнала через элементИ 5. После записи первой заявкив регистр 19,Ь осуществляется. выборее на обслуживание, сущность которого состоит в назначении определяемой заявкой задаче необходимогочисла процессоров для решения.Выбор заявки на обслуживаниЕ из 10регистра 19.Ь осуществляется всякийраз, когда в очереди есть заявки иустройство не занято обслуживанием,Сигнал о том, что устройство незанято обслуживанием заявки, Формируется на выходе элемента ИЛИ 8,если в регистре 20 все разряды установлены в нулевое состояние.В начале работы устройства регистр20 находится в нулевом состоянии и, 20поэтому, нулевым потенциалом с выхода .элемента ИЛИ 8 открыт блок 9 элементов И, После записи заявки в .регистр19,Ь на выходах блока 9 устанавливается код заявки, определяющий код 25количества процессоров,. необходимыхдля решения задачи (на выходах 24)и коды номера задачи и доступностипроцессоров. Так как на входе разрешения сдвига регистра 20 установлен, З 0нулевой потенциал, то под управлениемтактовых импульсов с выхода 18 генератора 16, поступающих на вход разрешения записи регистра 20, осуществляется запись параллельного кода свыходом 24 блока 9 в регистр 20,Кроме того, тактовые импульсыс выхода 18 генератора 16 поступаютна тактовые входы регистров 21,121.8, При этом к информационным 40входам этих регистров через блоки11. 1".11.И осуществляется подключение входов 24 только для тех регистров, которым соответствует единичноесостояние соответствующего разряда 4524.1-24.И. Таким образом, по очередному. тактовому импульсу с выхода 18генератора 16 происходит запись кодаколичества процессоров в регистр 20,а в регистры 21.1-21.0 - запись кодов номера задачи и доступности процессоров.После записи кода количество процессоров в регистр 20 на выходе элемента ИЛИ 8 устанавливается единичный 55потенциал, яо которому закрываетсяблок 9 элементов И, отключаются вы-ходы 24 от входов регистров 21. 1 9 1151 вий на входах блоков 10,1-10.0 элементов И с их выходов снимаются сиг. налы назначения процессоров, по которым через элементы ИЛИ 12,1-12.0 обнуляются соответствующие разряды , в регистре 20 и соответствующие регистры 21.1-21 Л. После этого в соответствующие блоки 10,1-10,0 :элементов И закрываются.Далее в работе устройствавозмож О ны две ситуации: после первоначального распределения все необходимые процессоры назначены задаче; после первоначального распределения не все необходимые процессоры назначены задаче.В первом случае устройства завершает обслуживание рассматриваемой задачи и Формируется сигнал считывания из регистра 19.Ь.аналагочно рас- О смотренному выше. Устройство переходит к обслуживанию следующей заявки на решение задачи.Второй случай соответствует второму этапу назначения процессоров, 25 который проходит следующим образом.В регистре 20 не все разряды обнулены, поэтому на выходе элемента ИЛИ 8 сохраняется единичный потенциал, что соответствует разрешению кольцевого циклического сдвига содержимого регистра 20 по тактовым 966 1 Оимпульсам с выхода 18 генератора 16,Этими же импульсами осуществляетсяуправление кольцевым циклическимсдвигом содержимого регистров 21,121.М. При этом после каждого очередного такта сдвига производится попытка распределения процессоров задаче,аналогично вышеуказанному. Этот процесс продолжается до тех пор, покане все требуемые процессоры 23.123,Я назначены задаче, Как толькораспределение процессоров будет завершено, на выходе элемента ИЛИ 8устанавливается нулевой потенциали новая. заявка выбирается на обслуживание из очереди,Работа устройства завершается втом случае, если в очереди нет заявоки устройство не занято обслуживаниемзаявки. В этом случае на выходеэлемента ИЛИ-НЕ 7 Формируется единичный потенциал, который поступает навход элемента И 4. По тактовому импульсу с выхода 17 генератора 16,поступающему на другой вход элементаИ 4, триггер 14 переводится в нулевоесостояние, запрещая генерацию тактовыхимпульсов генератором 16. В дальнейшем устройство готово к новому циклуработы,Применение изобретения позволяетповысить быстродействие устройства.1151966 ИИПИ Заказ 2325/38ж 710 Подписное Филиал ППП "Патент",Ужгород, ул. Проектная, 4