Устройство для исследования путей в графе Советский патент 1984 года по МПК G06F15/173 

И.зобретение относится к вычисли тельной технике и может быть испол зовано при исследовании параметров сетевых графов, а также при аппара ной реализации в специализированны процессорах макрокоманды определен максимальных критических путей в графах. Известно устройство для исследо ния путей в графах, содержащее мат рицу пхп триггеров формирования дуг графа и генератор тактовых импульсов, выход которого соединен с первым входом элемента И, второй вход которого является входом устр ства, по числу триггеров формирова ния дуг-- элемента И, по числу столб цов матрицы элементы ИЛИ, элементы задержки, регистры, первые, вторые и третьи группы элементов И, групп элементов ИЛИ, многовходовой cyMivia тор, узел выбора максимума, дешифр тор, элемент НЕ и :Е еверсивный счет чик ij . Недостатком данного устройства являются ограниченнне функциональные возможности из-за невозможности индентификации вершин графа, образующих максимальный критический путь. Наиболее близким к предлагаемому является устройство для исследования путей в графах, содержащее матрицу формирователей дуг, выходы ij-ro формирователя дуги которой через j -и элемент ИЛИ группы соеди нены с первым входом -то элемента И первой группы, генератор такто вых импульсов, выход которого соеди нен с первыми входами первого и вто рого элементов И, выход первого из которых соединен с входом вычитающего счетчика, выход которого соеди нен с входом дешифратора нуля и с входом первого дешифратора состоят ния, t -и выход которого соединен с первым входом i -го элемента И второй группы непосредственно, а с первым входом { -го элемента И третьей группы через соответствуюьдий элемент задержки, выход -го элемента И третьей группы через соответствующий регистр соединен с вторыми входами j -х элементов И первой и второй группы, выход первого из которых соединен с соответствующим входом узла выбора максимума, числовой выход которого сое динен с первым входом суглматора, выход I -го элемента И второй группы соединен с соответствующим входом элемента ШШ, выход которого соединен со вторым входом сумматора, выход которого соединен с вторыгди вхо элементов И третьей группы, прямой выход дешифратора нуля соединен с вторым ВХОДОМ первого элеMetiTa И, третий вход которого является входом пуска устройства, а инверсный выход дешифратора нуля соеди ней с вторым входом второго элемента И, выход которого через суммирующий счетчик соединен с входом второго дешифратора состояния, i-й выход которого соединен с первым входом элемента И четвертой группы, вторые входы которых подключены к выходу 1 -го триггера группы. Недостатком известного устройства является низкая надежность ввиду больших аппаратных затрат. Цель изобретения - сокращение аппаратурных затрат. Указанная цель достигается тем, что устройство для исследования путей в .графах, содержащее матрицу формирователей дуг, выходыfj-го формирователя дуги которой через « -ый элемент ИЛИ группы соединены с первым входом j -го элемента И первой группы, генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого из которых соединен с входом вычитающего счетчика, выход которого соединен с входом дешифратора нуля и с входом первого дешифратора состояния, j -и выход которого соединен с первым входом j -го элемента И второй группы непосредственно, а с первым входом j-го элемента И третьей группы через соответ ствующий элемент задержки, выход j-го элемента И третьей группы через соответствующий регистр соединен с вторыми входами j -х элементов И первой и второй групп, выход первого из которых соединен с соответствующим входом узла выбора максимума, числовой выход которого соединен.с первым входом сумматора, выходу -го элемента И второй группы соединен с соответствующим входом элемента ИЛИ, выход которого соединен с вторым входом cyMj/iaTopa, выход которого соединен с вторы11и входами элементов И третьей группы, прямой выход дешифратора нуля соединен с вторым входом первого элемента И, третий вход которого является входом пуска устройства, а инверсный выход дешифратора нуля соединен с вторым входом второго элемента И, вы ход которого через суммирующий счетчик соединен с входом второго дешифратора состояния, j -и выход которого соединен с первым входом J-гО элемента И четвертой группы, вторые входы которых подключены к выходу J -го триггера группы, содержит пятую группу элементов И, первые которых подключены к соответствующим поразрядным выходам узла выбора максимума, а вторые входы (Объединены и подключены к инверсному выходу дешифратора нуля, выход J-го элемента, И пятой группы, соеди не -с входом j -го триггера группы, выход j -го элемента И четвертой гру пы и j -и выход первого дешифратора состояния соединены соответственно с первыми и вторыми входами опроса ;формирователей дуг j-й строки матрицы . Формирователь дуги содержит триг гер и элемент И-ИЛИ, первый и второ входы которого подключены соответст венно к первому и второму входам оп роса форми 1ователя дуги, третий вхо элемента И-ИЛИ подключен к выходу триггера, а выход элемента И-ИЛИ является выходом формирователя дуги На фиг. 1 приведена блок-схема предлагаемого устройства; на фиг. 2 то же, узел выбора максимума. Устройство содержит матрицу 1 формирователей дуг, группу 2 элементов ИЛИ, группу 3 элементов И, элементы. 4 - 4 задержки, регистры 54 - 5„, группу 6 элементов И, группу 7 элементов И, элемент ИЛИ 8 сумматор 9, узел 10 выбора максимума, группу 11 элементов И, группу 1 триггеров, группу 13 элементов И, генератор 14 тактовых импульсов, эл менты И 15 и 16, вычитающий счетчик 17, дешифратор 18 состояния, су мирующий счетчик 19, дешифратор 20 состояния, вход 21 пуск-а и дешифратор 22 нуля. Матрица 1 формирователей дуг содержит формирователи 23 дуг. Формирователи 23 дуг содержат входы 24 и 25 опроса, триггеры 26 и элементы И-ИЛИ 27. Узел 10 выбора максимума содержит элементы илИгНЕ 2 поразрядные блоки 29 переноса, выходы 30 и 31 и входы 32. Поразрядные блоки 29 переноса содержат груп пы 33 элементов И и ИЛИ. Группы 33 элементов И и ИЛИ содержат элементы ИЛИ 34 и элементы И 35. Узел 10 работает следующим образом. Входы 32 подключены к выходам соответствующих элементов И 7, выходы 30 соединены с входом сумматора 9, а. выходы 31 соединены с одними из входов соответствующего элемента И 11. В первый момент анализи руются старшие разряды кодов чисел. Если хотя бы один из старших разрядов кодов равен 1, то на выходе элемента ИЛИ-НЕ 28( сформируется нулепой сигнал, при этом, если стар ший разряд {-го числа {i I...,n) равен О, то все разряды li -го числа не проходят через элементы И 35 1,-й группы первого узла 29 переноса. Если старший разряд i -го числа равен 1, то все разряды i -го числа проходят через элементы И 35 i -и группы первого узла 29| переноса. Если старшие разряды всех кодов чисел равны О, то на выходе.элемента ИЛИ-НЕ 28, сформируется 1, которая дает разрешение на прохождение всех кодов чисел через элементы И 35 первого узла 29 переноса. Таким образом, на выходе элемента И 35 первого узла 29 переноса формируются разряды кодов чисел, начиная со второго nom-fi разряды. Вторым элементом ИЛИ-НЕ 28 поразрядного узла 29 переноса анализируются вторые по старшинству разряды чисел таким же образом, как и старших разрядов, и т.д. Таким образом. код номера экстремального числа получается путем совпадения всех сигналов запрета, сформированных в каждом поразрядном узле 29 переноса. На выходах 30 получается обратный код экстремального числа. Устройство работает следующим образом. Первоначально в матрицу 1 заносится информация о топологии моделируемого графа (сети). При этом триггеры 26, моделирующие ветви графа, устанавливаются в единичное состояние. Соответствующий триггер 26 определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. В регистры 5 заносятся коды чисел, соответствующие весам вершин Ц,В счетчик 17 заносится код числа вершин в моделируемом графе, а счетчик 1.9 находится в нулевом состоянии. При этом исходная информация о графе заносится в модель в порядке, при котором наименьший номер (первый) имеет начальная вершина, а наибольший конечная вершина. В единичное состояние устанавливается также триггер 12, соответствующий начальной вершине. Такое занесение исходной информации позволяет использовать для расчета максимальных путей процедуру динамическоего программирования, по которой для каЬкдой -и вершины вычисляется1цр :г1;4 (iv;p;aij j где - элемент матрицы связности, равный О, если нет дуги изi -и вершины в j -ю, и равный 1, если такая дуга есть, С появлением пускового сигнала на входе 21 устройства элемент. .И 16 обеспечивает прохождение счетных . импульсов с выхода генератора 14 на вход счетчика 17, так как на втором входе элемента И 16 будет высокий потенциал с выхода дешифратора 22 нуля. С выхода счетчика 17 код поступает на вход дешифратора 18, в результате чего на п -м его появится высокий потенциал, где

/1 - .максимальное число вершин в мо делируемом графе. Этот высокий потенциал подается на вход элемента 4-f( задержки, первый вход элемента И 6(, одноименного столбца, а также первые входы .элементов Й-НЛИ 27 одноименной строки матрицы. В том случае, если триггеры 26 в данной строке находятся в единичном состоянии, то через элементы И-ИЛИ 27 и ИЛИ 2 высокий потенцигш с выходов этих триггеров подается на первыевходы соответст вующих элементов И 7, что в свою очередь обеспечивает подачу кодов с регистров 5 на входы узла 10 выбора максимума. Узел 10 обеспечивает выбор из поступивших на его вход кодов максимального числа и . подачу его на первый вход сумма- тора 9, Одновременно на второй вход сумматора 9 подается код с выхода избранного регистр 5 через соответствующий элемент И 6, и элемент ИЛИ 8. Результат с выхода сумматора 9 через открытую группу 3 элементов И {к этому моменту време- ни на управляемом входе элемента И 3 появится высокий потенциал с выхода элемента 4(i задержки) поступит на вход соответствующего регистра 5, На этом этап формирования кода максимального пути для одной отдельной вершины заканчивается. Далее на вход счетчика 17 поступает очередной импульс, в результате чего содержимое счетчика 17 уменьшается на единицу, поэтому на выходе дешифратора 18 возбуждается очередная (п-1)-я выходная шина, и процесс формирования.величины максимального пути для очередной вершины графа будет происходить аналогично.

Вычислительный процесс продолжается до тех пор., пока на счетчике. 17 не появится нулевой код, в результате его появляется низкий потенциал на втором входе элемента И 16, и подача счетных импу.льсов на вход счетчика 17 прекращается.

Одновременно высокий потенциал с выхода дешифратора 22 обеспечивает подачу сигналов с выхода генератора 14 через второй элемент И 15 на вход счетчика 19, выход которого подсоединен к входу дешифратора 20. Выходные шины дешифратора 20 подсоединены к одноименным управляемым входам элементов И 13. Если при этом соответствующий триггер 12 находится в единичном состоянии, то высокий потенциал с его выхода через одноименный элемент И 13 поступает на управляемые входы элементов И-ИЛИ 27 одноименной строки матрицы и поступает далее через группу 2 элементов ИЛИ на -те управляемые входы группы 7 элементов И, которым в данной строке матрицы соответствует дуга графа, т.е. единичное состояние триггера 26. Наличие высоких потенциалов на управляемых входах группы 7 элементов И обеспечивает поступление кодов с выходов регистра 5 на вхо;п узла 10 выбора максимума, который в свою очередь обеспечивает выбор максимального из поступивших

кода, при этом соответствующие триггеры 12 Перебрасываются в единичное состояние импульсе, проходящим через одноименный элемент И 11 и т.д. Процесс поиска максимального критического пути заканчивается при достижении показания счетчика 19 значения П максимального числа вершин в моделируемом графе.

Работу устройства при определении

максимального критического пути и графе поясним на следующием примере.

Пусть задан граф G, описываемый матрицей связности вектором Т весов вершин.

01100000001110

0000110

д ОООООО

0000001

О О О, О О 0; 1

0000000

т (2; 3; 4,- з; 4; 5, 2},

где элементы

О,если нет дуги из i -и вершины

а;Нв 3-ю,

1, если есть дуга из i -и вершины

в j -ю,

1J 1,...,п ,п ,7 i.j- вес время ) -и вершины.

После занесения исходной информации на регистрах 5 будут коды, соответствующие весам вершин i , а на счетчике 17 - код числа 7. Кроме того, в нулевом состоянии будет счетчик 19 и триггеры 12, кроме триггера 12 , который :находится в единичном состоянии. С приходом пускового сигнала на вход 21 устройства счетные импульсы с выхода генератора 14 поступают на вход вычитающего счетчика 17 через элемент и 16. С прихо дом первого импульса на счетчике 17 зафиксируется код числа 6, поэтому на выходе дешифратора 18 возбудится 5 шестая выходная шина и высокие потенциалы подаются на управляемые входы элементов -И 6, . элементов 4 задержки, а также элементов И-ИЛИ 27,

27

27,,.

Так как в единич62

ном состоянии находится только триггер 26, то высокий потенциал поступает только на элемент И 7. Поэтому на вход узла 10 поступает только код с регистра 5. Одновременно 5 на первый вход сумматора 9 через

группу 8 элементов ИЛИ поступает код с регистра 5 через группу б элементов И - код числаi 5. С выхода узла 10 на второй вход сумматора 9 поступает максимальный код из поступивших - 2. На выходе сумматора 9 появляется код числа 7ч 5+2, который через открытую группу 3 элементов И поступает на вход регистра 5. Далее с приходом очередных импульсов на вход счетчика 17 аналогичным образом на регистр 5е поступает код , на вход регистра 54 - Код 5 3+2. После прихода четвертого импульса на вход счетчика 17 на нем зафиксируется код числа 3, и на вход узла 10 поступают коды с регистров 5 и 5г. Поэтому с выхода сумматора 9 на вход регистра 5ч заносят код числа 11 4 + max {о; О, О, О; 6, 7; 0 4+7. Аналогично на регистр 5л заносят код числа 10 3 + 7 и на регистр 5 - код числа 13 2 + 11. Таким образом, показания регистров 5 соответствуют максимальным величинам путей в графе для каждой вершины, показания которых следующие: 13, 10; 11,

5; 6; 7; 2.

с появлением нулевого кода на счетчике 17 на выходе дешифратора 22 появляется низкий потенциал, поэтому счетные импульсы далее не поступают на вход счетчика 17, а поступают на вход счетчика 19 через элемент И 15. С приходом первого импул са на вход счетчика 19 возбуждается первая выходная шина дешифратора 20

и на управляемый вход элемента И 13 подается высокий потенциал.-А так как триггер 12 находится в единичном состоянии, то на вторых управляемых входах элементов И-ИЛИ 27 первой строки будут высокие потенциалы, благодаря чему высокие потенциалы с выходов элементов И-ИЛИ 27|Ч через элементы ИЛИ 2 и 2 поступают на управляемые входыэлементов И 7;

и 7- , через которые коды с выходов регистров 5 и 5 поступают на входы узла 10. На выходах узла 10 появляется позиционный код, соответствующий максимальному из поступивших, в данном случае в едини ное состояние перебросится триггер 12. После этого на вход счетчика 19 поступает очередной импульс и на нем зафиксируется код числа 2. Так как в этом случае

возбуждается вторая выходная шина

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

графа составят вершины: 1; 3; 5 и 7, Таким образом, предлагаемое устройство за счет введения новых связей и сокращения аппаратных затрат повышает надежность по сравнению с

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

J2ia

32пг

32пт

32т Г @

32 It

3213

Jf/2

32т Фаг. 2 -J г дЫ ЩЩ Щ Ш 231 T.HIJj izrizr: I izinri { jOm-t

1. УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПУТЕЙ В ГРАФЕ, содержащее матрицу формирователей дуг, выходы ij-ro формирователя дуги которой через i -и элемент ИЛИ группы соединены с. первым входом ) -го элемента И первой группы, генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого из которых соединен с входом вычитающего счетчика, выход которого соединен с входом дешифратора нуля и с входом первого дешифратора состояния, j-a выход которого соединен с первьом входом 3 -го элемента И второй группы непосредственно, а с первым входом 3-го элемента И третьей группы- через соответствующий элемент задержки, выход -го элемента И третьей группы через соответствующий регистр соединен с вторыми входами j -х элементов И первой и второй групп, выход первого из которых соединен с соответствующим входом узла выбора максимума, числовой выход которого соединен с первым входом сумматора, выход j-го элемента И второй группы соединен с соответствующим входом элемента ИЛИ, выход которого соединен с вторым входом сумматора, выход которого соединен с вторыми BxoflaiviH элементов И третьей группы, прямой выход дешифратора нуля соединей с вторым входом первого элемента И, третий вход которого является входом пуска устройства, а инверсный выход дешифратора нуля соединен с вторым входом второго элемента И, выход которого через суммирующий счетчик соединен с входом второго дешифратора состояния,j -и выход которого соединен с первым входом j-ro элемента И четвертой группы, вторые входы которых подключены к выходу j -го триггера группы, о тличаюцееся тем, что, с целью сокращения аппаратурных затс о рат, оно содержит пятую группу элементов И, первые входы которых подключены к соответствующим поразрядным выходам узла выбора мак- симума, а вторые объединены и подключены к инверсному выходу дешифратора нуля, выход j -го элемента И пятой группы соединен с входом j -го группы, выход j -го элемента И четвертой группы и j -и выход первого дешифрато« | ра состояния соединены соответст05 венно с первыми и вторыми входами опроса формирователей дуг j -и строки матри1Хы.. .. 2. Устройство по п. 1, отличающееся тем, что формирова;о тель дуги содержит триггер и элемент И-ИЛИ, первый и второй входы которого подключены соответственно к первому и второму входам опроса формирователя дуги, третий вход элемента И-ИЛИ подключен к выходу триггера, а выход элемента И-ИЛИ является выходом формирователя дуги.