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

 

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

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

РЕСПУБЛИН (504 G 06 F 9 4

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

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ специалйзированных процессорах . ,Целью изобретения является повыше ние быстродействия. В устройстве задания разбиваются на две группы.

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

Внутри заданий второй rpynrm — по максимуму времени решения и вывода.

Устройство состоит из трех групп регистров, двух групп блоков элементов

Ф

И, группы блоков элементов ИЛИ, группы блоков сравнения и элемента задержки. 2 ил. С:

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3890618/24 — 24 (22) 26.04.85 (46) 07.01.87. Бюл. Ф 1 (72) А.Я. Матов, С.Е. Карловский, А.M. Макарчук, В.Н. Дроник и И.М. Якуб (53) 681.325(088.8) (56) Авторское свидетельство СССР

9 959083, кл. G 06 F 9/46, 1983.

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

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

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

„,SU„„1282126 А 1

128212

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

Цель изобретения — повышение быстродействия устройства эа счет одновременного распределения всех заданий за один шаг работы устройства.

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

Устройство (фиг. I) содержит группы регистров 1 ... 1 1„ 1 l р, группу блоков 2,,...,2,, сравнения, блоки элементов И 3„,..., 3,„, 3,,..., 3 щ группы, блоки элементов ИЛИ 4 i,...,4 группы, регистр» 5,,5 группы элемент 6 задержки, входы 7-9, группу выходов

10,...,10„.

Блок 2 сравнения (фиг. 2) содержит элементы ИЛИ-НЕ 111,..., 11 (где

m — разрядность сравниваемых кодов), узлы 12,,...,12 „ анализа разрядов, которые состоят из узлов 13и,..., 13,, 13,,...,13 порязрядного пе30 реноса, включающих в свой состав элементы И14 и ИЛИ15, элемент НЕ 16, элемент И 17, выходы 18, и 18, группу входов 19„,..., 19,, 19 „..., 19 „.

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

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

Блок 2 сравнения работает следующим образом. На входы 19„,...,19„ подается код числа с регистра 1„, а

- на входы 19,,...,19 — код числа с регистра 1 ;. С помощью узла 12, Sg анализируются старшие разряды кодов.

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

ИЛИ-НЕ 11, появляется высокий потенциал, который через элемент ИЛИ 15 поступает на первые входы элемента

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

6 2 образом. Если старшие разряды обоих кодов равны единице, то на выходе элемента ИЛИ-НЕ 11 появляется низкий потенциал. Высокий потенциал с входов 19„, 19д„через элементы ИЛИ

15 узлов 13< и 13,< поступает на первые входы элементов И 14, разрешая кодам проходить на следуняций узел 12 анализа разрядов.

Если старший разряд первого числа равен единице, а второго — нулю, то на выходе элемента ИЛИ-НЕ 111 появляется низкий потенциал, который подается на первые входы элементов

ИЛИ 15 узлов 13„ и 13, . На второй вход элемента ИЛИ 15 узла 13,„ подается высокий потенциал. На выходе этого элемента появляется высокий погенциал, который подается на первые входы элементов И 14, разрешая прохождение остальных разрядов первого кода для анализа на узел 12 анализа разрядов.

Второй код не поступает на узел

12 анализа разрядов, так как на входы элемента ИЛИ 15 узла 13, поступают низкие потенциалы. Если код числа, подаваемого на входы 191 (= 1,...,m), больше числа, подаваемого на входы 19, то высокий потен циал появляется на выходе 18,, если же первое число меньше второго, то высокий потенциал появляется на выходе 18 . При равенстве кодов высокие потенциалы появляются на выходах элементов И 14 узлов 13„,, и

13 . С выхода 181 этот сигнал подается на элемент НЕ 16, на выходе которого формируется низкий потенциал, который подается на первый вход элемента И 17. На выходе 18 формируется низкий потенциал.

Каждый блок элементов И 3

Зщ, 3 „,...3 „, содержит (2ш+1) элемент И. С прямых выходов регистра I „ коды подаются на первые входы

1...,, m-го элемента И i-го блока элементов И 3,; . С прямых выходов регистра 1 ; коды подаются на первые входы m+1 2ш-ro элемента И блока элементов И 3, . С инверсных выходов регистра 1„ коды подаются на первые входы m+1,...,2m-го элемента И блока элементов И 3,, а с инверсных выходов. регистра 1 „. — на первые входы

1,...,m-го элемента И блока элементов И 3„ . С установочного входа 7 устройства низкий потенциал подает3 1282126 4

Ф ся на первый вход (2т+1)-го элемен- . схем 2,, 2,, 2,, 2а сравнения. С прита И блоков элементов И 3 3,„, ходом импульса запуска на вход 9 ота с установочного входа 8 устройства крываются блоки элементов И 3 3

1 2.»» 3» высокий потенциал подается на первый 3, 3, 3, 3, 3 3д С выходов

>5» rg » а»» zs» 27 И вход (2m+1)-ro элемента И блоков эле- 5 блоков элементов И 3,, 3,, 3,, 3, мента И 3,,...,3 ö. На второй вход на первые входы блоков элементов блока элементов И 3 „. подается сигнал ИЛИ 4, 4, 4, 4 поступают коды с выхода 18, блока 2;. сравнения, а на второй вход блока элементов И 3 - блоков И 3 „ 3, 3„, З а на вторые сигнал с выхода 18 блока 2> сравне- 10 входы блоков элементов ИЛИ 4,, 4, ния. 4,, 4g поступают коды 151 1» 152< >»

При подаче на. вход 9 импульса за- 140(g>, 130(g>. пуск устройства, который также поступает и на третий вход блоков эле- С выходов блоков элементов ИЛИ 4 ментов И Э, »...» 3,„, 3,,..., 3 15 перечисленные коды записываются в открываются те из блоков элементов Регистры 5

И 311,.... 3,„, на которые подается В результате устройство для Расвысокий потенциал с выхода 18 бло- пределения заданий преобразует ис1 ков 2 сравнения, и те из блоков эле- ходный пакет заданий в последовательментов И 3 1,...» 3 „, на кОторые по- 20 ность заданий, представленных в дается высокий потенциал с выхода табл.2.

18 блоков 2 сравнения.

На обслуживание задания выбираПрямые коды с регистров 1 группы, ютсЯ по минимальномУ кодУ на выхонулевой код с входа 7 устройства че- дах 10 регистра 5. рез открытые блоки элементов 25

И 3„,...,И 3, поступают на первые входы блока элементов ИЛИ 4.

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

Инверсные коды с регистров 1 группы, единичный код с входа 8 поступа- устройство для распределения задают через открытые блоки элементов ний, содержащее первую и вторую групИ 3,...,И 3 на вторые входы блоДР » 2М пы из Я (N — число заданий) ш-разрядков :элементов ИЛИ 4, а с выхода ных регистров, группу блоков сравнеблоков элементов ИЛИ 4 поступают на ния, причем инверсный выход i-го ре" гистра первой груп ы (i=1 2,...,N) соединен с первым входом i-го блока

С входа 9 устройства имп

Р тва импульс sa- сравнения группы, второй вход котопуска поступает также на в е на вход эле- рого соединен с инверсным выходом мента задержки и на тактовый актовыи вход - i-го регистра второй группы, о т— регистров 5, По s He му фронту им- л и ч а ю щ е е с я тем, что, с пульса осуществляется пе е перепись кодов 40 целью повышения быстродействия, в с выходов. блоков элементов Р Ж 4 нтов р щ 4 на него введены первая и вторая груп регистры 5 группы. С выхо а

ыхода элемен- пы блоков элементов И, группа блота 6 задержки импульс sàï ска

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

Р ры 1 очередного группы подключены к первому входу пакета заданий. с первого по m-й элементов и х-го блока элементов И первой группы, П сть инфо ма у формация о пакете решае- прямые выходы i-ro регистра. второй мых задач з ана табл. 1 ад ада а табл. 1, где t ° — gp группы подсоединены к первому вхосумма времен ввода и решения зада» цу с (m+1)-го по 2ш-й элементов И, ния t — с умма времен решения и z-ro блока элементов И первой групвывода результатов. В исходном состо- . пы, инверсные выходы i-ro регистра янин в емена э р м,,; ;записаны на регист- первой группы подключены к первому рах 1„, а времена t — на регист- gg входу с (ш+1)-ro по 2m-й элементов рах 1; . Состояние схем 2„сравненйя И i-го блока элементов И второй группы, инверсные выходы >-ro регистра ляется на выходе 18 д 18, схем 2З, 2д, второй группы подсоединены к перво2> 2а сравнения и н ия и на выходе 18 му входу с первого по m-й элементов

1282126

Номер задания в пакете

Таблица 2

Номер задания в пакете (i) Код на регистре 5.

35 140 ° 130( (в) «8) 57 152 23

«8) (8) (8) 151,, 33

Номер приоритета задания

7 2

И i-го блока элементов И второй группы, первый выход >-го блока сравнения группы подключен к второму входу с первого по (2тп+1)-й элементов И i-ro блока элементов И первой 5 группы, второй выход i-.ãî блока сравнения группы соединен с вторым входом с первого по (2m+1)-й элементов

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

И первой группы, выход i-го блока элементов ИЛИ группы подключен к

15 информационному входу i-го регистра третьей группы, синхронизирующий вход регистров третьей группы соединен с входом запуска устройства, входом элемента задержки и третьим входом с первого по (2m+1)-й элементов И блоков элементов И первой и второй групп, выход элемента задержки соединен с входом установки в "0" регистров первой и второй групп, вход логического нуля устройства соединен с первым входом (2m+

+1)-ro элемента И блоков элементов И первой группы, вход логической еди.ницы устройства соединен с первым входом (2ш+1)-го элемента И блоков элементов И второй группы.

1 .Таблица 1

1282126

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

Техред B.Kàäàð Корректор М. Максимишинец

Редактор О. Бугир

Заказ 7268/48 Тираж 670 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4