Устройство для распределения приоритетных заявок по процессорам

 

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

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

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

РЕСПУБЛИН (g!! 4 6 06 F 9/46

ОПИСАНИЕ ИЭОБРЕТ

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

IlO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГННТ СССР (2!) 4332071/24-24 (22) ?3.!1.87 (46) 23.07.89. Бюл. М 27 (72) А.Х. Ганитулин, В,Г, Попов и С.А. Шибаев (53) 681.325(088.8) (56) Авторское свидетельство СССР

G F 1985.

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

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

ПРИОРИТЕТНЫХ ЗАЯВОК ПО ПРОЦЕССОРАМ (57) Изобретение относится к вычисли,тельной технике и может быть использовано в многопроцессорных ЭВМ с приоритетным обслуживанием потока заявок, Цель изобретения — повышение быстродействия устройства за счет одновременного распределения группы заявок приоритетного канала свободным процессорам. Устройство содержит блоки элементов ИЛИ группы, одновибИзобретение относится к вычислительной технике и может быть использовано в многопроцессорных ЭВМ с приоритетным обслуживанием потока заявок.

Цель изобретения — повышение быстродействия устройства за счет одновременного распределения группы заявок приоритетного канала свободным процессором, На фиг, 1 показана структурная схема устройства для распределения приоритетных заявок по процессорам;

„„Я0„„1495795 А 1

2 ратор, группу дешифраторов, две группы блоков элементов И, группу регистров номера абонента, группу регистров номера канала, три группы элементов

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

Щ цессорам. При этом каждому процессору на обслуживание передаются двоичные коды номера канала и номера абонента, а соответствующие разряды регистра за- С просов и регистра готовности процес-, соров устанавливаются в нулевое состояние. 1 з.п ° ф-лы, 3 ил. М1

Я!

Сл

Ц на фиг, 2 — структурная схема канала; Ж на 4иг 3 — структурная схема блока CA распределения заявок.

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

l3 задержки, регистр !4 готовности

)495795 процессоров, элемент ИЛИ 15, элемент

И 16, элемент ИЛИ 17, элемент И 18, одновибратор 19, элемент 20 задержки, элемент И 21, группу элементов ИЛИ

22, группу элементов ИЛИ 23, дешифраторов 24, группы блоков элементов

И 25, группу блоков элементов ИЛИ 26, группу элементов ИЛИ 27, группу блоков элементов И 28, группу блоков 10 элементов И 29, группу регистров 30 номера абонента, группу регистров 31 номера канала, выход 32 готовности устройства, входы 33 кодов приоритета каналов устройства, входы 34 кодов 15 приоритета запросов устройства, запросные входы 35 устройства, вход 36 запуска устройства, входы 37 готовности процессоров устройства, выходы 38 номера абонента устройства, вы- 20 ходы 39 номера канала устройства, сигнальный выход 40 устройства, выходы 41, входы 42 каналов 1, выходы

43 канала 1, входы 44 каналов 1, выходы 45 каналов 1, выходы 46 каналов 1, входы 47 и 48 каналов 1, информационные входы 49 блока 2, вход

50 запуска блока 2, информационные входы 5! блока 2.

Канал 1 (фиг.2) содержит регистр

52 запросов, буферный регистр 53, группу регистров 54 приоритета, элемент ИЛИ 55, группу элементов И 56, дешифраторов 57, группу элементов

ИЛИ. 58, группу шифраторов 59, группу элементов И 60, группу блоков элементов И 61, группу элементов И 62.

Блок 2 распределения заявок (фиг.3) содержит группу элементов,.

И 63, регистры 64 и 65, каналы 66, 40 включающие в себя первые группы 67 и 68 элементов И.

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

Исходное состояние устройства характеризуется тем, что триггер 12„ регистры 30, 31 и 54 во всех каналах

1 и регистры 64 и 65 блока 2 установлены в состояние "0 (не показано).

В регистры 4 блока 3 по входам 33 принимаются приоритетные коды каналов, причем эти коды представляют собой коды чисел натурального ряда от 1 до п (п — число каналов), Кана55 лу с наивысшим приоритетом устанавливается двоичный код чисел 1, а каналу с самым низким приоритетом — двоичный код числа и, По входам 34 соответствующих каналов в регистры 54 подаются приоритетные коды запросов, которые также представляют собой двоичные коды чисел натурального ряда от 1 до S (S число абонентов канала), При этом абоненту с наивысшим приоритетом устанавливается двоичный код числа 1, а абоненту с самым низким приоритетом — двоичный код числа S.

По входам 35 соответствующих каналов поступают запросы от абонентов канала, которые фиксируются в одноименных разрядах регистра 52.

1Io входам 37 в соответствующих разрядах регистра 22 фиксируются сигналы готовности процессоров, При наличии запросов в регистрах

52 каналов 1, так как триггер 12 находится в нулевом состоянии, то единичным сигналом с нулевого выхода, поступающим по входу 42 в каналы 1 и разрешающим прием информации в регистры 53, производится отслеживание состояния потока заявок в регистрах 52. При этом на входах элементов

ИЛИ 55 соответствующих каналов 1 формируются единичные сигналы, поступающие по выходам 43 и управляющие входы одноименных блоков элементов И 5 блока 3 выбора канала, Блоком 3 производится выбор приоритетного канала на основе анализа приоритетных кодов путем их дешифрации посредством дешифраторов б, сигналы с одноименных выходов которых объединяются соответствующими элементами ИЛИ 7. При наличии запросов в нескольких каналах 1 на выходах элементов ИЛИ 7 формируется позиционный код, число единиц в котором соответствует количеству возбужденных каналов 1. С помощью элементов 8 запрета из данного кода выделяется крайняя левая единица, номер позиции которой соответствует значению приоритетного кода. Унитарный код (содержащий единицу только в одной позиции ) поступает на шифратор 9. Формирующий дво-. ичный код необходим для определения приоритетного канала, Выбор приоритетного канала обеспечивается сравнекием данного кода с приоритетными кодами каналов схемами 10 сравнения, на выходах которых формируется унитарный код. Номер позиции (номер схемы 10 сравнения) единицы этого кода

1495795 указывает номер приоритетного канала.

Выходные сигналы схем IO сравнения используются для коммутации выходных сигналов приоритетного канала с блоком 2 распределения заявок и формирования двоичного кода номера канала шифратором ll, который передается в дальнейшем процессорам, Выходные сигналы шифратора 17, кроме того, объединяются элементом

ИЛИ 15, открывающим по третьим входам элементы И 18 и 21.

При наличии сигналов готовности в регистре 14 на выходе элемента 15

ИЛИ 17 формируется единичный сигнал, открывающий элементы И 18 и 21 по

\ вторым входам.

Так как элемент И 21 открыт по всем трем входам, на его выходе ус- 20 танавливается единичный сигнал, поступающий в качестве сигнала готов ности устройства на выходе 32. По этому сигналу из 3ВМ по входу 36 по;дается сигнал опроса, которым устанавливается в единичное состояние

;триггер 12 через открытый элемент

И 18, и через некоторое время, определяемое элементом 20 задержки, запускается одновибратор 19. ЗЬПосле установки триггера 12 в единичное состояние на его нулевом выходе формируется нулевой сигнал, которым блокируется прием поступающих заявок в буферные регистры 53 каналов 1, Тем самым в цикле опроса обеспечивается выбор приоритетного канала и распределение заявок этого канала по свободным процессорам.

Время задержки элементом 20 за- 40 держки определяется временем перехоцных процессов в элементах блока выбора приоритетного канала: элементов

И 5, дешифраторах 6, элементах ИЛИ 7, элементах 8 запрета, шифраторе 9, схемах 10 сравнения, шифраторе ll и элементе ИЛИ 15 и выбирается так, чтобы к моменту запуска одновибратора 19 на первом элементе И 16 установился единичный сигнал с выхода эле- gp мента ИЛИ 15 в случае приема в регистры 53 запросов в момент поступления импульса опроса.

Пусть имеются пять каналов (n=5) по семь (S=7} запросов в каждом кана- 55 ле и три процессора (К=З}. При этом каналам установлены следующие коды приоритетов: «;-5, а у4, а =2, а 4 — — 1, а =3, а абонентам пятого канала приоритетные коды: Ь,=З, Ь =1, Ь =2, Ь4 4, Ь =6, Ъь 5, Ь

При данных условиях производится

1 выбор пятого канала, которому установлен наивысший приоритетный код, и на выходе шифратора ll формируется двоичный код номера пятого канала, Кроме того, единичным сигналом с выхода пятой схемы IO сравнения в канале I открываются по управляюХ щим входам элементы И 60-62 °

В данном канале при наличии запросов от первого и седьмого абонентов производится расстановка по приоритету заявок, На выходах элементов И 61 устанавливается следующая последовательность двоичных приоритетных кодов: 000, 000, 001, 000, 000, 000, 002, а на выходе элементов И 62: 0 0, 1,0,0,0,1, Это означает, что приоритетным кодом является двоичный код числа 3, принадлежащий первому абоненту.

Позиционный код с выходов элементов И 62 через элементы ИЛИ 27 поступает по входам 49 на первые входы

;лементов И 63 блока 2.

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

И 16 по входу 50 блока 2 на вторые входы элементов И 63; и синхронизирующий вход регистра 65, в регистре

64 фиксируется позиционный код

0010001, а в регистре 65 — позиционный код сигналов от первого и третьего свободных процессоров: 101, В этом блоке производится последовательное назначение очередной по приоритету заявки свободному процессору.

B первом канале 66, на выходах элементов И 68, включенных по приоритетной схеме с выходами регистра 64, формируется позиционный код: 0010000, поступающий на соответствующие выходы 41„, Так как сигнал готовности от второго процессора равен нулю, то седьмой абонент первого канала начинается третьему процессору узлом 66З, при этом на выходах 413 устанавливается позиционный код: 0000001.

В дальнейшем с помощью блоков элементов И 25 для первого и третьего процессоров производится передача в регистры 30, и 30 двоичных кодов, 1495795 принимаемых на обслуживание третьего и седьмого абонентов соответственно, Это выполняется следующим образом, Та как на выходе 41 присутствуют единичные сигналы, то открыты элементы И 25, через которые двоичный код Oll поступает на входы элементов

И 281 и на входы дешифратора 24.

Аналогично двоичный код седьмого абонента 1)1 через открытые элементы

И 25 „ поступает на входы элементов

И 28 и на входы дешифратора 24>, С помощью дешифраторов 24 и элементов ИЛИ 23 формируется поэицион- 15 ный код для управлений гашением разрядов регистра 52, сигналы из которых выделены для обслуживания процессором. В данном случае в дешифраторе ,24 возбуждается первый выход, а в 20

1 .дешифраторе 24 > — седьмой, Поэтому на выходах элементов ИЛИ 23, обьединяющих одноименные выходные сигналы дешифраторов 24, устанавливается позиционный код: 1000001. Единичные 25 сигналы означают, что на обслуживание принимаются первый и седьмой абоненты.

По импульсу одновибратора 19, задержанному элементом 13 задержки .. 30 двоичного кода, номера абонента и номера канала принимаются в регистры 30 и 3), Время задержки элементом 13 задержки определяется переходными процессами в блоке 2, элементах И 25, 35 дешифраторах 24 и элементах HJIH 23.

Для рассматриваемого примера в регистрах 30 номера абонента устанавливаются двоичные коды: 30,,-101, °

30 -000, 30 -ll!, а в регистрах 31 номера канала: 3) -101, 3)g-000, 3)з-) 01, Одновременно через элементы И 60

И 60, в канале ) устанавливаются в

Н 1»

0 первый и седьмой разряды регист- 45 ра 52» а через элементы ИЛИ 22, и

ИЛИ 22з — первый и третий разряды регистра 14, Кроме того, импульс одновибратора 19 с выхода элемента 13 задержки 50 устанавливает в "0" триггер 12 и по" ступает на выход 40, Сигнал с выхода

40 означает разрешение считывания информации из регистрон 30 и 31 с выходов 38 и 39 соответственно, После установки триггера 12 в нулевое состояние н каналах 1 производится передача сигналов нопросон из регистров 52 в буферные регистры 53, При наличии запросов и сигналов готонности процессов в регистре 14 на выходе элемента И 21 формируется еди ничный сигнал, поступающий на выход

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

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

1. Устройство для распределения приоритетных заявок по процессорам, содержащее одновибратор, группу дешифраторов, две группы блоков элементов И, группу регистров номера абонента, группу регистров номера канала, первую группу элементов ИЛИ, регистр готовности процессоров, три элемента ИЛИ, два элемента .И, первый элемент задержки, триггер, и (п - число заявок) каналов, блок выбора канала, две группы из К блоков элементов И, К групп из S блоков элементов И (где К=! ° 2,..., количестно процессоров в системе, S=l 2,... ° число абонентов канала), причем каждый канал содержит регистр запросов, входы которого являются запросными входами устройства, буферный регистр, группу регистров приоритета, входы которых являются входами кодов приоритета запросов устройства, первую группу блоков элементов И, группу дешифраторов, группу элементов ИЛИ, группу шифраторов, элемент ИЛИ и первую группу элементов И, выходы которых подключены к входам сброса одноименных разрядов регистра запросов, Выходы котброго соединены с входами соответствующих разрядов буферного регистра, синхронизирующий вход буферного регистра каждого канала соединен с инверсным выходом триггера в каждом канале, выходы буферного регистра подключены к входам элемента

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

I0 иены с выходами соответствующих регистров приоритета группы данного канала, выходы каждого блока элементов И первой группы канала подключены к входам соответствующего дешифратора группы канала,"одноименные выходы дешифраторов группы канала соединены с входами соответствующего элемента

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

l элементов И блока выбора канала подключены к входам одноименного дешифратора группы блока выбора канала и к первым входам соответствующих схем сравнения группы одноименных выходов ЗО дешифраторов, группы блока выбора канала соединены с входами соответст. вующего элемента ИЛИ группы блока выбора канала, выход первого элемента ИЛИ группы блока выбора канала. подключен к первому входу первого шифратора блока выбора канала и к первым инверсным входам элементов запрета группы блока выбора канала, выход z-го элемента ИЛИ (z=2,3,...,n) 411 группы блока выбора канала соединен с прямым входом (z-1) -го и с инверсными входами с з-ro по (n-1) -й элементов запрета группы блока выбора канала, выход t-го элемента запрета 45 группы блока выбора канала (=1,2, ...,n-1) соединен с (t+1)-м входом первого шифратора блока выбора канала, выходы которого соединены с вторыми входами схем сравнения группы ц блока выбора канала, выходы которых подключены к входам второго шифратора и к входам первых элементов И пефвой группы одноименных каналов, выходы второго шифратора блока выбора канала подключены к входам первого элемента ИЛИ и к информационным входам всех К блоков элементов И первой группы, выходы которых соединены с входами соответствующих регистров номера канала группы, выходы которых являются выходами номера канала устройства, выходы всех К блоков элементов И второй группы подключены к входам одноименных регистров номера абонента группы, выходы которых являются выходами номера абонента устройства, вход запуска устройства сЬединен с первым входом первого элемента И и через первый элемент задержки с входом одновибратора, выход которого подключен к первому входу второго элемента И, единичные выходы регистра готовности каналов, единичные входы которого являются входами готовности процессоров устройства, подключены к входам второго элемента ИЛИ, выход которого соединен с вторым вхо-. дом первого и второго элементов И, третий вход последнего подключен к третьему входу первого элемента И и к выходу первого элемента ИЛИ, выход первого элемента И подключен к единичному входу триггера, о т л и— ч а ю щ е е с я тем, что, с целью

I повышения быстродействия за счет одновременного распределения группы заявок приоритетного канала свободным процессорам, в него введены второй элемент задержки, группа блоков элементов KIH, вторая и третья группы элементов ИЛИ, третий элемент И, блок распределения заявок, а в каждый канал введены вторая группа блоков элементов И и вторая группа элементов И, причем входы i-го элементов ИЛИ группы канала (i=i °,,п) подключены к соответствующим входам

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

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

495795

50

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

5 ключен к управляющим входам всех К блоков элементов И первой и второй групп, к нулевому входу триггера и к сигнальному выходу устройства, выход готовности которого соединен с выходом третьего элемента И, первый вход которого подключен к нулевому выходу триггера, второй вход третьего элемента И подключен к выходу второго элемента ИЛИ, третий вход третьего элемента И подключен к выходу первого элемента ИЛИ, единичные выходы регистра готовности процессоров соединены с первой группой информационных входов блока распределения заявок,10 вторая группа информационных входов которого подключена к выходам элементов ИЛИ второй группы, входы j --го элемента ИЛИ которой подключены к выходу j-К элементов второй группы 25 всех каналов, группы входов j -ro блока элементов ИЛИ группы подключены к выходам j Ê блоков элементов второй группы всех каналов, выходы i-го блока элементов ИЛИ группы соединены чц с информационными входами i-х блоков элементов И в каждой из К групп, выходы каждой группы выходов блока распределения заявок соединены с управляющими входами всех 8 блоков элементов И одноименной группы, выходы всех

$ блоков элементов И каждой из К групп объединены и соединены с входами одноименного дешифратора группы и с . входами одноименного блока элемен- 411 тов И второй группы, i-e выходы дешифратора группы соединены с входами, i-го элемента ИЛИ первой группы, выходы блоков элементов И второй группы соединены с входами элементов

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

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

1495795!

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

Редактор В. Бугренкова Техред А.Кравчук Корректор Не Король

Заказ 4267/46 Тираж 668 Подписное

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

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

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