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

 

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

1076909

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

Известно устройство для исследования путей в графах, содержащее матрицу ими триггеров формирования дуг графа и генератоp тактовых импульсов, выход которого соединен с первым входом элемента И, второй вход которого является входом устрой стна, по числу триггеров формирова- t5 ния дуг: элемента И, по числу столбцов матрицы элементы ИЛИ, элементы задержки, регистры„ первые, вторые и третьи группы элементов И, группу элементов ИЛИ, многовходоной сумматор, узел выбора максимума, дешифратор, элемент НЕ и Реверсинный счетчик (1) .

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

5О

Наиболее близким к предлагаемому является устройство для исследования путей н графах„ содержащее матрицу формирователей дуг, выходы

j -ro формирователя дуги которой через -й элемент ИЛИ группы соеди- 35 иены с первым входам -го элемента И первой группы, геиератор таKTOвых импульсав, ныхад которого соединен с первыми нходами первого и второго элементов И, выход первого из которых соединен с входом вычитающего счетчика, выход которого соединен с входом дешифратора нуля и с входом первого дешифратора состояния, -й выход которого соединен

/ с первым входом q --го элемента И второй группы непосредственно, а с первым входом 1 -го элемента И третьей группы через саотнетстнующий элемент задержки, выход < --га элемента И третьей группы через саотнетствующий регистр соединен с вторыми входами j --х элементов И первой и второй группы, выход первого из которых соединен с соотгС ветствующим входом узла выбора максимума, числовой выход которого сое динен с первым входом сумматора, ( выход < --го элемента И второй группы соединен с соответстнующим входом элемента ИЛИ, выход которого соеди- 60 нен со вторым входом сумматора, выход каторога соединен с вторыми входами элементов И третьей группы, прямой выход дешифратора нуля соединен с вторым входом первого элемента И, третий вход которого является входом пуска устройства, а инверсный выход дешифратора нуля соеди нен с вторым входом второго элемента И, выход которого через суммирующий счетчик соединен с входом второго дешифратора состояния, 1-и выход которого соединен с первым входом

< -го элемента И четнертой группы, вторые входы которых подключены к выходу 1 -го триггера группы.

Недостатком известного устройства является низкая надежность ввиду больших аппаратных затрат, Цель изобретения — сокращение аппаратурных затрат.

Укаэанная цель достигается тем, чта устройство для исследования путей в графах, содержащее матрицу формирователей дуг, выходы -го формирователя дуги которой через -ый элемент ИЛИ группы соединены с перным входом 1 -го элемента И первой группы, генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого из которых соединен с входам вычитающего счетчика, выход которого соединен с входом дешифратора нуля и с входом первого дешифратара состояния, ) -й выход которого соединен с первым входом 1 -го элемента И второй группы непосредственна, à с первым входом j -го элемента И третьей группы через соответ ствующий элемент задержки, выход

j-го элемента И третьей группы через соответствующий регистр соединен с вторыми нходами -x элементов И первой и второй групп, выход первого из которых соединен с соответстнующим входом узла выбора максимума, числовой выход которого соединен с первым входом сумматора, выход 1 -ro элемента И второй группы соединен с соответствуют(им входом элемента ИЛИ, выход которого соединен с вторым входам сумматора, выход которого соединен с вторыми входами эле. ментов И третьей группы, прямой выход дешифратора нуля соединен с вторым входом первого элемента И, третий вход которого является входом пуска устройства, а инверсный выход дешифратара нуля соединен с вторым входам второго элемента И, вы ход котооого через суммирующий счетчик соединен с входом второго дешифоатора состояния, -й выход которого соединен с перным входом ,-го элемента И четвертой группы, вторые входы которых подключены к выходу 1 -го триггера группы, содержит пятую группу элементов И, первые входы которых подключены к соответствующим поразрядным выходам узла ,выбора максимума, а нторые входы

1076909,объединены и подключены к инверсному ныходу дешифратора нуля, выход !

1 -ro элемента И пятой группы, соеди. нен--с входом 1 -го триггера группы, выход I --го элемента И четвертой груп пы и -й выход первого дешифратора состояния соединены соответственно с первыми и вторыми входами опроса ,формирователей дуг J-й строки мат1. рицы.

Формирователь дуги содержит триггер и элемент И-ИЛИ, первый и второй входы которого подключены соответственно к первому и второму входам onроса формирователя дуги, третий вход элемента И-ИЛИ подключен к выходу триггера, а выход элемента И-ИЛИ является выходом формирователя дуги.

На фиг. 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 ныбора максимума содержит элементы ИЛИ HE 28, поразрядные блоки 29 переноса, выходы 30 и 31 и входы 32. Поразрядные блоки 29 переноса содержат группы 33 элементов И и ИЛИ. Группы 33 элементов И и ИЛИ содержат элементы ИЛИ 34 и элементы И 35, Узел 10 работает следующим образом. Входы 32 подключены к выходам соответствующих элементов И 7, выходы 30 соединены с входом сумматора 9, а- выходы 31 соединены с одними из входон соответствующего элемента И 11. B первый момент анализируются старшие разряды кодов чисел.

Если хотя бы один из старших разрядов кодов равен 1, то на выходе элемента ИЛИ-НЕ 28< сформируется нулевои сигнал, при этом, если стар. ший разряд j --ro числа (i = I....n) равен О, то все разряды i -го числа

Не проходят через элементы И 35 .-й группы первого узла 29 переноса. Если старший разряд q -го числа равен 1, то все разряды i -го числа проходят через элементы И 35 -й группы первого узла 29 переноса.

Если старшие разряды всех кодов чисел равны О, то на выходе элемента ИЛИ-HE 28 сформируется "1", которая дает разрешение на прохождение всех кодов чисел через эле5 менты И 35 первого узла 29 переноса ° Таким образом, на выходе элемента И 35 первого узла 29< переноса формируются разряды кодон чисел, начиная со второго по Щ-й разряды.

1р Вторым элементом ИЛИ-НЕ 28 поразрядного узла 29 переноса анализируются вторые по старшинству разряды чисел таким же образом, как и старших разрядов, и т.д. Таким образом. код номера экстремального числа получается путем совпадения всех сигналов запрета, сформированных в каждом поразрядном узле 29 переноса, На выходах 30 получается обратный код экстремального числа.

Устройство работает следующим образом, Первоначально в матрицу 1 заносится информация о топологии моделируемого графа (сети). При этом триггеры 26, моделирующие ветви графа, устанавливаются в единичное состояние. Соответствующий триггер 26 определяется пересечением строки с номером, равным номеру

ЗО начального узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. В регистры 5 заносятся коды чисел, соотнетствующие весам вершин t, счетчик 17 за1

35 носится код числа вершин в моделируемом графе, а счетчик 19 находится в нулевом состоянии. При этом исходная информация о графе заносится н модель н порядке, при котором

4р наименьший номер (первый) имеет начальная вершина, а наибоЛьший конечная вершина. В единичное состояние устанавливается также триггер 12, соответствующий начальной

45 веРшине. Такое занесение исходной информации позволяет использовать для расчета максимальных путей процедуру динамическоего программирования, по которой для каждой < -й вершины вычисляется1„Р,=(.„+ ма („р,"0;I)

)cq где g ; = элемент матрицй связнос1 ти, равный О, если нет дуги из 1 -й вершины в j -ю, и равный 1, если такая дуга есть.

С появлением пускового сигнала на входе 21 устройства элемент. И 16 обеспечивает прохождение счетных.. импульсов с выхода генератора 14 на вход счетчика 17, так как на втором входе элемента И 16 будет высобО кий потенциал с выхода дешифратора 22 нуля.

С выхода счетчика 17 код поступает на вход дешифратора 18, в результате чего на q -м его выходе б5 появится высокий потенциал, где

1076909

20, 25

65 †.максимальное число вершин в мо делируемом графе, Этот высокий потенциал подается на вход элемента 4-33 задержки, первый вход элемента lt 633 одноименного столбца, а также первые входы элементон И-ИЛИ 27 одноименной строки матрицы. В том случае, если триггеры 26 в данной строке находятся в единичном состоянии, то через элементы И-ИЛИ 27 и ИЛИ 2 высокий потенциал с выходов этих триггеров подается на первые входы соответст вующих элементов И 7, что в свою очередь обеспечивает подачу кодов с регистров 5 на входы узла 10 выбора максимума. Узел 10 обеспечивает выбор из поступивших на его вход кодов максимального числа и подачу его на первый вход сумма- . тора 9. Одновременно на нторой вход сумматора 9 подается код с выхода избранного регистра 5п через соответствующий элемент И 633 и элемент ИЛИ 8. Результат с выхода сумматора 9 через открытую группу 3 элементов И (к этому моменту времени на управляемом входе элемента И 3„ появится высокий потенциал с выхода элемента 431 задержки) поступит на вход соответствующего регистра 5д. °

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

Далее на вход счетчика 17 поступает очередной импульс, в результате чего содержимое счетчика 17 уменьшается на Единицу, поэтому на выходе дешифратора 18 возбуждается очередная (П-I)-я выходная шина, и процесс формирования. величины максимального пути для очередной вершины графа будет происходить аналогично.

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

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

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

Работу устройства при определении, максимального критического пути Ф графе поясним на следующием примере.

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

0 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 0 1

0 0 О, 0 0 0 1

0 0 0 0 0 0 0 т=f2 3;4;3;4;5,23 где элементы

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

Q н -ю ii Ф

1, если есть дуга из 3 -й вершины н ) -IG

1,....,п,п = 7, нес (время) 1 -й вершины.

После занесения исходной информации на регистрах 5 будут коды, соответствующие весам вершин 1, а на счетчике 17 — код числа 7. Кроме того, в нулевом состоянии будет счетчик 19 и триггеры 12, кроме триггера 12, который находится н единичном состоянии. С приходом пускового сигнала на вход 21 устройства счетные импульсы с выхода генератора 14 поступают на вход нычитающего счетчика 17 через элемент И 16. С приходом первого импульса на счетчике 17 зафиксируется код числа 6, поэтому на выходе дешифратора 18 нозбудится шестая выходная шина и высокие потен. циалы подаются на управляемые входы элементов И 66,.элементов 46 задержки, а также элементов И-ИЛИ 276, 2762 ... 2767 Так как н единичном состоянии находится только триггер 2667, то высокий потенциал поступает только на элемент И 76 ° Поэтому на вход узла 10 поступает только код с регистра 56 . Одновременно на первый вход сумматора 9 через

1076909 группу 8 элементов ИЛИ поступает код с регистра 5 через группу 6 элементов И вЂ” код числа16 = 5 ° С выхода узла 10 на второй вход сумматора 9 поступает максимальный код из поступивших — 2. На выходе сумматора 9 появляется код числа 7ч

5+2, который через открытую группу 3 элементов И поступает на вход регистра 5 . Далее с приходом очередных импульсов на вход счетчика 17 аналогичным образом на регистр 5 поступает код 6 = 4 + 2, на вход регистра 54 — код 5 = 3+2.

После прихода четвертого импульса на вход счетчика 17 на нем зафиксируется код числа 3, и на вход узла 10 поступают коды с регистров 5 и 5 . Поэтому с выхода сумматора 9 на вход регистра 5 заносят код числу 11 = 4 + max )0 0; О, 0; 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 подается высокий потенциал. A так как триггер 12 находится в единичном состоянии, то на вторых управляемых входах элементов И-ИЛИ 27 первой строки будут высокие потенциалы, благодаря чему высокие потенциалы с выходов элементов И-ИЛИ 27 g и 27 q через элементы ИЛИ 2 и 2 поступают на управляемые входы элементов И 7

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

2О возбуждается вторая выходная шина дешифратора 20 и триггер 12 находится в нулевом состоянии, то на узел 10 не поступают коды. Далее с приходом очередного импульса на -вход счетчи25 ка 19 процесс определения вершин графа, образующих максимальный критический путь, будет продолжаться аналогично. В результате критический максимальный путь моделируемого графа составят вершины: 1; 3; 5 и 7, Таким образом, предлагаемое устройство за счет введения новых связей и сокращения аппаратных затрат повышает надежность по сравнению с известными устройствами, обеспечивающую при таком же быстродействии опрецеление величины и вершин, образующих максимальный критический путь.

1076909

1076909

4ь2. 2

Составитель Г.Сорокин

Техред С,Легеза Корректор М.Демчик

Редактор Н. Ковалева

Подписное

Заказ 750/46 Тираж 699

ВНИИПИ Государст9енного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", r.Óæãîðoä, ул.Проектная, 4