Устройство для обслуживания групповых приоритетных запросов

 

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

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

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

РЕСПУБЛИК

Ф (si)s G 06 F 9/46

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4878780/24 (22) 24.09.90 (46) 07.08.92. Бал, N . 29 (72) А.X.Ãàíèòóëèí, В,Г,Попов и И,А.Шилов (56) Аа горское свидетельство СССР

М 1091163, кл. G 06 F 9/46; 1984.

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

М 1297047, кл. G 06 F 9/46, 1987, (54) УСТРОЙСТВО ДЛЯ ОБСЛУЖИВАНИЯ

ГРУППОВЫХ ПРИОРИТЕТНЫХ 3АПРОС08 (57) Изобретение относится к вычислительной технике и может быть использовано в многоканальных системах с приоритетным

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

Известно устройство приоритета; содержащее два регистра, два группы элементов И и группу элементов ИЛИ.

Недостаток данного устройства — низкое быстродействие.

Наиболее близким по технической сущности к изобретению является устройство для обслуживания групповых приоритетных запросов, содержащее два регистра, две группы элементов И, rpynny блоков элементов И, первую группу элементов ИЛИ, причем группа запросных входов устройства соединена с группой информационных входов первого регистра, прямые выходы первого регистра соединены с первыми входами соответствующих элементов И первой группы выходы элементов И первой группы соединены с информационными входами второго регистра, управляющие. Ж „1753473 А1 обслуживанием. Цель изобретения — "повышение быстродействия устройства. Новым в устройстве является использование группы элементов ИЛИ-НЕ, а в каждом узле выбора запросов, кроме первОго; третьего группы элементов И. Устройство обеспечивает для каждого свободного канала выбор приоритетного запроса с учетом выделенных запросов предыдущим свободным каналам.

При этом время выбора запроса зависит ot распределения сигналов готовности процессоров, Минимальное время затрачивается, когда от первого до назначаемого процессора отсутствуют сигналы их готовности. 1 ил, С: входы блоков элементов И группы соедйнены с опросным входом устройства, выходы блоков элементов И группы являются группой выходов устройства, тактовый вход устройства соединен с вторыми входами элементов И первой группы.

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

55 держит две группы элементов И и шифратор, первый уэлен выбора запросов содержит группу элементов И и шифратор, выходы элементов И первой группы узлов выбора запросов группы, начиная с второго, и выходы элементов И группы первого узла выбора запросов группы подключены к входам шифратора своего узла, прямой выход I-ro разряда второго регистра соединен с первым входом i-ro элемента (где 1 = 1, .„ и, и число запросов) группы первого узла выбора запросов группы и с первым входом

1-го элемента И первой группы узлов выбора запросов группы, начиная с второго, инверсный выход i-ro разряда второго регистра соединен с соответствующим. входом (i+ 1)-го и всех последующих элементов И группы первого узла выбора запросов группы и с соответствующим инверсным входом I-го элемента И первой группы всех узлов выбора запросов группы, начиная с второго, первый выход регистра готовности каналов соединен с соответствующими входами элементов И группы первого узла выбора запросов группы, выходы регистра соединены с соответствующими прямыми входами элементов И второй группы одноименного узла выбора запросов, выход 1-го элемента И первой группы каждого узла выбора запросов группы, начиная с второго, соединен с соответствующим прямым входом 1-го элемента И второй группы и с соответствующими инверсными входами (I + 1)-го и всех последующих элементов И второй группы своего узла выбора запросов группы, выход каждого элемента И второй группы узлов выбора запросов группы, начиная с второго, соединен с соответствующими инверсными входами одноименных элементов И первой группы всех последующих узлов выбора запросов группы, выходы шифратора i-ro узла выбора запросов группы соединены с группой входов i-го блока элементов И группы, выходы 1-ro элемента И группы первого узла выбора запросов группы и I-x элементов И второй группы узлов выбора запросов группы, начиная с второго соединены с входами

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

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

50 начиная с второго, последовательно соеди-. ненных двух групп элементов И.

Общее время цикла работы устройства определяется временем переходных процессов в последовательно соединенных узлах выбора запросов.

Если число каналов равно К, то это время можно оценить по выражению

Т =о +тг(К-1), где t< = т è8 — время задержки элемента И первого узла 5 выбора запроса; сг= 7w7+ Tv8 — суммарное время задержки элементами И каждого из остальных узлов выбора запроса.

TI гриб+ 2 Ти(К-1) =(2К- 1) 7ц . (1)

Из выражения (1) видно, что время работы устройства определяется только структурой узлов выбора запроса и не зависит от размещения сигналов готовности процессоров в регистре.

Пусть вычислительная система содержит К каналов, сигналы готовности от которых поступают в соответствующие разряды регистра. При этом возможны случаи, когда в 1-м разряде данного регистра (I = 2, 3, „„К) зафиксирован сигнал готовности от 1-го процессора, а во всех предыдущих разрядах с

1-го по (i - 1)-й сигналов готовности от соответствующих процессоров нет, В данном случае код номера заявки появляется на выходе шифратора i-го узла выбора запроса после последовательного прохождения через узлы с первого по (i - 1)-й сигналов разрешения передачи информации с выходов регистра заявок.

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

Приведем оценку непроизводительных затрат времени.

Пусть К=4, При ненулевом кодах в регистре число различных комбинаций размещения сигналов готовности составляет No = 2 - 1 при

К = 4, 1 ч0 = 15, Среди этих комбинаций возможны следующие ситуации, При наличии сигнала готовности от второго процессора:

0101

О 1 1 О.

0111 от третьего процессора:

1753473

Тогда

30 с — )- — 2 (3)

$1 (2k 1)2 . И т.е. при непрерывном потоке заявок и сигналов готовности процессоров, когда име- Р ется равновероятная воэможность 35 с появления сигналов готовности процессо- A ров в указанных комбинациях, быстродействие устройства снижается в два раза;

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

Укаэанная цель достигается тем, что в устройство для обслуживания групповых . приоритетных запросов, содержащее груп- 45 м пу блоков элементов И, выходы которых яв- гР ляются информационными выходами устройства, и группу узлов выбора запро сов, каждый из которых, кроме первого, включает в себя две группы элементов И и 50 Р шифратор, первый узел выбора запросов со- гр держит группу элементов И и шифратор, э причем выходы элементов И первой группы узлов выбора запросов, начиная с второго, гр и выходы элементов И группы первогоузла 5« выбора запросов группы подключены к вхо- то дам шифратора своего узла, прямой i-й вход 3 группы запросных входов устройства (i = 1, 2, ..., n, п — число запросов) соединен с riep- з

001 0

001 1 и от четвертого процессора:

000 1

Отсюда общее число таких комбинаций 5 составляет

N1-2 К1-1.

Если регистр заявок содержит и разря= ув, то количество ненулевых комбинаций сигналов запросов составляет 10

У =2"-1

Тогда число комбинаций сигналов заявок и готовности процессоров в рассматриваемой ситуации определяется по выражению .: 15

$1 = М . N1= (2" - 1X2 1-1), общее количество комбинаций этих сигналов равно

$о = (2" - 1)(2 - 1).

Если и= К то 20

S0 =(2 - 1)(2 - 1) = (2К вЂ” 1j;

$1 = (2 - 1)(2 .- 1) (2)

Из выражения (2) видно, что при боль- 25 ших значениях величины К можно принять р" (2

$1= вым входом i-го элемента И группы первого узла выбора запросов и с прямыми входами

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

ыбора запросов группы, выходы шифратоа каждого узла выбора запросов группы оединены с группой информационных вхоов одноименного блока элементов И групы, управляющие входы которых одключены к опросному входу устройства, ведены группа элементов ИЛИ-НЕ, а в кажый узел выбора запросов группы, начиная второго, третья группа элементов И, прием j-й вход группы входов готовности проессоров устройства (j - 1, 2, ..., К - 1, К— исло процессоров) соединен с j-ми входаи j-ro и последующих элементов ИЛИ-НЕ уппы и с первыми управляющими входаи элементов И третьей группы(1+1)-ro узла

ыбора запросов группы, выход j-го элемена ИЛИ-НЕ группы подключен к вторым упавляющим входам элементов И третьей уппы и инверсным управляющим входам лементов И второй группы (j + 1)-го узла

ыбора запросов. группы, прямой 1-й вход уппы запросных входов устройства соедиен с первыми прямыми входами 1-х элеменв И третьих групп каждого узла выбора апросов группы, начиная с второго, weepный у -й вход (g - 1, 2, ..., n - 1) группы апросных входов устройства подключен к

1753473

15

20 сигналов. 50

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

ИЛИ-НЕ 7 устанавливается нулевые сигналы, которыми закрыты элементы И 6 во всех узлах 1, начийая с второго, и открыты Ао

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

На чертеже показана структурная схема устройства, Устройство содержит узлы 1 выбора запросов, первый из которых включает в себя группу элементов И 2 и шифратор 3, а последующие — первую группу элементов И 4, вторую группу элементов И 5 и третью группу элементов И 6, группу элементов ИЛИНЕ 7, группу блоков 8 элементов И, группу запросных входов 9 устройства, группу входов 10 готовности процессоров устройства, опросный вход 11 устройства и группу информационных выходов 12 устройства, Устройство работает следующим образом.

Пусть в системе каждый из абонентов в соответствии с установленным для него приоритетом закреплен за соответствующим входом 9 так, что наивысшим приоритетом обладает абонент с меньшим номером входа 9 устройства. Сигналы готовности от процессоров подаются на соответствующие входы 10.

В определенные моменты времени операционной системой цикле работы устройства производится подача потенциальных сигналов запросов в парафазном коде на входы 9 и потенциальных сигналов готовности процессоров по входам 10. Одновременно по входу 11 подается потенциальный сигнал опроса.

Для каждого из свободных каналов (процессоров), от которых поступили сигналы готовности по входам 10, последовательно соответствующим узлом 1 выбора запросов производится выбор приоритетного запроса из совокупности зафиксированных сигналов запросов на входах 9, когда в цикле опроса перед крайней слева единицей кода на входах 10 нет нулевых инверсным управляющим входам элементы . И5.

Для первой единицы выбирается абонент из совокупности сигналов на входах 9, а для последующих возбужденных входов

10 — с учетом выделенных запросов для

ЗО

45 предыдущих свободных каналов. Для этого в каждом узле 1, начиная с второго, выделение абонента обеспечивается элементами И

5. Исходной информацией для этих элементов являются выходные сигналы элементов

И 4, посредством которых исключаются из анализа выбранные ранее сигналы предыдущими узлами 1, Так как единичный сигнал на выходах элементов И 5 формируется только в одном из них при наличии единичных сигналов на прямых входах элементов

И 5, то номер возбужденного элемента И 5 однозначно соответствует номеру абонента, от которого на соответствующем входе 9 зафиксирован запрос, Унитарный код (имеющий единицу на одной из его позиций) подается на шифратор 3, преобразующий его в двоичный код номера абонента, поступающий на входы соответствующего блока

8 элементов И.

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

Работа устройства, когда на нескольких подряд следующих входах 10 отсутствуют единичные сигналы, начиная с первого входа, заключается в следующем, Пусть на входах 10 зафиксирован нулевой код от(K 1)-го процессоров, на последнем имеется единичный сигнал готовности

00 ... 01, а на входах 9 имеется запрос от второго абонента. . При этом на выходах всех элементов

ИЛИ-НЕ 7 формируются единичные сигналы, которыми закрыты по инверсным управляющим входам элементы И 5 во всех узлах

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

И 2 и 6 в узлах 1 с первого по (К - 1)-й, В К-м узле 1 открыты единичным сигналом с входа

10к элементы И 6. Эти элементы, как в других узлах 1 (элементы И 2 в первом узле, элементы И 6 в остальных), подключены к парафазным входам 9 по приоритетной схеме.

- В рассматриваемом примере в узле 1к нулевым сигналом с прямого входа 9 закрыт элемейт И 61, а единичным сигналом с инверсного входа 91 открыты элементы с И с 6z по 6п. Так как на прямом входе R имеется единичный сигнал, а на инверсном входе 92 — нулевой, элемент И 62 открыт, а остальные элементы И6 в узле 1к закрыты.

При этом на выходах элементов И6 формируется унитарный код 010...0, поступающий на входы шифратора 3. На выходе шифрато1753473 ра 3 устанавливается двоичный код номера второго абонента, поступающий через блок

82 элементов И на выходы 122 устройства.

Таким образом, на выходах 12 единичные сигналы появляются последовательно 5 па мере завершения переходных процессов, начиная:с выходов 12i, если имеются сигналы готовности на входах 101 и т.д., либо начиная с выходов 12;, когда на входах

";01,..., 10j-i имеются нулевые сигналы, а на 10 входе 10i — единичный.

Проведем сравнительную оценку прототипа и предложенного устройства по быстродействию.

Выигрыш в быстродействии можно on- 15 ределить по соотношению

Т (4) где Т1 с учетом выражения (1) и общего числа . комбинаций запросов и сигналов готовно- 20 сти процессора в соответствии с выражением (2) равно

Т1 = (2к - 1)2(2К - 1) т., (5) где Тр — среднее время работы предложен- .25 ного устройства, Исходя из анализа количества комбинаций и времени преобразования кодов для каждой из них, время Т2 определяется по выражению 30

Тг = (((2 - 1)(2 К вЂ” 1)) + ((2 - 1) +,5, 2

j =1 . 2!)) ги (б) 35 где первое слагаемое отражает количества последовательно включенных схем И (И 2, И

4, И 5), участвующих в преобразованиях кода запросов, когда имеется единичный сигнал готовности от первого процессора. При 40 этом общее число комбинаций сигналов готовности составляет 2 - 1, Второе слагаемое соответствует общему числу последовательно включенных схем

И (И 6, И4, И 5), участвующих в преобразо- 45 вании кода запросов, когда имеются нулевые сигналы от первого, первого и второго и т.д. сигналов готовности..

Подставляя выражения (6), (5) в (4) получим 50

W (7)

К2 — 1 +, !2

1=1

Из выражения (7) видно, что выигрыш в

55 быстродействии обеспечивается при любом числе каналов. Так, при числе каналов К = 4 быстродействие предложенного устройства . в 1,38 выше быстродействия прототипа.

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

Устройство для обслуживания групповых приоритетных запросов, содержащее группу блоков элементов И, выходы которых являются информационными выходами устройства, и группу узлов выбора запросов, каждый из которых, кроме первого, содержит две группы элементов И и шифратор, первый узел выбора запросов содержит группу элементов И и шифратор, причем выходы элементов И первой группы узлов выбора запросов группы, начиная с второго, и выходы элементов И группы первогр узла выбора запросов группы подключены к соответствующим входам шифратора своего узла, прямой l-й вход группы запросных входов устройства (i = 1, 2, ..., и, n — число запросов) соединен с первым входом I-го элемента И группы первого узла выбора запросов и с прямыми входами I-x элементов

И второй группы узлов выбора запроса rpynllbl, начиная с второго, инверсный 1-Й вход группы запросных входов устройства соединен с (i + 1, г-ми входами (i + 1)-го и всех последующих элементов И группы первого узла выбора запросов группы, выход I-го элемента И группы которого соединен с первыми инверсными входами I-x элементов И второй группы всех узлов выбора запросов группы, начиная с второго, первый вход группы входов готовности процессоров устройства подключен к управляющим входам элементов И группы первого узла выбора. запросов rpysinv, второй и последующие входы группы входов готовности процессоров устройства соединены с прямыми управляющими входами элементов И первой группы одноименных узлов выбора запросов группы, выход i-ro элемента И второй группы каждого узла выбора запросов группы, начиная с второго, подключен к прямому входу 1-ro элемента И первой группы и к соответствующим инверсным входам (i + 1)-го и всех последующих элементов И первой группы своего узла выбора запросов, группы, выход каждого элемента И первой группы узлов выбора запросов группы, начиная с второго, подключен к соответствующим инверсным входам одноименных элементов И второй группы всех последующих узлов выбора запросов группы, выходы шифратора каждого узла выбора запросов группы соединены с группой информационных входов одноименного блока элементов

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

Составитель А,Ганитултн

Техред M.Mîðråíòàë Корректор Н. Ревская

Редактор И.Шмакова

Заказ 2769 .. - - Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 на третья группа элементов И, причем )-й вход группы входов готовности процессоров устройства (J =- 1, 2,;., К - 1, К вЂ” число процессоров) соединен с J-ми входами j-ro и всех последующих элементов ИЛИ-HE 5 группы и с первыми управляющими входами элементов И третьей группы (J + 1)-го узла выбора запросов группы, выход J-го элемента ИЛИ-HE группы подключен к вторым управляющим входам элементов И 10 третьей группы и к инверсным управляющим входам элементов И первой группы (J

+ 1)-го узла выбора запросов группы, прямой I-й вход группы запросных входов устройства соединен с первыми прямыми 15 входами i-x элементов И третьих групп каждого узла выбора запросов группы, начиная с второго, инверсный у-й вход(у- =

1, 2, ..., п - 1) группы запросных входов устройства подключен к(-+ 1)-м прямым входом (y+ 1)-х и последующих элементов

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