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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИРЕСПУБЛИН 9) ( 6 Г 9/46 Н ИЗ СВИДЕ К АВТОРСК темах и управляю етения - р устройств лительныхЦель изо щихас ласт пеий, а но- рой ширение о путем обе ения задан апоминания аданий. Ус я заданий группы эл рименен ения ко оля за менруппы о двеы эл г о И, четыре амяти, дека п емент заре пре иф аи соегчаетной ипотоко атк п с уппу элеменов 2, групуппу элемено ОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(56) Авторское свидетельство СССРУ 1348834, кл. С Об Р 9/46, 1986,Авторское свидетельство СССРВ 1234838 кл, С 06 Р 9/46, 1984.(57) Изобретение относится к автоматике и вычислительной технике, а именно к приоритетным устройствам для распределения заданий процессорам, ипредназначено для использования в многопроцессорных и многомашинных вычисИзобретение относится к автоматике и вычислительйой технике, а именно к приоритетным устройствам для распределения заданий процессорам, и предназначено для использования в многопроцессорных и многомашинных вычислительных и управляющих системах.Цель изобретения - расширение области применения устройства за счет обеспечения контроля завершения за, даний,- а также перезапуска и запоминания номеров незавершенных заданий,На фиг.1 и 2 приведена функциональная схема предлагаемого устройва. Устройство содержит гв ИЛИ 1, группу счетчи элементов ИЛИ-НЕ 3, г также перезапуска имеров незавершенныхство для распределенцессорам содержит двтов ИЛИ, группу счетэлементов ИЛИ-НЕ, двментов И, пять элемеэлемента ИЛИ, два блшифратор, два счетчикдержки, приоритетныйпу триггеров. Испольженного устройства оответствующей программной поддержке отладкграмм. 2 ил. тов ИЛИ-НЕ 4, группу элементов И 5,блок 6 памяти, группу элементов И 7элементы И 8-11, элемент ИЛИ 12, группу кодовых входов 13 устройства,группу адресных входов 14 устройства,вход 15 наличия законченных заданий устройства, тактовый вход Ь у тройства, вход 17 наличия свободныхпроцессоров устройства, группуинформационных выходов 18 устройства, сигнальный выход 19 устройства, вход 20 начальной установкиустройства, сигнальный выход 21устройства, группу сигнальных выходов22 устройства, информационный выход23 устройства, блок 24 памяти, дешифратор 25, счетчик 26, элемент 27 задержки, приоритетный шифратор 28,,2Устройство работает следующим образом,Для перевода устройства в исходное состояние на вход 20 устройстваподается единичный импульс, по которому элементы памяти устройства переходят в нулевое состояние, Блок 24памяти обнуляется (цепи сброса в ис ходное состояние на. чертеже не по ,казаны)Исходное состояние устройст,5, ва характеризуется тем, что импульсына тактовом входе 16 устройства отсутствуют, в связи с чем на информационных выходах 18 и сигнальном выходе 19 нулевые сигналы, а на сигнальных выходах 21 и 22 - единичные сигналы,Блок 6 памяти содержит информациюо топологии графа, описывающего наборинформационно связанных задач каж дой вершине графа соответствует совокупность ячеек х, +1+е по числу логических выходов вершины. В каждую ячейку занесено п-разрядное число(и - число вершин графа), имеющее всоответствующем ц-м разряде единицу,если иэ 1-й вершины графа исходит ду-га, ведующая в ц-ю вершину, Одному ло"гическому выходу вершины соответствует одна или несколько запускаемыхвершин-приемников. Кроме того, занесена единица в 1-ом разряде каждой35ячейки ,1 +1+1, соответствующему верЪинеисточника. Единица вд-х разрядах ячеек формирует псевдопетлю графа при возбуждении соответствующего логического выхода.40По нулевому адресу, соответствующему конечной вершине графа, в блок6 памяти занесен нуль. В счетчики2 с групп входов 13 заносятся в прямом коде коды степени захода соответствующим вершин графа, представляющие количества дуг, входящих в соответствующие вершины графа, В счетчики, которые не используются прирешении данного пакета заданий, заносится любое число, не равное "0",Соответствие вершины графа и счет. -чика 2 определяется весом вершины,представляющим собой величину максимального пути из данной вершины до 55конечной вершины графа, описывающего набор информационно связанныхзадач и имеющего в качестве весов дуг длительности решения задач, Первомусчетчику 2 (самому верхнему на Фиг,2)должна соответствовать вершина графас наибольшим весом, второму счетчику2 - вторая по весу вершина графа ит,д, Последнему счетчику 2 будет соответствовать конечная вершина графа,имеющая нулевой вес. Такое соответствие вершин и счетчиков 2 позволяет минимизировать время решения всего пакета информационно связанных задач, так как иэ некоторой совокупности запрашивающих решение задач (длярешения которых имеется вся необходимая информация) первой решаетсязадача, имеющая больший вес.Устройство работает следующим образом,Работа устройства начинается с приходом первого тактового импульса навход 16 устройства. Так как на выходах элементов ИЛИ-НЕ 3 группы, соответствующих счетчикам 2, в которыезанесен нулевой код степени захода,установлены единичные сигналы запросов, то на выходе элемента ИЛИ 12будет единичный сигнал, который приналичии сигнала на входе 17 устройства (свидетельствует о наличии свободных процессоров) проходит на выход элемента И 11, запрещая работуэлемента И 9 по его инверсному входу и разрешая передачу тактового импульса с входа 16 устройства черезэлемент И 10 на входы всех элементовИ 5 группы, при этом тактовый импульспроходит на выход только одного изэлементов И 5, соответствующего запросу на решение задачи с наибольшимвесом, т.е. проходит на выход самоговерхнего на чертеже элемента И 5,принимающего сигнал запроса с выхода одноименного элемента ИЛИ-НЕ 3группы. Все остальные расположенные ниже элементы И 5 группы запирают - ся нулевыми сигналами с выходов соответствующих элементов ИЛИ-НЕ 4 группы.Сформированный таким образом на одном иэ выходов 18 устройства импульсный сигнал инициирует решениесоответствующей задачи на одном иэсвободных процеСсоров вычислительной" системы и одновременно с этим переводит одноименный триггер 36, группы в единичное состояние и переключает одноименный счетчик 2, выводяего из нулевого состояния и тем самымснимая запрос на решение уже распре75182 51015 20 25 30 5 15деленной для решения задачи. Единич 1ный сигнал с прямого выхода триггера 36 группы поступает на одноименныйвход элемента ИЛИ 29, в результате чего разрешается прохождение тактовыхимпульсов через элемент К 32 на счетный вход счетчика 33, предварительносброшенного сигналом с выхода элемента И 10.Новый цикл работы устройства начинается с приходом очередного тактового импульса на вход 16 устройства.При наличии свободных процессоров исигнала запроса на выходе элементаИЛИ 12 тактовый импульс через элементИ 10 поступает на входы всех элементов И 5 группы и проходит на тот выход 18 устройства, который соответствует запросу на решение задачи снаибольшим весом. Происходит распределение выбранной задачи на одном изсвободных процессоров и одновременноснимается запрос на ее решение, Призапуске каждой новой задачи происходит сброс счетчика 33. Таким образом,счетчик 33 контролирует целостностьвременного интервала, необходимогодля решения самого длинного задания,Если при поступлении очередноготактового импульса на вход 16 устройства элемент И 10 оказывается заперчтым нулевым сигналом с выхода элемента И 11, возникающем при отсутствиизапросов на решение задач, либо приотсутствии свободных процессоров, тоанализируется состояние входа 15 устройства, т,е, наличие задач, решениекоторых в вычислительной системе закончено, При наличии единичного сигнала на входе.15 устройства тактовыйимпульс через элемент К 9 поступаетна входы всех элементов К 7 группы,разрешая выдачу на адресные входыблока 6 памяти кода решенной задачи с адресных входов 16 устройства,в результате чего Формируются импульсные сигналы на тех выходах блока 6 памяти, которые соответствуют задачам,непосредственно информационно связанным с решенной задачей, и происходитизменение на единицу кодов степенизахода этих задач (при этом могут ссформироваться запросы на решениенекоторых из этих задач, если станутнулевыми их коды степени захода). Приэтом псевдопетля вершины графа, образованная единичным значением разряда в коде решенной задачи, приводит к Формированию единичного импульса на выходе блока 6 памяти, соответствующем решенной задачеЭтот импульс поступает на входы одноименного элемента И 34 группы, закрытого нулевым сигналом с инверсного выхода одноименного триггера 36 группы, а также одноименного элемента КЛИ 35 группы и по заднему Фронту переводит триггер 36 группы в нулевое состояние, означающее, что задание не находится на выполнении в системе.Работа устройства продолжается до тех пор, пока не будет решена последняя задача, соответствующая конечной вершине графа, после чего вычислительная система устанавлива.-,ет на входе 15 устройства единичный сигнал при нулевом адресе на вхоцах 14 устройства, Очередной тактовый импульс, пройдя через открытые элементы И 8 и 9, формирует на выходе 19 устройства сигнал, свидетельствующий об окончании решения пакета задач,В случае возникновения аномальных ситуаций при решении пакета задач(зацикливание задачи, зависание процессора при сбое и т.п,) отрабатывает"ся следующая процедура. По превышении длительности временного интервала,необходимого для решения самого длинного задания вырабатывается сигнал переполнения счетчика 33, который поступает на прямой вход элемента КЛИ3 и открывает его по "0". Очередной тактовый импульс поступает на ин версный вход элемента ИЛК 31 и Формирует на его выходе нулевой сигналпо которому все процессоры системы переводятся в исходное состояние, а.номер невыполненного задания с выходаприоритетного шифратора 28 запоминается в блоке 24 памяти по адресу, определяемому содержимым счетчика 26,Этот же нулевой сигнал с задержкой,определяемой элементом 27 задержки и 50достаточной для надежного срабатывания блока 24 памяти, поступает насчетный вход счетчика 26, а также науправляющий вход дешифратора 25, Навыходе дешифратора 25, соответствующем незавершенному заданию, вырабатывается единичный сигнал, который поступает на вход одноименного элемента ИЛИ 1 первой группы и проходит через него на вход сброса одноименногосчетчика 2 группы и нулевой вход одНоименного триггера 36 группы. В результате этого на выходе одноименного элемента ИЛИ-НЕ 3 вырабатываЬтся единичныи сигнал, означающий нач5 личие готовой к решению задачи, Далее перезапуск задачи осуществляется аналогично описанному,В случае отказа процессоров вычислительной системы или неисправимой программной ошибки происходит ереполнение счетчика 2 б, на выходе переноса которого вырабатывается нулевой сигнал, поступающий на второй сигнальный выход 21 устройства и означающий аварийное завершение выполнения пакета информационно зависимых заданий. При этом в блоке 24 памяти сохраняются номера заданий при20 выполнении которых возникали аномальные ситуации. Анализ содержимого флока 24 памяти позволяет определить 1 ип ошибки (программная или аппаратная) и номер программного модуля с 25 Ошибкой.В дальнейшем устройство работает аналогично описанному.Формула и з о б р е т е и и яустройство для распределения заданий процессорам, содержащее группу Счетчиков, Первый блок памяти, первую 1 руппу элементов ИЛК, две группы элементов ИЛИ-НЕ, две группы элементов35 И, четыре элемента 1, первый элемент ИЛИ, причем группа адресных входов устройства поразрядно соединена с первыми входами элементов К первой группы и с группой инверсных входов Первого элемента И, выход которого является первым сигнальным выходом устройства, вход наличия законченных заданий устройства соединен с пер- вым входом второго элемента И, выход которого соединен с вторыми входами элементов И первой группы и с прямым входом первого элемента И, выходы элементов И первой группы соединены с ад)есными входами первого блока памя 50 ти, тактовый вход устройства соединен с вторым входом второго и первым входом третьего элементов К, выход третьего элемента К соединен с первыми входами элементов К второй груп-. пы, выходы которых являются первыми информационными выходами устройства, вход наличия свободных процессоров устройства соединен с первым входомчетвертого элемента И, выход которого соединен с инверсным входом вто"рого и вторым входом третьего элементов И, группа кодовых входов устройства соединена с информационными входами счетчиков группы, выходы которыхсоединены с входами элементов КЛИ-НЕпервой группы, группа тактовых входовустройства поразрядно соединена свходами записи счетчиков группы, выхо"ды элементов ИЛИ-НЕ первой группы поразрядно соединены с вторыми входамиэлементов К второй группы и с входами первого элемента ИЛИ, выход которого соединен с вторым входом четвертого элемента И, выход каждогоэлемента ИЛИ-НЕ первой группы с первого по К-й (где К - целая часть числа 0,5 п; п - разрядность номера задания) соединен с соответствующимвходом одноименного и последующихэлементов ИЛИ-НЕ второй группы доК-го включительно, выход каждого элемента ИЛИ-НЕ первой группы с (К+1)-гопо (п)-й соединен с соответствующимвходом одноименного и последующих элементов ИЛИ-НЕ второй группы до (п)го включительно, выход 1-го (х=1,п)элемента ИЛИ-НЕ второй группы соединен с третьим входом (1.+1)-го элемента И второй группы, о т л и ч а ю щ ее с я тем, что, с целью расширенияобласти применения устройства за счетобеспечения контроля завершения заданий, а также перезапуска и запоминания номеров незавершенных заданий,оно дополнительно содержит второй блокпамяти, два счетчика, дешифратор свторого по четвертый элементы ИЛИ,приоритетный шифратор, пятый элементИ, третью группу элементов К, вторуюгруппу элементов ИЛИ, группу триггеров и элемент задержки, причем выходкаждого элемента ИЛК-НЕ первой группыс первого по К"й соединен с соответствующим входом (К+1)-го и последующих элементов КЛИ-НЕ второй группы до(п)-го включительно, выход каждогоэлемента ИЛИ-НЕ первой группы соединен с информационным входом одноименного триггера группы, выход каждогоэлемента И второй группы соединен ссуммирующим входом одноименногосчетчика группы и спервым входом одноименного элемента ИЛК второй группы, группа выходов первого блока памяти поразрядно соединена с первыми входами элементов И третьей группь: и с вторыми входами элементов ИЛИ второй группы, выходы которых соединены с синхровходами соответствующих триггеров группы, инверсные выходы которых соединены с вторыми входами соответствующих элементов И третьей группы, выходы которых соединены с вычитающими входами соответствующих счет 10 чиков группы, прямые выходы триггеров группы соединены с входами входов второго элемента ИЛИ и приоритетного шифратора, выход с первым входом третьего элемента ИЛИ и приоритетногошифратора, выход с первым входом третьего элементаИЛИ, выход которого соединен с входом сброса первого счетчика, выход второго элемента ИЛИ соединен с первым прямым входом пятого элемента И, тактовый вход устройства соединен с вторым прямым входом пятого элемента И и с инверсным входом четвертого элемента ИЛИ, вход законченных заданий устройства соединен р 5 с инверсным входом пятого элемента И, выход которого соединен со счетным входом первого счетчика, выход переноса которого соединен с прямым входом четвертого элемента ИЛИ, входсброса устройства соединен с вторымвходом третьего элемента ЮП, с входомсброса второго счетчика и с первымивходами сброса элементов ИЛИ первойгруппы, группа выходов приоритетногошифратора соединена с группамиинформационных входов второго блока памятии дешифратора, группа выходов которогопоразрядно соединена с вторыми входами элементов ИЛИ первой группы, выходы которых соединены с входами сбро"са соответствующих триггеров и счетчиков групп, выход четвертого элемен"та ИЛИ является сигнальным выходомустройства и соединен с входом записи второго блока памяти и через элемент задержки со счетным входом второго счетчика и со стробирующим входом дешифратора, информационный выходвторого счетчика соединен с адреснымвходом второго блока памяти, выходкоторого является вторым информационным выходом устройства, выход переноса второго счетчика. является вторымсигнальным выходом устройства.1575182 2.2 Составитель М.СорочанРедактор Ю,Середа Техред Л,Сердюкова КорректорТ.Палий ул, Гага акаэ 1 785 Тираж ПодписноеНИИПИ Государственного к по изобретениям и 113035, М Ж, Раушская наб роизводственно-издательский комбинат "Патент", г, Ужг ытиям при ГКНТ 4/5