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

ментов И (где р- число разрядов кода длины ветви), третья групла из tn элементов И, элемент ИЛИ и второй триггер, причем первый вход узла вьщеления 1 старшего разряда кода режима работы устройства блока управления соединен с выходом элемента ИЛИ блока формирования топологии, второй и третий входы узла выделения 1 старшего разряда кода режима работы устройства блока управления соединены с выходами соответственно первого и второго элементов ИЛИ блока управления, первьш выход узла вьщеления 1 старшего разряда кода режима работы устройства блока управления соединен с вторым входом элемента И блока формирования топологии, второй и третий выходы узла вьщеления 1 старшего разряда кода режима работы устройства блока управ ления подключены к первым входам, соответственно первого и второго элементов И блока управления, вторые входы которых соединены с вьрсодом .генератора импульсов, выход первого элемента И блока управления соединен с первыми входами элементов И группы блока управления, вторые входы которых подключены к соответствующим выходам узла вьщеления 1 старшего разряда кода адреса ветви графа блока управления, входы узла вьщеления 1 старшего разряда кода адреса ветви графа блока управления объединены с соответствующими входами первого элемента ИЛИ блока управления и подключены к единичным выходам пер вых триггеров соответствующих моделей ветвей, выходы элементов И группы блока управления соединены с ну левыми входами первых триггеров, первыми входами элементов Р1ПИ и пер выми входами элементов И второй и третьей групп соответствующих моделей ветвей, вторые входы элементов И первой группы каждой модели ветви соединены с выходом элемента ИЛИ модели ветви, вторые входы элементо И второй группы каждой модели ветви соединены с выходами регистра длины ветви модели ветви, вторые входы элементов И третьей группы каждой модели ветви соединены с выходами регистра адреса задатчика адреса на чального узла модели ветви, выход схемы сравнения задатчика адреса на чального узла каждой модели ветви соединен с единичным входом второго 17 регистра модели ветви, единичный выход которого является выходом модели ветви, нулевой вход второго триггера каждой модели ветви соединен с вторым входом элемента ИЛИ модели ветви и подключен к выходу соответствзющего элемента И группы блока формирования топологии, выходы регистра кода адреса узла каждой модели узла соединены с первыми входами первой и второй схем сравнения и с первыми входами элементов И первой группы.модели узла, выходы элементов И первой группы каждой модели узла подключены к вторым входам схем сравнения задатчиков адресов конечных узлов каждой модели ветви, вторые входы первой схемы сравнения каждой модели узла соединены с выходами элементов И первой группы каждой модели ветви, вторые входы второй схемы сравнения каждой модели узла подключены к выходам элементов И третьей группы каждой модели ветви, выход первой схемы сравнения каждой модели узла соединен с входом счетчика ветвей и первым входом первого элемента И модели узла, второй вход которого подключен . к выходу третьейсхемы сравнения модели узла, а выход - к управляющему входу регистра длины пути модели узла, выход второй схемы сравнения каждой модели узла соединен с первыми входами элементов И второй группы модели узла, вторые входы которых подключены к выходам регистра длины пути модели узла и первым входам третьей схемы сравнения модели узла, а выходы - к первым входам сумматора модели узла, вторые входы сумматоров каждой модели узла соединены с выходами элементов И второй группы каждой модели ветви, выходы сумматора каждой модели узла соеди.нены с информационными входами регистра длины пути модели узла и вторыми входами третьей схемы сравнения модели узла, выход счетчика вет-. вей каждой модели узла соединен с единичным входом триггера модели узла, нулевой вход которого подключен к вторым входам элементов И первой группы модели узла и выходу второго элемента И модели узла, единичный выход триггера каждой модели узла соединен с первым входом второго элемента И модели узла и подключен к соответствующему входу второго элемента ИЛИ блока управления, а вторые входы вторых элементов И всех моделей узлов обьединены и подключены к выходу второго элемента И блока управления.

УСТРОЙСТВО ДПЯ МОГ ЕЛИРОВАКИЯ ЭКСТРЕМАЛЬНЫХ ПУТЕЙ НА ГРАЛЕ, содержащее блок из пмоделей ветвей по числу ветвей моделируемого графа, каждая из которых включает задатчики адресов начального и конечного узлов, содержащие регистр адреса и схему сравнения, перзую группу из m элементов И (где т- число разрядов кода адреса узла) и первый триггер, блок формирования топологии, содержащий элемент И, элемент ИЛИ, группу из п элементов И и узел выделения 1 старшего разряда кода адреса ветви; генератор импульсов, выход которого подключен к первому входу элемента И блока формирования топологии, выход элемента И блока формирования топологии соединен с первыми входами элементов И группы блока формирования топологии, вторые входы которых подключены .к соответствующим выходам узла выделения 1 старщего разряда кода адреса ветви блока формирования топологии, входы узла выделения 1 старшего разряда кода адреса ветви блока формирования топологии соединены с одноименными входами элемента ИЛИ блока формирования топологии и выходами соответствующих моделей ветвей, в каждой модели ветви выход регистра адг pecai задатчика адреса начального узла соединен с.первым входом схемы сравнения задатчкка адреса начального узла, второй вход которой соединен с выходами элементов И первой группы каждой модели ветви, первые .входы которых соединены с выходами регистра адреса и первыми входами . схемы сравнения задатчика адреса конечного узла соответствующей модели ветви, выход каждой схемы сравнения задатчика адреса конечного узла соединен с единичным входом первого триггера соответствующей модели (Л |ветви, отличающееся тем, что, с целью повышения быстрсВДейст- ВИЯ и распгарения функциональных возможностей за счет обеспечения определения максимального пути в графе, в уст эойство дополнительно введены блок управления, содержащий узел вьзделения 1 старшего разряда кода to адреса ветви графа., узел выделения со 1 старшего разряда кода режима О) работы устройства, группу из п элементов И, два элемента ИЛИ и два элемента И, блок ия q, моделей узлов по числу узлов моделируемого графа, каждая из которых содержит регистр кода адреса узла, регистр длины пути, три схемы сравнения, первую группу из (П элементов И, вторую группу из 5 элементов И (где s- число разрядов кода длины пути), триггер, два элемента И, сумматор и счетчик ветвей, в каждую модель дополнительно введены регистр длины ветви, вторая группа из f эле

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

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

блока автоматического формирования и к пятому входу блока управления CV.

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

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

входам элемента ИЛИ блока формирования топологии. В блок формирования топологии введены также группа из h элементов И (где п - число моделей ветвей) и узел выделения 1 старшего разряда кода адреса ветви графа, а в модели ветвей - группы из m элементов И (где т- число разрядов кода адреса узлов графа), npiiieM каждьм задатчик адреса начального и конечного узлов графа каждой модели ветви содержит регистр адреса и схе|му сравнения, первые входы схем сравнения, являющиеся входами задатчиков адресов узлов графа, объединены и подключены к выходам элементов И групп каждой модели ветви, вторые входы схем сравнения задатчиков адресов начальных узлов графа соединены с выходами регистров адреса начальных узлов графа, а выходами - с управляющими входами формирователей временных интервалов, вторые входы схем сравнения задатчиков адресов конечных узлов грдфа подключены к выходам регистров адресов конечньк узлов графа и первым входам элементо И групп соответствующей модели ветви выходы схем сравнения задатчиков адресов конечных узлов графы каждой модели ветви соединены с входами триггеров, выходы которых подключены к первым входам элементов И соответствующей модели ветви, вторые входы которых соединены с выходами формирователей временных интервалов, а выходы - с соответствующим входом узла вьщеления 1 старшего разряда кода адреса ветви графа блока формирования топологии, объединенным с одноименным входом элемента ИЛИ блока формирования топологии, выходы узла вьщеления 1 старшего разряда кода адреса ветви графа соединены с первыми входами элементов И группы блока формирования топологии, вторы входы которых подключены к выходу первого элемента И блока формирования топологии, а выходы соединены с вторыми входами элементов И групп соответствующих моделей ветвей графа 2, Однако данное устройство имеет .низкое быстродействие за счет моде лирования длины ветвей временными интервалами, при этом число импульсов моделирования длины ветви зависит от ее длины и в худшем случае

равно максимальной емкости счетчика формирователя временного интервала модели ветви. Наличие формирователя временных интервалов в моделях ветвей предполагает использование число-импульсного кода длины ветви, что ограничивает быстродействие при моделировании графа. Число импульсов .моделирования равно 2, где р - число двоичных разрядов кода длительности ветви. Таким .образом, чем больше точность моделирования (число разрядов р), тем менее быстродействующее устройство для моделирования. Кроме того, известное устройство не позволяет определить максимальный путь между узлами моделифуемого графа. Цель изобретения - увеличение быстродействия и расширение функциональных возможностей за счет обеспечения определения максимального пути в графе. Поставленная цель достигается тем, что в устройство для моделирования экстремальных путей на графе, содержащее .блок из п моделей ветвей по-числу ветвей моделируемого графа, каждая из которых включает задатчики адресов начального и конечного узлов, содержащие регистр адреса и схему сравнения, первую г.руппу из п элементов И (где m - число разрядов кода адреса узла) и первый триггер, блок формирования топологии, содержащий элемент И, элемент РШИ, группу из п элементов И и узел вьщеления 1 старшего разряда кода адреса ветви, генератор импульсов, выход которого подключен к первому входу элемента И блока формирования топологии, выход элемента И блока формирования топологии соединен с первыми входами элементов И группы блока формирования топологии, вторые входы которых подключены к соответствующим выходам узла вьщеления 1 старшего разряда кода адреса ветви блока формирования топологии, входы узла вьщеления 1 старшего разряда кода адреса ветви блока формирования топологии Соединены с одноименными входами элемента РШИ блока формирования топологии и выходами соответствующих моделей ветвей, в каждой модели ветви выход регистра адреса задатчика адреса начального узла соединен с первым входом схемы сравнения задатчика адреса HatlanbHoro узла, второй вход которой соединен с выходами элементов И первой группы каждой модели ветви, первые входы которых соединены с выходами регистра адреса и первыми входами схемы сравнения задатчика адреса конечного узла соответствующей модели ветви выход каждой схемы сравнения задатчи ка адреса конечного узла соединен с единичным входом первого триггера соответствующей модели ветви, дополнительно введены блок управления, содержащий узел выделения 1 старшего разряда кода адреса ветви графа, узел выделения 1 старш го разряда кода режима работы устройства, группу из п элементов И, два элемента ИЛИ и два элемента И, блок из . моделей узлов по числу узлов моделируемого графа, каждая из которых содержит регистр кода адреса узл регистр длины пути, три схемы срав,нения, первую группу из m элементов И, вторую группу из 5 элементов И (где 5 - число разрядов кода длины пути), триггер, два элемента И, сум матор и счетчик ветвей, в каждую мо дель ветви дополнительно введены регистр длины ветви, вторая группа из р элементов И (где р- число раз рядов кода длины ветви), третья группа из m элементов И, элемент ИЛИ и второй триггер, причем первый вход узла вьщеления 1 старшего разряда кода режима работы устройстг ва блока управления соединен с выходом элемента ИЛИ блока формирования топологии, второй и третий входы узла вьщелеиия 1 старшего разр да кода режима работы устройства блока управления соединен с выходами соответственно первого и второго элементов ИЛИ блока управления, первый выход узла вьщеления 1 старшего разряда кода режима работы устройства блока управления соединен с вторым входом элемента И блока формирования топологии, второй и третий выходы узла выделения 1 старшего разряда кода режима работы устройства блока управления подключены к первым входам соответственно первого и второго элементов И блока управления, вторые входы которых соединены с выходом генератора импульсов, выход первого элемента И блока управления соединен с первыми входами элементов И группы блока 176 управления, вторые входы которых подключены к соответствующим выходам узла выделения 1 старшего разряда кода адреса ветви графа блока управления, входы узла выделения 1 старшего разряда кода адреса ветви графа блока управления объединены с соответствующими входами первого элемента ИЛИ блока управления и подключены к единичным выходам первых триггеров соответствующих моделей ветвей, выходы элементов И группы блока управления соединены с нулевыми входами первых триггеров, первыми входами элементов ИЛИ и первыми входами элементов И второй и третьей групп -соответствующих моделей ветвей, вторые входы элементов И первой группы каждой модели ветви соединены с выходом элемента ИЛИ модели , вторые входы элементов И второй группы каждой модели ветви соединены с выходами регистра длины ветви модели ветви, вторые входы элементов И третьей группы каждой модели ветви соединены с выходами регистра адреса задатчика .адреса начального узла модели ветви, выход схемы сравнения задатчика aflpeqa начального узла каждой модели ветви соединен с единичным входом второго триггера модели ветви, единичный выход которого является выходом модели ветви, нулевой вход второго триггера каждой модели ветви соединен с вторым входом элемента ИЛИ модели Ветви и подключен к выходу соответствующего элемента И группы блока формирования топологии, выходы регистра кода адреса узла каждой модели узла соединены с первыми входами первой и второй схем сравнения и с первыми входами элементов И первой группы модели узла, выходы элементов, И первой группы каждой модели узла подключены к вторым входам схем сравнения задатчиков адреса конечных узлов каждой модели ветви, вторые входы первой схемы сравнения каждой модели узла соединены с выходами элементов И первой группы каждой модели ветви, вторые входы второй схемы сравнения каждой модели узла подключены к выходам элементов И третьей группы каждой модели ветви, выход первой схемы сравнения каждой модели узла соединен с входом счетчика ветвей и первым входом первого элемента И модели узла, второй вход которого подключей к выходу третьей схемы сравнения модели узла, а выход - к управляющему входу регистра длины пути модели узла, выход второй схемы сравнения каждой модели узла соединен с первыми входами элементов И второй группы модели узла, вторые входы которых подключены к выходам регистра длины пути модели узла и первым входам третьей схемы сравнения модели узла; а вькоды - к первым входам сумматора модели узла, вторы входы сумматоров каждой модели узла соединены с выходами элементов И второй группы каждой модели ветви, выходы сумматора каждой модели узла соединены с информационными входами регистра длины пути модели узла и вторыми входами третьей схемы сравнения модели узла, выход счетчика ветвей каждой модели узла соединен с единичным входом триггера модели узла, нулевой вход которого подключен к вторым входам .эл ементов И пер вой группы модели узла и выходу вто рого элемента И модели узла, единичный выход триггера каждой модели узла соединен с первым входом второ го элемента И модели узла и подключей к соответствуюР5ему входу второг элемента РШИ блока управления, а вторые -входы вторьк элементов И все моделей- узлов объединены и подключены к выходу второго элемента И блока управления Введение блока управления позволяет чередовать три режима работы устройства, а именно: режим распространения волны в графе, при которо происходит поочередный опрос каждой модели ветви с передачей адреса конечного узла ветви (волновой алго ритм) 5, этот режим имеет наименьший приоритет} режим определения экстре мяльного пути до узла, при котором происходит опрос модели ветви с вьщачей данных о длине ветви и адре сов начального и конечного узлов ветви, что в свою очередь приводит к выдаче экстремального расстояния до начального узла данной ветви и разрешения записи экстремального пути в регистр длины пути конечного узла данной ветви с выходом суммато ра, в котором суммируются экстремал ное расстояние до узла и длина ветв исходящей из этого узла, и режим опроса моделей узлов, при котором происходит опрос той модели узла, в которой на данный момент установлена готовность передачи кода адреса этого узла для перевода работы устройства во второй режим. Последний режим имеет высший приоритет. Узлы вьщеления 1 старшего разряда кода адреса ветви графа блока формирования топологии и блока управления используются для определения очередностей опроса моделей ветвей особенно в первом и втором режимах работы устройства. Очередность необходима вследствие использования одних и тех же линий передачи адресов и данных для всех моделей устройства. Таким образом, задача определения экстремального пути решается путем опроса каждой модели ветви при волновом процессе опроса каждой модели узла, когда все ветви до данного узла пройдены (для возбуждения тех моделей ветвей, которые входят в данный узел), и, наконец, повторного опроса ка ;одой модели ветви, входящей в данный узел, при определении экстремального пути. Для графа, имеющего п ветвей и q, узлов, задача решается за 2 п + с тактов и не зависит от точности моделирования веса ветвей. Расширение функциональных возможностей достигается за смет того, что для данного алгоритма функциодшрования устройства, т.е„ при определении пути после прохождения всех возможных путей до данного узла, можно определять как минимальный, тав и максимальный пути до данного узла. При этом меняется лишь режим работы схемы сравнения на больше-меньше и первоначальная установка регистров расстояний моделей узлов. На фиг. 1 дана функциональная схема предлагаемого устройства-, на фиг„ 2 - пример исследуемого графа на фиг. 3 - временная диаграмма работы устройства для данного примера; на фиг. 4 - узел вьщеления 1 старшего разряда кода режима работы для общего случая. Устройство содержит (фиг, 1) п моделей 1 ветвей, задатчики адресов начального 2 и конечного 3 узлов вершин модели ветви, регистры 4 адреса узлов, схемы 5 сравнения и первую

91

группу элементов И b модели ветви, первый триггер 7 модели ветви, блок 8 формирования топологии, элемент И 9, элемент ИЛИ 10 и группу из п элементов И 11 блока формирования топологии, узел 12 выделения 1 старшего разряда кода адреса ветви графа блока формирования топологии, генератор 13 импульсов, регистр 14 длины ветви модели ветви, вторую группу из р элементов И 15 модели ветви, третью группу из m элементов И 16 модели ветви, элемент ИЛИ 17 модели ветви, второй триггер 18 модели ветви, моделей 19 узлов, регистр 20 кода адреса узла модели узла, схемы 21 и 22 сравнения модели узла,, первую группу из w элементов И 23 модели узла, счетчик 24 ветвей модели узла, триггер 25 модели узла, первый и второй элементы И 26 и 27 модели узла, сумматор 28, регистр 29 длины пути модели узла, схему 30 сравнения модели узла, вторую группу из 5 элементов И 31 модели узла, узел 32 выделения 1 старшего разряда кода адреса ветви графа блока управления, узел 33 выделения 1 старшего разряда кода режима работы блока управления, группу элементов И 34 блока управления, первый и второй элементы ИЛИ 35 и 36 блока управления, первьш и второй элементы И 37 и 38 блока управления. Узел 33 выделения 1 старшего разряда кода режима работы (фиг. 4) включает группу из и элементов ИЛИ 39, группу из (п - 1) элементов НЕ 40, г|зуппу из ( п - 1) элементов И 41 .

Устройство работает следующим образом .(фиг, 1).

Первоначально в устройство заносится топология исследуемого графа путем установки регистров 4 и 20 адресов узлов графа в состояние, соответствующее кодам адресов узлов.

В регистры 14 длин ветвей заносятся величины, пропорциональные длинам ветвей, а в счетчики 24 ветвей число ветвей, входящих в данный узел. Кроме того, обнуляются все триггеры 7, 18 и 25 моделей и в зависимости от вида решаемой задачи устанавливается режим работы схем 30 сравнения на больше-меньше и состояния регистров 29 длины пути, при этом, если решается задача оп1710

ределения кратчайшего пути, схема 30 сравнения устанавливается в режим работы Сравнение на меньше, а в регистры 29 заносится максимальный

код. Если же решается задача определения максимального пути, схема 30 сравнения устанавливается в режим работы Сравнение на больше, а в регистры 29 заносится минимальный

КОД. Так как все триггеры 7, 18 и 25 находятся в нулевом состоянии, на выходах соответствующих элементов ИЛИ 35, 10 и 36 имеется нулевой сигнал, на выходах узла 33 также нулевой сигнап. Импульсы генератора 13 не проходят через элементы И 9, 37 и 38. Устройство, находится в состоянии, предшествующем рабочему.

Для запуска устройства на объединенные входы задатчиков 2 адресов начальньк узлов моделей ветвей, т.е. на схемы 5 сравнения задатчиков Ъдресов начальных узлов, подается код начального узла исследуемого графа.

При этом срабатывают задатчики адресов тех моделей ветвей, для которых этот узел является начальным, на выходах задатчиков адресов начальных узлов возникают импульсы, переводящие триггеры 18 этих моделей ветвей в единичное состояние. Сигналы от этих триггеров поступают на первый узел 12 выделения 1 старшего разряда кода адреса ветви графа, котоРьй выбирает один из этих сигналов, отмечая его сигналом уровня логической единицы на соответствующем выходе. Одновременно сигналы с триггеров 18 поступают на входы элемента

ИЛИ 10, откуда поступают на вход узла 33 выделения 1 старшего разряда кода режима работы На первом выходе узла 33 появляется уровень . логической единицы, который поступает на второй вход элемента И 9 блока формирования топологии В. С .приходом импульса от генератора 13 а выходе этого элемента И 9 также появляется импульс уровня логической

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

ветви, поступает на вторые входы первой группы элементов И 6, при этом содержимое регистра 4 задатчика адреса конечного узла 3 появляется на объединенных входах задатчиков адресов начальных узлов моделей ветвей, вызывая их срабатывание. Затем опрашивается следующая ветвь по сигналу готовности и т.д. По зад нему фронту сигнала опроса происходит сброс триггера 18 готовности. Таким образом происходит процесс рас пространений, волны в модели графа. В процессе распространения волны коды конечных узлов моделей 1 ветвей появляются на объединенных вторы входах первых схем 21 сравнения адресов узлов моделей 19 узлов. При равенстве кода адреса конечного узла опрашиваемой модели ветви и кода адреса соответствующего узла срабатывает схема 21 сравнения данной модели 19 узла, из содержимого счетчика 24 ветвей вычитается единица. Как только все пути до данного узла будут пройдены, содержимое счет чика 24 станет равным нулю и сработает триггер 25, выдавая сигнал готовности на второй элемент ИЛИ 36. С выхода этого элемента ИЛИ сигнал поступает на вход высшего приоритет узла 33, ас его выхода - на первый вход второго элемента И 38. Обслуживается только модель узла, все остальные сигналы готовностей моделей ветвей игнорируются, режим волнового распространения и режим сравнения путей временно приост анавливается. Опрашивается модель узла путем пода чи импульса генератора 13 через эле мент И 38 на второй вход второго элемента И 27, ас его выхода - на вторые входы первой группы элементо И 23 модели узла. При этом коД узла выдается на входы задатчиков 3 адре сов конечных узлов, т.е. на схему 5 сравнения этих задатчиков моделей ветвей. Срабатывают модели тех ветвей, которые входят в модель данного узла. Триггеры 7 готовности этих моделей устанавливаются в единичное состояние По заднему фронту сигнал опроса модели узла, приходящего на второй вход триггера 25, происходит его сброс. Затем устройство переходит в режим сравнения путей. Режим сравнения путей имеет бопее низкий приоритет, чем режим опроса узла, но более высокий, чем режим волнового распространения.При ритетность режимов определяется вхо |Дом подключения сигналов готовностей ;узла к узлу 33. Во время режима сравнения путей режим волнового распространения временно приостанавливается. Узел 33 блока управления по своей структуре и функционированию полностью аналогичен узлу вьщеления 1 старшего разряда кода адреса ветви графа и отличается только числом входов. Переходные процессы переключения логических цепей в устройстве должны полностью заканчиваться за период тактовой частоты генератора имиульсов, и во время действия следующего тактового импульса состояние выходов узлов выделения не должно меняться, в противном случае это может привести к сбою, выражающемуся в том, что во время действия одного тактового И1 ;1пульса будут опрошены две модели или даже устройство будет работать в двух режимах одновременно Для устранения подобных сбоев в сос:таве узлов следует применить выход1ной регистр (на фиг. 1 не показан), стробируемый импульсами генератора 13, Сигналы готовности с триггеров 7 моделей ветвей попадают на входы узла 32 вьщеления 1 старшего разряда кода адреса ветви графа и входы логического элемента ИЛИ 35 блока управления, с выхода которого они поступают на вход узла 33, а с него „а второй вход первого элемента И 37. Узел 32определяет первую по очередности модель ветви, и импульс опроса, приходящий на первые входы второй группы элементов И 15 с выхода соответствующего элемента группы элементов И 34, поступает ил эту модель ветви. Импульс опроса модели ветви приходит на входы второй 15, третьей 16 групп элементов И, а через элемент ИЛИ 17 - на входы первой группы элементов И 6. При этом из модели ветви выдаются коды начального и конечного адресов ветви и код, пропорциональный ее длине. Код начального адреса ветви поступает на вторые входы вторых схем 22 сравнения адресов узлов всех моделей узлов. Схема 22 сравнения той модели ветви, из которой выходит опрашиваемая ветвь, срабатывает, помещая через вторую группу элементов И 31 содержимое регистра длины пути до на первые входы сумматоров 28 всех моделей узлов, на вторые входь,которых приходит код длины опрашивае мой ветви. В сумматорах 28 моделей узлов происходит суммирование этих кодов. Содержимое сумматоров оравнивается с содержанием регистра 29 длины пути с помощью схемы 30 (Сравнения на больше-меньше. Из двух этих значений выбирается экстремальное. Если экстремальное значение находится в регистре 29, схема 30 сравнения не вырабатывает сигнала записи, а если оно находится на выходах сумматора 28 (сумматор комбинационного типа без памяти), вырабатывается сигнал записи. С помощью схемы 21 сравнения, соединенной с выходами первой группы элементов И опрашиваемой модели ветви, в свою очередь соединенных с регистром 4 задатчика 3 адреса конечного узла, выбирается модель узла, для которой данная ветвь является конечной Сигнал выбора модели узла с выхода схе мы 21 сравнения поступает на первый вход первого элемента И 26. Если на выходе схемы 30 сравнения этой модели, узла имеется импульс записи, юн проходит через элемент И 26 на вход записи регистра 29 длины пути Экстремальное значение заносится в регистр. Задним фронтом опроса модели ветви происходит сброс триггера 7 готовности по второму входу. Устройство производит последователь ньм опрос всех моделей ветвей, вход щих в данньй узел, выбирая каждый раз экстремальные значения из предьщущего значения длины пути, находящегося в регистре 29, и текущего расстояния на выходе сумматора 28. При вторичном опросе моделей ветвей для нахождения экстремальног пути счетчик 24 ветвей моделей узлов не обнулится, так как число опргшиваемых моделей ветвей не превысит число моделей, входящих в узел, а следовательно, максимальной емкос ти счетчика. Затем возобновляется волновой процесс распространения сигналов между моделями ветви. Таким образом, чередуя режимы ра боты устройства, вычисления длятся до тех пор, пока не будет просчитано экстремальное расстояние до конечного узла исследуемого графа или если он не задан, до тех пор, пока идут импульсы опроса моделей устрой ства. Результатом вычислений будут значения экстремальных путей от начального узла в регистрах 29 длины ч пути каждой модели узлов, связанной |С начальным узлом. Для пояснения работы устройства рассмотрим пример моделирования кратчайшего пути на графе. На фиг. 2, где представлен исследуемый граф, римскими цифрами обозначены номера узлов, в числителях арабских цифр Номера ветвей, в знаменателях - их длины. На фиг. 3 дана временная диаграмма устройства. Первоначально в устройство заносится топология исследуемого графа. При этом в регистрах 4 задатчиков адреса начального 2 и конечного 3 узлов графа и в регистре 14 длины ветви первой модели ветвей будет занесено соответственно 1, 2, 3, в регистрах второй модели ветви - 1, 2, 4, третьей - 2, 3, 3, четвертой 1, 3, 7. В регистрах 20 моделей первого узла будет занесена 1, второго узла - 2, третьего - 3, в счетчиках 24 второго и третьего узла - 2. Установлены в нулевое состояние все триггеры 7, 18 и 25 моделей. В регистрах 29 моделей узлов установлен максимальньй код, а в схемах 30 сравнения моделей узлов - режим сравнения на меньше. В регистре 29 модели первого узла заносится нулевое значениео Производится запуск устройства для моделирования посредством установки на входах задатчиков 2, начальных адресов узлов вершин моделей 1 ветвей кода 1 - начального узла графа (фиг. 3, эпюра б). При этом срабатьгоагот схемы 5 сравнения задатчиков 2 первой, второй и четвертой моделей ветвей, на выходах триггеров 18 этих моделей появятся сигналы уровня логической единицы (фиг. 3, эпюры в, г, д), которые, проходя через первый элемент ИЛИ 10 (фиг.З, эпюра е), поступают на вход узла 33; На втором входе элемента И 9 появляется уровень логической единицы, а с приходом импульса генератора 13 (фиг. 3, эшора а) на выходе элемента 9 появляется импульс (фиг. 3, эпюра ж) опроса модели ветви. Этот импульс, проходя через Первый элемент группы элементов И 11, опрашивает в порядке очередности первую модель ветвИо Импульсы опроса, проходя через элемент ИЛИ 17, поступают на вторые входы первой группы элементов И 6 этой модели ветви. При этом адрес конечного узла этой модели ветви (2) появляется на входах задатчиков 2 адресов начальных узлов моделей ветвей (фиг. 3, эпюра б). Это приводит к срабатьтанию задатчика 2 последней третьей модели ветви, а.следовательно, триггера 18 готовности этой модели ветви (фиг. 3, эпю ра з), а также к срабатыванию первой схемы 21 сравнения модели второго узла и из счетчика 24 этой модели вьр читается единица. По заднему фронту сигнала опроса (фиг. 3, эпюра ж) сбрасывается триггер 18 готовности первой модели ветви (фиг. 3, эпюра в) . Так как имеется готовность от оставшихся трех моделей ветвей, сигнал с выхода первого элемента ИЛИ Ю не исчезает (фиг. 3, эпюры г, д, з, е) и происходит опрос следующей по очередности второй модели ветви посредством подачи импульса опроса с выхода элемента И 9 (фиг. 3, эпюра ж) через соответствующий элемент группы 11, При этом на входе задатчиков 2 начальных узлов выдается код адреса конечного узла второй модели ветви (фиг. 3, эпюра б). В этот момент времени из.счетчика 24 ветвей модели 19 второго узла вычитается послед-няя единица и срабатьшает триггер 25 готовности (фиг. 3, эпюра и). На выходе второго элемента ИЛИ 36 появляется сигнал логической единицы, которьй,проходя через узел 33, подготавливает к срабатыванию второй элемент И 38. Дпя устранения состояНИИ в логических цепях узел выделения старшего по приоритету необходимо выполнить .3 памятью, стробируемой каждый раз импульсом генератора 13. С приходом импульса тактового генератора 13 на вькоде элемента 38 появляется импульс опроса модели узла (фиг. 3, эпюра к). Импульс опроса проходит через элемент И 27 модели второго узла, на первом входе которого имеется разрешающий уровень с выхода триггера 25 готовности, и проводит опрос регистра 20 адреса узла через первую группу элементов И 23. На входе задатчиков 3 .адреса конечных узлов моделей ветвей появляется Код данного узла - 2 (фиг. 3, эпюра л), При этом срабатывает задатчик 3 первой и второй моделей ветвей, на выходах их триггеров 7 готовностей,а следовательно, на выходе первого элемента ИЛИ 35 появляются сигналы уровня логической единицы (фиг. 3, эпюры м, н, о). По заднему фронту импульса опроса моделей узла (фиг. 3, эпюры к) происходит сброс триггера 25 готовности модели второго узла (фиг, 3, эпюра и). Сигналы готовностей моделей узлов больше не поступают на третий вход узла 33. Имеются только сигналы, готовностей второй, третьей, четвертой моделей ветвей от триггера 18, первой, второй моделей ветвей от триггеров 7. Узел 33 выбирает наиболее приоритетное из этих требований и устройство переходит в режим сравнения расстояний до узла (в данном случае до второго узла). Сигналы триггеров 7 моделей ветвей приходят через элемент ИЛИ 35 и узел 33 на второй вход первого элемента И 37, и с приходом тактового импульса генератора 13 .на его выходе появляется импульс опроса моделей ветвей в режиме сравнения (фиг. 3, эпюра п). Этот импульс, проходя через группу элементов И 34, появляется на выходе первого элемента этой группы и производится опрос первой по очередности модели первой ветви. Импульс -опроса проходит на управляющие входы третьей 16, второй 15, а через элемент Ш1И 17 первой 6 групп элементов И, вызывая появление соответственно на входах второй схемы 22 сравнения адреса узла кода начального адреса опрашиваемой ветви 1 (фиг, 3, эпюра р), на вторых . входах сумматоров 28 кода веса ветви - 3 (фиг. 3, эпюра с), на входах первой схемы 21 сравнения кода адреса конечного узла - 2 (фиг. 3, эпюра т) всех моделей узлов устройства моделирования. Вторая схема 22 сравнения модели первого узла срабатьгеает и через вторую группу элементов И 31 подается код расстояния до первого узла (О) на первые входы сумматоров 28 всех моделей узлов (фиг. 3, эпюра у). На выходах сумматоров 28 будет код суммы (фиг, 3, эпюра ф), который будет сравниваться с максимальным числом регистров 29, и схемы сравнения выдадут сигналы на запись (фиг. 3, эпюра х). Первая схема 21 сравнения модели второго узла сработает и импульс записи через элемент И 26 моде ли второго узла пройдет на вход записи регистра 29, в регистр занесется код 3 (для устранения состязаний в логической цепи записи регистр 29 необходимо вьшолнить с двойной памятью, при этоминформация с выхода сумматора по переднему фронту сигнала записи записывается в первую ступень регистра, а по заднему фронту - во вторую) . Произошел .опрос модели первой ветви, в результате чего в регистре 29 второго узла занеслось число 3. По заднему фронту сигнала опроса (фиг. 3, эпюра п) сбрасывается триггер 7 готовности модели первой ветви (фиг. 3, эпюра м), но имеется еще сигнал готовности модели второй ветви, и в следующем такте происходит опрос этой модели ветви (фиг. 3, эпюра п), при этом на входе вторых схем 22 сравнения адресов узлов появится код 1, на втором входе сумматора 28 - код 4 (вес второй ветви), на входе первых схем 21 сравнения - код 2, на пер вом входе сумматора - код О, а следовательно,на выходе сумматора код А (соответственно эпюры р, с, т, у, ф на фиг. 3). Импульс записи схемой 30 сравнения модели второго узла сформирован не будет, так как в регистре 29 этой модели находится число, меньше числа на выходе сумма тора, и состояние регистра не изменится,. По заднему .импульсу опроса сбрасывается триггер 7 готовности модели второй ветви и устройство переходит в режим распространения волны. В этом режиме происходит опрос моделей третьей и четвертой ветвей, после чего сработает триггер готовности третьего узла, а следовательно, элемент ИЛИ 36 (фиг. 3, эпюра и Следующим импульсом будет импульс оп роса модели третьего узла, в результате которого на входах задатчиков 3 адресов конечных узлов появится код 3 (соответственно эпюры к, л на фиг. 3) „ Сработают задатчики адре-сов конечных узлов третьей и четвертой моделей ветвей, а следовательно, триггеры 7 этих моделей ветвей. При этом на выходе элемента ИЛИ.35 появится сигнал готовности (фиг, 3, эпюра о) режима сравнения, В начале произойдет опрос третьей модели ветви, в результате чего в регистр 29 модели третьего узла занесется сумма длины третьей ветви и кратчайшего расстояния до второго узла . При опросе четвертой модели ветви сумма будет О + 7 7, импульса записи не возникнет. Результатом вычисления являются значения кратчайших путей от перво- i го узла в регистре расстояния второго узла-- 3, третьего - 6, Таким образом, в предлагаемом устройстве волновой процесс распространения сигнала от одной модели ват-. ви к другой осуществляется за один ; такт работы генератора, за одич.-такт происходит опрос модели узла для возбуждения всех входящих в него неделей ветвей и за один такт происходит опрос каждой входящей модели ветви с суммированием, веса самой ветви и расстояния до узла, из которого она выходит, и сравнением этой суммы с результатом предьщущих сравнений. Следовательно, задача нахождения экстремального пути в графе решается за 2 п + тактов работы устройства и не зависит от степени точности моделирования веса ветви. Для индикации непосредственно самого в графе в каждую модель узла мбжно ввести регистр, в который заносился бы код начального узла опрашиваемой ветви всякий раз; когда происходит запись экстремального расстояния в регистре.

2

2/2Л1У/рсуЬотУГох

:хз:гсж

Угт

.J