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

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

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

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

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

Блок 2 сравнения (фиг.2) содержит элементы ИЛИ-НЕ 11| , - Jim (Д ш - разрядность сравниваемьп : кодов), узлы 12,,...,12 анализа разрядов, которые состоят из узлов 13,..., 13,, 13„ ,... , порязрядного пе- peHocai, включающих в свой состав элементы И14 и ИЛИ15, элемент НЕ 16, элемент И 17, выходы 18, и 18 , групу входов 19,,,,. ., 19, , 1 9,,„ . .., 19,

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

В исходном состоянии на регистры

1 2 lx 1 ai 1И заносятся коды, пропорциональные сумме времени ввода и решения задачи и ре

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

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

11 1 ГП

подается код числа с регистра 1, , а на входы 19,, ,..., код числа с регистра 1 ,, . С помощью узла 12 анализируются старшие разряды кодов. Если старшие разряды обоих кодов равны нулю, то на выходе элемента ИЛИ-НЕ 11 появляется высокий потенциал, который через элемент ИЛИ 15 поступает на первые входы элемента И 14, Обеспечивая прохождение кодов на следующий узел 12 анализа разрядов, который работает аналогичным

15

, 5

, 20

0 п.

35

282126 2

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

40

45

а 50 . 55элемента ИЛИ-НЕ 11 появляется низкий потенциал. Высокий потенциал с входов 19,,, через элементы ИЛИ 15 узлов 13 и 13,;j поступает на первые входы элементов И. 14, разрешая кодам проходить на следующий узел 1 2 rj анализа разрядов.

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

Второй код не поступает на узел 12 анализа разрядов, так как на входы элемента ИЛИ 15 узла 13,„, поступают низкие потенциалы. Если код числа, подаваемого на входы 19ы ( J 1,...,т), больше числа, подаваемого на входы 19,./ , то высокий потен циал появляется на выходе 18, , если же первое число меньше второго, то высокий потенциал появляется на выходе 18. При равенстве кодов высокие потенциалы появляются на выходах элементов И 14 узлов 13, и- 13 . С выхода 18 этот сигнал подается на элемент НЕ 16, на выходе которого формируется низкий потенциал, которьш подается на первый вход элемента И 17. На выходе 184j формируется низкий потенциал.

Каждый блок элементов И 3,,,..., 3,1 , 3, ,...3, содержит (2т+1) элемент И. С прямых выходов регистра 1 ,; коды подаются на первые входы 1 ,.,,, т-го элемента И i-ro блока элементов ИЗ,-. С прямых выходов регистра коды подаются на первые входы m+l,...2т-го элемента И блока элементов ИЗ,,. С инверсных выходов регистра 1,,- коды подаются на первые входы m-J-1 ,. , . ,2m-го элемента И блока элементов И 3 ,, а с инверсных выходов, регистра 1,,- на первые входы 1,...,т-го элемента И блока элементов И З,,, . С установочного входа 7 устройства низкий потенциал подаетсхем

2,, 2, 2,, 2gсравнения. С п ходом импульса запуска на вход 9 о крываются блоки элементов И 3, 3

iS

13 - ai 27

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

вход (2т+1)-го элемента И блоков эле- 5 блоков элементов И 3, мента И 3,. . , , . На второй вход блока элементов И 3,- подается сигнал с выхода 18 блока 2 сравнения, а на второй вход блока элементов .И сигнал с выхода 18 блока 2{ сравне- О ния.

При подаче на вход 9 импульса запуск устройства, который также поступает и на третий вход блоков элементов И , . . . , 3 IN . 3,j, , . . . , 3j3,|g ,

открываются те из блоков элементов И 3,,,... , 3,jj , на которые подается

3yg. С выходов

12

ЛЗ 16

на первые входы блоков элементов ИЛИ 4-5, А,, AS, 4 поступают коды 33(8,, (8) 23(8), 35сй), а с выходов блоков и 3j,, 3j, 3,,,, вторые

;входы блоков элементов ИЛИ 4,, 4, 4,, 4g поступают коды 151), 152(д)

.140(8), 130{s).,. С выходов блоков элементов ИЛИ 4 15 перечисленные коды записываются в регистры 5.

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

высокий потенциал с выхода 18 блоков 2 сравнения, и те из блоков элементов И 3,ib..., Ззм , на которые по- 20 ность заданий, представленных в дается высокий потенциал с выхода табл.2.

На обслуживание задания выбира18 блоков 2 сравнения.

Прямые коды с регистров 1 группы, нулевой код с входа 7 устройства через открытые блоки элементов 25 ИЗ,, ,...,И 3, поступают на первые входы блока элементов ИЛИ 4.

Инверсные коды с регистров 1 группы, единичный код с входа 8 поступают через открытые блоки элементов И 3j,И 3 2,1, на вторые входы блоков элементов ИЛИ 4, а с выхода блоков элементов ИЛИ 4 поступают на входы регистров 5.

ются по минимальному коду на выходах 10 регистра 5.

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

Устройство для распределения зад 30 НИИ, содержащее первую и вторую гру пы из N (N - число заданий) т-разря ных регистров, группу блоков сравне ния, причем инверсный выход i-ro ре гистра первой группы (,2,. .. ,ГТ) 35 соединен с первым входом i-ro блока сравнения группы, второй вход которого соединен с инверсным выходом i-ro регистра второй группы, отличающееся тем, что, с

Устройство для распределения зад 30 НИИ, содержащее первую и вторую гр пы из N (N - число заданий) т-разр ных регистров, группу блоков сравн ния, причем инверсный выход i-ro р гистра первой группы (,2,. .. ,ГТ) 35 соединен с первым входом i-ro блок сравнения группы, второй вход кото рого соединен с инверсным выходом i-ro регистра второй группы, отличающееся тем, что, с

С входа 9 устройства импульс запуска поступает также на вход элемента задержки и на тактовый вход регистров 5. По заднему фронту импульса осуществляется перепись кодов 40 целью повышения быстродействия, в с выходов блоков элементов ИЛИ 4 на него введены первая и вторая груп- регйстры 5 группы. С выхода элемента 6 задержки импульс запуска поступает на вход установки в нуль регист- ..,

ров 1, сбрасывая их. Устройство гото-45 прямые выходы i-ro регистра первой во к приему на регистры 1 очередного группы подключены к первому входу

с первого по т-й элементов и i-ro блока элементов И первой группы.

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

пакета заданий.

Пусть информация о пакете решаепрямые выходы 1-го регистра, второй

мых задач задана табл. 1, где t - 50 группы подсоединены к первому вхосумма времен ввода и решения зада- ния, tj, - сумма времен решения и вывода результатов. В исходном состоянии времена записаны на регист,цу с (т+1)-го по 2П1-Й элементов И, i-ro -блока элементов И первой группы, инверсные выходы i-ro регистра первой группы подключены к первому

pax 1,; , а времена - на регист- 55 «ходу с (т+1)-го по 2т-й элементов

pax 1j . Состояние схем 2 сравнения следующее: высокий потенциал появляется на выходе 18, схем 2. 2з, 2f сравнения и на выходе 18j

-3 s

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

схем

2,, 2, 2,, 2gсравнения. С приходом импульса запуска на вход 9 открываются блоки элементов И 3, 3,

iS

13 - ai 27

блоков элементов И 3,

3yg. С выходов

12

ЛЗ 16

на первые входы блоков элементов ИЛИ 4-5, А,, AS, 4 поступают коды 33(8,, (8) 23(8), 35сй), а с выходов блоков и 3j,, 3j, 3,,,, вторые

;входы блоков элементов ИЛИ 4,, 4, 4,, 4g поступают коды 151), 152(д),

.140(8), 130{s).,. С выходов блоков элементов ИЛИ 4 15 перечисленные коды записываются в регистры 5.

В результате устройство для рас- пределения заданий преобразует исходный пакет заданий в последователь0 ность заданий, представленных в табл.2.

ются по минимальному коду на выходах 10 регистра 5.

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

Устройство для распределения зада- НИИ, содержащее первую и вторую группы из N (N - число заданий) т-разряд- ных регистров, группу блоков сравнения, причем инверсный выход i-ro регистра первой группы (,2,. .. ,ГТ) соединен с первым входом i-ro блока сравнения группы, второй вход которого соединен с инверсным выходом i-ro регистра второй группы, отличающееся тем, что, с

целью повышения быстродействия, в него введены первая и вторая груп- ..,

целью повышения быстродействия, в него введены первая и вторая груп- ..,

прямые выходы i-ro регистра первой группы подключены к первому входу

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

прямые выходы 1-го регистра, второй

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

«ходу с (т+1)-го по 2т-й элементов

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

512

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

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

26 6

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

элементов И второй группы.

I

Таблица 1

Таблица 2

o-fHp--

I-I

pal.f

гт

т

II I

/

L.

L

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

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

Техред В.Кадар Корректор М. Максимишинец

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

фиг.г