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

 

ОПИСАНИЕ

ИЗОВРЕТЕНИЯ

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

Союз Советския

Социалистических

Республик

<>959083 (61) Дополнительное к авт. саид-ву (22) Заявлено 191280 (21)3234017/18-24

Р М К з

С 06 F 9/46 с присоединением заявки ¹

Государственный комитет

СССР по делам изобретений и открытий (23) Приоритет

Опубликовано 150982 Бюллетень ¹ 34 (53) УДК 684. 325 (088.8) Дата опубликования описания 150982

ы (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ

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

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

И и НЕ 1 .

Недостатком данного устройства является сложность и низкое быстродействие при решении пакета задач в

ЦВМ.

Наиболее близким к предлагаемому является устройство для распределе.ния заданий, содержащее по.числу заданий в пакете первую и вторую группы регистров, первую и вторую группу вентилей, группу схем сравнения Е23.

Недостатком данного устройства ss- ляется невозможность осуществления оптимального распределения пакета

5 решаемых задач в ЦВМ по критерию минимума суммарного времени их реализации.

Цель изобретения — расширение области применения устройства.

10. Поставленная цель достигается тем, что устройство для распределения за-. даний-, включающее группу схем сравне-. ния, первую, вторую группы блоков элементов И, первую, вторую группы ре-, гистров, причем первый выход каждого регистра первой группы соединен с первым входом соответствующего блока эле-I ,ментов И первой группы, содержит третью, четвертую и пятую группы блоков элементов И, элемент И, три узла поиска максимального кода три группы элементов НЕ, группу элементов ИЛИ,; третью группу регистров и две группй элементов И-HE причем второй выход каждого I-го регистра (f. 1...n) nep25 вой группы соединен с первым входом

1-го блока элементов И второй группок второй вход которого соединен с i-м выходом первого узла. поиска максимального кода и с первым входом i-го бло30 ка элементов И третьей группы, второй

959083

35 вход которого соединен с выходом

1-го регистра второй группы, второй выход которого соединен с первым входом i-ro блока элементов И третьей группы, второй вход которого соединен с выходом i-ro элемента НЕ первой 5 группы и с первым входом i-ro элемента И-НЕ первой группы, вйход которого соединен с управляющими входами х регистров первой и второй групп выход каждого i-ro блока элементов И 19 второй и третьей группы соединен соответственно с первым и вторым входами 1-й схемы сравнения группы, выход которой через i-й элемент НЕ второй группы соединен с первым входом I го элемента И-НЕ второй группы и с входом

i-ro элемента HE первой группы, второй вход каждого 1-го элемента И-НЕ второй группы соединен с i-м выходом второго узла поиска максимальногг кода, входы которого соединены .соответственно со вторыми входами схем сравнения группы, выходы i-x элементов И-НЕ второй группы соединейы со вторыми входами i-х элементов И-НЕ первой группы и с первыми входами элементов ИЛИ группы, выходы которых являются информационными -выходами устройства, вход считывания устройства соединен со вторыми входами каждого i-го блока элементов И пер- ЗО вой группы, выходы которых соединены с i-ми входами первого узла поиска максимального кода, выход которого соединен с входами элемента И, выход которого соединен с первыми входами блоков элементов И пятой группы, вторые входы которых соединены с выходами соответствующих регистров третьей группы, первый, второй входы каждого i-го регистра третьей 4g группы соединены соответственно с выходом i-ro блока элементов И четвертой группы и с i-м выходом третьего узла поиска максимального кода, второй вход кащцого i-ro элемента

ИЛИ группы через i-й элемент. НЕ третьей группы соединен с i-м выходом третьего узла поиска максимального кода, третий вход каждого блока элементов И пятой группы соединен с тактовым входом устройства, выход каждого i-ro блока элементов И пятой группы соединен с -м входом третьего узла поиска максимального кода.

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

Схема устройства содержит узел 1. поиска максимального кода, группы блоков 2 элементов И, группы региат- !9 ров 3, .4,группы блоков 5 .элементов

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

ИЛИ-НЕ 23, группы 24 элементов И-ИЛИ

25, содержащие элементы ИЛИ 26 и элементы И 27 (на фиг. 2 обозначены выходы 28 и входы 29), Схемы сравнения 7, входящие в устройстуо, выполнены аналогично узлам поиска максимального кода, но на две группы входов.

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

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

В исходном состоянии на группу регистров 3 заносятся коды, пропорциональные времени ввода решаемых задач.На группу регистров 4 заносятся коды, пропорциональные сумме времени решения задачи и вывода результатов .решения. После занесения информации на регистры первой группы 3 подается управляющий сигнал по шине 20 на вход первой группы блоков элементов 4 и устройство начинает свою работу по выбору очередной задачи из пакета.

На узел 1 подаются коды с инверсных выходов регистров 3; т.е. информация на узел 1 подается в обратном коде, поэтому в узле 1 выбирается минимальное число из кодов, занесенных в регистры 3 (выбирается один или несколько кодов, если имеются среди них равные).

Если минимальный код один, то с узла 1 на соответствующий блок элементов И 5 и 6 поступает высокий потенциал, благодаря чему коды с прямых выходов регистров 3 и 4 через блоки 5 и 6 поступают на соответствующую схему сравнения 7, где происходит сравнение кодов времени ввода и решение одной задачи.

Если. время решения оказалось больше времени "ввода, то на выходе схемы

7 — низкий потенциал, который поступает на элемент HE 8, где инвертиру-. ется, и высокий потенциал поступает на соответствующий элемент И-НЕ 10.

Одновременно код с регистра 4 подается на узел 9. Иэ поступивших кодов выбирается максимальный, а так как

1 поступил только один код, то он является максимальным и высокий потенциал с выхода узла 9 поступает на элемент И-НЕ 10.

5 959083 6

На выходе элемента И-HE 10 появляется низкий потенциал, что указавает на позиционный номер очередного выбранного задания. Такое же состояние на выходе элемента ИЛИ 19. Далее нызкий потенциал с элемента И-НЕ 10 поступает на вход соответствующего элемента И-HE 11.

С выхода элемента НЕ 8 высокий потенциал поступает на элемент НЕ 12, с выхода которого низкий потенциал поступает на вход соответствующего элемента И-HE 11, что соответствует записи в регистры 3 и 4 единичного кода.

Если максимальных кодов несколько, то с выхода узла 1 на соответствующие блоки элементов И 5 и 6 поступают высокие потенциалы. Пусть,- например, высокий потенциал поступает на вентили 5 1, бк, 5<, Ня, 5„+q, 6 + (к = 1,2,... ) . С регистров 3õ 4

4 „, Зк, 4 +., 4K+4 информация поступает соответственно на схемы сравнения 7к, q 7„, 7к, где происходят сравнения двух кодов.

Пусть код времени ввода в регистре

3 q больше кода времени решения в регистре 4 „ .Тогда высокий потенциал поступает на вход элемента НЕ 8„ <, выход которого подключен ко входу элемента НЕ 12 q . .Если на схему 9 поступают три кода с блоков 6к g 6, 6к+, то из них выбирается максимальный. Допустим, что код, поступивший с выхода 6 к, минимален. Тогда эле мент 11„ переводит регистры 3 и

4к в единичное состояние. На первый вход элемента ИЛИ 19 q поступает высокий потенциал, таким образом, на выходе устройства на (к-1)-м эле" менте высокий потенциал, а для указания выбора задания в пакете служит . низкий.

Пусть коущ, пропорциональные времени ввода, занесенные в регистры

3, 3 +, меньше кодов, пропорциональнйх времени решения, занесенным соответственно в регистры 4я и 4, а код,занесенный в регистр 4,меньше кода, занесенного в регистр 4к+, .

Тогда информация поступает на входы схем 7„, 7к+ . Низкие потенциалы выходов схем 7к и 7 к < поступа"ют, соответственно на вход элемента

ЙЕ 8 и Bg+g где инвертируются и далее подаются на входы элементов

10к и 10х+1. Одновременно на вход схемы 9 поступают коды с блоков

6к. 1, 6к, 6 .. все изменения, происшедшие с кодом к-1-ro номера,описаны, но на узел 9 (к-1)-Й код поступает одновременно с к-м и (к-1)-м кодами. Узел 9 выбирает максималь" ный код с номером к+1 и высокий потенциал с выхода схемы 9 поступает на второй вход элемента 10к . Таким образом, низкий потенциал, который появляется на выходе 10 +, указывает на позиционный номер очередного выбранного задания, так как на выходе элемента 22к+ устройства будет такой же сигнал. Одновременно низкий потенциал с выхода элемента 10« переводит регистры 3 +„ и 4 „ в единичное состояние.

Одновременно с выхода узла 9 на элемент И-НЕ 10 поступает низкий

>0 .потенциал, который образует на выходе элемента 10@. высокий потенциал, поступающий на элемент ИЛИ 19 . С выхода элемента 8 высокий потенциал подается на элемент НЕ 12, где инвертируется, информация, занесенная в регистры Зк и 4„, не.изменяется, 15 а на выходе 22к — высокий потенциал.

Одновременно, перед переведением,регистров 3„ <и 4 y q в единичное сосжется, что коды, занесенные в регистры 4 и 4 pig равны,:то выбор очередного задания осуществляется в по"

З0 рядке поступления. Сначала выбирает" ся к-е задание и затем (к+1)-е задание ° После выбора очередного задания шаг выборки заканчивается. Для продолжения работы необходимо снова

З5 подат импУльс на вход 20.

Когда все задания в пакете пересмотрены и выбраны те, у которых время ввода меньше времени решения, первый цикл (цикл определения наибо. лее приоритетных для ЦВМ заданий)

40 заканчивается.

После первого цикла подается следующий сигнал по входу 20 и устройство снова переходит в рабочее состояние. На выходе узла 1 после прихода, 45 импульса на вход 20 образуются высо-. кие потенциалы во всех .выходах, так как все коды, записанные в регистрах

3 после первого цикла, максимальны (единичные коды). Открывается элемент

$g И 15, и высокий потенциал поступает на группы блоков 16..

По приходу синхрониэирующего сиг-...нала на вход 21 продолжается дальнейшая выборка очередных заданий.

С выходов регистров 14 через блоки 16 информация поступает на узел

17. Из всех кодов, пропорциональных времени решений, поступивших с реги;стров 14, выбирается максимальный, 6© и высокий потенциал поступает на вход соответствующего элемента HE 18, где инвертируется и определяет позиционный .номер очередного выбранного задания, а на выходе 22 — низкия п65 тенциал.

20 тояние, высоким уровнем потенциала, поступающего с выхода элемента НЕ

12 1, открывае"гся блок 13к q и информация с регистра 4 „ заносится на регистр 14 „. Затем блок 13 зау5 пирается

Если в рассмотренном случае ока959083

Одновременно высокий потенциал с выхода узла 17 поступает на регистр

14 и сбрасывает его в нулевые состояния. Низкие потенциалы с выходов узла 17 поступают на те регистры, которым они соответствуют, и оставляют их состояния без изменений.

А

Схема переводится в рабочее состояние путем подачи нового синхронизирующего импульса по входу 21 и таким образом начинается следующий

roar выборки.

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

Устройство заканчивает свою .работу после выбора всех заданий, присутствующих в пакете.

Работу предлагаемого устройства рассмотрим на конкретном примере.

Пусть информация о пакете решаемых задач задана следующей (t -- время ввода, „ — суммарное. время решения и вывода результата решения задачи):

Р задачи в пакете 1 2 3 4 5 6 7 8

И 3 3 4 6 7 3 4 4

t 35223722

В исходном состоянии время ti занесено и хранится на регистрах 3, а время t — на регистрах 4.

После подачи управляющего сигнала на вход 20 коды с инверсных выходов регистров 3 через открытые блоки 2. поступают на узел 1, где производится выбор заданий с номерами 1, 2 и 6.

Одновременно коды с регистров 3 поступают на соответствующие блоки 5, но

:проходят только 5 ., 5 и 5ь блоки.Коды с регистров 4 поступают на первые входы группы блоков 6, на вторые входы которых поступают управляющие сигналы с cooòâåòñòâóêùèx выходов узла

1. Только с выходов открытых- блоков

5„и б, 5 и 6>, 5 и бб кодЫ поступают на схемы сравнения 7,7у и 7А соответственно, а нулевой сигнал появляМся на выходах схем 7 и 76.

Одновременно через блоки 64, б и 6 коды с регистров 4« 4 и 4ь поступают на узел 9, иа. б-м выходе которо-. го появляется высокий потенциал, котс4рый поступает на первый вход элемента 10ь, поступает такыре высокий потенциал с выхода элемента НЕ 8 .

Поэтому на выходе элемента 226 появляется низкий цотенциай, что свиде-.тельствует о назначении в первую очередь для реализации в ПВИ 6-й задачи, и так далее.

В результате устройство для распределения заданий преобразует исходные данные последовательности заданий в следующие:

Р задачи в пакете 1 2 3 4 5 6 7 8

2.3 7 3 4 б 4 4

7 5 3 3 2 2 2 2

Применение изобретения позволяет расширить область применения устройства за счет применения его там,где требуется оптимизировать пакеты заданий в соответствии с алгоритмом

Джонсона.

10

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

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

20 расширения области применения устройства, оно содержит третью, четвертую и пятую группы блоков элементов И, элемент И, три узла поиска максимального кода, три группы элементов НЕ, группу элементов ИЛИ, третью группу регистров и две группы элементов ИНЕ, причеМ второй выход каждого i-го (i = 1,...,n) регистра первой группы соединен с первым входом i-ro блока элементов И второй группы, второй вход которого соединен с i-м выходом первого узла поиска максимального кода и с первым входом i««ro блока элементов И третьей группы, второй вход которого соединен с выходом

i-ro регистра второй группы, второй

46 выход которого соединен с первым входом 1-ro блока элементов И третьей группы, второй вход которого соединен с выходом i-ro элемента НЕ первой группы и с первым входом i-го

45 элемента И-НЕ первой группы выход которого соединен с управляющими входами i-х регистров первой и второй групп, выход каждого i-ro блока элементов И второй и третьей групп д соединен соответственно с первым и вторым входами i-й схемы сравнения группы, выход которой через i-й элемент НЕ второй группы соединен с первыМ входом t-го элемента И-НЕ второй гРУппы и с входом i-ro элемента НЕ. первой группы, второй вход каждого

i-ro элемента И-HE второй группы. соединен с i-м выходом второго узла поиска максимального кода, входы которого соединены соответственно со вторыми входами схем сравнения группы, выходы i-x элементов И-НЕ второй .группы соединены со вторыми входами

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

i ì выходом третьего узла поиска максимального кода, третий вход каждого блока элементов И пятой группы соедн« нен с тактовым входом устройства, выход каждого i-го блока элемента И пятой группы соединен с i-м входом третьего узла поиска максимального кода. о

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

9 696471, кл. G 06 F 15/20, 1979..

2. Авторское свидетельство СССР

9 339916, кл. G 06 F 9/46, 1972 (прототип).

959083

Составитель М.Кудряшов

Редактор О.Колесникова Техред З.Палий Корректор А.Гриценко

Заказ 7018/66 Тираж 731 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4