МНОГОВЫХОДНОЙ АРБИТР ПРИОРИТЕТОВ Российский патент 2018 года по МПК H03M7/22 

Описание патента на изобретение RU2649943C1

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

Известен указатель старшей единицы (Угрюмов Е.П. Цифровая схемотехника: учеб. пособие для вузов. - СПб.: БХВ-Петербург, 2010. - 816 с., рис. 2.9 с. 87-90), содержащий группу элементов И и группу элементов запрета И с одним инверсным входом. В данном устройстве реализована цепочечная схема передачи сигнала опроса путем последовательного опроса, начиная со старшего разряда, и прекращения дальнейшего опроса при выявлении первой же единицы.

Известен указатель старшей единицы (Схемотехника ЭВМ. Сборник задач: учебное пособие. М.: НИЯУ МИФИ, 2012. - 240 с., рис. 53, с. 55-56), содержащий группу элементов ИЛИ, объединенных в цепочку, и группу элементов запрета И с одним инверсным входом.

Недостатком данных устройств является определение одного старшего приоритета только одного ранга.

Известны приоритетные шифраторы (Дж.Ф. Уэйкерли. Проектирование цифровых устройств. В 2-х томах. - М.: Постмаркет, 2002. - 1088 с., с. 440-445; Лехин С.Н. Схемотехника ЭВМ. - СПб.: БХВ-Петербург, 2010. - 672 с., с. 213-220; Угрюмов Е.П. Цифровая схемотехника. - СПб.: БХВ-Петербург, 2000. - 528 с., с. 50-53), в которых формируется двоичный код номера устройства старшего приоритета.

Известен двойной приоритетный шифратор (Дж.Ф. Уэйкерли. Проектирование цифровых устройств. В 2-х томах. - М.: Постмаркет, 2002. - 1088 с., рис. 6.6, с. 561-562), содержащий два блока приоритетного шифратора, дешифратор, группу элементов И-НЕ и группу элементов НЕ. Данное устройство определяет не только сигнал с наивысшим приоритетом, но также сигнал «со вторым по старшинству приоритетом».

Недостатком данных устройств является необходимость преобразования кода номера в соответствующий сигнал в виде унитарного кода «1 из N» обращения к устройству со старшим приоритетом, например, с помощью двоичного дешифратора.

Известно многоканальное устройство приоритета (RU №2415465 С2, МПК G06F 9/46, заявлен 01.06.2009, опубликован 27.03.2011, Бюл. №9), содержащее М каналов, каждый из которых содержит дешифратор, группу элементов И, первый и второй элементы ИЛИ, элемент И с прямым и инверсными входами, элемент задержки, группу кодовых входов приоритетов, вход запроса и выход ответа, причем в каждом канале вход запроса соединен с входом элемента задержки, выход которого соединен со вторыми входами всех элементов И группы элементов И своего канала, группа кодовых входов канала соединена с группой входов дешифратора канала, а выход первого элемента ИЛИ является выходом ответа канала.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятый за прототип многовыходной указатель старшей единицы (RU №2591017 С1, МПК H03M 7/22, G06F 13/37, G06F 9/46, заявлен 23.07.2015, опубликован 10.07.2016, Бюл. №19), содержащий группу из N внешних входов запроса Z1, Z2, …, ZN (высший приоритет имеет вход ZN), К каскадов (К - количество формируемых указателей старших единиц) и К групп внешних выходов U указателей старшей единицы, при этом каждый i-й каскад (i=1, 2, …, К) содержит группу из (N-i-1) элементов ИЛИ 1i1, 1i2, …, 1i(N-i-1) и группу из (N-i) элементов запрета И с одним инверсным входом 2i1, 2i2, …, 2i(N-i), а также группу из (N+1-i) входов запроса в i-й каскад Ai1, Ai2, …, Ai(N+1-i) и группу из (N+1-i) внешних выходов указателей старшей единицы i-го ранга Ui1, Ui2, …, Ui(N+1-i) (1-й ранг имеет высший приоритет), каждый из первых (К-1) каскадов, кроме последнего К-го каскада, содержит также группу из (N-i) элементов И 3i1, 3i2, …, 3i(N-i) и группу из (N-i) выходов запроса Si1, Si2, …, Si(N-i) в следующий (i+1)-й каскад, причем в каждом i-м каскаде (i=1, 2, …, К) первые (N-i) входов Ai1, Ai2, …, Ai(N-i) из группы входов запроса, кроме последнего входа запроса Ai(N-i+1), соединены со вторыми прямыми входами соответствующих элементов 2i1, 2i2, …, 2i(N-i) из группы элементов запрета И с одним инверсным входом, выходы всех элементов группы из (N-i-1) элементов ИЛИ 1i1, 1i2, …, 1i(N-i-1) соединены с первыми инверсными входами соответствующих первых (N-i-1) элементов 2i1, 2i2, …, 2i(N-i-1) группы из элементов запрета И с одним инверсным входом, кроме последнего элемента 2i(N-i), у которого первый инверсный вход соединен с последним (N-i+1) входом Ai(N-i+1) группы запроса i-го каскада и первым входом последнего элемента 1i(N-i-1) из группы элементов ИЛИ, кроме того, в каждом i-м каскаде (i=1, 2, …, К) вторые входы (N-i-1) элементов 1i1, 1i2, …, 1i(N-i-1) из группы элементов ИЛИ соединены с соответствующими (N-i-1) входами Ai2, Ai2, …, Ai(N-i) запроса в i-й канал, начиная со второго входа запроса, кроме последнего входа запроса Ai(N-i+1), а первые входы первых (N-i-2) элементов 1i1, 1i2, …, 1i(N-i-2) из группы элементов ИЛИ соединены с выходами соответствующих последующих элементов 1i2, 1i3, …, 1i(N-i-1) из группы элементов ИЛИ, кроме того, в каждом i-м каскаде (i=1, 2, …, К) выходы (N-i) элементов 2i1, 2i2, …, 2i(N-i) из группы элементов И являются первыми (N-i) внешними выходами из группы внешних выходов указателей старшей единицы i-го ранга Ui1, Ui2, …, Ui(N-i), а последний (N-i+1) внешний выход Ui(N+1-i) соединен с последним (N-i+1) входом запроса в i-й канал Ai(N-i+1).

Недостатком данного устройства является определение К указателей старших единиц в порядке старшинства приоритетов только одного ранга.

Техническим результатом изобретения является расширение функциональных возможностей в части формирования М групп указателей номера группы запросов в унитарном коде «1 из N» в порядке старшинства приоритетов и указателя ранга приоритета в группе.

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

N групп внешних входов запросов IZ1, IZ2, …, IZN, каждая из которых содержит по М разрядов ранга приоритета (высший приоритет имеет старшая группа IZN, а старший ранг приоритета имеет старший М-й разряд), М первых групп U1i, U2i, …, UNi, каждая из которых содержит по N внешних выходов указателей номера группы старшего приоритета (i=1, 2, …, М), вторую группу из М внешних выходов указателей ранга приоритета в группе OZ1, OZ2, …, OZM,

группу из М первых блоков указателей старшей единицы 11, 12, …, 1M, при этом каждый i-й первый блок (i=1, 2, …, М) содержит первую группу из (N-2) элементов ИЛИ 2i1, 2i2, …, 2i(N-2), первую группу из (N-1) элементов запрета И с одним инверсным входом 3i1, 3i2, …, 3i(N-1), N входов и N выходов,

группу из N вторых блоков указателей старшей единицы 41, 42, …, 4N, при этом каждый j-й второй блок (j=1, 2, …, N) содержит вторую группу из (М-1) элементов запрета И с одним инверсным входом 5j1, 5j2, …, 5j(M-1), вторую группу из (М-2) элементов ИЛИ 6j1, 6j2, …, 6j(M-2), 2(М-1) входов и (М-1) выходов,

третью группу из М элементов ИЛИ 71, 72, …, 7M,

причем в каждом i-м (i=1, 2, …, М) первом блоке указателя старшей единицы 1i первые (N-1) входов I1, I2, …, I(N-l), кроме последнего входа IN, соединены со вторыми прямыми входами соответствующих элементов 3i1, 3i2, …, 3i(N-1) из первой группы элементов запрета И с одним инверсным входом, выходы всех элементов первой группы из (N-2) элементов ИЛИ 2i1, 2i2, …, 2i(N-2) соединены с первыми инверсными входами соответствующих первых (N-2) элементов 3i1, 3i2, …, 3i(N-2) первой группы из элементов запрета И с одним инверсным входом, кроме последнего элемента 3i(N-1), у которого первый инверсный вход соединен с последним входом IN i-го первого блока указателя старшей единицы 1i и первым входом последнего (N-2)-го элемента 2i(N-2) из первой группы элементов ИЛИ,

кроме того, в каждом i-м (i=1, 2, …, М) первом блоке указателя старшей единицы 1i вторые входы (N-2) элементов 2i1, 2i2, …, 2i(N-2) из первой группы элементов ИЛИ соединены с соответствующими (N-2) входами I2, I3, …, I(N-1) i-го первого блока, начиная со второго входа 12, кроме последнего входа IN, а первые входы первых (N-3) элементов 2i1, 2i2, …, 2i(N-3) из первой группы элементов ИЛИ соединены с выходами соответствующих последующих элементов 2i2, 2i3, …, 2i(N-2) из первой группы элементов ИЛИ,

причем в каждом i-м (i=1, 2, …, М) первом блоке указателя старшей единицы 1i выходы (N-1) элементов 3i1, 3i2, …, 3i(N-1) из первой группы элементов И с одним инверсным входом являются первыми (N-1) выходами O1, O2, …, O(N-1) первого блока указателя старшей единицы 1i, в котором последний выход ON соединен с последним входом IN,

причем в каждом j-м (j=1, 2, …, N) втором блоке указателя старшей единицы 4j первые (М-1) входов I1, I2, …, I(М-1), начиная с первого входа I1 до (M-1)-го входа I(М-1), соединены со вторыми прямыми входами соответствующих элементов 5j1, 5j2, …, 5j(M-1) из второй группы элементов запрета И с одним инверсным входом, выходы всех элементов второй группы из (М-2) элементов ИЛИ 6j1, 6j2, …, 6j(M-2) соединены с первыми инверсными входами соответствующих первых (М-2) элементов 5j1, 5j2, …, 5j(M-2) второй группы из элементов запрета И с одним инверсным входом, кроме последнего элемента 5j(M-1), у которого первый инверсный вход соединен с последним входом I(2M-2) j-го второго блока указателя старшей единицы 4j и вторым входом последнего (М-2)-го элемента 6j(M-2) из второй группы элементов ИЛИ,

кроме того, в каждом j-м (j=1, 2, …, N) втором блоке указателя старшей единицы 4j первые входы (М-2) элементов 6j1, 6j2, …, 6j(M-2) из второй группы элементов ИЛИ соединены с соответствующими (М-2) входами IM, I(М+1), …, I(2M-3) j-го второго блока, начиная с входа IM, кроме последнего входа I(2М-2), а вторые входы первых (М-3) элементов 6j1, 6j2, …, 6j(M-3), кроме последнего (М-2)-го элемента 6j(M-2), из второй группы элементов ИЛИ соединены с выходами соответствующих последующих элементов 6j2, 6j3, …, 6j(M-2), начиная со второго элемента, из второй группы элементов ИЛИ,

причем в каждом j-м (j=1, 2, …, N) втором блоке указателя старшей единицы 4j выходы (М-1) элементов 5j1, 5j2, …, 5j(M-1) из второй группы элементов И с одним инверсным входом являются (М-1) выходами O1, O2, …, O(M-1) второго блока указателя старшей единицы 4j,

причем старший М-й разряд каждой j-й (j=1, 2, …, N) группы внешних входов запросов IZ1, IZ2, …, IZN соединен с соответствующим j-ым входом I1, I2, …, IN последнего М-го первого блока указателя старшей единицы 1M, а разряды с первого до (M-1)-го каждой j-й группы внешних входов запросов IZj соединены с соответствующими одноименными входами I1, I2, I(М-1), начиная с первого I1 до (М-1)-го входа, одноименных j-х вторых блоков указателей старшей единицы 4j,

входы с М-го до (2М-2)-го каждого j-го второго блока указателей старшей единицы 4j соединены с соответствующим j-ым выходом соответственно со второго до М-го первых блоков указателя старшей единицы 12, 13, …, 1M, а выходы с первого до (M-1)-го каждого j-го второго блока указателей старшей единицы 4j соединены с соответствующим j-ым входом соответственно с первого до (M-1)-го первых блоков указателя старшей единицы 11, 12, …, 1(M-1),

все N выходов каждого i-го (i=1, 2, …, М) первого блока указателя старшей единицы 1i также соединены с соответствующими входами одноименного i-го элемента ИЛИ третьей группы 71, 72, …, 7M, выходы которых являются соответственно выходами второй группы из М внешних выходов указателей ранга приоритета в группе OZ1, OZ2, …, OZM, а также N выходов каждого i-го (i=1, 2, …, М) первого блока указателя старшей единицы 1i являются соответственно N внешними выходами указателей номера группы старшего приоритета соответствующей i-й первой группы U1i, U2i, …, UNi.

На фиг. 1 представлена схема предлагаемого многовыходного арбитра приоритетов для N=5 групп внешних входов запросов IZ1, IZ2, …, IZ5 (IZN), каждая из которых содержит по М=4 разрядов ранга приоритета (высший приоритет имеет старшая группа IZ5, а старший ранг приоритета имеет старший М-й разряд).

На фиг. 1 введены следующие обозначения:

IZ1, IZ2, …, IZ5 (IZN) - N групп внешних входов запросов (N=5), каждая из которых

содержит по М разрядов (М=4) ранга приоритета (высший приоритет имеет старшая группа IZ5 (IZN), а старший ранг приоритета имеет старший М=4-й разряд),

U1i, U2i, …, U5i (UNi) - M первых групп, каждая из которых содержит по N внешних выходов указателей номера группы старшего приоритета (i=1, 2, …, М),

OZ1, OZ2, …, OZ4 (OZM) - вторая группа из М внешних выходов указателей ранга приоритета в группе (М=4),

11, 12, …, 1M - группа из М первых блоков указателей старшей единицы (М=4),

2i1, 2i2, …, 2i(N-2) - первая группа из (N-2) элементов ИЛИ каждого i-го (i=1, 2, …, М) первого блока указателя старшей единицы 11, 12, …, 1M, ((N-2)=3),

3i1,3i2, …, 3i(N-1) - первая группа из (N-1)=4 элементов запрета И с одним инверсным входом каждого i-го первого блока указателя старшей единицы 11, 12, …, 1M, ((N-1)=4).

41, 42, …, 4N - группа из N вторых блоков указателей старшей единицы (N=5),

5j1, 5j2, …, 5 - вторая группа из (М-1) элементов запрета И с одним инверсным входом каждого j-го (j=1, 2, …, N) второго блока указателя старшей единицы 41, 42, …, 4N, ((М-1)=3),

6j1, 6j2, …, 6j(M-2) - вторая группа из (М-2) элементов ИЛИ каждого j-го второго блока указателя старшей единицы 41, 42, …, 4N, ((М-2)=3),

71, 72, …, 7M - третья группа из М элементов ИЛИ (М=4).

Предлагаемый многовыходной арбитр приоритетов содержит N групп внешних входов запросов IZ1, IZ2, …, IZN, каждая из которых содержит по М разрядов ранга приоритета (высший приоритет имеет старшая группа IZN, а старший ранг приоритета имеет старший М-й разряд), М первых групп U1i, U2i, …, UNi, каждая из которых содержит по N внешних выходов указателей номера группы старшего приоритета (I=1, 2, …, М), вторую группу из М внешних выходов указателей ранга приоритета в группе OZ1, OZ2, …,OZM.

Кроме того, предлагаемый многовыходной арбитр приоритетов содержит группу из М первых блоков указателей старшей единицы 11, 12, …, 1M, группу из N вторых блоков указателей старшей единицы 41, 42, …, 4N, третью группу из М элементов ИЛИ 71, 72, …, 7M. При этом каждый i-й первый блок (i=1, 2, …, М) содержит первую группу из (N-2) элементов ИЛИ 2i1, 2i2, …, 2i(N-2), первую группу из (N-1) элементов запрета И с одним инверсным входом 3i1, 3i2, …, 3i(N-1), N входов и N выходов. При этом каждый j-й второй блок (j=1, 2, …, N) содержит вторую группу из (М-1) элементов запрета И с одним инверсным входом 5j1, 5j2, …, 5j(M-1), вторую группу из (М-2) элементов ИЛИ 6j1, 6j2, …, 6j(M-2), 2(М-1) входов и (М-1) выходов.

Причем в каждом i-м (i=1, 2, …, М) первом блоке указателя старшей единицы 1i первые (N-1) входов I1, I2, …, I(N-1), кроме последнего входа IN, соединены со вторыми прямыми входами соответствующих элементов 3i1, 3i2, …, 3i(N-1) из первой группы элементов запрета И с одним инверсным входом, выходы всех элементов первой группы из (N-2) элементов ИЛИ 2i1, 2i2, …, 2i(N-2) соединены с первыми инверсными входами соответствующих первых (N-2) элементов 3i1, 3i2, …, 3i(N-2) первой группы из элементов запрета И с одним инверсным входом, кроме последнего элемента 3i(N-1), у которого первый инверсный вход соединен с последним входом IN i-го первого блока указателя старшей единицы 1i и первым входом последнего (N-2)-го элемента 2i(N-2) из первой группы элементов ИЛИ.

Кроме того, в каждом i-м (i=1, 2, …, М) первом блоке указателя старшей единицы 1i вторые входы (N-2) элементов 2i1, 2i2, …, 2i(N-2) из первой группы элементов ИЛИ соединены с соответствующими (N-2) входами I2, I3, …, I(N-1) i-го первого блока, начиная со второго входа I2, кроме последнего входа IN, а первые входы первых (N-3) элементов 2i1, 2i2, …, 2i(N-3) из первой группы элементов ИЛИ соединены с выходами соответствующих последующих элементов 2i2, 2i3, …, 2i(N-2) из первой группы элементов ИЛИ. Причем в каждом i-м (i=1, 2, …, М) первом блоке указателя старшей единицы 1i выходы (N-1) элементов 3i1, 3i2, …, 3i(N-1) из первой группы элементов И с одним инверсным входом являются первыми (N-1) выходами O1, O2, …, O(N-1) первого блока указателя старшей единицы 1i, в котором последний выход ON соединен с последним входом IN.

Причем в каждом j-м (j=1, 2, …, N) втором блоке указателя старшей единицы 4j первые (М-1) входов I1, I2, …, I(М-1), начиная с первого входа I1 до (M-1)-го входа I(М-1), соединены со вторыми прямыми входами соответствующих элементов 5j1, 5j2, …, 5j(M-1) из второй группы элементов запрета И с одним инверсным входом, выходы всех элементов второй группы из (М-2) элементов ИЛИ 6j1, 6j2, …, 6j(M-2) соединены с первыми инверсными входами соответствующих первых (М-2) элементов 5j1, 5j2, …, 5j(M-2) второй группы из элементов запрета И с одним инверсным входом, кроме последнего элемента 5j(M-1), у которого первый инверсный вход соединен с последним входом I(2M-2) j-го второго блока указателя старшей единицы 4j и вторым входом последнего (М-2)-го элемента 6j(M-2) из второй группы элементов ИЛИ.

Кроме того, в каждом j-м (j=1, 2, …, N) втором блоке указателя старшей единицы 4j первые входы (М-2) элементов 6j1, 6j2, …, 6j(M-2) из второй группы элементов ИЛИ соединены с соответствующими (М-2) входами IM, I(М+1), …, I(2M-3) j-го второго блока, начиная с входа IM, кроме последнего входа I(2М-2), а вторые входы первых (М-3) элементов 6j1, 6j2, …, 6j(M-3), кроме последнего (М-2)-го элемента 6j(M-2), из второй группы элементов ИЛИ соединены с выходами соответствующих последующих элементов 6j2, 6j3, …, 6j(M-2), начиная со второго элемента, из второй группы элементов ИЛИ. Причем в каждом j-м (j=1, 2, …, N) втором блоке указателя старшей единицы 4j выходы (М-1) элементов 5j1, 5j2, …, 5j(M-1) из второй группы элементов И с одним инверсным входом являются (М-1) выходами O1, O2, …, O(М-1) второго блока указателя старшей единицы 4j.

Причем старший M-й разряд каждой j-й (j=1, 2, …, N) группы внешних входов запросов IZ1, IZ2, …, IZN соединен с соответствующим j-ым входом I1, I2, …, IN последнего M-го первого блока указателя старшей единицы 1M, а разряды с первого до (M-1)-го каждой j-й группы внешних входов запросов IZj соединены с соответствующими одноименными входами I1, I2, …, I(М-1), начиная с первого I1 до (М-1)-го входа, одноименных j-х вторых блоков указателей старшей единицы 4j.

Входы с М-го до (2М-2)-го каждого j-го второго блока указателей старшей единицы 4j соединены с соответствующим j-ым выходом соответственно со второго до М-го первых блоков указателя старшей единицы 12, 13, …, 1M, а выходы с первого до (M-1)-го каждого j-го второго блока указателей старшей единицы 4j соединены с соответствующим j-ым входом соответственно с первого до (M-1)-го первых блоков указателя старшей единицы 11, 12, …, 1(M-1).

Все N выходов каждого i-го (i=1, 2, …, M) первого блока указателя старшей единицы 1i также соединены с соответствующими входами одноименного i-го элемента ИЛИ третьей группы 71, 72, …, 7M, выходы которых являются соответственно выходами второй группы из М внешних выходов указателей ранга приоритета в группе OZ1, OZ2, …, OZM, а также N выходов каждого i-го (i=1, 2, …, М) первого блока указателя старшей единицы 1i являются соответственно N внешними выходами указателей номера группы старшего приоритета соответствующей i-й первой группы U1i, U2i, …, UNi.

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

Предлагаемый многовыходной арбитр приоритетов позволяет определить среди N групп внешних входов запросов IZ1, IZ2, …, IZN, каждая из которых содержит по М разрядов ранга приоритета (высший приоритет имеет старшая группа IZN, а старший ранг приоритета имеет старший M-й разряд), группы с наивысшим приоритетом по каждому рангу запроса, при этом в каждой j-й группе запросов IZj (j=1, 2, …, N) разрешается обслуживание только одного запроса приоритета в порядке старшинства и при отсутствии запросов данного ранга в группах с более высоким приоритетом. Количество М рангов приоритетов определяет количество групп выходных указателей номера групп старшего приоритета. На внешних выходах каждой i-й первой группы U1i, U2i, …, UNi указателя номера старшего приоритета (i=1, 2, …, М) формируется результат в виде унитарного кода «1 из N». Кроме того, на внешних выходах второй группы указателей ранга приоритета в группе OZ1, OZ2, …, OZM формируется единичный сигнал для каждого ранга приоритета при наличии соответствующих разрешенных сигналов запроса.

На N групп внешних входов запросов IZ1, IZ2, …, IZN устройства одновременно поступают сигналы запросов, содержащие по М разрядов. При этом каждому входу запроса и каждой группе присваиваются фиксированные приоритеты. В устройстве высший приоритет присвоен группе запросов со старшим номером IZN, а далее приоритет уменьшается от номера к номеру. Младший приоритет задан у первой группы запросов IZ1., каждая группа запросов содержит М разрядов ранга приоритета. При этом каждому разряду присваивается фиксированный ранг.В предлагаемом устройстве старший ранг приоритета присвоен разряду со старшим номером М, а далее приоритет уменьшается от номера к номеру. Младший ранг приоритета присвоен первому разряду запросов.

При поступлении разрешенных сигналов запросов в каждом первом блоке указателей старшей единицы 11, 12, …, 1M проводится поиск групп с наивысшим приоритетом в соответствии с j-ым рангом приоритета групп - поиск старшей (левой) единицы для j-й группы входных запросов. На внешних выходах U1i, U12i, …, UNi первых блоков указателей старшей единицы 11, 12, …, 1M формируется результат в виде унитарного кода «1 из N» - единичный сигнал будет установлен только на одном выходе соответствующем группе наивысшего приоритета. Количество выходов указателей старшей единицы U в каждом 1i-м блоке из первых блоков указателей равно количеству N внешних групп входов запросов IZN.

В группе из N вторых блоков указателей старшей единицы 41, 42, …, 4N осуществляется поиск старшего приоритета запроса, с учетом разрешенных запросов в соответствующей j-й группе запросов, в зависимости разрешения запроса от более старших приоритетов запроса от первых блоков указателей старшей единицы 11, 12, …, 1M.. Кроме того, сигналы с выходов каждой i-й первой группы U1i, U2i, …, UNi указателя номера старшего приоритета поступают на соответствующие входы i-х элементов ИЛИ третьей группы из М элементов ИЛИ 71, 72, …, 7M, на которых формируются единичные сигналы при наличии соответствующих разрешенных сигналов запроса i-го ранга.

Таким образом, на N выходах каждой i-й первой группы U1i, U2i, …, UNi указателей номера группы старшего приоритета (i=1, 2, …, М) формируется результат в виде унитарного кода «1 из N», а на внешних выходах второй группы указателей ранга приоритета в группе OZ1, OZ2, …, OZM формируется единичный сигнал для каждого ранга приоритета при наличии соответствующих разрешенных сигналов запроса i-го ранга.

Предлагаемый многовыходной арбитр приоритетов работает следующим образом.

На входы устройства одновременно поступают сигналы запросов по N группам внешних входов запросов IZ1, IZ2, …, IZN, каждая из которых содержит по М разрядов ранга приоритета (высший приоритет имеет старшая группа IZN, а старший ранг приоритета имеет старший М-й разряд).

При этом старшие М-е запросы каждой из N групп поступают на соответствующие входы М-го блока указателя старшей единицы 1 м. Данные сигналы М-х запросов, начиная с первой до (N-1)-й групп запросов, среди которых может быть несколько единичных сигналов, с входов М-го блока 1 м поступают на соответствующие вторые входы первой группы из (N-2) элементов ИЛИ 2M1, 2M2, …, 2M(N-2), объединенных в цепочку по первым входам - выход последующего элемента соединен с первым входом предыдущего элемента. На элементах ИЛИ 2M1, 2M2, …, 2M(N-2) входной код от групп запросов преобразуется в код «00…011..1», где левая (старшая) единица соответствует группе с наивысшим приоритетом. Далее эти сигналы поступают на соответствующие входы первой группы из (N-1) элементов И с одним инверсным входом 3M1, 3M2, …, 3M(N-1), на которых только на выходе одного элемента, на входы которого поданы значения «01», формируется единичное значение, указывающее на группу запроса с наивысшим приоритетом, а на остальных выходах будут установлены нулевые значения. Данные значения с выходов первой группы элементов запрета И с одним инверсным входом 3M1, 3M2, …, 3M(N-1) являются выходами М-го блока указателя старшей единицы 1M и передаются на (N-1) внешних выходов M-й группы U1M, U2M, …, U(N-1)M первых групп указателей номера группы старшего приоритета. Если M-й запрос наивысшего приоритета соответствует старшей группе запросов IZN, то единичное значение на N-й внешний выход М-й группы передается с входа М-го запроса старшей группы запросов IZN и устанавливается только на выходе старшего указателя группы UNM.

Далее сигналы с выходов М-го блока указателя старшей единицы 1M передаются на входы М-го элемента ИЛИ 7M из третьей группы и, при наличии единичного сигнала хотя бы на одном из его входов, на выходе М-го элемента ИЛИ 7M формируется единичное значение, которое передается на М-й внешний выход OZM второй группы указателей ранга приоритета в группе. Таким образом, на N выходах М-й группы внешних выходов указателей группы высшего приоритета U1M, U2M, …, UNM формируется результат в виде унитарного кода «1 из N» и единичный сигнал на М-м внешнем выходе OZM второй группы указателей ранга приоритета в группе при наличии соответствующих сигналов запроса М-го ранга.

Кроме того, одновременно сигналы с выходов М-го блока указателя старшей единицы 1M передаются на (2М-2)-е входы соответствующих вторых блоков указателей старшей единицы 41, 42, …, 4N, в которых данные входы соединены с соответствующими первыми инверсными входами (М-1)-х элементов И 5j(M-1) (j=1, 2, …, N) второй группы элементов И с одним инверсным входом и вторыми входами (М-2)-х элементов ИЛИ 6j(M-2) второй группы элементов ИЛИ. При этом на вторые прямые входы (М-1)-х элементов И 5j(M-1) второй группы элементов И с одним инверсным входом поступают сигналы с (М-1)-х входов соответствующих вторых блоков указателей старшей единицы 41, 42, …, 4N, в которых эти входы соединены с входами запросов (M-1)-го ранга соответствующих групп запросов IZ. При наличии нулевого сигнала на инверсном входе и единичного сигнала запроса (M-1)-го ранга на прямом входе соответствующих (М-1)-х элементов И 5j(M-1), на его выходе формируется единичное значение, которое передается на (М-1)-й выход соответствующих вторых блоков указателей старшей единицы 41, 42, …, 4N. Таким образом, на (М-1)-х выходах вторых блоков указателей старшей единицы 41, 42, …, 4N формируются (разрешаются) запросы (M-1)-го ранга соответствующих j-х групп, если в соответствующей j-й группе отсутствует разрешенный запрос М-го ранга с выходов М-го блока 1 м первых блоков указателей старшей единицы.

Далее сигналы с (М-1)-х выходов вторых блоков указателей старшей единицы 41, 42, …, 4N передаются на соответствующие входы (M-1)-го первого блока указателя старшей единицы 1(M-1), в котором, аналогично как в М-м первом блоке указателя старшей единицы 1M, на выходах формируется номер группы наивысшего приоритета с разрешенными входами запроса (M-1)-го ранга. При этом аналогично на N выходах (М-1)-й первой группы внешних выходов указателей группы высшего приоритета U1(М-1), U2(M-1), …, UN(M-1) формируется результат в виде унитарного кода «1 из N» и единичный сигнал на (М-1)-м внешнем выходе OZ(M-1) второй группы указателей ранга приоритета в группе при наличии соответствующих разрешенных сигналов запроса (М-1)-го ранга.

Одновременно сигналы с выходов (M-1)-го блока указателя старшей единицы 1(м-1) передаются на (2М-1)-е входы соответствующих вторых блоков указателей старшей единицы 41, 42, …, 4N, соединенные с соответствующими первыми входами (М-2)-х элементов ИЛИ 6j(M-2) второй группы элементов ИЛИ. При этом сигналы с выходов (М-2)-х элементов ИЛИ 6j(M-2) второй группы элементов ИЛИ соединены с соответствующими первыми инверсными входами (М-2)-х элементов И 5j(M-2) (j=1, 2, …, N) второй группы элементов И с одним инверсным входом и вторыми входами (М-3)-их элементов ИЛИ 6j(M-3) второй группы элементов ИЛИ. При этом на вторые прямые входы (М-2)-х элементов И 5j(M-2) второй группы элементов И с одним инверсным входом поступают сигналы с (М-2)-х входов соответствующих вторых блоков указателей старшей единицы 41, 42, …, 4N, в которых эти входы соединены с входами запросов (М-2)-го ранга соответствующих групп запросов. Поэтому, если в соответствующей j-й группе отсутствуют разрешенные запросы М-го или (M-1)-го рангов с выходов М-го блока 1 м или (M-1)-го блока 1(M-1) первых блоков указателей старшей единицы, на выходах соответствующих (М-2)-х элементов ИЛИ 6j(M-2) будут установлены нулевые значения, аналогично как для (М-1)-х выходов, а на (М-2)-х выходах вторых блоков указателей старшей единицы 41, 42, …, 4N, с выходов соответствующих элементов И с одним инверсным входом, формируются (разрешаются) запросы (М-2)-го ранга соответствующих j-х групп.

Далее аналогично соответствующие сигналы запросов с (М-2), (М-3), …, 1 выходов вторых блоков указателей старшей единицы 41, 42, …, 4N передаются на соответствующие входы (М-2), (М-3), …, 1 первых блоков указателя старшей единицы 1(M-2), 1(M-3), …, 1, в которых аналогично определяются номера групп наивысшего приоритета с соответствующим рангом запроса и на внешних выходов указателей группы наивысшего приоритета U формируется результат в виде унитарного кода «1 из N» и единичный сигнал на внешних выходах OZ второй группы указателей ранга приоритета в группе при наличии сигналов запроса соответствующих рангов.

Для предлагаемого устройства в таблицах 1 и 2 приведены формируемые значения внешних выходов первых групп U1i, U2i, …, U5i указателей номера группы старшего приоритета и второй группы внешних выходов OZ1, OZ2, …, OZ4 указателей ранга приоритета в группе на двух примерах при N=5 группах входных запросов IZ1, IZ2, …, IZ5 по М=4 разряда ранга приоритета, а также указаны обслуженные запросы в группах. В таблице 1 в первой строке запросу со старшим четвертым рангом приоритета OZ4=1 предоставлен приоритет 4-й группе, так как отсутствует запрос четвертого ранга в 5-й группе, и поэтому формируется сигнал U44=1. Но так как в каждой группе может быть обслуживаться только один запрос, то другие запросы в 4-й группе не обслуживаются. Поэтому второй по старшинству третий ранг приоритета OZ3=1 предоставлен запросу приоритета в 3-й группе и формируется сигнал U33=1, хотя запрос третьего ранга для 4-й группы имеет приоритет выше 3-й группы, но для 4-й группы уже разрешен запрос старшего ранга OZ4=1. Также, так как запросы одного ранга предоставляются только для одной группы, то для 2-й и 1-й групп запрещены запросы четвертого и третьего рангов. Запрос со вторым рангом приоритета OZ2=1 предоставлен 1-й группе и формируется сигнал U12=1, так как отсутствуют запросы второго ранга в 5-й и 2-й группах и запрещены запросы второго ранга в 4-й и 3-й группах. Запрос младшего первого ранга приоритета OZ1=1 предоставлен старшей пятой группе U51=1. В последней графе таблицы 1 приведены обслуженные запросы в группах, из которой видно, что для всех запросов 2-й группы право обслуживания не предоставлено.

Аналогично в таблице 2 приведены разрешенные запросы по группам для второго примера. Из таблицы 2 видно, что отсутствуют разрешенные запросы второго ранга OZ2=0, так как данные запросы поступают от 5-й и 3-й групп, но для которых уже разрешены запросы старших четвертого U34=1 и третьего U53=1 рангов приоритетов. Аналогично как для первого примера в таблице 1 отсутствуют разрешенные запросы для 4-й и 2-й групп.

Таким образом, в предлагаемом устройстве на внешних выходах М первых групп указателей U1i, U2i, …, UNi будут установлены сигналы соответствующие номеру группы старшего приоритета в унитарном коде «1 из N» в соответствии с рангами приоритетов, а на внешних выходах второй группы указателей OZ1, OZ2, …, OZM будут установлены сигналы соответствующего ранга приоритета в группе.

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

Похожие патенты RU2649943C1

название год авторы номер документа
АРБИТР ПРИОРИТЕТОВ МНОГОРАНГОВЫХ ЗАПРОСОВ 2017
  • Новиков Григорий Григорьевич
  • Ядыкин Игорь Михайлович
RU2649948C1
АРБИТР ПРИОРИТЕТОВ МНОГОКАНАЛЬНЫХ ЗАПРОСОВ 2017
  • Новиков Григорий Григорьевич
  • Ядыкин Игорь Михайлович
RU2649953C1
АРБИТР ДИСПЕТЧЕРА ЗАДАЧ 2020
  • Шурыгин Виктор Александрович
  • Ядыкин Игорь Михайлович
RU2749151C1
МНОГОКАНАЛЬНЫЙ АРБИТР ДИСПЕТЧЕРА ЗАДАЧ 2021
  • Шурыгин Виктор Александрович
  • Ядыкин Игорь Михайлович
RU2777841C1
МНОГОВЫХОДНОЙ УКАЗАТЕЛЬ СТАРШЕЙ ЕДИНИЦЫ 2015
  • Новиков Григорий Григорьевич
  • Чуканов Всеволод Озирисович
  • Ядыкин Игорь Михайлович
RU2591017C1
АРБИТР ДИСПЕТЧЕРА ЗАДАЧ КАСКАДНОЙ СТРУКТУРЫ 2022
  • Шурыгин Виктор Александрович
  • Ядыкин Игорь Михайлович
RU2799990C1
КРУГОВОЙ АРБИТР ДИСПЕТЧЕРА ЗАДАЧ 2022
  • Ядыкин Игорь Михайлович
RU2785771C1
АРБИТР ДИСПЕТЧЕРА ЗАДАЧ ПАРАЛЛЕЛЬНОЙ СТРУКТУРЫ 2022
  • Новиков Григорий Григорьевич
  • Ядыкин Игорь Михайлович
RU2799386C1
УСТРОЙСТВО ДЛЯ КОМПРЕССИИ ДАННЫХ 2019
  • Новиков Григорий Григорьевич
  • Ядыкин Игорь Михайлович
RU2710987C1
УСТРОЙСТВО ДЛЯ КОМПРЕССИИ ДАННЫХ 2017
  • Новиков Григорий Григорьевич
  • Ядыкин Игорь Михайлович
RU2672625C1

Иллюстрации к изобретению RU 2 649 943 C1

Реферат патента 2018 года МНОГОВЫХОДНОЙ АРБИТР ПРИОРИТЕТОВ

Изобретение относится к арбитражу в системах обработки информации при организации обмена данными между устройствами. Техническим результатом изобретения является расширение функциональных возможностей, в части формирования М групп указателей номера группы запросов в унитарном коде «1 из N» в порядке старшинства приоритетов и указателя ранга приоритета в группе. Многовыходной арбитр приоритетов содержит N групп внешних входов запросов IZ1, IZ2, …, IZN, каждая из которых содержит по М разрядов ранга приоритета, М первых групп U1i, U2i, …, UNi, каждая из которых содержит по N внешних выходов указателей номера группы старшего приоритета (i=1, 2, …, М), вторую группу из М внешних выходов указателей ранга приоритета в группе, группу из М первых блоков указателей старшей единицы, группу из N вторых блоков указателей старшей единицы 41, 42, …, 4N, третью группу из М элементов ИЛИ, при этом каждый i-й первый блок (i=1, 2, …, М) содержит первую группу из (N-2) элементов ИЛИ, первую группу из (N-1) элементов запрета И с одним инверсным входом, N входов и N выходов, а каждый j-й второй блок (j=1, 2, …, N) содержит вторую группу из (М-1) элементов запрета И с одним инверсным входом, вторую группу из (М-2) элементов ИЛИ, 2(М-1) входов и (М-1) выходов. 1 ил., 2 табл.

Формула изобретения RU 2 649 943 C1

Многовыходной арбитр приоритетов содержит N групп внешних входов запросов IZ1, IZ2, …, IZN, каждая из которых содержит по М разрядов ранга приоритета (высший приоритет имеет старшая группа IZN, а старший ранг приоритета имеет старший М-й разряд), М первых групп U1i, U2i, …, UNi, каждая из которых содержит по N внешних выходов указателей номера группы старшего приоритета (i=1, 2, …, М), вторую группу из М внешних выходов указателей ранга приоритета в группе OZ1, OZ2, …, OZM, группу из М первых блоков указателей старшей единицы 11, 12, …, 1M, при этом каждый i-й первый блок (i=1, 2, …, М) содержит первую группу из (N-2) элементов ИЛИ 2i1, 2i2, …, 2i(N-2), первую группу из (N-1) элементов запрета И с одним инверсным входом 3i1, 3i2, …, 3i(N-l), N входов и N выходов, группу из N вторых блоков указателей старшей единицы 41, 42, …, 4N, при этом каждый j-й второй блок (j=1, 2, …, N) содержит вторую группу из (М-1) элементов запрета И с одним инверсным входом 5j1, 5j2, …, 5j(M-1), вторую группу из (М-2) элементов ИЛИ 6j1, 6j2, …, 6j(M-2), 2(М-1) входов и (М-1) выходов, третью группу из М элементов ИЛИ 71, 72, …, 7M, причем в каждом i-м (i=1, 2, …, М) первом блоке указателя старшей единицы 1i первые (N-1) входов I1, I2, …, I(N-1), кроме последнего входа IN, соединены со вторыми прямыми входами соответствующих элементов 3i1, 3i2, …, 3i(N-1) из первой группы элементов запрета И с одним инверсным входом, выходы всех элементов первой группы из (N-2) элементов ИЛИ 2i1, 2i2, …, 2i(N-2) соединены с первыми инверсными входами соответствующих первых (N-2) элементов 3i1, 3i2, …, 3i(N-2) первой группы из элементов запрета И с одним инверсным входом, кроме последнего элемента 3i(N-1), у которого первый инверсный вход соединен с последним входом IN i-го первого блока указателя старшей единицы 1i, и первым входом последнего (N-2)-го элемента 2i(N-2) из первой группы элементов ИЛИ, кроме того, в каждом i-м (i=1, 2, …, М) первом блоке указателя старшей единицы 1i вторые входы (N-2) элементов 2i1, 2i2, …, 2i(N-2) из первой группы элементов ИЛИ соединены с соответствующими (N-2) входами I2, I3, …, I(N-1) i-го первого блока, начиная со второго входа I2, кроме последнего входа IN, а первые входы первых (N-3) элементов 2i1, 2i2, …, 2i(N-3) из первой группы элементов ИЛИ соединены с выходами соответствующих последующих элементов 2i2, 2i3, …, 2i(N-2) из первой группы элементов ИЛИ, причем в каждом i-м (i=1, 2, …, М) первом блоке указателя старшей единицы 1i выходы (N-1) элементов 3i1, 3i2, …, 3i(N-i) из первой группы элементов И с одним инверсным входом являются первыми (N-1) выходами O1, O2, …, O(N-1) первого блока указателя старшей единицы 1i, в котором последний выход ON соединен с последним входом IN, причем в каждом j-ом (j=1, 2, …, N) втором блоке указателя старшей единицы 4j первые (М-1) входов I1, I2, …, I(М-1), начиная с первого входа I1 до (M-1)-го входа I(М-1), соединены со вторыми прямыми входами соответствующих элементов 5j1, 5j2, …, 5j(M-1) из второй группы элементов запрета И с одним инверсным входом, выходы всех элементов второй группы из (М-2) элементов ИЛИ 6j1, 6j2, …, 6j(M-2) соединены с первыми инверсными входами соответствующих первых (М-2) элементов 5j1, 5j2, …, 5j(M-2) второй группы из элементов запрета И с одним инверсным входом, кроме последнего элемента 5j(M-1), у которого первый инверсный вход соединен с последним входом I(2M-2) j-го второго блока указателя старшей единицы 4j и вторым входом последнего (М-2)-го элемента 6j(M-2) из второй группы элементов ИЛИ, кроме того, в каждом j-м (j=1, 2, …, N) втором блоке указателя старшей единицы 4j первые входы (М-2) элементов 6j1, 6j2, …, 6j(M-2) из второй группы элементов ИЛИ соединены с соответствующими (М-2) входами IM, I(М+1), …, I(2M-3) j-го второго блока, начиная с входа IM, кроме последнего входа I(2М-2), а вторые входы первых (М-3) элементов 6j1, 6j2, …, 6j(M-3), кроме последнего (М-2)-го элемента 6j(M-2) из второй группы элементов ИЛИ, соединены с выходами соответствующих последующих элементов 6j2, 6j3, …, 6j(M-2), начиная со второго элемента из второй группы элементов ИЛИ, причем в каждом j-м (j=1, 2, …, N) втором блоке указателя старшей единицы 4j выходы (М-1) элементов 5j1, 5j2, …, 5j(M-1) из второй группы элементов И с одним инверсным входом являются (М-1) выходами O1, O2, …, O(М-1) второго блока указателя старшей единицы 4j, причем старший М-й разряд каждой j-й (j=1, 2, …, N) группы внешних входов запросов IZ1, IZ2, …, IZN соединен с соответствующим j-м входом I1, I2, …, IN последнего М-го первого блока указателя старшей единицы 1М, а разряды с первого до (M-1)-го каждой j-ой группы внешних входов запросов IZj соединены с соответствующими одноименными входами I1, I2, …, I(М-1), начиная с первого I1 до (М-1)-го входа, одноименных j-х вторых блоков указателей старшей единицы 4j, входы с М-го до (2М-2)-го каждого j-го второго блока указателей старшей единицы 4j соединены с соответствующим j-м выходом соответственно со второго до М-го первых блоков указателя старшей единицы 12, 13, …, 1M, а выходы с первого до (M-1)-го каждого j-го второго блока указателей старшей единицы 4j соединены с соответствующим j-м входом соответственно с первого до (M-1)-го первых блоков указателя старшей единицы 11, 12, …, 1(M-1), все N выходов каждого i-го (i=1, 2, …, М) первого блока указателя старшей единицы 1i также соединены с соответствующими входами одноименного i-го элемента ИЛИ третьей группы 71, 72, …, 7М, выходы которых являются соответственно выходами второй группы из М внешних выходов указателей ранга приоритета в группе OZ1, OZ2, …, OZM, а также N выходов каждого i-го (i=1, 2, …, М) первого блока указателя старшей единицы 1i являются соответственно N внешними выходами указателей номера группы старшего приоритета соответствующей i-й первой группы U1i, U2i, …, UNi.

Документы, цитированные в отчете о поиске Патент 2018 года RU2649943C1

МНОГОВЫХОДНОЙ УКАЗАТЕЛЬ СТАРШЕЙ ЕДИНИЦЫ 2015
  • Новиков Григорий Григорьевич
  • Чуканов Всеволод Озирисович
  • Ядыкин Игорь Михайлович
RU2591017C1
СПОСОБ, УСТРОЙСТВО, КОМПЬЮТЕРНАЯ ПРОГРАММА И ГРАФИЧЕСКИЙ ИНТЕРФЕЙС ПОЛЬЗОВАТЕЛЯ ДЛЯ ПОЛЬЗОВАТЕЛЬСКОГО ВВОДА В ЭЛЕКТРОННОЕ УСТРОЙСТВО 2006
  • Ю Кун
  • Ванг Конг Кьяо
  • Кангас Яри
RU2415464C2
ПРЕДСТАВЛЕНИЕ ФИЛЬТРАЦИИ НАБЛЮДЕНИЯ, АССОЦИИРОВАННОЙ С БУФЕРОМ ДАННЫХ 2013
  • Нейлл Жозе С.
  • Каттер Дэниэл Ф.
  • Аллен Джеймс Д.
  • Лимайе Деепак
  • Касавне Шади Т.
RU2608000C2
US 6081914 A, 27.06.2000.

RU 2 649 943 C1

Авторы

Новиков Григорий Григорьевич

Ядыкин Игорь Михайлович

Даты

2018-04-05Публикация

2017-07-04Подача