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

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

Известно устройство для распределения заданий, содержащее матрицу ячеек памяти, блок анализа строку содержащий приёмный регистр, узел опроса, регистр назначений, шифрат | блок анализа столбов, содержащий приемный регистр, узел опроса ре гистр назначений, шифратор, регистр, генератор, счетчик назначений, схеЦ сравнения, триггеры, элементы ИЛИ/ И и НЕ tl J.

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

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

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

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

Поставленная цель достигается тем,

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

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

20 поиска максимального группы элементов НЕ, группу элементов ИЛИ, : третью группу ре -истров и две rpynnri элементов И-НЕ, причем второй выход каждого i-ro регистра (i - 1,..п) пер25вой группы соединен с первым ъходам Г-го блока элементов И второй группь / втррой вход которого соединен с i-м выходом -первого узла, поиска максимального кода и с первым входом 1-го бло30ка элементов И третьей группы, второй вход которого соединен с выходом 1-го регистра второй группы, второй выход которого соединен с первым вхо дом i-ro блока элементов И третьей группы, второй вход которого соедине с выходом элемента НЕ первой группы и с первым входом i-ro элемента И-НЕ первой группы, выход кото рого соединен с управляющими входами i- X регистров первой и второй групп выход каждого i-ro блока элементов И второй и третьей группы соединен соответственно с первым и вторым входа ми i -и схемы сравнения группы, выход которой через (-и элемент НЕ второй группы соединен с первым входом i-ro элемента И-НЕ второй группы и с вход I-го элемента НЕ первой группы, второй вход каждого 1-го элемента И-НЕ второй группы соединен с i-м выходом второго узла поиска максимальног кода, входы которого соединены соответственно со вторыми входами схем сравнения группы, выходы i-x элементов И-НЕ второй группы соединены со вторыми входами i-x элементов И-НЕ первой группы и с первыми входами элементов ИЛИ группы, выходы которых являются информационными -выходами устройства, вход считывания устройства соединен со вторыми входами каждого i-ro блока элементов И первой группы, выходы которых соединены с i-ми входами первого узла поис,ка максимального кода, выход которого соединен с входами элемента И, выход которого соединен с первыми входами блоков элементов И пятой группы, вторые входы которых соединены с выходами соответствующих реги стров третьей группы, первый, второй входы каждого i-го регистра третьей группы соединены соответственно с выходом i-ro блока элементов И четвертой группы и с i-M выходом третье го узла поиска максимального кода, второй вход каждого i-ro элемента ИЛИ группы через i-и элемент. НЕ третьей группы соединен с i-м выходо третьего узла поиска максимального кода, третий вход каждого блока элеменгов И пятой группы соединен с так товым входом устройства, выход каждо го i-го блока элементов И пятой группы соединен с i -м входом третье го узла поиска максимального кода. , На фиг. 1 представлена структурна схема устройства , на фиг. 2 - структурная схема узла поиска максимального кода. Схема устройства содержит узел 1 поиска максимального кода, группы блоков 2 элементов И, группы регистров 3, .4 группы блоков 5 -элементов И, группу блоков 6 элементов И,групп схем 7 сравнения, группу элементов НЕ 8, узел 9 поиска максимального ко да, группы элементов И-НЕ 10, 11, группу элементов НЕ 12, группу элементов И 13, группу регистров 14, элемент И 15, группу блоков 16 элементов И, узел 17 поиска максимального кода, группу элементов НЕ 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 - низкий потенциал, который поступает на элемент НЕ 8, где инвертируется, и высокий потенциал поступает на соответствующий элемент И-НЕ 10. Одновременно код с регистра 4 подается на узел 9. Из поступивших кодов выбирается максимальный, а так как поступил только один код, то он является максимальным и высокий потенциал с выхода узла 9 поступает на элемент И-НЕ 10. На выходе элемента И-НЕ 10 появля ется низкий потенциал, что указавает на позиционный номер очередного выбранного задания. Такое же состояние на выходе элемента ИЛИ 19. Далее низ кий потенциал с элемента И-НЕ 10 поступает на вход соответствующего эле мента. И-НЕ 11. С выхода элемента НЕ 8 высокий потенциал поступает на элемент НЕ 12 с выхода ко,торого низкий потенциал поступает на вход соответствующего элемента И-НЕ 11, что соответствует записи в регистры 3 и 4 единичного кода. Если максимальных кодов несколько то с выхода узла 1 на соответствующие блоки элементов И 5 и 6 поступают высокие потенциалы. Пусть, например, высокий потенциал поступает на йентили 5|с.1 , 6ц. , SK., Н, 5к , 6- (к 1,2,...). С регистров к.-1 . 4 ц. , 4к-и информация поступает соответственно на схемы сравнения 7к.-1 , 7ic f I где происходят сравнения двух кодов. Пусть код времени ввода в регистр больше кода времени решения в регистре 4 ц.Тогда высокий потенциал поступает на вход элемента НЕ 8, выход которого подключен ко входу элемента НЕ 12к--. Если на схему 9 поступают три кода с блоков бк-i , f 6к4-1, то из них выбирается максималь ный. Допустим, что код, поступивший |С выхода б K-i I минимален. Тогда эле мент 11к-4 переводит регистры 3|e- и 4к- в единичное состояние. На первый вход элемента ИЛИ 19ц-1 поступает высокий потенциал, таким образом, на выходе устройства на {к-1)-м элементе высокий потенциал, а для указа ния выбора задания в пакете служит низкий. Пусть коды, пропорциональные времени ввода, занесенные в регистры 3(tf Lt I меньше кодов, пропорциональных времени решения, занесенным соответственно в регистры 4к и 4ц4.| , а код,занесенный в регистр 4,меньше кода, занесенного в регистр 4к4. Тогда информация поступает на входы схем 7(с, . Низкие потенциалы выходов схем 7ц и 7 |с4- ют соответственно на вход элемента НЕ 8 и 8ц., где инвертируются и далее подаются на входы элементов 10ц и 10к4. Одновременно на вход схемы 9 поступают коды с блоков Sit-f / 6к, бк. J все изменения, происшедшие с кодом К-1-ГО номера,описаны, но на узел 9 (к-1)-Й код поступает одновременно с к-м и {к-1)-м кодами. Узел 9 выбирает максимальный код с номером к+1 и высокий потенциал с выхода схемы 9 поступает на второй вход элемента lOjct. Таким образом, низкий потенциал, который появляется на выходе , указывает на позиционный номер очередного выбранного задания, так как на выходе элемента устройства будет такой же сигнал. Одновременно низкий потенциал с выхода элемента 10|t переводит регистры Зц4,и 4, в единичное состояние. Одновременно с выхода узла 9 на элемент И-НЕ Юц поступает низкий потенциал, который образует на выходе элемента lOic. высокий потенциал, поступающий на элемент ИЛИ 19,. С -выхода элемента 8| высокий потенциал подается на элемент НЕ 12ц, где инвертируется, информация, занесенная в регистры 3It и 4у. , не изменяется, а на выходе 22к - высокий потенциал. Одновременно, перед переведением регистров 4 |с- в единичное состояние, высоким уровнем потенциала, поступающего с выхода элемента НЕ 12 ц , открываеТся блок 13ц и информация с регистра 4ц заносится на регистр 14. Затем блок 13 запирается.. . Если в рассмотренном случае окажется, что коды, занесенные- в регистры 4 | и 4ц, равны, то выбор очередного задания осуществляется в порядке поступления. Сначала выбирается к-е задание и затем (K-fl)-e зада- нйе. После выбора очередного задания шаг выборки заканчивается. Для продолжения работы необходимо снова подать импульс на вход 20. Когда все задания в пакете пересмотрены и выбраны те, у которых время ввода меньше времени решения, первый цикл (цикл определения наибо- лее приоритетных для ЦВМ заданий) заканчивается. После первого цикла- подается следующий сигнал по входу 20 и устройство снова переходит в рабочее состояние. На выходе узла 1 после прихода импульса на вход 20 образуются высо- кие потенциалы во всех выходах, так как все коды, записанные в регистрах 3 после первого цикла, максимальны (единичные коды). Открывается элемент И 15, и высокий потенциал поступает на группы блоков 16. По приходу синхронизирующего сиг-г нала на вход 21 продолжается дальнейшая выборка очередных заданий. С выходов регистров 14 через блоки 16 информация поступает на узел 17. Из всех кодов, пропорциональных времени решений, поступивших с регистров 14, выбирается максимальный, и высокий потенциал поступает на вход соответствующего элемента НЕ 18, где инвертируется и определяет позиционный .номер очередного выбранного задания, а на выходе .22 - низкий потенциал.

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

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

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

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

Работу предлагаемого устройства рассмотрим на конкретном примере. Пусть информация о пакете решаемых задач задана следующей {t - время ввода, t - суммарное, время решенця 25 и вывода результата решения задачи}:

задачи.

в пакете12345678

И3 3 4 673 44

tf 35223722 0 В исходном состоянии время t занесено и хранится на регистрах 3 а время tj- - на регистрах 4.

После подачи управляющего сигнала на вход 20 коды с инвер|сных выходов 35 регистров 3 через открытые блоки 2 поступают на узел 1, где производится вгыбор заданий с номерами 1, 2 и 6. Одновременно коды с регистров 3 поступают на соответствующие блоки 5, но 40 проходят только 5 , 52. Я 5б блоки.Коы с регистров 4 поступают на первые входы группы блоков 6, на вторые входы котррых поступают управляющие сигналы с Соответствующих выходов узла 45 1. Только с выходов открытых блоков 5 и 6,, , 5 и 6у 5s- и 6 коды поступают на схемы сравнения 7 ,7. и 7 соответственно, а нулевой сигнал появляется на выходах схем 1 и 7. MJ Одновременно через блоки 6 , бд и б коды с-регистров 4 , 4. и 4 поступают на узел 9, на 6-м выходе которого появляется высокий потенциал, котсчрый поступает на первый вход элемента 10 поступает такя(е высокий потенциал с выхода элемента НЕ . ОЭТОМУ на выходе элемента 22 появяетсй низкий потенциа д что свиде- тельствуёт о назначении в первую оче- . редь для реализации в ЦВМ 6-й задачи, и так далее.

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

задачи

12345678 пакете

t. tf 237 3 4 6 4 4

75 3 322 22

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

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

Усжройствр для распределения заданий, содержащее группу схем сравнения первую и вторую группы блоков элементов И, первую и вторую группы регистров, причем первый выход каждого регистра первой группы соединен с первым входом соответствующего блока элементов И первой группы, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения устройства, оно содержит третью, четвертую и пятую группы блоков элементов И, элемент И, три узла поиска максимального кода, три группы элементов НЕ, группу элементов ИЛИ, третью группу регистров и две группы элементов ИНЕ, причем второй выход каждого 1-го { 1,...,п) регистра первой группы соединен с первым входом i-го блока элементов И второй группы, второй вход которого соединен с i-м выходом первого узла поиска максимального кода И с первым входом i -го блока элементов И третьей группы, второй вход которого соединен с выходом i-ro регистра второй группы, второй выход которого соединен с первым входом -го блока элементов И третьей группы, второй вход которого соединен с выходом i-ro элемента НЕ первой группы и с первым входом f-го элемента И-НЕ первой группы выход которого соединен с управляющими входами i-x регистров первой и второй ГРУПП, выход каждого i-ro блока, элементов И второй и третьей групп соединен соответственно с первым и вторым входами i-и схемы сравнения группы, выход которой через i-и элемент НЕ второй группы соединен с первым входом f-ro элемента И-НЕ втррой группы и с входом i-ro элемента НЕ. первой группы, второй вход каждого i-ro элемента И-НЕ второй группы соединен с i-м выходом второго узла поиска максимального кода, входы которого соединены соот)ветственно со вторыми входами схем сравнения группы, выходы i-x элементов И-НЕ второй группы соединен со вторыми входами i-x элементов И-НЕ первой группы и с первыми входами элементов ИЛИ группы, выходы которых являются информационными выходами устройства, вход считывания устройства соединен со вторыми входами каждого i-го блока элементов И первой группы, выходы которых соединены с i-ми входами первого узла поиска максимального кода, выход которого соединен с входами элемента И, выход которого соединен с первыми входами блоков элементов и пятой группы, вторые входы которых соединены с выходами соответствующих регистров третьей группы, первый,второй входы кгикдого i-ro регистра третьей группы соединены соответственно с выходом i-ro блока элементов И четвертой группы и с i-м выходом третьего узла поиска максимального кода, второй вход каждого i-ro

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

0

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

1.Авторское свидетельство СССР 6.96471, кл. G 06 F 15/20, 1979.

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

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