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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик ц 1005066фФ(61) Дополнительное к авт. сеид-ву Р 943738 (22) Заявлено 280531 (21) 3292013/18-24 11 М Кп 3 6 06 Г 15/20 с присоединением заявки Нов Государственный комитет СССР по делам изобретений и открытий.57(088.8) Дата опубликования описания 150383 В.А. Титов, В.Л. Гайдуков, Ю.Н. Родионов и А.Л. Гайдуков(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПУТЕЙ В ГРАФАХИзобретение относится к вычислительной технике и может быть использовано при исследовании параметровсетевых графов, а также при аппаратной реализации в специализированныхпроцессорах макрокоманды определениямаксимальных критических путей в графах.По основному авт, св. Р 943738известно устройство для исследованияпутей в графах, содержащее матрицупп триггеров формирования дуг графа и генератор тактовых импульсов,выход которого соединен с первымвходом. элемента И, второй вход которого является входом устройства, почислу триггеров формирования дугэлементы И дуг, по числу столбцовматрицы элементы ИЛИ, элементы задержки, регистры, первые, вторыеитретьи группы элементов Й, группуэлементов ИЛИ, многовходовой сумматор, узе 1 т выбора максимума, дешифратор, элемент.НЕ и реверсивныйсчетчик, вход которого подключен квыходу элемента И, третий вход которого через элемент НЕ подключен квыходу устройства и к выходу реверсивного счетчика, выход которогосоединен с входом дешифратора,-й (=1, 2, , л) выход которогоподключен через элемент задержкик управляющему входу элемента Ипервой группы -го столбца, к управляющему входу элемента И 1-гостолбца и к первым входам элементовИ дуг -й строки, выход каждого триггера формирования дуги соединен свторым входом элемента И дуги, выходкаждого из которых подключен к входу элемента ИЛИ одноименного -гостолбца,.выход которого соединен суправляЬЦим. входом элемента И второйгруппы 1-го столбца, выход которогоподключен к соответствующему входуузла выбора максимума, выход которогосоединен с первым входом многовходового сумматора, выход которого под О.ключен к информационным входам элементов И первой группы выход элемента И первой группы 1-го столбца .соединен с входом регистра -гостолбца; выход которого подключенк информационному входу элемента Ивторой группы 1-го столбца и к информационному входу элемента И третьейгруппы 1-го столбца, выходы элементов И третьей группы соединены соответственно с входами элементов ИЛИ группы, выходы которых подключены10 Устройство содержит матрицу 1,почислу строк и столбцов матрицы Формирователи весов дуг, каждый из которых включает.в себя триггер 2,элемент И 3 дуг и дополнительныйэлемент И 4 дуг, по числу столбцовматрицы первую группу элементовИЛИ 5 м .5, вторую группу элементов ИЛИ б, , би, по числустолбцов матрицы элементы.7,7,. задержки, первую группу элементов И 84, , 8 я, по числу столбцов матрицы регистры 94 .9 и,вторую группу элементов И 10,10, третью группу элементов И 11,11, четвертую группу элементовИ 12, , 12, по числу столбцов 65 к второму входу многовходового сумматора 113Недостатком известного устройства являются ограниченные функциональные возможности из-,за невозможности идентификации вершин графа, образующих максимальный критический путь.Цель изобретения - расширение функциональных возможностей путем идентификации вершин, образующих максимальных критический путь.Указанная цель достигается тем, что в устройство для исследования путей в графах введены второй элемент И, счетчик, второй дешифратор, второй узел выбора максимума, по чис лу столбцов матрицы триггеры, четвер- тая и пятая группы элементов И, вто- . рая групоа элементов ИЛИ и по числу строк и столбцов матрицы дополнительные элементы И дуг, первый вход 1-го дополнительного элемента И дуг (=1,2п) соединен с выходом -го триггера формирования дуги, а выход - с -м входом 1-го элемента ИЛИ второй группы, выход которого э 5 подключен к первому входу -го элемента И четвертой группы, второй . вход которого соединен с выходом -го регистра, выход -го элемента И четвертой группы подключен к -му входу второго узла выбора максимума, выходы которого соединены соответственно с входами триггеров, выход 1-го триггера подключен к первому входу -го элемента И пятой группы, второй вход которого соединен с 1-м выходом второго дешифратора, а выход - с вторыми входами дополнительных элементов И дуг 1-и строки матрицы, выход реверсивного счет-, чика подключен к первому входу вто рого элемента И, второй вход которого соединен с выходом генератора тактовых импульсов, выход второго элемента И через счетчик подключен к входу второго дешифратора. 45На чертеже представлена схема устройства для исследования путей в графах. матрицы триггеры 13, , 13 и, пятуюгруппу элементов И 14, , 14 к,группу элементов ИЛИ 15, сумматор 16,второй 17 и первый 18 узлы выборамаксимума, генератор 19 тактовыхимпульсов, первый элемент И 20, реверсивный счетчик 21, первый дешиф-.ратор 22, второй элемент И 23, счетчик 24, второй дешифратор 25, элементНЕ 26, вход 27 устройства,Устройство работает следующимобразом.Первоначально в матрицу 1 заносит.ся информация о топологии моделируемого графа (сети). При этом триггеры2, моделирующие ветви графа, устанавливаются в единичное состояние. Соответствующий триггер 2 определяется пересечением строки с номером,равным номеру .конечного узла моделируемой ветви, и столбца сномером,равным номеру ее начального узла.В регистры 9 заносятся коды чисел,соответствующие "весам" вершин. Всчетчик 21 заносится код числа вершин в моделируемом графе, а счетчик24 находится в нулевом состоянии.При этом исходная информации о графе заносится в модель в порядке,при котором наименьший номер (первый) имеет начальная вершина, анаибольший - конечная. В единичноесостояние устанавливается такжетриггер 13, соответствующий начальной вершине. Такое занесение исходной информации о графе позволяетиспользовать для расчета максимальных путей процедуру динамическогопрограммирования.С появлением пускового сигнала навходе 27 устройства элемент И 20обеспечивает прохождение счетныхимпульсов с выхода генератора 19 навход счетчика 21, так как на второмвходе элемента И 20 присутствуетвысокий потенциал с выхода элементаНЕ 26, вход которого подсоединен квторому выходу счетчика 21 - выходу,на котором появляется сигнал нулевого состояния этого счетчика.1С первого выхода счетчика 21 кодпоступает на вход дешифратора 22, врезультате чего на и-м его выходепоявляется высокий потенциал, гдеи - максимальное число. вершин в мо-.делируемом графе. Этот высокий потенциал подается на вход элемента 7задержки, на первый вход элементаИ 11 одноименного столбца, а такжена первые входы элементов И 3 одноименной строки матрицы. В том случае, если триггеры 2 в данной строкенаходятся в единичном состоянии,через элементы И 3 и ИЛИ 5 высокийпотенциал с выходов этих триггеровподается на первые входы соответствующих элементов И 10, что, в своюочередь, обеспечивает подачу кодовс регистров 9 на входы узла 18 выбора максимума, Узел 18 обеспечиваетвыбор из поступивших на его вход кодов максимального числа и подачу егона первый вход сумматора 16. Одновременно на второй вход сумматора 16подается код с выхода избранногорегистра 9 через соответствующийэлемент И 11 и элемент ИЛИ 15, Результат с выхода сумматора через открытую группу элементов И 8 (к этомумоменту времени на управляемом входе элемента И 8 появляется высокийпотенциал с выхода элемента 7 задержки) поступает на вход соответст-,вующего регистра 9. На этом этапформирования кода максимального пути для одной отдельной вершины заканчивается Далее на вход счетчика 21 поступает очередной импульс,в результате чего содержимое этогосчетчика уменьшается на единицу,поэтому на выходе дешифратора 22возбуждается очередная (и)-явыходная шина, и процесс формирования величины максимального путидля очередной вершины графа про-исходит аналогично,Вычислительный процесс продолжается до тех пор, пока на счетчике21 не появляется нулевой код, в результате чего появляется высокийпотенциал на входе элемента НЕ 26,а следовательно, на втором входеэлемента,И 20 присутствует низкийпотенциал, и подача счетных импульсов на вход счетчика 21 прекращаетОдновременно высокий потенциал с выхода счетчика 21 обеспечивает подачу сигналов с выхода генератора .19 через второй элемент И 23 на вход счетчика 24, выход которого подсоединен к входу дешифратора 25. Выходные шины дешифратора 25 подсоединены к одноименным управляевым входам элементов И 14. Если при этом соответствующий триггер 13 находится в единичном состоянии, высокий потенциал с его выхода через одноименный элемент И 14 поступает на управляемые входы элементов И 4 одноименной строки матрицы сети и далее через элемент ИЛИ 6 на те управляемые входы элементов И 12, которым в данной строке матрицы сети соответствует дуга графа, т.е. единичное состояние триггера 2. Наличие высоких потенциалов на управляемых входах элементов И 12 обеспечивает поступление кодов с выходов регистров 9 на входы узла 17 выбора максимума, который, в свою очередь, обеспечивает выбор максимального из поступивших кодов, при этом соответствующие триггеры 13 перебрасываются в единичное состоя ние и т.д. Процесс поиска максимального критического пути заканчивается при достижении показаниями счетчика 24 значения и - максимальногочисла вершин в моделируемом графе,Работа устройства при определении максимального критического путив графе поясняется на следующем примере,Пусть задан граф С, описываеьнйматрицей связности А и вектором Тфвесовф вершин 1100 0111 0011 0000 0000 А 000 000 4; 5; 2) е элемен если нет дугшины в )-ю; З 0 1 . 1, если есть дуги из 1 вершины в -ю;1, , 0; Пс - "весфвремя) 1-й вершины.35После занесения исходной инфор"мации на регистрах 9 присутствуюткоды, соответствующие "весамф вершин с,.а на счетчике 21 в .код чис ла 7. Кроме того, в нулевом состоянии находятся счетчик 24 и триггеры 13, кроме триггера 13, которыйнаходится в единичном состоянииСприходом пускового сигнала на вход27 устройства счетные импульсы свыхода генератора 19 поступают навход реверсивного счетчика 21 черезэлемент И 20, С приходом первогоимпульса на счетчике 21 Фиксируетсякод числа "6", поэтому на выходе дешифратора 22 возбуждается шестаявыходная шина, тем самым, высокиепотенциалы подаются на управляеьиевходы элементов. И 116, задержки 7,а также элементов И 3 у,3 рТак как в единичном состоянии находится только триггер 2, высокийпотенциал поступает только на элементИ 106 через элемент ИЛИ 56. Поэтомуна вход узла 18 поступает только код.с регистра 96, Одновременно на пер-вый вход сумматора 16 через элементИЛИ 15 поступает код с регистра 9через группу элементов И 11 ь - этокод числа с=5. С выхода узла 18 на А 5 второй вход сумматора 16 поступает 60максимальный код из поступивших - 2. На входе сумматора 16 появляется код чила 7 = 5 + 2, который через открытую группу элементов И 88 поступает на вход регистра 9 . Далее с приходом очередных импульсов на вход счетчика 21 аналогичным образом на регистр 9 поступает код 6=4+2, на вход регистра 94 - код 5 = 3 + 2. После.прихода четвертого импульса на вход счетчика 21 на нем фиксируется код числа 3, и на вход узла 18 поступа" ют коды с регистров 96 и 9. Поэтому с выхода сумматора 16 на вход регист. ра 9 заносится код числа15 11=4+ввхО;ОО 01 бу 701 =4 + 7.Аналогично на регистр 9 заносится код числа 10 = 3 + 7 и на регистр 91 - код числа 13 = 2 + 11. Таким образом, показания регистров 9 соответствуют максимальным величинам путей в графе для каждой вершины. Эти показания следующие: 13; 10; 11;5 ю, б; 7 к 2.С появлением нулевого кода на счетчике 21 на выходе элемента НЕ 26 появляется высокий потенциал, поэтому счетные импульсы далее не поступают на вход счетчика 21, а проходят на вход счетчика 24 через элемент И 23. ЗО С приходом первого импульса на вход, счетчика 24 возбуждается первая выходная шина, и на управляемый вход элемента и 141 подается высокий.потенциал. А так как триггер 13 находит ся в единичном состоянии, на управляемых входах элементов И 4 первой строки присутствуют высокие потенциалы, благодаря чему высокие потенциалы с выходов элементов И 4 и 41 Э 40 через элементы ИЛИ б и 6 поступают на управляемые входы элементов И 12 и 12, через которые коды с выходов регистров 9 д. и 9 поступают на входы узла 17. На выходе узла 45 17 появляется позиционный код, соответствующий максимальному из пос.тупивших, в данном случае в единичное состояние перебрасывается триг" гер 13. После этого на вход счетчика 24 поступает очередной импульс и фиксируется код числа 2. Так как в этом случае возбуждается вторая выходная .шина дешифратора 25 и триггер 13 находится в нулевом состоянии, на увел 17 не поступают коды. Далее с приходом очередного импуль" са на вход счетчика 24 процесс опре,деления вершин графа, образующих максимальный критический путь, продолжается аналогично. В результате критический максимальный путь моделируемого графа составляют вершины: 1; 3; 5 и 7,Таким образом, устройство за счет введения дополнительных элементов с соответствующими связями обеспечивает расширение функциональных возможностей прототипа и обладает повышенным быстродействием по сравнению с известными устройствами при определении максимального пути в графе. Формула изобретенияУстройство для исследования путейв графах по авт. св, Р 943738,о т л и ч а ю щ е е с.я тем, что,с целью расширения функциональныхвозможностей за счет идентификациивершин, образующих максимальный критический путь, в него введены второйэлемент И, счетчик, второй дешифратор, второй узел выбора максимума,по числу столбцов матрицы триггеры,четвертая и пятая группы элементов И,вторая группа элементов ИЛИ и почислу строк и столбцов матрицы дополнительные элементы И дуг, первыйвход 1-го дополнительного элементаИ дуг (1=1, 2.и) соединены свыходом 1-го триггера формированиядуги, а выход - с 1-ым входом 1-гоэлемента ИЛИ второй группы, выход которого подключен к первому входу1-го элемента И четвертой группы,второй вход котброго соединен с выходом 1-го регистра, выход 1-го элемента И четвертой группы подключенк 1-му входу второго узла выборамаксимума, выходы которого соединены соответственно с входами триггеров, выход 1-го триггера подключенк первому входу 1-го элемента И пя-.той группы, второй вход которогосоединен с 1-ым выходом второго дешифратора, а выход - с вторыми входами дополнительных элементов И дуг1-й строки матрицы, выход реверсивного счетчика подключен к первомувходу второго элемента И, второйвход которого соединен с выходом генератора тактовых импульсов, выходвторого элемента И через счетчикподключен к входу второго дешифратора.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРф 943738 ф кл. 6 06 Г 15/20, 1982100506 б к Подписнота СССРытийаб., д. 4/5 каэ 190 5 Тираж 704 ИИПИ Государственного комит по делам изобретений н отк 35, Москва, Ж, Раушская 1130 Филиал ППП фПатент", г. Ужгород, ул, Проектная,Составитель И. ДубининаАлексеенко Техред Т.Маточка Корректор Е. Рошк