АРБИТР ДИСПЕТЧЕРА ЗАДАЧ Российский патент 2021 года по МПК G06F13/37 G06F9/50 

ОБЛАСТЬ ТЕХНИКИ

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

ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ

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

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

Известен многовыходной указатель старшей единицы (RU №2591017 C1, МПК Н03М 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) элементов ИЛИ 1_i, 1_i2, …, 1_i(N-i-1) и группу из (N-i) элементов запрета И с одним инверсным входом 2_i1, 2_i2, …, 2_i(N-i), а также группу из (N+1-i) входов запроса в i-й каскад A_i1, A_i2, …, A_i(N+1-i) и группу из (N+1-i) внешних выходов указателей старшей единицы i-го ранга U_i1, U_i2, …, U_i(N+1-i) (1-й ранг имеет высший приоритет), каждый из первых (К-1) каскадов, кроме последнего К-го каскада содержит также группу из (N-i) элементов И 3_i1, 3_i2, …, 3_i(N-i) и группу из (N-i) выходов запроса S_i1, S_i2, …, S_i(N-i) в следующий (i+1)-й каскад.

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

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятый за прототип, арбитр приоритетов многоранговых запросов (RU №2649948 С1, МПК G06F 13/37, заявлен 15.05.2017, опубликован 05.04.2018, Бюл. №10), содержащий N групп внешних входов запросов IZ1, IZ2, …, IZN, каждая из которых содержит М разрядов ранга приоритета (высший ранг приоритета имеет старший М-ый разряд, старший приоритет имеет старшая группа IZN), первую группу из N внешних выходов указателей группы старшего приоритета U1, U2, …, UN, вторую группу из М внешних выходов указателей высшего ранга приоритета в группе OZ1, OZ2, …, OZM, группу из (N-2) элементов ИЛИ 4₁, 4₂, …, 4_(N-2), первую группу из (N-1) элементов запрета И с одним инверсным входом 5₁, 5₂, …, 5_(N-1), группу из М элементов ИЛИ-НЕ 6₁, 6₂, …, 6_M, вторую группу из (М-1) элементов запрета И с одним инверсным входом 7₁, 7₂, …, 7_(M-1), инвертор 8 и группу из N блоков каналов анализа приоритета 1₁, 1₂, …, 1_n, каждый из которых содержит элемент ИЛИ 3 и группу из (М-1) элементов И 2₁, 2₂, …, 2_(M-1), при этом каждый v-й элемент И 2_V (v=1, …, 2, (М-1)) содержит (М-v+1) входов.

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

ЗАДАЧА ИЗОБРЕТЕНИЯ

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

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

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

Указанный технический результат при осуществлении изобретения достигается тем, что арбитр диспетчера задач содержит внешнюю шину входной заявки IP, которая состоит из L групп параметров задачи, N внешних шин параметров каналов IC1, IC2, …, ICN, каждая из которых состоит из L групп параметров каналов, N внешних шин занятости каналов IT1, IT2, …, ITN, каждая из которых содержит М разрядов ранга приоритета (высший ранг приоритета имеет младший нулевой разряд, старший приоритет имеет старший канал ITN), первую группу из N внешних выходов указателей канала старшего приоритета QU1, QU2, …, QUN и вторую группу из М внешних выходов указателей высшего ранга приоритета в канале OZ0, OZ1, …, OZ(M-1), N внутренних шин запросов IZ1, IZ2, …, IZN, каждая из которых содержит М разрядов приоритета, N разрядов внутренней шины состояния каналов S1, S2, …, SN, N разрядов внутренней шины готовности каналов К1, К2, …, КN и флаг готовности F, а также содержит группу из N блоков анализа параметров 1₁, 1₂, …, 1_N, каждый из которых содержит группу из L компараторов 2₁, 2₂, …, 2_L и элемент И 3, группу из N блоков разрешения запросов 4₁, 4₂, …, 4_N, каждый из которых содержит первую группу из М элементов И 5₀, 5₁, …, 5_(M-1), первую группу из М элементов ИЛИ 6₀, 6₁, …, 6_(M-1), вторую группу из (М-1) элементов запрета И с инверсными входами 7₁, 7₂, …, 7_(M-1), группу из N блоков анализа готовности каналов 8₁, 8₂, …, 8_N, каждый из которых содержит третью группу из (М-1) элементов И 9₁, 9₂, …, 9_(M-1) и первый элемент ИЛИ 10, а также второй элемент ИЛИ 11, вторую группу из (N-2) элементов ИЛИ 12₁, 12₂, …, 12_(N-2) и четвертую группу из (N-1) элементов запрета И с одним инверсным входом 13₁, 13₂, …, 13_(N-1), причем L групп параметров задачи внешней шины входной заявки IP соединены с первыми группами входов соответствующих одноименных компараторов 2₁, 2₂, …, 2_L всех N блоков анализа параметров 1₁, 1₂, …, 1_N, в каждом из которых вторые группы входов компараторов 2₁, 2₂, …, 2_L соединены с соответствующими одноименными L группами соответствующих N внешних шин параметров каналов IC1, IC2, …, ICN, а также в каждом блоке анализа параметров 1₁, 1₂, …, 1_N выходы компараторов 2₁, 2₂, …, 2_L соединены с соответствующим элементом И3, выходы которых являются соответствующими N разрядами S1, S2, …, SN внутренней шины состояния каналов, в каждом из N блоков разрешения запросов 4₁, 4₂, …, 4_N первые входы элементов И первых групп из М элементов И 5₀, 5₁, …, 5_(M-1) соединены между собой, а также подключены к соответствующим N разрядам S1, S2, …, SN внутренней шины состояния каналов одноименным номеру канала, а вторые входы элементов И первых групп из М элементов И 5₀, 5₁, …, 5_(M-1) подключены к соответствующим одноименным М разрядам из N внешних шин занятости каналов IT1, IT2, …, ITN одноименных номеру канала, причем выходы элементов И первых групп из М элементов И 5₀, 5₁, …, 5_(M-1) являются соответствующими М разрядами ранга приоритета, с 0-го по (М-1)-й разряды, соответствующих N внутренних шин запросов IZ1, IZ2, …, IZN. одноименных номеру канала,

причем все М разрядов приоритета каждой из N внутренних шин запросов IZ1, IZ2, …, IZN соединены с соответствующими одноименными входами одноименных N блоков анализа готовности каналов 8₁, 8₂, …, 8_N, а также каждый i-й разряд (i=0, 1, …, (М-1)) приоритета каждой из N внутренних шин запросов IZ1, IZ2, …, IZN соединен с соответствующим входом одноименного i-го элемента из первой группы из М элементов ИЛИ 6₀, 6₁, …, 6_(М-1), при этом выходы элементов ИЛИ, начиная с первого 61 до М-го 6_(M-1), соединены с первыми прямыми входами одноименных элементов второй группы из (М-1) элементов запрета И с инверсными входами 7₁, 7₂, …, 7_(M-1), у которых инверсные входы j-го элемента 7_j (j=1, 2, …, (М-1)) соединены с соответствующими выходами к элементов (k=0, 1, …, (j-1)) первой группы из М элементов ИЛИ 6₀, 6₁, …, 6_(M-1),

одноименные входы М, (М+1), …, (2М-2) каждого из N блоков каналов анализа готовности каналов 8₁, 8₂, …, 8_N соединены между собой, а также подключены к соответствующим выходам (М-1) элементов, начиная с первого до (M-1)-го элемента, из второй группы элементов И с инверсными входами 7₁, 7₂, …, 7_(M-1),

выходы элементов И второй группы из (М-1) элементов запрета И с одним инверсным входом 7₁, 7₂, …, 7_(M-1) являются соответствующими (М-1) выходами OZ1, OZ2, …, OZ(M-1) второй группы из М внешних выходов указателей высшего ранга приоритета в канале, а младшим нулевым выходом OZ0 является выход элемента ИЛИ 6₀,

в каждом из N блоков 8₁, 8₂, …, 8_N анализа готовности каналов (М-1) входов блока, начиная с первого входа до (М-1) входа, соединены с соответствующими первыми входами одноименных элементов И из третьей группы из (М-1) элементов И 9₁, 9₂, …, 9_(M-1) блока, у которых вторые входы соединены с соответствующими входами блока, начиная с М-го входа до (2М-2)-го входа, а выходы третьей группы из (М-1) элементов И 9₁, 9₂, …, 9_(M-1) блока и 0-й вход блока соединены с соответствующими входами элемента ИЛИ 10, выход которого является выходом соответствующего блока каналов анализа готовности каналов 8₁, 8₂, …, 8_N, которые подключены к N разрядам внутренней шины готовности каналов К1, К2, …, КN и соответствующим входам второго элемента ИЛИ 11, выход которого является флагом готовности F,

причем выходы первых (N-1) блоков каналов анализа готовности каналов 8₁, 8₂, …, 8_(N-1), начиная с первого блока до предпоследнего (N-1) блока, также соединены с первыми прямыми входами соответствующих (N-1) элементов 13₁, 13₂, 13_(N-1) четвертой группы из элементов запрета И с одним инверсным входом, а выход последнего N-го блока каналов анализа приоритета 8_N, соединен со вторым инверсным входом (N-1) элемента 13_(N-1) четвертой группы из элементов запрета И с одним инверсным входом,

выходы всех элементов второй группы из (N-2) элементов ИЛИ 12₁, 12₂, …, 12_(N-2) соединены со вторыми инверсными входами соответствующих одноименных первых (N-2) элементов 13₁, 13₂, …, 13_(N-2) четвертой группы из элементов запрета И с одним инверсным входом, а также первые и вторые входы всех (N-2) элементов 12₁, 12₂, …, 12_(n-2) из второй группы элементов ИЛИ подключены соответственно к первым прямым и ко вторым инверсным входам соответствующих (N-2) элементов И 13₂, 13₃, …, 13_(N-1), начиная со второго элемента до последнего (N-1) элемента четвертой группы элементов запрета И с одним инверсным входом,

выходы четвертой группы элементов запрета И с одним инверсным входом 13₁, 13₂, …, 13_(N-1) являются первыми (N-1) внешними выходами QU1, QU2, …, QU(N-1) из первой группы внешних выходов указателей канала старшего приоритета, а старшим N-m внешним выходом QUN является выход последнего N-го блока анализа готовности каналов приоритета 8_N.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

На фиг. 1 представлена схема предлагаемого арбитра диспетчера задач для входных заявок IP содержащих L=2 групп параметров задач и для N=4 каналов обработки, каждый из которых содержит М=3 уровня (ранга) длительности обработки заявок (высший ранг приоритета имеет младший нулевой разряд, старший приоритет имеет старший 4-й канал).

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

IP - внешняя шина входной заявки, содержащая L групп параметров задачи

IC1, IC2, …, IC4 (ICN) - внешние шины параметров N=4 каналов обработки задач, содержащие по L групп параметров каналов;

IT1, IT2, …, IT4 (ITN) - внешние шины занятости N=4 каналов обслуживанием заявок, каждая из которых содержит М=3 разрядов уровня (ранга) длительности обработки заявок (высший ранг приоритета имеет младший нулевой разряд, старший приоритет имеет старший 4-й канал IT4 (ITN));

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

F - флаг готовности;

К1, К2, …, К4 (КN) - N разрядов внутренней шины готовности каналов к обслуживанию;

S1, S2, …, S4 (SN) - N разрядов внутренней шины состояния каналов;

QU1, QU2, …, QU4 (QUN) - первая группа из N=4 внешних выходов указателей

канала старшего приоритета, QZ0, QZ1, …, QZ2 (QZ(M-1)) - вторая группа из М=3 внешних выходов указателей

высшего ранга приоритета в канале, 1₁, 1₂, …, 1_n - группа из N=4 блоков анализа параметров;

2₁, 2₂, …, 2_L - группа из L=2 компараторов каждого блока анализа параметров 1₁, 1₂, …, 1_n,

3 - элемент И каждого блока каналов анализа параметров 1₁, 1₂, …, 1_N, 4₁, 4₂, …, 4_N - группа из N=4 блоков разрешения запросов;

5₀, 5₁, …, 5_(M-1) - первая группа из М=3 элементов И каждого блока разрешения запросов 4₁, 4₂, …, 4_N, 6₀, 6₁, …, 6_(M-1) - первая группа из М=3 элементов ИЛИ,

7₁, 7₂, …, 7_(M-1) - вторая группа из (М-1)=2 элементов запрета И с инверсными входами,

8₁, 8₂, …, 8_N - группа из N=4 блоков анализа готовности каналов, 9₁, 9₂, …, 9_(M-1) - третья группа из (М-1)=2 элементов И каждого блока анализа готовности каналов 8₁, 8₂, …, 8_N,

10 - первый элемент ИЛИ каждого блока анализа готовности каналов 8₁, 8₂, …, 8_N,

11 - второй элемент ИЛИ;

12₁, 12₂, …, 12_(N-2) - вторая группа из (N-2)=2 элементов ИЛИ,

13₁, 13₂, …, 13_(N-1) - четвертая группа из (N-1)=3 элементов запрета И с одним инверсным входом.

Предлагаемый арбитр диспетчера задач содержит внешнюю шину входной заявки IP, которая состоит из L групп параметров задачи, N внешних шин параметров каналов IC1, IC2, …, ICN, каждая из которых состоит из L групп параметров каналов, N внешних шин занятости каналов IT1, IT2, …, ITN, каждая из которых содержит М разрядов ранга приоритета (высший ранг приоритета имеет младший нулевой разряд, старший приоритет имеет старший канал ITN), первую группу из N внешних выходов указателей канала старшего приоритета QU1, QU2, …, QUN и вторую группу из М внешних выходов указателей высшего ранга приоритета в канале OZ0, OZ1, …, OZ(M-1), N внутренних шин запросов IZ1, IZ2, …, IZN, каждая из которых содержит М разрядов приоритета, N разрядов внутренней шины состояния каналов S1, S2, …, SN, N разрядов внутренней шины готовности каналов К1, К2, …, KN и флаг готовности F.

Предлагаемый арбитр диспетчера задач также содержит группу из N блоков анализа параметров 1₁, 1₂, …, 1_N, каждый из которых содержит группу из L компараторов 2₁, 2₂, …, 2_L и элемент И 3, группу из N блоков разрешения запросов 4₁, 4₂, …, 4_N, каждый из которых содержит первую группу из М элементов И 5₀, 5₁, …, 5_(M-1), первую группу из М элементов ИЛИ 6₀, 6₁, …, 6_(M-1), вторую группу из (М-1) элементов запрета И с инверсными входами 7₁, 7₂, …, 7_(M-1), группу из N блоков анализа готовности каналов 8₁, 8₂, …, 8_N, каждый из которых содержит третью группу из (М-1) элементов И 9₁, 9₂, …, 9_(M-1) и первый элемент ИЛИ 10, а также второй элемент ИЛИ 11, вторую группу из (N-2) элементов ИЛИ 12₁, 12₂, …, 12_(N-2) и четвертую группу из (N-1) элементов запрета И с одним инверсным входом 13₁, 13₂, …, 13_(N-1).

Причем L групп параметров задачи внешней шины входной заявки IP соединены с первыми группами входов соответствующих одноименных компараторов 2₁, 2₂, …, 2_L всех N блоков анализа параметров 1₁, 1₂, …, 1_N, в каждом из которых вторые группы входов компараторов 2₁, 2₂, …, 2_L соединены с соответствующими одноименными L группами соответствующих N внешних шин параметров каналов IC1, IC2, …, ICN. Также в каждом блоке анализа параметров 1₁, 1₂, …, 1_N выходы компараторов 2₁, 2₂, …, 2_L соединены с соответствующим элементом И3, выходы которых являются соответствующими N разрядами S1, S2, …, SN внутренней шины состояния каналов.

В каждом из N блоков разрешения запросов 4₁, 4₂, …, 4_N первые входы элементов И первых групп из М элементов И 5₀, 5₁, …, 5_(M-1) соединены между собой, а также подключены к соответствующим N разрядам S1, S2, …, SN внутренней шины состояния каналов одноименным номеру канала, а вторые входы элементов И первых групп из М элементов И 5₀, 5₁, …, 5_(M-1) подключены к соответствующим одноименным М разрядам из N внешних шин занятости каналов IT1, IT2, …, ITN одноименных номеру канала. Причем выходы элементов И первых групп из М элементов И 5₀, 5₁, …, 5_(M-1) являются соответствующими М разрядами ранга приоритета, с 0-го по (М-1)-й разряды, соответствующих N внутренних шин запросов IZ1, IZ2, …, IZN. одноименных номеру канала.

Причем все М разрядов приоритета каждой из N внутренних шин запросов IZ1, IZ2, …, IZN соединены с соответствующими одноименными входами одноименных N блоков анализа готовности каналов 8₁, 8₂, …, 8_N, а также каждый i-й разряд (i=0, 1, …, (М-1)) приоритета каждой из N внутренних шин запросов IZ1, IZ2, …, IZN соединен с соответствующим входом одноименного i-го элемента из первой группы из М элементов ИЛИ 6₀, 6₁, …, 6_(M-1). При этом выходы элементов ИЛИ, начиная с первого 6₁ до М-го 6_(M-1), соединены с первыми прямыми входами одноименных элементов второй группы из (М-1) элементов запрета И с инверсными входами 7₁, 7₂, …, 7_(M-1), у которых инверсные входы j-го элемента 7_j (j=1, 2, …, (М-1)) соединены с соответствующими выходами к элементов (k=0, 1, …, (j-1)) первой группы из М элементов ИЛИ 6₀, 6₁, …, 6_(M-1).

Одноименные входы М, (М+1), …, (2М-2) каждого из N блоков каналов анализа готовности каналов 8₁, 8₂, …, 8_N соединены между собой, а также подключены к соответствующим выходам (М-1) элементов, начиная с первого до (M-1)-го элемента, из второй группы элементов И с инверсными входами 7₁, 7₂, …, 7_(M-1).

Выходы элементов И второй группы из (М-1) элементов запрета И с одним инверсным входом 7₁, 7₂, …, 7_(M-1) являются соответствующими (М-1) выходами OZ1, OZ2, …, OZ(M-1) второй группы из М внешних выходов указателей высшего ранга приоритета в канале, а младшим нулевым выходом OZ0 является выход элемента ИЛИ 6₀.

В каждом из N блоков 8₁, 8₂, …, 8_N анализа готовности каналов (М-1) входов блока, начиная с первого входа до (М-1) входа, соединены с соответствующими первыми входами одноименных элементов И из третьей группы из (М-1) элементов И 9₁, 9₂, …, 9_(M-1) блока, у которых вторые входы соединены с соответствующими входами блока, начиная с М-го входа до (2М-2)-го входа. Выходы третьей группы из (М-1) элементов И 9₁, 9_2, …, 9_(M-1) блока и 0-й вход блока соединены с соответствующими входами элемента ИЛИ 10, выход которого является выходом соответствующего блока каналов анализа готовности каналов 8₁, 8₂ …, 8_N, которые подключены к N разрядам внутренней шины готовности каналов К1, К2, …, КN и соответствующим входам второго элемента ИЛИ 11. Выход элемента ИЛИ 11 является флагом готовности F.

Причем выходы первых (N-1) блоков каналов анализа готовности каналов 8₁, 8₂, …, 8_(N-1), начиная с первого блока до предпоследнего (N-1) блока, также соединены с первыми прямыми входами соответствующих (N-1) элементов 13₁, 13₂, …, 13_(N-1) четвертой группы из элементов запрета И с одним инверсным входом, а выход последнего N-го блока каналов анализа приоритета 8_N, соединен со вторым инверсным входом (N-1) элемента 13_(N-1) четвертой группы из элементов запрета И с одним инверсным входом.

Выходы всех элементов второй группы из (N-2) элементов ИЛИ 12₁, 12₂, …, 12_(N-2) соединены со вторыми инверсными входами соответствующих одноименных первых (N-2) элементов 13₁, 13₂, …, 13_(N-2) четвертой группы из элементов запрета И с одним инверсным входом, а также первые и вторые входы всех (N-2) элементов 12₁, 12₂, …, 12_(N-2) из второй группы элементов ИЛИ подключены соответственно к первым прямым и ко вторым инверсным входам соответствующих (N-2) элементов И 13₂, 13₃, …, 13_(N-1), начиная со второго элемента до последнего (N-1) элемента четвертой группы элементов запрета И с одним инверсным входом.

Выходы четвертой группы элементов запрета И с одним инверсным входом 13₁, 13₂, …, 13_(N-1) являются первыми (N-1) внешними выходами QU1, QU2, …, QU(N-1) из первой группы внешних выходов указателей канала старшего приоритета, а старшим N-м внешним выходом QUN является выход последнего N-го блока анализа готовности каналов приоритета 8_N.

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

Принцип работы предлагаемого устройства состоит в следующем. В устройстве входная заявка на внешней шине IP содержит L групп требуемых параметров для исполнения вычислительной задачи - объем памяти для ввода и вывода информации, наличие соответствующих программ для алгоритма обработки вычислительной задачи и соответствующие маски групп. Предлагаемый арбитр диспетчера задач в N блоках анализа параметров 1₁, 1₂, …, 1_N проверяет возможность обслуживания заявок путем сравнения L групп требуемых параметров для задачи на внешней шине IP и соответствующих L групп параметров каналов обработки задач, поступающим по шинам IC1, IC2, …, ICN. При соответствии всех параметров L групп по каналам формируются единичные значения в соответствующих N разрядах внутренней шины состояния каналов S1, S2, …, SN или нулевые значения при не соответствии параметров.

Одновременно по внешним шинам занятости N каналов IT1, IT2, …, ITN поступают в унитарном коде «1 из М» значения соответствующее времени занятости каналов обслуживанием предыдущих заявок (высший ранг приоритета имеет младший нулевой разряд, старший приоритет имеет старший 4 (N)-й канал IT4 (ITN)). Единичное значение в нулевом разряде соответствует отсутствию заявок на обслуживание в канале - готовности канала к обслуживанию заявки без ожидания. Единичное значение в старшем (М-1) разряде соответствует максимальной занятости канала - максимальному времени ожидания обслуживания.

В N блоках разрешения запросов 4₁, 4₂, …, 4_N при единичных значениях соответствующих разрядов внутренней шины состояния каналов S1, S2, …, SN значения с входных шин занятости каналов IT1, IT2, …, ITN передаются на соответствующие внутренние шины запросов IZ1, IZ2, …, IZN или нулевые значения при нулевых значениях соответствующих разрядов внутренней шины состояния каналов S1, S2, …, SN.

Далее в предлагаемом арбитре диспетчера задач в первой группе элементов ИЛИ 6₀, 6₁, …, 6_(M-1) и второй группе элементов запрета И с инверсными входами 7₁, 7₂, …, 7_(M-1), определяется высший приоритет (ранг) запроса готовности каналов к обслуживанию по значениям на внутренних шинах запросов IZ1, IZ2, …, IZN и формируется номер ранга в унитарном коде «1 из М» на второй группе из М внешних выходов указателей высшего ранга приоритета в канале QZ0, QZ1, …, QZ(M-1) или нулевой код, если параметры всех каналов не соответствуют параметрам входной заявки IP.

В блоках анализа готовности каналов 8₁, 8₂, …, 8_N, на основании высшего ранга приоритета в канале QZ0, QZ1, …, QZ(M-1), на выходах формируются единичные значения на разрядах внутренней шины готовности каналов к обслуживанию К1, К2, …, КN, по которым проводится поиск канала готовности к обслуживанию с наивысшим приоритетом. При этом на выходах четвертой группа из (N-1) элементов запрета И с одним инверсным входом 13₁, 13₂, …, 13_(N-1) единичный сигнал будет установлен только на одном выходе соответствующем каналу старшего приоритета готовности. Таким образом, на первой группе внешних выходах указателей канала старшего приоритета QU1, QU2, …, QUN формируется результат в виде унитарного коде «1 из N» или нулевой код если все каналы не готовы к приему заявки. Одновременно при наличии единичного значения на одном из разрядов внутренней шины готовности каналов к обслуживанию К1, К2, …, КN формируется флаг готовности F=1.

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

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

На внешнюю шину IP поступают L групп требуемых параметров входной заявки для исполнения вычислительной задачи и от N каналов обработки по внешним шинам IC1, IC2, …, ICN. поступают по L групп параметров каналов и по внешним шинам занятости N каналов IT1, IT2, …, ITN поступают в унитарном коде «1 из М» значения

соответствующие времени занятости канала обслуживанием предыдущих заявок (высший ранг приоритета имеет младший нулевой разряд, старший приоритет имеет старший 4 (N)-й канал IT4 (ITN)). Данные сигналы поступают на соответствующие входы блоков анализа параметров 1₁, 1₂, …, 1_N и блоков разрешения запросов 4₁, 4₂, …, 4_N.

В таблице 1 приведены тестовые примеры формирования указателей канала старшего приоритета QU1, QU2, …, QU4 и высшего ранга приоритета QZ0, QZ1, QZ2 для N=4 каналов обработки, каждый из которых содержит М=3 уровня (ранга) длительности ожидания обработки заявок (высший ранг приоритета имеет младший нулевой разряд QZ0, старший приоритет имеет старший 4-й канал QU4).

В тесте №1 значения параметров L групп входной заявки IP не соответствуют параметрам L групп всех каналов IC1, IC2, …, IC4, поэтому нулевые значения формируются во всех N=4 разрядах внутренней шины состояния каналов S1, S2, …, S4. Одновременно поступают значения унитарных кодов «100» на всех входных шинах занятости каналов IT1, IT2, …, IT4, что соответствует отсутствию обрабатываемых заявок в каналах, но на внутренних шинах запросов IZ1, IZ2, …, IZ4 формируются нулевые значения, так как нулевые значения установлены в разрядах внутренней шины состояния каналов S1, S2, …, S4. Далее нулевые значения формируются на выходах указателя высшего ранга приоритета в канале QZ0, QZ1, QZ2, в разрядах внутренней шины готовности каналов к обслуживанию К1, К2, …, К4 и на первой группе внешних выходах указателей канала старшего приоритета QU1, QU2, …, QU4, а также нулевое значение флага готовности F=0, что соответствует запрету передачи данных.

В тесте №2 значения параметров L групп входной заявки IP соответствуют параметрам L групп всех каналов IC1, IC2, …, IC4, поэтому единичные значения формируются во всех N=4 разрядах внутренней шины состояния каналов S1, S2, …, S4. Одновременно поступают значения унитарных кодов «100» на всех входных шинах занятости каналов IT1, IT2, …, IT4, что соответствует отсутствию обрабатываемых заявок в каналах, которые передаются на разряды всех внутренних шин запросов IZ1, IZ2, …, IZ4. Далее на выходах указателя высшего ранга приоритета в канале QZ0, QZ1, QZ2 формируется унитарный код «100» (единичное значение соответствует младшему нулевому разряду QZ0=1), по которому далее формируются единичные значения во всех разрядах внутренней шины готовности каналов к обслуживанию К1, К2, …, К4, что соответствует готовности всех N=4 каналов к обслуживанию заявки без ожидания. Но так как старший приоритет присвоен старшему четвертому каналу, то на первой группе внешних выходах указателей канала старшего приоритета QU1, QU2, …, QU4 формируется унитарный код «0001» (единичное значение соответствует старшему каналу QU4=1) и одновременно формируется единичное значение флага готовности F=1.

В тесте №3 значения параметров L групп входной заявки IP не соответствуют параметрам L групп в третьем канале S3=0 и соответствуют параметрам в первом S1=1, втором S2=1 и четвертом S4=1 каналах. Одновременно на входных шинах занятости каналов IT1, IT2, …, IT4 устанавливаются соответствующие значения унитарных кодов занятости, которые далее передаются на внутренние шины запросов IZ1, IZ2, IZ4 и нулевые значения устанавливаются на шине IZ3=0, так как нулевое значение установлено в третьем разряде S3=0 внутренней шины состояния каналов. Высший приоритет готовности (младший нулевой разряд) установлен на шине IZ1, поэтому на выходах указателя высшего ранга приоритета в канале QZ0, QZ1, QZ2 формируется унитарный код «100», по которому далее формируется единичное значение для первого канала К1=1 на внутренней шине готовности каналов к обслуживанию. Поэтому далее на первой группе внешних выходах указателей канала старшего приоритета QU1, QU2, …, QU4 формируется унитарный код «1000» (единичное значение соответствует первому каналу QU1=1) и одновременно формируется единичное значение флага готовности F=1.

В тесте №4 значения параметров L групп входной заявки IP не соответствуют параметрам L групп в первом S1=0 и четвертом S4=0 каналах и соответствуют параметрам во втором S2=1 и третьем S3=1 каналах, по которым соответствующие им унитарные коды «010» с шин занятости каналов IT2 и IT3 передаются на соответствующие внутренние шины запросов IZ2 и IZ3 и на выходах указателя высшего ранга приоритета в канале QZ0, QZ1, QZ2 формируется унитарный код «010». Далее единичные значения устанавливаются для второго К2=1 и третьего К3=1 каналов на внутренней шине готовности данных каналов к обслуживанию. Поскольку третий канал имеет высший приоритет, то на первой группе внешних выходах указателей канала старшего приоритета QU1, QU2, …, QU4 формируется унитарный код «0010» (единичное значение соответствует третьему каналу QU3=1) и одновременно формируется единичное значение флага готовности F=1.

В тесте №5 значения параметров L групп входной заявки IP не соответствуют параметрам L групп в четвертом канале S4=0 и соответствуют параметрам в первом S1=1, втором S2=1 и третьем S3=1 каналах по которым соответствующие им унитарные коды с шин занятости каналов IT1, IT2 и IT3 передаются на соответствующие внутренние шины запросов IZ1, IZ2 и IZ3 и на выходах указателя высшего ранга приоритета в канале QZ0, QZ1, QZ2 формируется унитарный код «100» (единичное значение соответствует младшему нулевому разряду QZ0=1). Далее единичные значения устанавливаются для первого К1=1 и второго К2=1 каналов на внутренней шине готовности данных каналов к обслуживанию. Поскольку второй канал имеет высший приоритет, то на первой группе внешних выходах указателей канала старшего приоритета QU1, QU2, …, QU4 формируется унитарный код «0100» (единичное значение соответствует второму каналу QU2=1) и одновременно формируется единичное значение флага готовности F=1.

В тесте №6 значения параметров L групп входной заявки IP не соответствуют параметрам L групп в первом S1=0 и третьем S3=0 каналах и соответствуют параметрам во втором S2=1 и четвертом S4=1 каналах, по которым соответствующие им унитарные коды с шин занятости каналов IT2 и IT4 передаются на соответствующие внутренние шины запросов IZ2 и IZ4 и на выходах указателя высшего ранга приоритета в канале QZ0, QZ1, QZ2 формируется унитарный код «010» (единичное значение соответствует первому разряду QZ1=1). Далее единичное значение устанавливается только для второго К2=1 канала на внутренней шине готовности данных каналов к обслуживанию и на первой группе внешних выходов указателей канала старшего приоритета QU1, QU2, …, QU4 формируется унитарный код «0100» (единичное значение соответствует второму каналу QU2=1) и одновременно формируется единичное значение флага готовности F=1.

Таким образом, в предлагаемом устройстве на первой группе внешних выходов указателей канала старшего приоритета QU1, QU2, …, QUN будут установлены значения унитарных кодов «1 из N», а на выходах второй группы из М внешних выходов указателей высшего ранга приоритета в канале OZ0, OZ1, …, OZ(M-1) будет установлено значение, соответствующее номеру высшего ранга приоритета в унитарном коде «1 из М» и формируется единичное значение флага готовности F=1.. Если параметры L групп входной заявки по шине IP не соответствуют параметрам L групп по шинам всех каналов обработки IC1, IC2, …, ICN, то на первой QU1, QU2, …, QUN и второй OZ0, OZ1, …, OZ(M-1 группах выходов будут установлены нулевые значения, а также нулевое значение флага готовности F=0.

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

АРБИТР ДИСПЕТЧЕРА ЗАДАЧ

Изобретение относится к области вычислительной техники и может быть использовано для арбитража в многопроцессорных системах обработки информации для распараллеливания потока заявок. Техническим результатом является обеспечение возможности анализа параметров входной задачи и параметров каналов обработки задач. Устройство содержит внешнюю шину входной заявки IP и N внешних шин параметров каналов IC1, IC2, …, ICN, которые состоят из L групп параметров, N внешних шин занятости каналов IT1, IT2, …, ITN, каждая из которых содержит М разрядов ранга приоритета (высший ранг приоритета имеет младший нулевой разряд, старший приоритет имеет старший канал ITN), первую группу из N внешних выходов указателей канала старшего приоритета QU1, QU2, …, QUN и вторую группу из М внешних выходов указателей высшего ранга приоритета в канале OZ0, OZ1, …, OZ(M-1), N внутренних шин запросов IZ1, IZ2, …, IZN, каждая из которых содержит М разрядов приоритета, N разрядов внутренней шины состояния каналов S1, S2, …, SN, N разрядов внутренней шины готовности каналов К1, К2, …, КN и флаг готовности F, а также содержит группу из N блоков анализа параметров, каждый из которых содержит группу из L компараторов и элемент И, группу из N блоков разрешения запросов, каждый из которых содержит первую группу из М элементов И, первую группу из М элементов ИЛИ, вторую группу из (М-1) элементов запрета И с инверсными входами, группу из N блоков анализа готовности каналов, каждый из которых содержит третью группу из (М-1) элементов И и первый элемент ИЛИ, а также второй элемент ИЛИ, вторую группу из (N-2) элементов ИЛИ и четвертую группу из (N-1) элементов запрета И с одним инверсным входом. 1 ил., 1 табл.

Арбитр диспетчера задач содержит внешнюю шину входной заявки IP, которая состоит из L групп параметров задачи, N внешних шин параметров каналов IC1, IC2, …, ICN, каждая из которых состоит из L групп параметров каналов, N внешних шин занятости каналов IT1, IT2, …, ITN, каждая из которых содержит М разрядов ранга приоритета (высший ранг приоритета имеет младший нулевой разряд, старший приоритет имеет старший канал ITN), первую группу из N внешних выходов указателей канала старшего приоритета QU1, QU2, …, QUN и вторую группу из М внешних выходов указателей высшего ранга приоритета в канале OZ0, OZ1, …, OZ(M-1), N внутренних шин запросов IZ1, IZ2, …, IZN, каждая из которых содержит М разрядов приоритета, N разрядов внутренней шины состояния каналов S1, S2, …, SN, N разрядов внутренней шины готовности каналов К1, К2, …, КN и флаг готовности F,

а также содержит группу из N блоков анализа параметров 1₁, 1₂, …, 1_N, каждый из которых содержит группу из L компараторов 2₁, 2₂, …, 2_L и элемент И3, группу из N блоков разрешения запросов 4₁, 4₂, …, 4_N, каждый из которых содержит первую группу из М элементов И 5₀, 5₁, …, 5_(M-1), первую группу из М элементов ИЛИ 6₀, 6₁, …, 6_(M-1), вторую группу из (М-1) элементов запрета И с инверсными входами 7₁, 7₂, …, 7_(M-1), группу из N блоков анализа готовности каналов 8₁, 8₂, …, 8_N, каждый из которых содержит третью группу из (М-1) элементов И 9₁, 9₂, …, 9_(M-1) и первый элемент ИЛИ 10, а также второй элемент ИЛИ 11, вторую группу из (N-2) элементов ИЛИ 12₁, 12₂, …, 12_(N-2) и четвертую группу из (N-1) элементов запрета И с одним инверсным входом 13₁, 13₂, …, 13_(N-1),

причем L групп параметров задачи внешней шины входной заявки IP соединены с первыми группами входов соответствующих одноименных компараторов 2₁, 2₂, …, 2_L всех N блоков анализа параметров 1₁, 1₂, …, 1_N, в каждом из которых вторые группы входов компараторов 2₁, 2₂, …, 2_L соединены с соответствующими одноименными L группами соответствующих N внешних шин параметров каналов IC1, IC2, …, ICN, а также в каждом блоке анализа параметров 1₁, 1₂, …, 1_N выходы компараторов 2₁, 2₂, …, 2_L соединены с соответствующим элементом И3, выходы которых являются соответствующими N разрядами S1, S2, …, SN внутренней шины состояния каналов,

в каждом из N блоков разрешения запросов 4₁, 4₂, …, 4_N первые входы элементов И первых групп из М элементов И 5₀, 5₁, …, 5_(M-1) соединены между собой, а также подключены к соответствующим N разрядам S1, S2, …, SN внутренней шины состояния каналов, одноименным номеру канала, а вторые входы элементов И первых групп из М элементов И 5₀, 5₁, …, 5_(M-1) подключены к соответствующим одноименным М разрядам из N внешних шин занятости каналов IT1, IT2, …, ITN, одноименных номеру канала, причем выходы элементов И первых групп из М элементов И 5₀, 5₁, …, 5_(M-1) являются соответствующими М разрядами ранга приоритета, с 0-го по (М-1)-й разряды, соответствующих N внутренних шин запросов IZ1, IZ2, …, IZN, одноименных номеру канала,

причем все М разрядов приоритета каждой из N внутренних шин запросов IZ1, IZ2, …, IZN соединены с соответствующими одноименными входами одноименных N блоков анализа готовности каналов 8₁, 8₂, …, 8_N, а также каждый i-й разряд (i=0, 1, …, (М-1)) приоритета каждой из N внутренних шин запросов IZ1, IZ2, …, IZN соединен с соответствующим входом одноименного i-го элемента из первой группы из М элементов ИЛИ 6₀, 6₁, …, 6_(M-1), при этом выходы элементов ИЛИ, начиная с первого 6₁ до М-го 6_(M-1), соединены с первыми прямыми входами одноименных элементов второй группы из (М-1) элементов запрета И с инверсными входами 7₁, 7₂, …, 7_(M-1), у которых инверсные входы j-го элемента 7_j (j=1, 2, …, (М-1)) соединены с соответствующими выходами k элементов (k=0, 1, …, (j-1)) первой группы из М элементов ИЛИ 6₀, 6₁, …, 6_(M-1),

одноименные входы М, (М+1), …, (2М-2) каждого из N блоков каналов анализа готовности каналов 8₁, 8₂, …, 8_N соединены между собой, а также подключены к соответствующим выходам (М-1) элементов, начиная с первого до (M-1)-го элемента, из второй группы элементов И с инверсными входами 7₁, 7₂, …, 7_(M-1),

выходы элементов И второй группы из (М-1) элементов запрета И с одним инверсным входом 7₁, 7₂, …, 7_(M-1) являются соответствующими (М-1) выходами OZ1, OZ2, …, OZ(M-1) второй группы из М внешних выходов указателей высшего ранга приоритета в канале, а младшим нулевым выходом OZ0 является выход элемента ИЛИ 6₀,

в каждом из N блоков 8₁, 8₂, …, 8_N анализа готовности каналов (М-1) входов блока, начиная с первого входа до (М-1) входа, соединены с соответствующими первыми входами одноименных элементов И из третьей группы из (М-1) элементов И 9₁, 9₂, …, 9_(M-1) блока, у которых вторые входы соединены с соответствующими входами блока, начиная с М-го входа до (2М-2)-го входа, а выходы третьей группы из (М-1) элементов И 9₁, 9₂, …, 9_(M-1) блока и 0-й вход блока соединены с соответствующими входами элемента ИЛИ 10, выход которого является выходом соответствующего блока каналов анализа готовности каналов 8₁, 8₂, …, 8_N, которые подключены к N разрядам внутренней шины готовности каналов К1, К2, …, КN и соответствующим входам второго элемента ИЛИ 11, выход которого является флагом готовности F,

причем выходы первых (N-1) блоков каналов анализа готовности каналов 8₁, 8₂, …, 8_(N-1), начиная с первого блока до предпоследнего (N-1) блока, также соединены с первыми прямыми входами соответствующих (N-1) элементов 13₁, 13₂, …, 13_(N-1) четвертой группы из элементов запрета И с одним инверсным входом, а выход последнего N-го блока каналов анализа приоритета 8_N соединен со вторым инверсным входом (N-1) элемента 13_(N-1) четвертой группы из элементов запрета И с одним инверсным входом,

выходы всех элементов второй группы из (N-2) элементов ИЛИ 12₁, 12₂, …, 12_(N-2) соединены со вторыми инверсными входами соответствующих одноименных первых (N-2) элементов 13₁, 13₂, …, 13_(N-2) четвертой группы из элементов запрета И с одним инверсным входом, а также первые и вторые входы всех (N-2) элементов 12₁, 12₂, …, 12_(N-2) из второй группы элементов ИЛИ подключены соответственно к первым прямым и ко вторым инверсным входам соответствующих (N-2) элементов И 13₂, 13₃, …, 13_(N-1), начиная со второго элемента до последнего (N-1) элемента четвертой группы элементов запрета И с одним инверсным входом,

выходы четвертой группы элементов запрета И с одним инверсным входом 13₁, 13₂, …, 13_(N-1) являются первыми (N-1) внешними выходами QU1, QU2, …, QU(N-1) из первой группы внешних выходов указателей канала старшего приоритета, а старшим N-м внешним выходом QUN является выход последнего N-го блока анализа готовности каналов приоритета 8_N.