Устройство для исследования путей в графе

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН 119) И 11 315 И 0 06 Г 15/20 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ ИЗОБРЕТЕНИЯ. К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) 1. Авторское свидетельство СССР М 1011038, кл. 0 06 Г 15/20, 1980.2. Авторское свидетельство СССР М 1035066, кл, 0 06 Р 15/20, 1981 (прототип).(54)(57) 1. УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПУТЕЙ В ГРАФЕ, содержащее матрицу формирователей дуг, выходы 1-го формирователя дуги которой через 1 -й элемент ИЛИ группы соединены с.первым входом ) -го элемента И первой группы, генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого из которых соединен с входом вычитающего счетчика, выход которого соединен с входом дешифратора нуля и с входом первого дешифратора состояния, 1-й выход которого соединен с первым входом 1 -го элемента И второй группы непосредственно, а с первым входом 1 -го элемента И третьей группы- через соответствующий элемент задержки, выход 1 -го элемента И третьей группы черезсоответствующий регистр соединен с вторыми входами 1 -х элементов И цервой и второй групп, выход первого из которых соединен с соответствующим входом узла выбора максимума, числовой выход которого соединен с первым входом сумматор)ра, выход ) -го элемента И второй группы соединен с соответствующим входом элемента ИЛИ, выход которого соединен с вторым входом сумматора, выход которого соединен с вторыми входами элементов И третьей группы,прямой выход дешифратора нуля соеди"нен с вторым входом первого элемента И, третий вход которого являетсявходом пуска устройства, а инверсный выход дешифратора нуля соединенс вторым входом второго элемента И,выход которого через суммирующийсчетчик соединен с входом второгодешифратора состояния,-й выходкоторого соединен с первым входом-го элемента И четвертой группы,вторые входы которых подключены квыходу 1 -го триггера группы, о тл и ч а ю ц е е с я тем, что, сцелью сокращения аппаратурных затрат, оно содержит пятую группу элементов И, первые входы которыхподключены к соответствующим поразрядным выходам узла выбора максимума, а вторые входы объединеныи подключены к инверсному выходудешифратора нуля, выход ) -го элемента И пятой группы соединен свходом 1 -го триггера группы, выход-го элемента И четвертой группы и 1 -й выход первого дешифратора состояния соединены соответственно с первыми и вторымИ входамиопроса формирователей дуг ) -й строки матрицы.2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что формирователь дуги содержит триггер и элемент И-ИЛИ, первый и второй входыкоторого подключены соответственнок первому и второму входам опросаформирователя дуги, третий входэлемента И-ИЛИ подключен к выходутриггера, а выход элемента И-ИЛИявляется выходом формирователядуги, 1076909Изобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графов, а также при аппаратнсй реализации в специализированных процессорах макрокоманды определения максимальных критических путей в графах.Известно устройство для исследования путей в графах, содержащее матрицу и и триггеров Формирования дуг графа и генератор тактовых импульсов, выход которого соединен с первым входом элемента И, второй вход которого является входом устрой стна, по числу триггеров формирова ния дуг: элемента И, по числу столбцов матрицы элементы ИЛИ, элементы задержки, регистры первые, вторые и третьи группы элементов И, группу элементов ИЛИ, многовходоной сумматор, узел выбора максимума, дешифратор, элемент НЕ и реверсинный счетчик 1 .Недостатком данного устройства являются ограниченные функциональ ные воэможности из-за невозможности индентификации вершин графа, образующих максимальный критический путь. О Наиболее близким к предлагаемому является устройство для исследования путей н графах содержащее матрицу формирователей дуг, выходы -го формирователя дуги которойчерез-й элемент ИЛИ группы соеди. 35 иены с первым входом 1 -го элемента И первой группы, геиератор тактовых импульсов, ныхад которого соединен с первыми нходами первого и второго элементов И, выход первого из которых соединен с входом вычитаю- щего счетчика, выход которого соединен с входом дешифратора нуля и с входом первого дешифратора состоя-.ния,-й выход которого соединен/с первым входом-го элемента И второй группы непосредственно, а с первым входом 1 -го элемента И третьей группы через саотнетстнующий элемент задержки, выход-га элемента И третьей группы черезсаотнетствующий регистр соединен с вторыми входами-х элементов И первой и второй группы, выход первого из которых соединен с соотгС ветствующим входом узла выбора максимума, числовой выход которого сое динен с первым входом сумматора, выход-го элемента И второй группы соединен с соответстнующим входом элемента ИЛИ, выход которого соеди нен со вторым входом сумматора, выход каторога соединен с вторыми вха. дами элементов И третьей группы, прямой выход дешифратора нуля соединен с вторым входом первого эле мента И, третий вход которого является входом пуска устройства, а инверсный выход дешифратора нуля соединен с вторым входом второго элемента И, выход которого через суммирующий счетчик соединен с входом второго дешифратора состояния, 1-и выходкоторого соединен с первым входом-го элемента И четвертой группы,вторые входы которых подключены квыходу 1 -го триггера группы,Недостатком известного устройства является низкая надежность ввидубольших аппаратных затрат,Цель изобретения - сокращение аппаратурных затрат.Укаэанная цель достигается тем, чта устройство для исследования путей в графах, содержащее матрицу Формирователей дуг, выходы-го Формирователя дуги которой через-ый элемент ИЛИ группы соединены с перным входом-го элемента И первой группы, генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого из которых соединен с входам вычитающего счетчика, выход которого соединен с входом дешифратора нуля и с входом первого дешифратара состояния,-й выход которого соединен с первым входом 1 -го элемента И второй группы непосредственна, а с первым входом-го элемента И третьей группы через соответ ствующий элемент задержки, выход 1-го элемента И третьей группы через соответствующий регистр соединен с вторыми нходами-х элементов И первой и второй групп, выход первого из которых соединен с соответстнующим входом узла выбора максимума, числовой выход которого соединен с первым входом сумматора, выход-го элемента И второй группы соединен с соответствующим входом элемента .ЛИ, выход которого соединен с втаоым входам сумматора, выход кото. рого соединен с вторыми входами эле ментов И третьей группы, прямой выход дешифратора нуля соединен с вторым входом первого элемента И, третий вход которого является входом пуска устройства, а инверсный выход дешифратара нуля соединен с вторым входам второго элемента И, вы ход котооого через суммирующий счетчик соединен с входом второго дешифоатора состояния,-й выход которого соединен с перным входом "-го элемента И четвертой грУппы, вторые входы которых подключены к выходу 1 -го триггера группы, содержит пятую группу элементов И, первые входы которых подключены к соответствующим поразрядным выходам узла ,выбора максимума, а нторые входы,объединены и подключены к инверсному выходу дешифратора нуля, выход1 -го элемента И пятой группы, соединенсвходом 1 -го триггера группы,выход 1 -го элемента И четвертой группы и-й выход первого дешифраторасостояния соединены соответственнос первыми и вторыми входами опроса,формирователей дуг д-й строки матрицы. Формирователь дуги содержит триггер и элемент И-ИЛИ, первый и второйвходы которого подключены соответственно к первому и второму входам опроса Формирователя дуги, третий входэлемента И-ИЛИ подключен к выходутриггера, а выход элемента И-ИЛИявляется выходом формирователя дуги.На фиг. 1 приведена блок-схемапредЛагаемого устройства; на фиг, 2 то же, узел выбора максимума,Устройство содержит матрицу 1формирователей дуг, группу 2 элементов ИЛИ, группу 3 элементов И,элементй 4 - 4 п задержки, регистры 5 - 5 п, группу 6 элементов И,группу 7 элементов И, элемент ИЛИ 8,сумматор 9, узел 10 выбора максимума, группу 11 элементов И, группу 12триггеров, группу 13 элементов И,генератор 14 тактовых импульсов, элементы И 15 и 16, вычитающий счетчик 17, дешифратор 18 состояния, суммирующий счетчик 19, дешифратор 20состояния, вход 21 пуска и дешифратор 22 нуляМатрица 1 формирователей дуг содержит формирователи 23дуг. Формирователи 23 дуг содержатвходы 24 и 25 опроса, триггеры 26.и элементы И-ИЛИ 27, Узел 10 выборамаксимума содержит элементы ИЛИ-НЕ 28,поразрядные блоки 29 переноса, выходы 30 и 31 и входы 32, Поразрядные блоки 29 переноса содержат группы 33 элементов И и ИЛИ, Группы 33элементов И и ИЛИ содержат элементы ИЛИ 34 и элементы И 35,Узел 10 работает следующим образом. Входы 32 подключены к выходамсоответствующих элементов И 7, выходы 30 соединены с входом сумматора 9, а. выходы 31 соединены с одними из входов соответствующего элемента И 11. В первый момент анализируются старшие разряды кодов чисел.Если хотя бы один из старших разрядов кодов равен 1, то на выходеэлемента ИЛИ-НЕ 28 сформируетсянулевои сигнал, при этом, если старший разряд-го числа (1 = 1 п)равен О, то все разряды 1 -го числаНе проходят через элементы И 35.-й группы первого узла 29 переноса. Если старший разряд 1 -го числаравен 1, то все разряды 1 -го числапроходят через элементы И 35 1 -йгруппы первого узла 29, переноса. Если старшие разряды всех кодовчисел равны О, то на выходе элемента ИЛИ-НЕ 28 сформируется "1",которая дает разрешение на прохождение всех кодов чисел через эле 5 менты И 35 первого узла 29 переносаТаким образом, на выходе элемента И 35 первого узла 29 переноса формируются разряды кодов чисел,начиная со второго по Щ-й разряды.1 О Вторым элементом ИЛИ-НЕ 28 поразрядного узла 29 переноса анализируются вторые по старшинству разрядычисел таким же образом, как и старших разрядов, и т.д. Таким образом.код номера экстремального числаполучается путем совпадения всехсигналов запрета, сформированных вкаждом поразрядном узле 29 переноса, На выходах 30 получается обратный код экстремального числа.Устройство работает следующимобразом,Первоначально в матрицу 1 заносится информация о топологии моделируемого графа (сети), При этомтриггеры 26, моделирующие ветвиграфа, устанавливаются в единичноесостояние. Соответствующий триггер 26 определяется пересечениемстроки с номером, равным номеруЗО начального узла моделируемой ветви,и столбца с номером, равным номеру ее конечного узла. В регистры 5заносятся коды чисел, соответствующие весам вершин ,В счетчик 17 за.135 носится код числа вершин в моделируемом графе, а счетчик 19 находится в нулевом состоянии. При этомисходная информация о графе заносит.ся в модель в порядке, при котором4 О наименьший номер (первый) имеетначальная вершина, а наибоЛьшийконечная вершина. В единичное состояние устанавливается также триггер 12, соответствующий начальной45 вершине, Такое занесение исходнойинформации позволяет использоватьдля расчета максимальных путей процедуру динамическоего программирования, по которой для каждой-йвершины вычисляется 1.Р, (.+ ча кр," ,Р 1 1 )1где д ; - элемент матрицй связности, равный О, если нет дуги из 1 -йвершины в-ю, и равный 1, еслитакая дуга есть.С появлением пускового сигналана входе 21 устройства элемент. И 16обеспечивает прохождение счетных .импульсов с выхода генератора 14на вход счетчика 17, так как на втором входе элемента И 16 будет высобО кий потенциал с выхода дешифратора 22 нуля.С выхода счетчика 17 код поступает на вход дешифратора 18, врезультате чего на-м его выходепоявится высокий потенциал, где5 10 15 20, 25 30 35 40 45 50 55 60 65 в ,максимальное число вершин в моделируемом графе, Этот высокий потенциал подается на вход элемента 4 и задержки, первый вход элемента И б одноименного столбца,а также первые входы элементон И-ИЛИ 27 одноименной строкиматрицы. В том случае, если триггеры 26 в данной строке находятсяв единичном состоянии, то черезэлементы И-ИЛИ 27 и ИЛИ 2 высокийпотенциал с выходов этих триггеровподается на первыевходы соответствующих элементов И 7, что в своюочередь обеспечивает подачу кодовс регистров 5 на входы узла 10выбора максимума. Узел 10 обеспечивает выбор из поступивших на еговход кодов максимального числа иподачу его на первый вход сумматора 9. Одновременно на нторой входсумматора 9 подается код с выходаизбранного регистра 5 п через соответствующий элемент И бп и элемент ИЛИ 8. Результат с выхода сумматора 9 через открытую группу 3элементов И (к этому моменту времени на управляемом входе элемента И 3появится высокий потенциал с выходаэлемента 4 задержки) поступит навход соответствующего регистра 5На этом этап формирования кода максимального пути для однойотдельной вершины заканчивается.Далее на вход счетчика 17 поступаеточередной импульс, в результате чегосодержимое счетчика 17 уменьшаетсяна Единицу, поэтому на выходе дешифратора 18 возбуждается очередная(О)-я выходная шина, и процессФормирования. величины максимальногопути для очередной вершины графабудет происходить аналогично.Вычислительный процесс продолжается до тех пор, пока на счетчике 17не появится нулевой код, в результате чего появляется низкий потенциална втором входе элемента И 16, и подача счетных импульсов на вход счетчика 17 прекращается,Одновременно высокий потенциалс выхода дешифратора 22 обеспечивает подачу сигналов с выхода генератора 14 через второй элемент И 15на вход счетчика 19, выход которогоподсоединен к входу дешифратора 20,Выходные шины дешифратора 20 подсоединены к одноименным управляемымнходам элементов И 13. Если при этомсоответствующий триггер 12 находится н единичном состоянии, то высокийпотенциал с его выхода через одноименный элемент И 13 поступает науправляемые входы элементов И-ИЛИ 27одноименной строки матрицы и поступает далее через группу 2 элементов ИЛИ на те управляемые входы группы 7 элементов И, которым в данной строке матрицы соответствует дуга графа, т,е. единичное состояние триггера 26. Наличие высоких потенциалов на управляемых входах группы 7 элементов И обеспечивает поступление кодов с выходов регистра 5 на нходЬ узла 10 выбора максимума, который в свою очередь обеспечивает выбор максимального из поступивших кода, при этом соответствующие триггеры 12 Перебрасываются н единичное состояние импульссй, проходящим через одноименный элемент И 11 и т.д, Процесс поиска максимального критического пути заканчивается при дости жении показания счетчика 19 значениямаксимального числа вершин в моделируемом граФе.Работу устройства при определении, максимального критического пути нф графе поясним на следующием примере.Пусть задан граф О, описываемый матрицей связности Аи вектором Т весов вершин. О 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 О 0 0 0 0 0 1 О 0 0 0 0 0 1 О 0 0 0 0 0 0 т =2, 3; 4; 3; 4 5 23 где элементыО,если нет дуги из-й вершины Я=В 4-юф 1, если есть дуга из 1 -й вершины в-ю 1п,п = 7, нес (время) 1 -й вершины. После занесения исходной информации на регистрах 5 будут коды, соответствующие весам вершин 1, а на счетчике 17 - код числа 7. Кроме того, н нулевом состоянии будет счетчик 19 и триггеры 12, кроме триггера 12, который находится в единичном состоянии. С приходом пускового сигнала на вход 21 устройства счетные импульсы с выхода генератора 14 поступают на вход нычитающего счетчика 17 через элемент И 16. С приходом первого импульса на счетчике 17 зафиксируется код числа б, поэтому на выходе дешифратора 18 возбудится шестая выходная шина и высокие потен циалы подаются на управляемые входы элементов И бб,.элементов 46 задержки, а также элементов И-ИЛИ 276, 276, ,271. Так как н единичном состоянии находится только триггер 26 б 7, то высокий потенциал поступает только на элемент И 76 . Поэтому на вход узла 10 поступает только код с регистра 5 . Одновременно на первый вход сумматора 9 черезгруппу 8 элементов ИЛИ поступает код с регистра 5 б через группу б элементов И - код числа 1 б = 5. С выхода узла 10 на второй вход сумматора 9 поступает максимальный код из поступивших - 2. На выходе сумматора 9 появляется код числа 7 ч5+2, который через открытую группу Зб элементов И поступает на вход регистра 5 б . Далее с приходом очередных импульсов на вход счетчика 17 аналогичным образом на регистр 5 поступает код б = 4 + 2, на вход регистра 54 - код 5 = 3+2. После прихода четвертого импульса на вход счетчика 17 на нем зафиксируется код числа 3, и на вход узла 10 поступают коды с регистров 5 б и 5. Поэтому с выхода сумматора 9 на вход регистра 5 заносят код числу 11 = 4 + щахО; 0; О, 0; б, 7, 0 = 4 + 7. Аналогично на регистр 5 заносят код числа 10 - 3 + 7 и на регистр 54 - код числа 13 = 2 + 11. Таким образом, показания регистров 5 соответствуют максимальным величинам путей в графе для каждой вершины, показания которых следующие: 13; 10; 11, 5; б, 7; 2.С появлением нулевого кода на счетчике 17 на выходе дешифратора 22 появляется низкий потенциал, поэтому счетные импульсы далее не поступают на вход счетчика 17, а поступают на вход счетчика 19 через элемент И 15. С приходом первого импуль са на вход счетчика 19 возбуждается первая выходная шина дешифРатора 20,и на управляемый вход элемента И 134подается высокий потенциал. А таккак триггер 12 находится в единичном состоянии, то на вторых управляемых входах элементов И-ИЛИ 27 первой строки будут высокие потенциалы,благодаря чему высокие потенциалы свыходов элементов И-ИЛИ 27 ц и 27через элементы ИЛИ 2 и 2 поступаютна управляемые входыэлементов И 7и 7 , через которые коды с вйходоврегистров 5 и 5 поступают на входыузла 10. На выходах узла 10 появляется позиционный код, соответствующиймаксимальному из поступивших, в дан ном случае в единичное состояние перебросится триггер 129. После этогона вход счетчика 19 поступает очередной импульс и на нем зафиксируетсякод числа 2. Так как в этом случае 20 возбуждается вторая выходная шинадешифратора 20 и триггер 12 находится в нулевом состоянии, то на узел 10не поступают коды. Далее с приходомочередного импульса на вход счетчи ка 19 процесс определения вершинграфа, образующих максимальный критический путь, будет продолжатьсяаналогично. В результате критический максимальный путь моделируемогографа составят вершины: 1; 3; 5 и 7,Таким образом, предлагаемое устройство за счет введения новых связей и сокращения аппаратных затратповышает надежность по сравнению сизвестными устройствами, обеспечивающую при таком же быстродействииопрецеление величины и вершин, образующих максимальный критический путь.107 б 909 г Подписное аказ 750 с 4/ г,ужгород, ул.Проектная, 4 ПП фПатен фили дактор Н.Ковалева ВНИИПИ по де 113035, Составитель Г,СорокиТехред С,Легеза Тираж 699арстйенного комитета ССзобретений и открытийва, Ж, Раушская наб,орректор М.Демчи