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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (!9) (!1) (51)5 G 06 F 9/46

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОЬ У СВИДЕТЕЛЬСТВУ

f

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4252428/24-24

22) 29.05.87

46) 30,06.90, Бюл, 9 24 (72) Г,Н,Тимонькин, К,А,Ручка, С,И,Ткаченко и В,С.Харченко (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 1348834, кл. G 06 Р 9/46, 1986, Авторское свидетельство СССР

Ф 1234838 кл, G 06 F 9/46, 1984. (54) УСТРОЙСТВО Д11Я РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение относится к автоматике и вычислительной технике, а именно к приоритетным устройствам для распределения заданий процессорам, и предназначено для использования в многопроцессорных и многомашинных вычисИзобретение относится к автоматике и вычислительйой технике, а именно к приоритетным устройствам для распределения заданий процессорам, и предназначено для использования в

-многопроцессорных и многомашинных вычислительных и управляющих системах.

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

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

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

Цель изобретения — расширение области применения устройства путем обеспечения контроля завершения заданий, а также перезапуска и запоминания номеров незавершенных заданий. Устройство для распределения заданий процессорам содержит две группы элементов ИЛИ, группу счетчиков, две группы элементов ИЛИ-НЕ, две группы элементов И, пять элементов И, четыре элемента ИЛИ, два блока памяти, дешифратор, два счетчика, элемент задержки, приоритетный шифратор, группу триггеров. Использование предложенного устройства облегчает при соответствующей программной и аппарат- @ ной поддержке отладку потоковых программ. 2 ил, тов ИЛИ-НЕ 4, группу элементов И 5, ь блок 6 памяти, группу элементов И 7» элементы И 8-11, элемент ИЛИ 12, группу кодовых входов 13 устройства, С группу адресных входов 14 устройства, вход 15 наличия законченных заданий устройства, тактовый вход !Ь устройства, вход 17 наличия свободных процессоров устройства, группу информационных выходов 18 устройства, сигнальный выход 19 устройства, вход 20 начальной установки устройства, сигнальный выход 21 ° ей устройства, группу сигнальных выходов

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

23 устройства, блок 24 памяти, дешифратор 25, счетчик ?6, элемент 27 saдержки, приоритетный шифратор 28, 1575182 элементы ИЛИ 29-31, элемент И 32, счетчик 33, группу элементов И 34, группу элементов ИЛИ 35, группу триггеров 36, ! ;2

Устройство работает следующим образом, Для перевода устройства в исходное состояние на вход 20 устройства подается единичный импульс, по которому элементы памяти устройства переходят в нулевое состояние, Блок 24 памяти обнуляется (цепи сброса в ис-! ходное состояние на. чертеже не по,казаны) ° Исходное состояние устройст- 1,5

, ва характеризуется тем, что импульсы на тактовом входе 16 устройства отсутствуют, в связи с чем на информационных выходах 18 и сигнальном выходе 19нулевые сигналы, а на сигнальных выходах 21 и 22 — единичные сигналы.

Блок 6 памяти содержит информацию о топологии графа, описывающего набор информационно связанных задач каж. дой вершине графа соответствует сово- 25 купность ячеек i i+1 i+å по числу логических выходов вершины. В каждую ячейку занесено и-разрядное число (п — число вершин графа), имеющее в соответствующем «1-м разряде единицу, если иэ i-й вершины графа исходит ду- га, ведующая в q-ю вершину. Одному логическому выходу вершины соответствует одна или несколько запускаемых вершин-приемников. Кроме того, занесена единица в i-ом разряде каждой ячейки i i +1...,,i+1 соответствующему веригине источника. Единица в

i-х разрядах ячеек формирует псевдопетлю графа при возбуждении соответ40 ствующего логического выхода.

По нулевому адресу, соответствующему конечной вершине графа, в блок

6 памяти занесен нуль. В счетчики

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

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

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

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

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

" системы и одновременно с этим переводит одноименный триггер 36, группы в единичное состояние и переключает одноименный счетчик 2, выводя

его из нулевого состояния и тем самым снимая запрос на решение уже распре75182

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 устройства сигнал, свидетельствующий об окончании решения пакета задач, В случае возникновения аномальных ситуаций при решении пакета задач (зацикливание задачи, зависание процессора при сбое и т.п,) отрабатывается следующая процедура. По превышении длительности временного интервала, необходимого для решения самого длин35 ного задания вырабатывается сигнал переполнения счетчика 33, который поступает на прямой вход элемента КЛИ

31 и открывает его по "0". Очередной тактовый импульс поступает на ин40 версный вход элемента ИЛК 31 и формирует на его выходе нулевой сигнал по которому все процессоры системы переводятся в исходное состояние, а.номер невыполненного задания с выхода приоритетного шифратора 28 запоминается в блоке 24 памяти по адресу, определяемому содержимым счетчика 26, Этот же нулевой сигнал с задержкой, определяемой элементом 27 задержки и

50 достаточной для надежного срабатывания блока 24 памяти, поступает на счетный вход счетчика 26, а также на управляющий вход дешифратора 25, На выходе дешифратора 25, соответствующем незавершенному заданию, вырабатывается единичный сигнал, который поступает на вход одноименного элемента ИЛИ 1 первой группы и проходит через него на вход сброса одноименного! 5751 82 счетчика 2 группы и нулевой в сод одНоименного триггера 36 группы. В результате этого на выходе одноименного элемента ИЛИ-HF. 3 вырабатываЬтся единичныи сигнал, означающий на5 личие готовой к решению задачи. Далее перезапуск задачи осуществляется аналогично описанному, В случае отказа процессоров вычислительной системы или неисправимой программной ошибки происходит

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

gèï ошибки (программная или аппаратная) и номер программного модуля с 25

Ошибкой.

В дальнейшем устройство работает аналогично описанному. формула изобретеEIия устройство для распределения заданий процессорам, содержащее группу

Счетчиков, Первый блок памяти, первую

1руппу элементов ИЛК, две группы элементов ИЛИ-НЕ, две группы элементов

И, четыре элемента 1, первый элемент

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

I"ðóïïû и с группой инверсных входов

Первого элемента И, выход которого является первым сигнальным выходом устройства, вход наличия законченных заданий устройства соединен с пер-„ вым входом второго элемента И, выход которого соединен с вторыми входами элементов И первой группы и с прямым входом первого элемента И, выходы эле- ментов И первой группы соединены с ад1)есными входами первого блока памя50 ти, тактовый вход устройства соединен с вторым входом второго и первым входом третьего элементов К, выход третьего элемента К соединен с первыми входами элементов К второй груп-пы, выходы которых являются первыми информационными выходами устройства, вход наличия свободных процессоров устройства соединен с первым входом четвертого элемента Vi, выход которого соединен с инверсным входом второго и вторым входом третьего элементов И, группа кодовых входов устройства соединена с информационными входами счетчиков группы, выходы которых соединены с входами элементов КЛИ-НЕ первой группы, группа тактовых входов устройства поразрядно соединена с входами записи счетчиков группы, выходы элементов ИЛИ-НЕ первой группы поразрядно соединены с вторыми входами элементов V. второй группы и с входами первого элемента ViJIH, выход которого соединен с вторым входом четвертого элемента И, выход каждого элемента ИЛИ-НЕ первой группы с первого по К-й (где К вЂ” целая часть числа 0 5n, п — разрядность номера задания) соединен с соответствующим входом одноименного и последующих элементов ИЛИ-НЕ второй группы до

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

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

1575182 дами элементов И третьей группы и с вторыми входами элементов ИЛИ второй группы, выходы которых соединены с синхровходами соответствующих триггеров группы, инверсные выходы которых соединены с вторыми входами соответствующих элементов И третьей группы, выходы которых соединены с вычитающими входами соответствующих счет 0 чиков группы, прямые выходы триггеров группы соединены с входами входов второго элемента ИЛИ и приоритетного шифратора, выход с первым входом третьего элемента ИЛИ и приоритетного шифратора, выход с первым входом третьего элемента ИЛИ, выход которого соединен с входом сброса первого счетчика, выход второго элемента ИЛИ соединен с первым прямым входом пятого элемента И, тактовый вход устройства соединен с вторым прямым входом пятого элемента И и с инверсным входом четвертого элемента ИЛИ, вход законченных заданий устройства соединен р5 с инверсным входом пятого элемента И, выход которого соединен co счетным входом первого счетчика, выход переноса которого соединен с прямым входом четвертого элемента ViJIH вход сброса устройства соединен с вторым входом третьего элемента ЮП, с входом сброса второго счетчика и с первыми входами сброса элементов ИЛИ первой группы, группа выходов приоритетного шифратора соединена с группами информационных входов второго блока памяти и дешифратора, группа выходов которого поразрядно соединена с вторыми входами элементов ИЛИ первой группы, выходы которых соединены с входа m сбро" са соответствующих триггеров и счетчиков групп, выход четвертого элемента ИЛИ является сигнальным выходом устройства и соединен с входом записи второго блока памяти и через элемент задержки со счетным входом второго счетчика и со стробирующим входом дешифратора, информационный выход второго счетчика соединен с адресным входом второго блока памяти, выход которого является вторым информационным выходом устройства, выход переноса второго счетчика. является вторым сигнальным выходом устройства.

1575182

Фи2. 2

Составитель М.Сорочан

Редактор lO,Ñåðåäà Техред Л. Сердюкова Корректор Т.Палий

Закаэ l 785

Тираж 573

Подписи о е

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СЧСР

113035, Москва, Ж-ÇS, Раушская наб., д. 4/5

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