Устройство для обслуживания групповых приоритетных запросов — SU 1753473 (original) (raw)
союз со СОЦИАЛИ РЕСПУБЛИФ ТСКИХческих ЗА Р 9(51) СА Ни ОБ ЬСТВ ВТОРСКОУУ А,А.Шилов ССР84. ССР. ЛУЖИ ВАНИ ЫХ ЗАПРО ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(56) Аа горское свидетельствоМ 1091163, кл. 6 06 Р 9/46, 19Авторское свидетельствоМ 1297047, кл. 0 06 Р 9/46, 19(54) УСТРОЙСТВО ДЛЯ ОБСГРУППОВЫХ ПРИОРИТЕТН СОВ57) Изобретение относится к вычислительной технике и может быть использовано вмногоканальных системах с приоритетным Изобретение относится к вычислительной технике и может быть использовано в многоканальных системах с приоритетным обслуживанием абонентов.Известно устройство приоритета; содержащее два регистра, два группы элементов И и группу элементов ИЛИ.Недостаток данного устройства - низкое быстродействие.Наиболее близким по технической сущности к изобретению является устройство для обслуживания групповых приоритетных запросов, содержащее два регистра, две группы элементов И, группу блоков элементов И, первую группу элементов ИЛИ, причем группа запросных входов устройства соединена с группой информационных входов первого регистра, прямые выходы первого регистра соединены с первыми входами соответствующих элементов И первой группы выходы элементов И первой группы соединены с информационными входами второго регистра, управляющие обслуживанием. Цель изобретения- "повышение быстродействия устройства. Новым в устройстве является использование группы элементов ИЛИ-НЕ, а в каждом узле выбора запросов, кроме первого; третьего группы элементов И. Устройство обеспечивает для каждого свободного канала выбор приоритетного запроса с учетом выделенных запросов предыдущим свободным каналам. При этом время выбора запроса зависит от распределения сигналов готовности процессоров, Минимальное время затрачивается, когда от первого до назначаемого процессора отсутствуют сигналы их готовности, 1 ил,входы блоков элементов И группы соедйнены с опросным входом устройства, выходы блоков элементов И группы являются группой выходов устройства, тактовый вход устройства соединен с вторыми входами элементов И первой группы.Кроме того, устройство содержит регистр готовности каналов, единичные входы которого являются группой входов готовности устройства, элемент задержки, руппу узлов выбора запросов йвторую группу элементов ИЛИ, выходы элементов ИЛИ первой группы подключены к нулевым входам соответствующих разрядов первого регистра, опросный вход устройства через элемент задержки подключен к входам сброса разрядов второго регистра, выходы блоков элементов И группы подключены к входам соответствующих элементов ИЛИ второй группы, выходы которых соединены с входами сброса соответствующих разрядов регистра готовности каналов, каждый узел выбора запросов группы, кроме первого, со55 держит две группы элементов И и шифратор, первый уэлен выбора запросов содержит группу элементов И и шифратор, выходы элементов И первой группы узлов выбора запросов группы, начиная с второго, и выходы элементов И группы первого узла выбора запросов группы подключены к входам шифратора своего узла, прямой выход 1-го разряда второго регистра соединен с первым входом 1-го элемента (где 1= 1, . и, и число запросов) группы первого узла выбора запросов группы и с первым входом 1-го элемента И первой группы узлов выбора запросов группы, начиная с второго, инверсный выход 1-го разряда второго регистра соединен с соответствующим. входом (1+ 1)-го и всех последующих элементов И группы первого узла выбора запросов группы и с соответствующим инверсным входом 1-го элемента И первой группы всех узлов выбора запросов группы, начиная с второго, первый выход регистра готовности каналов соединен с соответствующими входами элементов И группы первого узла выбора запросов группы, выходы регистра соединены с соответствующими прямыми входами элементов И второй группы одноименного узла выбора запросов, выход 1-го элемента И первой группы каждого узла выбора запросов группы, начиная с второго, соединен с соответствующим прямым входом 1-го элемента И второй группы и с соответствующими инверсными входами (1 + 1)-го и всех последующих элементов И второй группы своего узла выбора запросов группы, выход каждого элемента И второй группы узлов выбора запросов группы, начиная с второго, соединен с соответствующими инверсными входами одноименных элементов И первой группы всех последующих узлов выбора запросов группы, выходы шифратора 1-го узла выбора запросов группы соединены с группой входов 1-го блока элементов И группы, выходы 1-го элемента И группы первого узла выбора запросов группы и 1-х элементов И второй группы узлов выбора запросов группы, начиная с второго соединены с входами 1-го элемента ИЛИ первой группы,Устройство обеспечивает для каждого свободного канала выбор приоритетного запроса с учетом выделенных запросов предыдущим свободным каналам, Для каждого канала формируется двоичный код номера абонента, принимаемого на обслуживание,Недостатком устройства является низкое быстродействие, обусловленное большой логической глубиной за счет применения в каждом узле выбора запроса,10 15 20 25 30 35 40 45 50 начиная с второго, последовательно соеди-. ненных двух групп элементов И.Общее время цикла работы устройства определяется временем переходных процессов в последовательно соединенных узлах выбора запросов.Если число каналов равно К, то это время можно оценить по выражениюТ = о + тг(К - 1),где 11 = т иб - время задержки элемента И первого узла 5 выбора запроса;тг =ги 7+ таз - суммарное время задержки элеменгами И каждого из остальных узлов выбора запроса.Т = т и 6 + 2 ти (К - 1) = (2 К - 1) 7 и . (1) Из выражения (1) видно, что время работы устройства определяется только структурой узлов выбора запроса и не зависит от размещения сигналов готовности процессоров в регистре.Пусть вычислительная система содержит К каналов, сигналы готовности от которых поступают в соответствующие разряды регистра. При этом возможны случаи, когда в 1-м разряде данного регистра( = 2, 3, К) зафиксирован сигнал готовности от 1-го процессора, а во всех предыдущих разрядах с 1-го по (1 - 1)-й сигналов готовности от соответствующих процессоров нет,В данном случае код номера заявки появляется на выходе шифратора 1-го узла выбора запроса после последовательного прохождения через узлы с первого по (1 -1)-й сигналов разрешения передачи информации с выходов регистра заявок,Таким образом, выбор запроса на обслуживание свободному каналу выполняется по существу одинаково, как и для первого канала. Такое положение свидетельствует о непроизводительных затратах времени, что обусловливает низкое быстродействие устройства,Приведем оценку непроизводительных затрат времени.Пусть К=4,При ненулевом кодах в регистре число различных комбинаций размещения сигналов готовности составляет Йо = 2 - 1 при К=4, Но=15,Среди этих комбинаций возможны следующие ситуации,При наличии сигнала готовности от второго процессора:010001 010110.0111от третьего процессора:(2) идно, что при больы К можно принять Из выраших значени ния (2) величи 2 да 30)иго 2 (3Я (2 м 1 )2т.е. при непрерывном потоке заявок и с налов готовности процессоров, когда имеется равновероятная воэможность 35 появления сигналов готовности процессоров в указанных комбинациях, быстродействие устройства снижается в два раза;Целью изобретения является повышение быстродействия за счет снижения не производительных затрат времени на поиск свободного процессора.Укаэанная цель достигается тем, что в устройство для обслуживания групповых . приоритетных запросов, содержащее груп пу блоков элементов И, выходы которых являются информационными выходами устройства, и группу узлов выбора запро- сов, каждый из которых, кроме первого, включает в себя две группы элементов И и 50 шифратор, первый узел выбора запросов содержит группу элементов И и шифратор, причем выходы элементов И первой группы узлов выбора запросов, начиная с второго, и выходы элементов И группы первогоузла 55 выбора запросов группы подключены к входам шифратора своего узла, прямой 1-й вход группы запросных входов устройства (1 = 1, 2, , и, п - число запросов) соединен с пер 00100011 и от четвертого процессора: 0001 Отсюда общее число таких комбинаций 5 составляетЕсли регистр заявок содержит и разря= ув, то количество ненулевых комбинаций сигналов запросов составляет 10 11 =2 оТогда число комбинаций сигналов зая- вок и готовности процессоров в рассматриваемой ситуации определяется по выражению .: 1531 = М . М 1 = (2" - 1 Х 2" " - 1),общее количество комбинаций этих сигналовравноЯо = (2" - 1 Х 2 - 1) Если и= К то 20 Яо=(2 -1 Х 2 -1) =(2 К)с Я = (2 к - 1)(2 - 1) к К вым входом 1-го элемента И группы первого узла выбора запросов и с прямыми входами 1-х элементов И первой группы узлов выбора запроса, начиная с второго, инверсный 1-й вход группы запросных входов устройства соединен с (1 + 1)-ми входами (1 + 1)-го и всех последующих элементов И группы первого узла выбора запросов группы, выход 1-го элемента И группы которого соединен с первым инверсным входом 1-х элементов И первой группы всех узлов выбора запросов группы, начиная с второгд, первый вход, группы входов готовности процессоров устройства подключен к управляющим входам элементов И группы первого узла выбора , запросов группы, второй и последующие входы группы входов готовности процессоров устройства соединены с прямыми управляющими входами элементов И второй группы одноименных узлов выбора запросов группы, выход 1-го элементов И первой группы каждого узла выбора запросов группы, начиная с второго, подключен к прямому входу 1-го элемента И второй группы и к соответствующим инверсным входам (1+ 1)- го и всех последующих элементов И второй группы своего узла выбора запросов группы, выход каждого элемента И второй группы узлов выбора запросов группы, начиная с второго, подключен к соответствующим инверсным входам одноименныхэлемвнтов И первой группы всех последующих узлов выбора запросов группы, выходы шифратора каждого узла выбора запросов группы соединены с группой информационных входов одноименного блока элементов И группы, управляющие входы которых подключены к опросному входу устройства, введены группа элементов ИЛИ-НЕ, а в каждый узел выбора запросов группы, начиная с второго, третья группа элементов И, причем )-й вход группы входов готовности процессоров устройства 0 - 1, 2, , К - 1, К - число процессоров) соединен с )-ми входами )-го и последующих элементов ИЛИ-НЕ группы и с первыми управляющими входами элементов И третьей группы 0+ 1)-го узла выбора запросов группы, выход)-го элемента ИЛИ-НЕ группы подключен к вторым управляющим входам элементов И третьей группы и инверсным управляющим входам элементов И второй группы 0+ 1)-го узла выбора запросов. группы, прямой 1-й вход группы запросных входов устройства соединен с первыми прямыми входами 1-х элементов И третьих групп каждого узла выбора запросов группы, начиная с второго, инверсный у -й вход (- 1, 2, ., и - 1) группы запросных входов устройства подключен к10 15 20 сигналов, 50При этом на выходах всех элементов ИЛИ-НЕ 7 устанавливается нулевые сигналы, которыми закрыты элементы И 6 во всех узлах 1, начийая с второго, и открыты поинверсным управляющим входам элементы .И 5.Для первой единицы выбирается абонент из совокупности сигналов на входах 9, а для последующих возбужденных входов 10 - с учетом выделенных запросов для( у + 1)-ым прямым входам (у + 1)-х и последующих элементов И третьих групп в каждом узле выбора запросов группы, начиная с второго, выходы элементов И третьей группы в каждом узле выбора запросов группы, начиная с второго, соединены через монтажное ИЛИ с выходами одноименных элементов И второй группы своего узла выбора запросов группы. На чертеже показана структурная схема устройства, Устройство содержит узлы 1 выбора запросов, первый из которых включает в себя группу элементов И 2 и шифратор 3, а последующие - первую группу элементов И 4, вторую группу элементов И 5 и третью группу элементов И 6, группу элементов ИЛИНЕ 7, группу блоков 8 элементов И, группу запросных входов 9 устройства, группу входов 10 готовности процессоров устройства, опросный вход 11 устройства и группу информационных выходов 12 устройства,Устройство работает следующим образом,Пусть в системе каждый из абонентов в соответствии с установленным для него приоритетом закреплен за соответствующим входом 9 так, что наивысшим приоритетом обладает абонент с меньшим номером входа 9 устройства. Сигналы готовности от процессоров подаются на соответствующие входы 10.В определенные моменты времени операционной системой цикле работы устройства производится подача потенциальных сигналов запросов в парафазном коде на входы 9 и потенциальных сигналов готовности процессоров по входам 10. Одновременно по входу 11 подается потенциальный сигнал опроса.Для каждого из свободных каналов (процессоров), от которых поступили сигналы готовности по входам 10, последовательно соответствующим узлом 1 выбора запросов производится выбор приоритетного запроса из совокупности зафиксированных сигналов запросов на входах 9, когда в цикле опроса перед крайней слева единицей кода на входах 10 нет нулевых 30 35 40 45 предыдущих свободных каналов, Для этого в каждом узле 1, начиная с второго, выделение абонента обеспечивается элементами И 5. Исходной информацией для этих элементов являются выходные сигналы элементов И 4, посредством которых исключаются из анализа выбранные ранее сигналы предыдущими узлами 1, Так как единичный сигнал на выходах элементов И 5 формируется только в одном из них при наличии единичных сигналов на прямых входах элементов И 5, то номер возбужденного элемента И 5 однозначно соответствует номеру абонента, от которого на соответствующем входе 9 зафиксирован запрос, Унитарный код (имеющий единицу на одной из его позиций) подается на шифратор 3, преобразующий его в двоичный код номера абонента, поступающий на входы соответствующего блока 8 элементов И.По сигналу опроса, присутствующему на входе 11, в группах выходов 12 формируются сигналы номеров абонентов, поступающих на обслуживание в назначенные свободные каналы.Работа устройства, когда на нескольких подряд следующих входах 10 отсутствуют единичные сигналы, начиная с первого входа, заключается в следующем,Пусть на входах 10 зафиксирован нулевой код от(К)-го процессоров, на последнем имеется единичный сигнал готовности 0001, а на входах 9 имеется запрос от второго абонента,При этом на выходах всех элементов ИЛИ-НЕ 7 формируются единичные сигналы, которыми закрыты по инверсным управляющим входам элементы И 5 во всех узлах 1, начиная с второго, и открыты в этих же узлах по вторым управляющим входам элементы И 6. Одновременно нулевыми сигналами с входом 101, 10 кзакрыты элементы И 2 и 6 в узлах 1 с первого по (К - 1)-й, В К-м узле 1 открыты единичным сигналом с входа 10 к элементы И 6, Эти элементы, как в других узлах 1 (элементы И 2 в первом узле, элементы И 6 в остальных), подключены к парафазным входам 9 по приоритетной схеме.В рассматриваемом примере в узле 1 к нулевым сигналом с прямого входа 9 закрыт элемейт И 61, а единичным сигналом с инверсного входа 91 открыты элементы с И с Ъ по 6 п. Так как на прямом входе 92 имеется единичный сигнал, а на инверсном входе 92 - нулевой, элемент И 62 открыт, а остальные элементы И 6 в узле 1 к закрыты. При этом на выходах элементов И 6 формируется унитарный код 0100, поступающий на входы шифратора 3. На выходе шифратоТ 1 = (2 к - 1)2(2 К - 1) т, (5) где Т 2 - среднее время работы предложен ного устройства,Исходя из анализа количества комбинаций и времени преобразования кодов для каждой из них, время Т 2 определяется по выражению 30 к - гТг=(Е(2-1)(2 К)1+2 к "-1)+ , 21=1. 2) ти (б) 35где первое слагаемое отражает количествапоследовательно включенных схем И (И 2, И4, И 5), участвующих в преобразованиях кода запросов, когда имеется единичный сигнал готовности от первого процессора. При 40этом общее число комбинаций сигналов готовности составляет 2 - 1,Второе слагаемое соответствует общему числу последовательно включенных схемИ (И б, И 4, И 5), участвующих в преобразовании кода запросов, когда имеются нулевые сигналы от первого, первого и второгои т.д. сигналов готовностиПодставляя выражения (6), (5) в (4) получим 50Ю - . (7) К - 22" - 1 + Г 2 Из выражения (7) видно, ч быстродействии обеспечивает числе каналов. Так, при числе быстродействие предлаженна . в 1,38 выше быстродействия то вцигся при л каналов га устро прототип ышв юбом К=4 ЙСТВЭа. ра 3 устанавливается двоичный код номера второго абонента, поступающий через блок 82 элементов И на выходы 122 устройства.Таким образом, на выходах 12 единичные сигналы появляются последовательно 5 . по мере завершения переходных процессов, начиная с выходов 12 с, если имеются сигналы готовности на входах 101 и т.д., либо начиная с выходов 12 ь когда на входах 10 с, 101-1 имеются нулевьсе сигналы, а на 10 входе 101 - единичный.Проведем сравнительную оценку прототипа и предложенного устройства по быстродействию.Выигрыш в быстродействии можно оп ределить по соотношениюТ(4) где Т 1 с учетом выражения (1) и общего числа. комбинаций запросов и сигналов готовно сти процессора в соответствии с выражением (2) равно Формула изобретения Устройство для обслуживания групповых приоритетных запРосов, содержащее группу блоков элементов И, выходы которых являются инф 6 рмацианньсми выходами устройства, и группу узлов выбора запросов, каждый из которых, кроме первого, содержит две группы элементов И и шифратор, первый узел выбора запросов содержит группу элементов И и шифратор, причем выходы элементов И первой группы узлов выбора запросов группы, начиная с второго, и выходы элементов И группы первогр узла выбора запросов группы подключены к соответствующим входам шифратора своего узла, прямой 1-й вход группы запросных входов устройства ( = 1, 2, , п, и - число запросов) соединен с первым входом 1-го элемента И группы первого узла выбора запросов и с прямыми входами 1-х элементов И второй группы узлов выбора запроса группы, начиная с вТорого, инверсный 1-Й вход группы запросных входов устройства соединен с ( + 1).ми входами (1 + 1)-го и всех последующих элементов И группы первого узла выбора запросов группы, выход 1-го элемента И группы которого соединен с первыми инверсными входами 1-х элементов И второй группы всех узлов выбора запросов группы, начиная с второго, первый вход группы входое готовности процессоров устройства подключен к управляющим входам элементов И группы первого узла выбора. запросов группы, второй и последующие входы групды входов готовности процессоров устройства соединены с прямыми управляющими входами элементов И первой группы одноименных узлов выбора запросов группы, выход 1-го элемента И второй группы каждого узла выбора запросов группы, начиная с второго, подключен к прямому входу 1-го элемента И первой группы и к соответствующим инверсным входам (1 + 1)-го и всех последующих элементов И первой группы своего узла выбора запросов, группы, выход каждого элемента И первойгруппы узлов выбора запросов группы, начиная с второго, подключенк соответствующим инверсным входам одноименных элементов И второй группы всех последующих узлами выбора запросов группы, выходы шифратора каждого узла выбора запросов группы соединены с группой информационных входов одноименного блока элементов И группы, управляющие входы которых подключены к опросному входу устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены группа элементов ИЛИ-НЕ, а в каждый узел выбора запросов группы, начиная с второго, введе1753473 12 Составитель А,Ганитултнактор И,Шмакова Техред М.Моргентал Корректор вска аказ 2769 ВНИИП Тираж Подписноеосударственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 роизводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина,на третья группа элементов И, причем )-й вход группы входов готовности процессоров устройства 0 = 1, 2,;, К - 1, К - число процессоров) соединен с )-ми входами )-го и всех последующих элементов ИЛИ-НЕ 5 группы и с первыми управляющими входами элементов И третьей группы Д + 1)-го узла выбора запросов группы, выход )-го элемента ИЛИ-НЕ группы подключен к вторым управляющим входам элементов И 10 третьей группы и к инверсным управляющим входам элементов И первой группы О + 1)-го узла вцбора запросов группы, прямой 1-й вход группы запросных входов устройства соединен с первыми прямыми 15 входами 1-х элементов И третьих групп каждого узла выбора запросов группы, начиная с второго, инверсный у-й вход(у- = 1, 2, , п - 1) группы запросных входов устройства подключен к(у-+ 1)-м прямым входом (у+ 1)-х и последующих элементов И третьей группы каждого узла выбора запросов группы, начиная с второго, выходы элементов И третьей группы каждого узла выбора запросов группы, начиная с второго, соединены через монтажное ИЛИ с выходами одноименных элементов И первой группы своего узла выбора запросов группы,