Устройство для обслуживания групповых приоритетных запросов Советский патент 1992 года по МПК G06F9/46 

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

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

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

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

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

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

с

VI сл со

vj

GO

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

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

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

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

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

Если число каналов равно К, то это время можно оценить по выражению Ti ti+tz(K-1).

где ti Гиб - время задержки элемента И первого узла 5 выбора запроса;

t2 t wi+ TVt8 суммарное время задержки элементами И каждого из остальных узлов выбора запроса.

Ti Тиб+ 2 ги(К-1) (2К-1) Ти .(1)

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

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

в 1-м разряде данного регистра (i 2, 3К)

зафиксирован сигнал готовности от 1-го процессора, а во всех предыдущих разрядах с 1-го no (i - 1)-й сигналов готовности от соответствующих процессоров нет.

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

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

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

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

Пусть К 4,

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

Среди этих комбинаций возможны следующие ситуации.

При наличии сигнала готовности от второго процессора: 0100

0101

0110

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

001 О

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

000 1

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

Ni 2K 1-1.

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

М 2п-1.

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

Si M.Ni (2n-lX2k 1-1), общее количество комбинаций этих сигналов равно

S0 (2n-1)(2k-1). Если п К. то

50 (2k-1K2K-1) (2K-1)2;

51 (2К - 1)( - 1) :r2k-1)((2k-2)(2)

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

Sl-(2k-n2 61 - 2

Тогда

50 (2k-1)2 9

51(2k-1)2

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

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

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

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

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

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

15 элементов И группы первого узла выбора запросов группы, второй и последующие входы группы входов готовности процессоров устройства соединены с прямыми управляющими входами элементов И второй

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

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

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

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

запросных входов устройства подключен к

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

На чертеже показана структурная схема устройства.

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

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

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

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

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

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

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

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

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

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

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

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

5 свободные каналы.

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

0 Пусть на входах 10 зафиксирован нулевой код от (К - 1)-го процессоров, на последнем имеется единичный сигнал готовности 00 ... 01, а на входах 9 имеется запрос от второго абонента.

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

0 узлах по вторым управляющим входам элементы И 6. Одновременно нулевыми сигна- ламис входом 10i, ...10к-1 закрыты элементы И 2 и 6 в узлах 1 с первого по (К - 1}-й. В К-м узле 1 открыты единичным сигналом с входа

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

0 В рассматриваемом примере в узле 1к нулевым сигналом с прямого входа 9i закрыт элемент И 6i, а единичным сигналом с инверсного входа 9i открыты элементы с И с 62 по 6п. Так как на прямом входе 9а име5 ется единичный сигнал, а на инверсном входе 92 - нулевой, элемент И 62 открыт, а остальные элементы Ие в узле 1к закрыты. При этом на выходах элементов Ие формируется унитарный код 010...О, поступающий на входы шифратора 3. На выходе шифратоpa 3 устанавливается двоичный код номера второго абонента, поступающий через блок 8а элементов И на выходы 12а устройства.

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

10i10и имеются нулевые сигналы, а на

входе 10| - единичный.

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

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

w

Т2

(4)

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

Ti(2K-1)2(2K-1) ти.

(5)

где Т2 - среднее время работы предложенного устройства.

Исходя из анализа количества комбинаций и времени преобразования кодов для каждой из них, время Та определяется по выражению

Т2 {(2к-1Х2К-1) + {(2

К-1

К -2

-1)+ gi 2

. ги(6)

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

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

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

w, (2|с-1)(2К-1).

К Т

К -2

1 + 2 i2

i 1

()

I +1

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

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

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

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

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

5 последующих элементов И группы первого узла выбора запросов группы, выход 1-го элемента И группы которого соединен с первыми инверсными входами 1-х элементов И второй группы всех узлов выбора эа0 просов группы, начиная с второго, первый вход группы входов готовности процессоров устройства подключен к управляющим входам элементов И группы первого узла выбора запросов группы, второй и последу5 ющие входы группы входов готовности процессоров устройства соединены с прямыми управляющими входами элементов И первой группы одноименных узлов выбора запросов группы, выход i-ro элемента И

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

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

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

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

o

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

1, 2 п - 1) группы запросных входов

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

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