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

 

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

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

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

РЕСПУБЛИК (si)s G 06 F 9/46

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИ4ЕТЕЛЬСТВУ. (21) 4902435/24 (22) 14.01.91 (46) 15.08,93. Бюл. ¹ 30 (72) В.B.Áàòèöåâ, В.М.Лукьянов, В,В.Милованов, А.B.Ïëàòóíîâ и В.А.Титов (56) Авторское свидетел ьство СССР

¹ 1065856, кл. G 06 F 9/46, 1984.

Авторское свидетельство СССР № 1295395, кл, G 06 F9/46,,1986, (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ (57) Изобретение относится к области вычислительной техники и может быть испольИзобретение относится к области вычислительной техники и может быть использовано при организации пакетной обработки в ЭВМ, а также в устройствах, предназначенных для решения задач в специализированных процессорах.

Цель изобретения — повышение быстродействия за счет сокращения времени на пересчет "весов" фаз выполняемых задач, На фиг.1 представлена структурная схема устройства для распределения заданий; на фиг,2 — структурная схема блока выдачи результатов, Устройство содержит (фиг.1) генератор тактовых импульсов 1, элемен И2, элементы И311...32п, где n — число задач в пакете, блок элементов И 4, элемент ИЛИ 5, блок элементов И 6, блок выдачи результатов 7, вычитающие счетчики 811...82n, элементы

ИЛИ 911...92n, элемент И 1011...102n, триггеры 1111...112 . дифференцирующие цепочки

1211...122n, элементы И131...13n, блоки 141 и

„„ Ы„„1833873 Al зоэано при органиэации пакетной обработки в ЭВМ, а также в устройствах, предназначенных для решения задач в специализированных процессорах. Цель изобретения — повышение быстродействия за счет сокращения времени при пересчете

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

142 приоритета, вход 15, выходы 16, 171, 172, 18, входы 19, 2011...201п, 2021...20zn.

Блок 7 (фиг.2) содержит элементы ИЛИ

211 и 212, два формирователя импульсов 221 и 222, элемент ИЛИ23, блоки элементов И

241 и 24z, блок элементов ИЛИ 25, элемент

ИЛИ 26, счетчики 27, 28, триггер 29, счетчик

30, элемент И 31, блок элементов ИЛИ 32, блок элементов И 33, входы 3411...342П, выход 35.

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

В исходном состоянии все триггеры 11 и 29, счетчики 8, 27, 28, 30 находятся в нулевом состоянии (входы установки в нуль на фиг.1 и фиг.2 не показаны). На счетчик :, 811„.81л ЗаНОСятСя КадЫ, СООтВЕтСтоуещИЕ первой фазе работ (задач), по входам

2011...201n. На счетчики 821...82n заносятся коды, соответствующие второй фазе работ (задач), по входам 2021...20zл. На вычитающий счетчик 27 блока 7 заносится код, соот1833873 ветствующий числу (п+1), где и — количество задач в пакете (входы занесения кода на счетчик 27 на рисунке не показана). Устройство обеспечивает упорядочивание всех задач в наборе следующим образом, Введены следующие обозначения;

Ai — время реализации i-ой задачи на ее первой фазе;

 — время реализации i-ой задачи на ее второй фазе, С выходов вычитэющих счетчиков . 811...82ri коды поступают на блок элементов

И 4(число элементов И 4 в блокв равно числу разрядности счетчиков 8), где одноименные разряды кодов первых и вторых фаз задач проверяются на одновременное наличие в них единиц.,С выхода блока И4 на вход элемента ИЛИ 5 поступают сигналы, соответствующие.единице (если все одноименные разряды имеют "1") и нулю,(ecnp хотя бы один из них имеет "0"), При наличии на входе элемента ИЛИ 5 хотя бы одной единицы с инверсного выхода элемента. ИЛИ 5 снимается нулевой сигнал, который поступает на вход элемента

И2, запрещая подачу через .соответствующие. элементы И 3 тактовых импульсов на вычитающие счетчики 811„,8z>, Одновременно с выхода элемента ИЛИ 5 ..единичный сигнал поступает на входы блока элемента

И 6, куда также поступают сигналы с выхода блока элементов, И 4, С выхода блока элементов И6 сигналы поступают на входы сброса в нуль разрядов вычитающих счетчиков.811 ...82n (как первых, так и вторых фаз), обнуляя одноименные разряды счетчиков, содержащие единицы, С выхода счетчиков 8 коды фаз поступают на блок элементов И 4, с выхода которого теперь снимается нулевой сигнал (так как в одноименных разрядах кодов обеих фаз теперь нет всех единиц), который поступает на вход элемента ИЛИ 5 и с его инверсного выхода единичный сигнал поступает на вход элемента И 2, разрешая при наличии пускового единичного сигнала на входе 15 элемента И 2 поступление тактовых импульсов на входы вычитающих счетчиков 8«...82ï через,соответствующие элементы И 3.

Если Ai < В (i = 1, n), то в первую очередь обнуляется счетчик 8я и нэ выходе элемента

ИЛИ 911 появляется нулевой сигнал, При изменении уровня сигнала на выходе элемента ИЛИ 91 с единичного уровня на нулевой на выходе дифференцирующей цепочки 12п появляется импульсный сигнал, который устанавливает триггер 111 в единичное состояние.

50 устройства. Одновременно с инверсного выхода элемента ИЛИ 211 нулевой сигнал поступает на выход 35 блока 7, а затем поступает на вход элемент И2, после чего прекращается и рохождение тактовых импульсов с выхода генератора через элементы И 2. Кроме того единичный сигнал с выхода элемента 211 через элемент ИЛИ 26 поступает нэ выход 18 устройства, свидетельствуя о наличии на выходе 17 кода но мера задачи в. очереди, После выдачи позиционного кода номера задачи по выходу 172 и номера этой задачи в очереди по выходу 17i операционная система ЭВМ выдает сигнал приема задачи к обработке на вход 19, который далее поступает на первые входы .элементов И 10ii...102 . Так как на второй вход элемента И 10ii (i = 1, n) поступает единичный сигнал с -го выхода узла

14>, на выходе элемента И 10н устанавливается единичный сигнал, который поступает на второй вход триггера 11 н, после чего

Так как счетчик 8и находится в нулевом состоянии, то на выходе элемента ИЛИ 9ц устанавливается нулевой сигнал, который закрывает элементы И Зп и 32 . и запрещает прохождение нэ счетчики 811 и 821 счетных импульсов с генератора 1. При обнулении счетчика 8ц значение (Bi - Ai) на счетчике 8z ранее не изменяется, так как на одном из вйходов элементов И 31 и 32 будет посто"0 янно находиться нулевой сигнал с выхода элемента ИЛИ 91ь С выхода триггера 11и единичный сигнал поступает на вход узла

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

15 выходов. Структура блока 14> (142) полностью совпадает со структурой аналогичного блока в прототипе.

С выхода блока 141 снимаетея позиционный код номера очередной выполняемой задачи, которую необходимо ставить в нача-,. ло очереди. В случае одновременного обну.-. ления нескольких счетчиков 81)и появление единичных сигналов на нескольких входах узла 141 позиционный код выдается пооче-, редно, начиная с наименьшего номера. Кроме того с i-ro выхода блока 141 единичный сигнал поступает нэ i-й вход элемента ИЛИ

211 блока 7 (фиг.2) и с его прямого выходэ — на вход счетчика 30, с выхода которого сни30 мается двоичный код номера задачи в оче.реди; который через открытые элементы И

31 (открытый сигналом с выхода формирова- теля импульсов 22: ) и через блок элементов

ИЛИ 32 поступает на выход 17> устройства.

35 А позиционный код данной задачи в наборе выдается через открытый блок элементов И

24 и блок элементов ИЛИ 25 на выход 17

1833873

15

25

35

55 триггер 11> устанавливается в нулевое состояние.

Следовательно, на I-ом выходе блока

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

811...82n.

С выхода счетчика 30 снимается код номера задачи только при выполнении условия Ai < Вь и тогда задачи в очереди располагаются в порядке возрастания А, начиная с первой.

Если Ai = Вь то счетчики 81 и Sz обнуляются одновременно и триггеры 11ц и 11zi устанавливаются в единичное состояние;

Нулевой сигнал с выхода элемента ИЛИ

9ii поступает на первый вход элемента И 13ь на втором входе которого будет единичный сигнал с выхода триггера 11гь В результате на выходе элемента И 13 будет нулевой сигнал, следовательно, единичные сигналы на блок 14z приоритета не поступают. С выхода триггера 111 единичный сигнал поступает на i-й вход блока 14ь Далее процесс постановки i-ой задачи в очередь повторяется аналогичным образом), как при условии А < B;.

Если А > Вь то счетчик 82) обнуляется раньше, чем счетчик 8н,. В этом случае триггер 11z устанавливается в единичное состоя ние.

Единичный сигнал с выхода триггера

11zi поступает на первый вход элемента

И13ь на второй вход которого поступает единичный сигнал с выхода элемента ИЛИ

91ь Так как счетчик 81|еще необнулился, то нэ выходе элемента И 13 устанавливается единичный сигнал, который поступает íà i-й вход блока 14z. С выхода блока 14z снимается код номера задачи, которую необходимо ставить в конец очереди, Кроме того, с выхода блока 14z поступает на входы элемента ИЛИ 21z, с инверсного выхода которого нулевой сигнал поступает по выходу 35 блока 7 на вход элемента И 2 и запрещает подачу тактовых импульсов с генератора 1.

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

22z и единичный сигнал через элемент ИЛИ

23з поступает на вход счетчика 28, который осуществляет подсчет числа распределенных задач. Одновременно с прямого выхода элемента ИЛИ 21z единичный сигнал поступает на вход вычитэющего счетчика 27, с выходов которого снимается номер задачи в очереди, Содержимое счетчика 27 уменьшается всегда на единицу и в порядке поступления сигналов с прямого выхода элемента ИЛИ 21z задачи устанавливаются с конца очереди в порядке увеличения Вь начиная с п-го, Если Ai = Ai или Bi = Bj (i,/= 1, n, ) = 1), то на входе блока 141 (или 14z соответственно) поступают одновременно несколько сигналов, на инверсном выходе элемента ИЛИ

211(или 212) появляется нулевой сигнал. который поступает на вход элемента И 2, и запрещает подачу тактовых импульсов с выхода генератора 1 на счетчикй 8 до тех пор, пока все задачи одинаковой приоритетности не установятся в очередь. Если на всех выходах блоков 141 или 14z будут нулевые сигнаЛы, то на входы элемента И 2 с инверсных выходов элементов ИЛИ 211 (или 212) поступают единичные сигналы, и тактовые импульсы с выхода генератора 1 начинают поступать на счетчики 8.

Устройство заканчивает работу, когда счетчик 2 с коэффициентом пересчета и переполняется и сигнал переполнения устанавливает триггер 2 в единичное состояние.

В результате на выходе 16 появляется сигнал окончания работы устройства, а с инверсного выхода триггера 2 поступает нулевой сигнал на вход элемента И 2, запрещая поступление на входы счетчиков 8 тактовых импульсов. На этом устройство заканчивает свою работу, Формирователи 221 и 222 имеют разное время задержки и выдачи импульса на своих выходах, что исключает одновременную выдачу информации на выходе 172 состояний счетчиков 27 и 30.

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

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

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

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

25 элемента ИЛИ и второму входу первого бло30 элемента И и четвертого элемента ИЛИ, вы35

5

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

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

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

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

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

1833873

77z 1В f7i 16 фу,э/.1833873

Составитель В. Батищев

Техред М.Моргентал Корректор М. Керецман

Редактор

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

Заказ 2687 Тираж Подписное

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

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