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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 80124295 511 4 С 06 Е 9/46 ИСАНИЕ ИЗОБРЕТЕНИЯ ЖОтЩ ГОСУДАРСТВЕННЫИ НОМИТЕТ СССРГ 10 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ К АВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССРУ 629538, кл. С 06 Р 9/00, 1978.Авторское свидетельство СССРР 866560, кл. С 06 Р 9/46, 1981.(54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯЗАДАЧ МЕЖДУ ПРОЦЕССОРАМИ(57) Устройство для распределениязадач между процессорами относится квычислительной технике и может бытьиспользовано для распределения задачмежду процессорами в мультипроцессорных системах. Целью настоящего изобретения является расширение функциональных возможностей устройства за счет организации обслуживания с усеченным приоритетом. Приоритетное обслуживание необходимо в системах,работающих в реальном масштабе времени, где большие требования предъявляются к своевременности обработки информации. Закрепление за приоритетными задачами определенного вычислитель.ного ресурса повышает вероятность ихсвоевременного решения, снижая времястарения срочной информации. Устройство содержит группу из ш триггеров,групну из ш регистров хранения, группу из ш элементов И, первую группуиз и блоков элементов И, вторую группу из ш блоков элементов И, первый,второй и третий элементы И, элементНЕ, регистр номера задачи, блок сдвигающего регистра, регистр готовностипроцессоров, блок анализа, элементИЛИ, группу из и элементов ИЛИ, элемент задержки. 2 з.п.ф-лы, 4 ил.1242950 2 Изобретение относится к вычисли.тельной технике и предназначено для распределения задач между процессорами в мультипроцессорных системах.Цель изобретения - расширение функциональных возможностей устройства за счет организации обслуживасния с усеченным приоритетомНа фиг.1 представлена структурная схема устройства; на фиг. 2 - структурная схема блока сдвигающего регистра; на фиг. 3 - структурная схема блока анализа; на" фиг. 4 - структурная схема узла анализа.Устройство содержит группу триггеров 1, группу регистров 2 хране-, ния, группу элементов И 3, группу блоков элементов И 4, группу формирователей 5 импульсов элемент И 6, элемент НЕ 7, регистр 8 номера задачи, блок 9 сдвигающего регистра, блок 10 анализа, .регистр 11 готовности процессоров, пер-, вый 12 и третий 13 элементы И, элемент 14, задержки, элемент ИЛИ 15, группу блоков элементов И 16, группу элементов ИЛИ 17, запросные входы 18 устройства, сигнальные выкоды 19 устройства, информационные взводы 20 устройства, сигнальные входы 21 устройства, группу входов 22 и входы 23 и 24 блока 9, группу входов 25 и выходы 26 блока 9, входы 27 и выход 28 блока 10, информационные выходы 29 устройства и вход 30 запуска устройства. 40 45 со 55 Блок 9 сдвигающего регистра (фиг. 2) содержит собственно сдвигающий регистр 31 и задающий генератор 32.Задающий генератор 32 содержит элемент И 33, элемент 34 задержки и элемент НЕ 35.Блок 10 анализа (фиг. 3;) содержит узел 36 анализа, входы 37 и выходы38 узлов 36, входы 39 и вьгходы 40 узлов 36.Узел 36 блока 10 анализа (фиг. 4) содержит элемент И 41 и элемент ИЛИ 42.Устройство работает следующим образом.В исходном состоянии информация о задачах на входах 20 отсутствует, сигналы на входы 18 не поступают, на сигнальных выходах 19 устройства - потенциалы, свидетельствующие о готовности устройства к работе. Регист. ры 2, регистр 8, сдвигающий регистр31 обнулены, триггеры 1 находятся внулевом состоянии, элементы И 3 закрыты по вторым входам запрещающимсигналом с прямых выходов соответствующих триггеров 1. Блоки элементов И 4 закрыты по управляющим входам запрещающим сигналом от соответствующего элемента И 3, На информационных входах и выходах блоковэлементов И 4, регистра 8, блока 9,блоков элементов И 16, элементов ИЛИ 17, входах сброса регистра 11 готовности, входах 25 сброса блока 9 и на входах 21 нулевая информация. Нулевые сигналы с выходов 26 блока 9поступают на входы элемента ИЛИ 15и на вторые управляющие входы соответствующих блоков элементов И,закрывая их. Нулевой сигнал с выходаэлемента ИЛИ 15 поступает на первыйвход первого элемента И 12, на втором входе которого действует нулевой сигнал с выхода 26 старшего разрядаблока. 9 на вход элемента 14 задержки и на третий вход элемента И 13. Таким образом, элемент И 12 закрыт нулевым сигналом по двум входам, а1элемент И 13 - по второму и третьему входам, Нулевой сигнал с выхода элемента И 12 поступает на вход 23 блока9. Нулевой сигнал с выхода элемента И 13 через вход 24 блока 9 поступает на элемент И 33 задающего генератора 32, закрывая его. Генератор 32 находится в ждущем режиме. Так как процессоры свободны, весь регистр 11 готовности заполнен единицами. Единичные сигналы с информационных выходоврегистра 11 поступают на входы 27блока 1 0 и ца первые управляющие вхо.ды соответствующих блоков элементовИ 16. Так как на всех входах 27 бло 1ка 10 анализа присутствуют единичныесигналы, то на первом (28) и второмвыходах блока также единичные сигналы, которые подаются соответственнона первый вход третьего элементаИ 13 и на второй вход второго элемента И 6. Нулевой сигнал с выхода элемента ИЛИ 15 инвертируется на элементе НЕ 7 и поступает на первые входысоответствующих элементов И 3 и напервый вход эпемента И 6, с выходакоторого единичный сигнал подаетсяна первые входы остальных элементовИ 3, На управляющий вход 30 подаетсянулевой управляющий сигнал.Программа-планировщик операционнойсистемы в зависимости от срочности(приоритетности) задачи выставляетзапрос на тот или иной вход 18 устройства, предварительно записав всоответствующий регистр 2 информацию, содержащую код номера задачи иколичество процессоров, необходимоедля ее решения. Информация о номерезадачи и количестве необходимых дляее решения процессоров выдаетоя впарафазном коде, что позволяет исключить нуление регистров 2 перед приемом новой информации, Единичный потенциал запроса поступает через вход18 на вход формирователя 5 импульсов,короткий единичный импульс с выходакоторого поступает на установочный.вход соответствующего триггера 1 иустанавливает его в единичное состояние, снимая единичные сигналы с входов соответствующих элементов И 3,Единичный сигнал с прямого выходатриггера 1 поступает на второй входэлемента И 3 группы, на первом входекоторого действует единичный сигналс выхода элемента НЕ 7 либо с выхода элемента И 6, а на остальных входах - единичные сигналы с инверсныхвыходов триггеров 1. На выходе элемента И 3 группы устанавливается еиничный сигнал, который, поступая науправляющий вход блока элементовИ 4, открывает его,Код номера задачи с регистра 2 через открытый блок элементов И 4 в парафазном коде записывается в регистр 8. Применение парафазного кода для передачи кода номера задачи позволяет избежать нуления регистра 8 номера задачи перед записью в него новой информации. Так как сдвигающий регистр 31 после распределения очередной задачи между процессорами обнуляется, то для передачи количества потребных для решения задачи процессоров используется обычный код, т.е. используется информация только с прямых выходов триггеров регистра 2 хранения. Код количества необходимых для решения задачи процессоров через открытый блок элементов И 4 поступает на группу информационных входов 22 блока 9 и записывается в сдвигающий регистр 31На выходе элемента ИЛИ 15 после этого появляется единичный потенциал, который поступает на вход эле 5 О 15 20 25 30 35 40 45 50 55 мента НЕ 7, нулевой потенциал, появляющийся на выходе НЕ 7, закрываетпо первому входу соответствующиеэлементы И 3 и элемент И 6, нулевой потенциал с выхода которого закрывает по первому входу остальныеэлементы И 3. На выходе элемента И 3, который перед этим открыт, формируется задний фронт единичного сигнала (1 - 0), который поступая на С-вход триггера 1 (на входы С, 2 и К которого постоянно подается нулевой потенциал), устанавливает триггер 1 в нулевое состояние. Элемент И 3 закрывается и по второму входу нулевым потенциалом с прямого выхода триггера 1. Единичный сигнал с инверсного выхода триггера 1 группы подается на .сигнальный выход 19устройства, указывая, что задачапринята на обслуживание. Одновременно единичный сигнал с инверсного выхода триггера 1 поступает на входы соответствующих элементов И 3. Единичные сигналы с группы выходов 26блока 9 поступают на входы элемента ИЛИ 15 и на вторые управляющиевходы блоков элементов И 16. С выхода элемента ИЛИ 15 единичный сигнал поступает на вход элемента НЕ .7,первый вход первого элемента И 12,третий вход третьего элемента И 13 и вход элемента 14 задержки. Единичный сигнал, инвертируясь на элементе НЕ 7, закрывает по первым входам соответствующие элементы И 3 и элемент И 6, с выхода которого нулевой сигнал закрывает по первым входамостальные элементы И 3, блокируятем самым поступление новой информации на регистр 8 и блок 9 до окончания распределения процессоров.Так как количество необходимых длярешения задачи процессоров,поступает на группу информационных входов22 блока 9 в позиционном коде, то на выходе 26 старшего разряда блока9 присутствует нулевой сигнал, который, поступая на второй вход элемента И 12, закрывает его. На выходе элемента И 12 и, следовательно,на входе 23 младшего разряда блока 9 устанавливается нулевой сигнал. Элемент 14 задержки введен для .блокировки сдвига сдвигающего.регистра 31 при первом распределении задачи между процессорами.Единичный сигнал на выходе элемента 14 задержки появляется толькопосле прохождения сигнала через соответствующий блок элементов И 16, соответствующий элемент ИЛИ 17 и сброса триггера сдвигающего регист ра 31. Единичный сигнал с выхода 26 блока 9 поступает на второй управляющий вход блока элементов И 16, на первом управляющем входе которого действует единичный сигнал с соот О ветствующего выхода регистра 11, а на информационных входах - код номера задачи, поступающий с регистра 8. Под воздействием единичного сигнала с выхода 26 группы информационных 1.1 выходов блока 9 блок элементов И 16 открывается и код номера задачи поступает на соответствующую группу выходов 29 и на группу входов соответствующего элемента ИЛИ 17, Еди ничный сигнал с выхода элемента ИЛИ 17 поступает на вход группы входов 25 блока 9 и на вход группы входов сброса регистра 11 готовности, устанавливая в нулевое состояние со ответствующий триггер сдвигающего регистра 31 и соответствующий триггер регистра 11. Нулевой сигнал с выхода регистра 11 готовности поступает на информационный вход 27 блока ЗО 10 анализа. Блок 10 анализа работает следующим образом.Блок 10 анализа представляет собой двумерную итеративную сеть размером из узлов Зб. Каждый узел Зб представляет собой конечный автомат без памяти,Узел Зб обеспечивает распространение сигналов в двух направлениях: сверху вниз и слева направо. Блок 10 анализа выполняет операцию взвешивания (подсчета числа единиц). На информационные (граничные) входы 27 блока 10 анализа поступает позиционный код количества свободных процессоров от регистра 11 готовности. На управляющий вход 30 блока подается нулевой граничный сигнал, который поступает на входы 30 узлов 36. Таким образом, на первых входах элементов И 4 и ИЛИ 42 действует нулевой сигнал с входов 39. Допустим, что свободен только первый процессор. Тогда единичный сигнал через вход 27, 55 блока 10 и вход 37 узла 36 подается на вторые входы элементов И 41 и ИЛИ 42 Так как элемент И 41 эакрыт по первому входу нулевым граничным сигналом, то единичный сигнал через элемент ИЛИ 42 и выход 40, подается на вход 39узла 36,. Через вход 39, единичный сигнал поступает на первые входы элементов И 41, и ИЛИ 42 на вторых входах которых ,действует нулевой сигнал с информационного входа 27 блока, закрывая элемент И 41 . Единичный сигнал через элемент И 42, и выход 40 узла поступает на вход 39узла 36, где операция повторяется. Таким образом, единичный сигнал распространяется по первому столбцу узлов 36 и выделяется на управляющем выходе 28 блока 10. Аналогично блок 10 работает при,любом свободном процессоре. Единичный сигнал может распространяться только в первом столбце и только вниз, так как его распространение вправо ограничивают закрытые элемен - ты И 41.Распределение задачи между процессорами при условии незанятости всех процессоров осуществляется параллельно, так как все блоки элементов И 16 имеют на своем первом управляющем входе разрешающий потенциал, поступающий с соответствующих выходов группы информационных выходов регистра 11 готовности, сдвигающий регистр 31 блока 9 попностью обнуляется. Нулевые сигналы с информационных выходов 26 блока 9 поступают на входы элемента ИЛИ 15, с выхода которого нулевой сигнал подается на первый вход элемента И 12 первый вход элемента И 13 закрывая их. и на вход элемента НЕ 7. На втором входе элемента И 12 действует нулевой сигнал с выхода 26 старшего разряда блока 9. Нулевые сигналы с выходов элементов И 12 и 13 подаются на вход 23 младшего разряда и управляющий вход 24 блока 9 соответственно. Нулевой сигнал, инвертируясь на элементе НЕ 7, поступает на первые входы элементов И 3 и на первый вход элемента И б.Дальнейшая работа происходит аналогично.Формула изобретения1 . Устройство для распределения задач между процессорами, содержащее45 50 55 регистр готовности процессоров первую группу блоков элементов И, блок сдвигающих регистров, группу элементов ИЛИ, первый элемент И, элемент ИЛИ, группу регистров хранения, сигнальные входы устройства соединены с группой информационных входов регистра готовности процессоров, каждый выход 1 руппы выходов которого соединен с первым управляющим входом соответствующего блока элементов И первой группы, группа выходов каждого блока элементов И первой группы подключена к группе информационных выходов устройства и к группе входов соответствующего элемента ИЛИ группы, выход которого подключен к одноименному входу группы входов сброса регистра готовности процессоров и к одноименному входу группы входов сброса блока сдвигающих регистров, каждый выход группы выходов которого подключен к второму управляющему входу одноименного блока элементов И первой группы и к соответствующему входу элемента ИЛИ, выход которого подключен к первому входу первого элемента И, второй вход которого подключен к выходу старшего разряда группы выходов блока сдвигающих регистров, выход первого элемента И подключен к входу младшего разряда блока сдвигающих регистров, о т - л и ч а ю щ е е с я тем, чтос целью расширения функциональньгх возможностей устройства за счет организации обслуживания с,усеченным приоритетом, в него введены группа триггеров, вторая группа блоков элементов И, группа из ш, где ш - число источников запоосов, элементов И, группа формирователей имггульсов, регистр номера задачи, второй и третий элементы И, элемент НЕ, элемент задержки, блок анализа, причем вход элемента НЕ подключен к выходу элемента ИЛИ, выход элемента НЕ подключен к первым входам элементов И группы, с первого по ш/2-й, и к первому входу второго элемента И, выход которого соединен с первыми входами элементов И группы с (М/2-1)-го по ш-й второй вход каждого -го Я=2/1 ш) элемента И группы соединен с прямым выходом -го триггера группы, единичный вход которого подключенк выходу 1-го формирователя импульсов группы, вход которого является 1-м запросным входом устройства, инверс 5 10 15 20 25 30 35 40 ный выход 1-го триггера группы является 1-м сигнальным Выходом устройства, инверсный выход каждого триггера группы соединен с соответствующим входом каждого последующего элемента И группы, вьгход каждого элемента И группы соединен с синхронизирующим входом одноименного триггера группы И с управляющим входом одноименного блока элементов И второй группы, группа информационных входов каждого из которых соединена с группой информационных выходов одноименного регистра хранения группы, первая группа выходов каждого блока элементов И второй группы подключена к группе информационных входов регистра номера задачи, группа выходов которого подключена к группе информа. ционных входов каждого блока элементов И первой группы, вторая группа информационных выходов каждого блока элементов И второй группы подключена к группе информационных входов блока сдвигающих регистров, вход управления сдвигом которого подключен к выходу третьего элемента И, первый вход которого подключен к выходу элемента ИЛИ и входу элемента задержки, второй вход третьего элемента И подключен к выходу элемента задержки, третий вход третьего элемента И подключен к первому. выходу блока анализа, второй выход которого подключен к второму входу второго элемента И, группа входов блока анализа подключена к группе выходов регистра готовности процессоров, группа информационных входов каждого регистра хранения группы является -й группой информационных входов устройства, вход запуска устройства соединен с входом блока анализа.2. Устройство по п. 1, о т л и - чающее с я тем, что блок анализа содержит п групп из 1 узлованализа, где п - число процессоров, а 2и, причем в каждой 3 - й (1 =1, и) группе узлов анализа первый выход 1 с-го 11 с=111-1)1 узла анализа подключен к первому входу (1 с + +1)-го узла этой группы, а первый вход первого узла подключен к 3-му информационному входу группы информационных входовблока анализа, в каждой м-й группе узлов анализа м=1, (и)1 второй выход каждого 1-го узла анализа подключен к вто 921рому входу к-го узла (3+1)-й груп пы, вторые входы всех узлов анализа первой группы подключены к управляющему входу блока анализа, второй выход первого узла анализа,п-й группы подключен к первому управляющему выходу блока, а второй выход 1-го узла п-й группы подключен к второму управляющему выходу блока.3. Устройство по пп. 1 и 2, о т - л и ч а ю щ е е с я тем, что в блоке 42950анализа каждый .узел анализа содержит элемент И и элемент И 31 И, причем первый вход элемента И подключен к первому входу узла и к первому входу 5 элемента ИЛИ, второй вход элемента И - к второму входу узла и к второму входу элемента ИЛИ, а выход элемента И - к первомуФвыходу узла, выход элемента ИЛИ 1 О подключен к второму выходу узла.1242950 е а е Составитель М. КудряшевТехред О,Гортвай Корректор М. Максимишинец Редактор И. Николайчук Тираж 671комитета ССи открытийская наб.,дпи Заказ 3706 ВНИИПИ Государственного СР по делам изобретений113035, Москва, Ж, Рауш дпроектная, 4 Производственно-полиграфическое предприятие, г. Ужгород,