Устройство для распределения заданий процессорам Советский патент 1990 года по МПК G06F9/50 

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

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

На фиг.1 и 2 приведена функциональная схема предлагаемого устройства.

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

22устройства, информационный выход

23устройства, блок 24 памяти, дешифратор 25, счетчик 26, элемент 27 задержки, приоритетный шифратор 28,

сл |

СД

эо

N5

элементы ИЛИ 29-31, элемент И 32, счетчик 33, группу элементов И 34, группу элементов ИЛИ 35, группу триггеров 36,

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

Для перевода устройства в исходное состояние на вход 20 устройства подается единичный импульс, по кЪто- рому элементы памяти устройства пере ходят в нулевое состояние. Блок 24 памяти обнуляется (цепи сброса в исходное состояние на чертеже не показаны) . Исходное состояние устройст- ва характеризуется тем, что импульсы на тактовом входе 16 устройства отсутствуют, в связи с чем на информационных выходах 18 и сигнальном выходе 19 нулевые сигналы, а на сигнальных вы- ходах 21 и 22 - единичные сигналы.

Блок 6 памяти содержит информацию о топологии графа, описывающего набор информационно связанных задач каждой вершине графа соответствует сово- купность ячеек i, i+l,..,,i+e по числу логических выходов вершины. В каждую ячейку занесено n-разрядное число (п - число вершин графа), имеющее в соответствующем q-м разряде единицу, если из i-й вершины графа исходит ДУ

га, ведующая в q-ю вершину. Одному логическому выходу вершины соответствует одна или несколько запускаемых вершин-приемников. Кроме того, занесена единица в i-ом разряде каждой ячейки i,i +l,...,i+l, соответствующему верТпине источника, Единица в 1-х разрядах ячеек формирует псевдопетлю графа при возбуждении соответствующего логического выхода.

По нулевому адресу, соответствующему конечной вершине графа, в блок 6 памяти занесен нуль. В счетчики 2 с групп входов 13 заносятся в прямом коде коды степени захода соответствующим вершин графа, представляющие количества дуг, входящих в соответствующие вершины графа. В счетчики, которые не используются при решении данного пакета заданий, заносится любое число, не равное О.

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

длительности решения задач. Первому счетчику 2 (самому верхнему на фиг.2) должна соответствовать вершина графа с наибольшим весом, второму счетчику 2 - вторая по весу вершина графа и т.д. Последнему счетчику 2 будет соответствовать конечная вершина графа, имеющая нулевой весс Такое соответствие вершин и счетчиков 2 позволяет минимизировать время решения всего пакета информационно связанных задач, так как из некоторой совокупности запрашивающих решение задач (для решения которых имеется вся необходимая информация) первой решается задача, имеющая больший вес.

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

Работа устройства начинается с приходом первого тактового импульса на вход 16 устройства. Так как на выходах элементов ИЛИ-НЕ 3 группы, соот«

5

0

ветствующих счетчикам 2, в которые занесен нулевой код степени захода, установлены единичные сигналы запросов, то на выходе элемента КЛК 12 будет едичичный сигнал, который при наличии сигнала на входе 17 устройства (свидетельствует о наличии свободных процессоров) проходит на выход элемента И 11, запрещая работу элемента И 9 по его инверсному входу и разрешая передачу тактового импульса с входа 16 устройства через элемент И 10 на входы всех элементов И 5 группы, при этом тактовый импульс проходит на выход только одного из элементов К 5, соответствующего запросу на решение задачи с наибольшим весом, т.е. проходит на выход самого верхнего на чертеже элемента И 5, принимающего сигнал запроса с выхода одноименного элемента ИЛИ-НЕ 3 группы. Все остальные расположенные ниже элементы И 5 группы запирают- - ся нулевыми сигналами с выходов соответствующих элементов КЛИ-НЕ 4 группы.

Сформированный таким образом на одном из выходов 18 устройства им- 0 пульсный сигнал инициирует решение соответствующей задачи на одном из свободных процессоров вычислительной 1 системы и одновременно с этим переводит одноименный триггер 36, группы в единичное состояние и переключает одноименный счетчик 2, выводя его из нулевого состояния и тем самым снимая запрос на решение уже распре5

5

деленной для решения задачи. Ьдинич- i

ный сигнал с прямого выхода триггера 36 группы поступает на одноименный вход элемента ИЛИ 29, в результате чего разрешается прохождение тактовых импульсов через элемент К 32 на счетный вход счетчика 33, предварительно сброшенного сигналом с выхода элемента И 10,

Новый цикл работы устройства начинается с приходом очередного тактового импульса на вход 16 устройства, При наличии свободных процессоров и сигнала запроса на выходе элемента ИЛИ 12 тактовый импульс через элемент И 10 поступает на входы всех элементов И 5 группы и проходит на тот выход 18 устройства, который соответствует запросу на решение задачи с наибольшим весом. Происходит распределение выбранной задачи на одном из свободных процессоров и одновременно снимается запрос на ее решение. При запуске каждой новой задачи происхо- дит сброс счетчика 33. Таким образом, счетчик 33 контролирует целостность временного интервала, необходимого для решения самого длинного задания,

Если при поступлении очередного тактового импульса на вход 16 устройства элемент И 10 оказывается запертым нулевым сигналом с выхода элемента И 11, возникающем при отсутствии запросов на решение задач, либо при отсутств ии свободных процессоров, то анализируется состояние входа 15 устройства, т.е. наличие задач, решение

которых в вычислительной системе за-

кончено, При наличии единичного сигнала на входе15 устройства тактовый импульс через элемент И 9 поступает на входы всех элементов К 7 группы, разрешая выдачу на адресные входы блока 6 памяти кода решенной задачи с адресных входов 16 устройства, в результате чего формируются импульсные сигналы на тех выходах блока 6 памяти, которые соответствуют задачам, непосредственно информационно связанным с решенной задачей, и происходит изменение на единицу кодов степени захода этих задач (при этом могут с сформироваться запросы на решение некоторых из этих задач, если станут нулевыми их коды степени захода), При этом псевдопетля вершины графа, обрадованная единичным значением разряда

0

0 5 0

п 0

,- .,

5

5

в коде решенной задачи, приводит к формированию единичного импульса на выходе блока 6 памяти, соответствующем решенной задаче. Этот импульс поступает на входы одноименного элемента И 34 группы, закрытого нулевым сигналом с инверсного выхода одноименного триггера 36 группы, а также одноименного элемента ИЛИ 35 группы и по заднему фронту переводит триггер 36 группы в нулевое состояние означающее, что задание не находится на выполнении в системе.

Работа устройства продолжается до тех пор, пока не будет решена последняя задача, соответствующая конечной вершине графа, после чего вычислительная система устанавливает на входе 15 устройства единичный сигнал при нулевом адресе на входах 14 устройства. Очередной тактовый импульс, пройдя через открытые элементы И 8 и 9, формирует на выходе 19 устройства сигнал, свидетельствующий об окончании решения пакета задач.

Б случае возникновения аномальных ситуаций при решении пакета задач (зацикливание задачи, зависание процессора при сбое и т.п.) отрабатывается следующая процедура0 По превышении длительности временного интервала, необходимого для решения самого длинного задания вырабатывается сигнал переполнения счетчика 33, который поступает на прямой вход элемента ИЛИ 31 и открывает его по О. Очередной тактовый импульс поступает на инверсный вход элемента ИЛИ 31 и формирует на его выходе нулевой сигнал по которому все процессоры системы переводятся в исходное состояние, а номер невыполненного задания с выхода приоритетного шифратора 28 запоминается в блоке 24 памяти по адресу, определяемому содержимым счетчика 26, Этот же нулевой сигнал с задержкой, определяемой элементом 27 задержки и достаточной для надежного срабатывания блока 24 памяти, поступает на счетный вход счетчика 26, а также на управляющий вход дешифратора 25, На выходе дешифратора 25, соответствующем незавершенному заданию, вырабатывается единичный сигнал, который поступает на вход одноименного элемента ИЛИ 1 первой группы и проходит через него на вход сброса одноименного

счетчика 2 группы и нулевой вход од- йоименного триггера 36 группы. В ре- зультате этого на выходе одноимен- Його элемента ИЛИ-НЕ 3 вырабатывается единичный сигнал, означающий наличие готовой к решению задачи, Далее перезапуск задачи осуществляется аналогично описанному,

В случае отказа процессоров вычислительной системы или неисправимой программной ошибки происходит переполнение счетчика 26, на выходе переноса которого вырабатывается ну- Аевой сигнал, поступающий на второй Сигнальный выход 21 устройства и означающий аварийное завершение выполнения пакета информационно зависимых заданий При этом в блоке 24 памяти сохраняются номера заданий при выполнении которых возникали аномальные ситуации. Анализ содержимого флока 24 памяти позволяет определить Тип ошибки (программная или аппаратная) и номер программного модуля с Ошибкой.

В дальнейшем устройство работает аналогично описанному.

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

Устройство для распределения заданий процессорам, содержащее группу Счетчиков, первый блок памяти, первую группу элементов ИЛИ, две группы элементов ИЛИ-НЕ, две группы элементов И, четыре элемента II, первый элемент ИЛИ, причем труппа адресных: входов устройства поразрядно соединена с первыми входами элементов И первой группы и с группой инверсных входов первого элемента И, выход которого Является первым сигнальным выходом устройства, вход наличия законченных заданий устройства соединен с первым входом второго элемента И, выход которого соединен с вторыми входами шементов К первой группы и с прямым входом первого элемента И, выходы эле

ментов И первой группы соединены с адресными входами первого блока памя- , тактовый вход устройства соединен с вторым входом второго и первым входом третьего элементов К, выход третьего элемента К соединен с первыми входами элементов К второй группы, выходы которых являются первыми информационными выходами устройства, вход наличия свободных процессоров

0

5

Q

0

5

5

0

5

0

5

устройства соединен с первым входом четвертого элемента И, выход которого соединен с инверсным входом второго и вторым входом третьего элементов И, группа кодовых входов устройства соединена с информационными входами счетчиков группы, выходы которых соединены с входами элементов КЛИ-НЕ первой группы, группа тактовых входов устройства поразрядно соединена с входами записи счетчиков группы, выходы элементов ИЛИ-НЕ первой группы поразрядно соединены с вторыми входами элементов И второй группы и с входами первого элемента ИЛИ, выход которого соединен с вторым входом четвертого элемента И, выход каждого элемента ИЛИ-НЕ первой группы с первого по К-й (где К - целая часть числа 0,5n; n - разрядность номера задания) со.единен с соответствующим входом одноименного и последующих элементов ИЛИ-НЕ второй группы до включительно, выход каждого элемента ИЛИ-НЕ первой группы с (К-Н)-го по (п-1)-й соединен с соответствующим входом одноименного и последующих элементов ИЛИ-НЕ второй группы до (п-1)- го включительно, выход 1-го (,п) элемента ИЛИ-НЕ второй группы соединен с третьим входом (i+l)-ro элемента И второй группы, отличающееся тем, что, с целью расширения области применения устройства за счет обеспечения контроля завершения заданий, а также перезапуска и запоминания номерор незавершенных заданий, оно дополнительно содержит второй блок памяти, два счетчика, дешифратор с второго по четвертый элементы ИЛИ, приоритетный шифратор, пятый элемент И, третью группу элементов И, вторую группу элементов ИЛИ, группу триггеров и элемент задержки, причем выход каждого элемента ИЛИ-НЕ первой группы с первого по К-й соединен с соответствующим входом (К+1)то и последующих элементов ИЛИ-НЕ второй группы до (п-1)-го включительно, выход каждого элемента ИЛИ-НЕ первой группы соединен с информационным входом одноименного триггера группы, выход каждого элемента И второй группы соединен с суммирующим входом одноименного счетчика группы и с первым входом одноименного элемента ИЛИ второй группы, группа выходов первого блока памяти поразрядно соединена с первыми вхо915

дами элементов И третьей группы и с вторыми входами элементов ИЛИ второй группы, выходы которых соединены с синхровходами соответствующих триггеров группы, инверсные выходы которых соединены с вторыми входами соответствующих элементов И третьей группы, выходы которых соединены с вычитающими входами соответствующих счетчиков группы, прямые выходы триггеров группы соединены с входами входов второго элемента ИЛИ и приоритетного шифратора, выход с первым входом третьего элемента ИЛИ и приоритетного шифратора, выход с первым входом третьего элемента ИЛИ, выход которо го соединен с входом сброса первого счетчика, выход второго элемента ИЛИ

соединен с первым прямым входом пятого элемента И, тактовый вход устройства соединен с вторым прямым входом пятого элемента И и с инверсным входом четвертого элемента ИЛИ, вход законченных заданий устройства соединен с инверсным входом пятого элемента И, выход которого соединен со счетным входом первого счетчика, выход пере82

10

0

5

0

5

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

Фиг. 2

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

Составитель М.Сорочан Редактор Ю,Середа Техред Л.Сердюкова Корректор Т.Палий

Заказ 1785

Тираж 573

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат Патент, г. Ужгород, ул. Гагарина, 101

Подписное