Устройство для моделирования экстремальных путей на графе

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУЬЛИН зд 6 06 Р 15/2 СССРРЫТИЙ ОПИСАНИЕ ИЗОБРЕТН АВТОРСНОМУ СВИДЕТЕЛЬСТВУ(56) 1. АвторскоеУ 485451, кл, С 062, Авторское снпо заявке Р 347059кл, Ь Об Г 15/20,еи ветвеи ветстнующих мод дой модели нетв Реса задатчика аж- адвыход регист адреса начальн первым входом кка адреса на Р 46В.К,Репинй центр С) го узла соединен с схемь альн равнения задато узла, второйен с выходами ьстно СССР 1975. тно СССРвход которои соедилементов И первой ет пы каждои модели ветви, первые соединены с выходами идетель 8/18 - 24 14.07.8которых стра адресравненчного чзл ервыми входами атчика адреса ветствующей моаждой схемы срав ег хе з с ли ветви, вых ния задатчика соединен с ед триггера соот реса конечного уз ичным входтствующей м первогоодели вет тлич е е с я тем быстродейстональных воз целью повышен т асширения Функ ей за счет обе и ечения ожно Ж 4 й узла кода ГОСУДАРСТВЕННЫЙ НОМИТЕ ПО ДЕЛАМ .ИЗОБРЕТЕНИЙ И О(54)(57) УСТРОЙСТВО ДПЯ МОДЕЛИРОВАНИЯЭКСТРЕМАЛЬНЫХ ПУТЕЙ НА ГРААЕ, содержащее блок из имоделей ветвей по числу ветнеи моделируемого графа, каждая из которых включает задатчики адресов начального и конечного узлов, содержащие регистр адреса и схему сравнения, перзую группу из в элементов И (где гп - число разрядон кода адреса узла) и первый триггер, блок Формирования топологии, содержащий элемент И, элемент ИЛИ, группу из и элементов И и узел вьделения "1" старшего разряда кода адреса ветви, генератор импульсов, наход которого подключен к первому входу элемента И блока Формирования топологии, выход элемента И блока Формирования топологии .соединен с первыми входами элементов И группы блока Формирования топологии, вторые входы которых подключены .к соответствующим выходам узла вьделения "1" старшего разряда кода адреса ветви блока Формирования топологии, входывыделения " 1" старшего разрядаадреса ветви блока Формирования топологии соединены с одноименными входами элемента ИЛИ блока фор 80112961 верования топологии и выходами соот деления максимального пути в графе,в устройство дополнительно введеныблок управления, содержащий узелвьделения "1" старшего разряда кодаадреса ветви графа, узел вьделения"1" старшего разряда кода режимаработы устройства, группу из п элементов И, два элемента ИЛИ и дваэлемента И, блок измоделей узловпо числу узлов моделируемого графа,каждая из которых содержит регистркода адреса узла, регистр длиныпути, три схемы сравнения, первуюгруппу из ю элементов И, вторуюгруппу из ь элементов И (где Б - число разрядов кода длины пути), триггер, два элемента И, сумматор исчетчик ветвей, в каждую модель ветви дополнительно введены регистрдлины ветви, вторая группа из Р эле"ветви, Импульсы опроса, проходя через элемент ИЛИ 17, поступают на вторые входы первой группы элементов И 6 этой модели ветви. При этом адрес конечного узла этой модели 5 ветви ("2") появляется на входах задатчиков 2 адресов начальных узлов моделей ветвей (фиг, 3, эпюра б). Это приводит к срабатыванию задатчика 2 последней третьей модели ветви, а,следовательно, триггера 18 готовности этой модели ветви (фиг, 3, эпюра з), а также к срабатыванию первой схемы 21 сравнения модели второго узла и из счетчика 24 этой модели вычитается единица. По заднему фронту сигнала опроса (фиг. 3, эпюра ж) сбрасывается триггер 18 готовности первой модели ветви (фиг. 3, эпюра в). 20Так как имеется готовность от оставшихся трех моделей ветвей, сигнал с выхода первого элемента ИЛИ 10 не исчезает (фиг. 3, эпюры г, д, з, е) и происходит опрос. следующей по очередности второй модели ветви посредством подачи импульса опроса с выхода элемента И 9 (фиг; 3, эпюра ж) через соответствующий элемент группы 11. При этом на входе задатчиков 2.ЗО начальных узлов выдается код адреса конечного узла второй модели ветви - "2" (фиг. 3, эпюра б), В этот момент времени из счетчика 24 ветвей модели 19 второго узла вычитается послед няя единица и срабатывает триггер 25 готовности (фиг. 3, эпюра и), На выходе второго элемента ИЛИ 36 появляется сигнал логической единицы, который, проходя через узел 33, под готавливает к срабатыванию второй элемент И 38. Для устранения состояний в логических цепях узел выделения старшего по приоритету необходимо выполнить в памятью, стробируемой 45 каждый раз импульсом генератора 13.С приходом импульса тактового генератора 13 на выходе элемента 38появляется импульс опроса модели узла (фиг. 3, эпюра к). Импульс опро са проходит через элемент И 27 модели второго узла, на первом входе которого имеется разрешающий уровень с выхода триггера 25 готовности, и проводит опрос регистра 20 адреса 55 узла через первую группу элементов И 23. На входе задатчиков З,адреса конечных узлов моделей ветвей появляется код данного узла - "2" (фиг. 3, эпюра л), При этом срабатывает задатчик 3 первой и второй моделей ветвей, на выходах их триггеров 7 готовностей,а следовательно, на выходе первого элемента ИЛИ 35 появляются сигналы уровня логической единицы (фиг. 3, эпюры и, н, о). По заднему фронту импульса опроса моделей узла (фиг. 3, эпюры к) происходит сброс триггера 25 готовности модели второго узла (фиг. 3, эпнра и). Сигналы готовностей моделей узлов больше не поступают на третий вход узла 33. Имеются только сигналы.готовностей второй, третьей, четвертой моделей ветвей от триггера 18, первой, второй моделей ветвей от триггеров 7. Узел 33 выбирает наиболее приоритетное из этих требований и устройство переходит в режим сравнения расстояний до узла (в данном случае до второго узла).Сигналы триггеров 7 моделей ветвей приходят через элемент ИЛИ 35 и узел 33 на второй вход первого элемента И 37, и с приходом тактового импульса генератора 13 .на его выходе появляется импульс опроса моделей ветвей в режиме сравнения (фиг, 3, эпюра п). Этот импульс, проходя через группу элементов И 34, появляется на выходе первого элемента этой группы и производится опрос первой по очередности модели первой ветви. Импульс опроса проходит на управляющие входы третьей 16, второй 15, а через элемент ИЛИ 17 первой 6 групп элементов И, вызывая появление соответственно на входах второй схемы 22 сравнения адреса узла кода начального адреса опрашиваемой ветви "1" (фиг. 3, эпюра р), на вторых входах сумматоров 28 кода веса ветви - "3" (фиг. 3, эпюра с), на входах первой схемы 21 сравнения кода адреса конечного узла - "2" (фиг, 3, эпюра т) всех моделей узлов устройства моделирования. Вторая схема 22 сравнения модели первого узла срабатывает и через вторую группу элементов И 31 подается код расстояния до первого узла ("0") на первые входы сумматоров 28 всех моделей узлов (фиг. 3, эпюра у). На выходах сумматоров 28 будет код суммы - 3 + 0 = 3 (фиг. 3, эпюра ф), который будет сравниваться с максимальным числомрегистров 29, и схемы сравнения выдадут сигналы на запись (Аиг. 3, эпюра х). Первая схема 21 сравнения модели второго узла сработает и импульс записи через элемент И 26 модели второго узла пройдет на вход записи регистра 29, в регистр занесется код 3 (для устранения состязаний в логической цепи записи регистр 29 необходимо выполнить с двойной памятью, при этоминформация с выхода сумматора по переднему фронту сигнала записи записывается в первую ступень регистра, а по заднему фронту - во вторую). Произошел .опрос модели первой ветви, в результате чего в регистре 29 второго узла занеслось число "3". По заднему Аронту сигнала опроса (фиг. 3, эпюра п) сбрасывается триггер 7 готовности модели первой ветви (Аиг, .3, эпюра м), но имеется еще сигнал готовности модели второй ветви, и в следующем такте происходит опрос этой модели ветви (Аиг. 3, эпюра г), при этом на входе вторых схем 22 сравненияии адресов узлов появится код 1 , на1411 втором входе сумматора 28 - код (вес второй ветви), на входе первых схем 21 сравнения - код "2", на пер 11 11 вом входе сумматора - код 0 , а следоват ельно , на выходе сумматора - код " 4" ( со отв ет ственно эпюры р , с , т, у, ф на фиг . 3 ) . Импульс записи схемой 3 О сравнения модели второго узла сАормиров ан не будет, так как в регистре 2 9 этой модели находится число, меньше числа на выходе сумматора , и состояние регистра не изменится . По заднему импульсу опроса сбрасывается триггер 7 готовностимодели второй ветви и устройствопереходит в режим распространенияволны .В этом режиме происходит опросмоделей третьей и четвертой ветвей,после чего сработает триггер готовности третьего узла, а следовательно , элемент ИЛИ 3 6 (фиг , 3 , эпюр а и)ЗО 40 дели ветви сумма будет О + 7 = 7, импульса записи не возникнет.Результатом вычисления являются значения кратчайших путей от первого узла в регистре расстояния второго узла - 3, третьего - 6Таким образом, в предлагаемом устройстве волновой процесс распрост- ранения сигнала от одной модели вет-, ви к другой осуществляется за один такт работы генератора, за один, такт происходит опрос модели узла для возбуждения всех входящих в него моделей ветвей и за один такт происходит опрос каждой входящей модели ветви с суммированием веса самой1 ветви и расстояния до узла, из которого она выходит, и сравнением этойсуммы с результатом предыдущих срав-нений. Следовательно, задача нахож"дения экстремального пути в граферешается за 2 п +тактов работыустройства и не зависит от степениточности моделирования веса ветви.Для индикации непосредственносамого пути в граАе в каждую модельузла мджно ввести регистр, в который заносился бы код начального уэла опрашиваемой ветви всякий раэ,когда происходит запись экстремаль/ного расстояния в регистре. Следующим импульсом будет импульс оп- роса модели третьего узла, в результате которого на входах задатчиков13 адресов конечных узлов появится5 код 3 (соответственно эпюры к, лна фиг, 3), Сработают задатчики адре-.сов конечных узлов третьей и четвертой моделей ветвей, а следовательно,триггеры 7 этих моделей ветвей. При 10 этом на выходе элемента ИЛИ 35 появится сигнал готовности (фиг. 3,эпюра о) режима сравнения; В началепроизойдет опрос третьей моделиветви, в результате чего в регистр 15 29 модели третьего узла занесетсясумма длины третьей ветви и кратчайшего расстояния до второго узла3 + 3 = 6При опросе четвертой мо1129 Ы 7 Р С Я 2 Король ктор М.Петр еф Заказ 9454 Тираж 69Государствеелам изобреква, Ж,сноеСР Подпиомитета ССоткрытийя наб д, 4/ ого е 113035,а а б д д е Ж 3 0 Составитель С,НазаровТехред Ж.Кастелевич Корре Патент", г, Ужгород, ул, Проектная,11296 ментов И (где р - число разрядов кода длины ветви), третья группа из м элементов И, элемент ИЛИ и второй триггер, причем первый вход узла выделения "1" старшего разряда кода режима работы устройства блока управления соединен с выходом элемента ИЛИ блока Аормирования топологии, второй и третий входы узла выделения "1" старшего разряда кода режима работы устройства блока управления соединены с выходами соответственно первого и второго элементов ИЛИ блока управления, первый выход узла выделения "1" старшего разряда кода режима работы устройства блока управления соединен с вторым входом элемента И блока Ьормирования топологии, второй и третий выходы узла выделения "1" старшего разряда кода режима работы устройства блока управления подключены к первым входам соответственно первого и второго элементов И блока управления, вторые входы которых соединены с выходом .генератора импульсов, выход первого элемента И блока управления соединен с первыми входами элементов И группы блока управления, вторые входы которых подключены к соответствующим выходам узла выделения "1" старшего разряда коца адреса ветви граАа блока управления, входы узла выделения "1" старшего разряда кода адреса ветви грайа блока управления объединены с соответствующими входами первого элемента ИЛИ блока управления и подключены к единичным выходам первых триггеров соответствующих моделей ветвей, выходы элементов И группы блока управления соединены с ну 1 левыми входами первых триггеров, первыми входами элементов ИЛИ и первыми входами элементов И второй и третьей групп соответствующих моделей ветвей, вторые входы элементов И первой группы каждой модели ветви соединены с выходом элемента ИЛИ модели ветви, вторые входы элементов И второй группы каждой модели ветви, соединены с выходами регистра длины ветви модели ветви, вторые входы элементов И третьей группы каждой модели ветви соединены с выходами регистра адреса задатчика адреса начального узла модели ветви, выход схемы сравнения задатчика адреса на" чального узла каждой модели ветви соединен с единичным входом второго 17регистра модели ветви, единичныйвыход которого является выходом модели ветви, нулевой вход второготриггера каждой модели ветви соединен с вторым входом элемента ИЛИмодели ветви и подключен к выходусоответствующего элемента И группыблока Аормирования топологии, выходырегистра кода адреса узла каждой модели узла соединены с первыми входами первой и второй схем сравненияи с первыми входами элементов Ипервой группы модели узла, выходыэлементов И первой группы каждоймодели узла подключены к вторым входам схем сравнения задатчиков адресов конечных узлов каждой моделиветви, вторые входы первой схемысравнения каждой модели узла соединены с выходами элементов И первойгруппы каждой модели ветви, вторыевходы второй схемы сравнения каждоймодели узла подключены к выходамэлементов И третьей группы каждоймодели ветви, выход первой схемысравнения каждой модели узла соединен с входом счетчика ветвей ипервым входом первого элемента И моделиузла, второй вход которого подключен .к выходу третьей схемы сравнения модели узла, а выход - к управляющемувходу регистра длины пути модели узла, выход второй схемы сравнениякаждой модели узла соединен с первыми входами элементов И второй груп-.пы модели узла, вторые входы кото -рых подключены к выходам регистрадлины пути модели узла и первым входам третьей схемы сравнения моделиузла, а выходы - к первым входамсумматора модели узла, вторые входысумматоров каждой модели узла соединены с выходами элементов И второйгруппы каждой модели ветви, выходысумматора каждой модели узла соединены с информационными входами регистра длины пути модели узла ивторыми входами третьей схемы сравнения модели узла, выход счетчика вет-.вей каждой модели узла соединен сединичнымвходом триггера моделиузла, нулевой вход которого подключен к вторым входам элементов Ипервой группы модели узла и выходувторого элемента И модели узла, единичный выход триггера каждой моделиузла соединен с первым входом второго элемента И модели узла и подключен к соответствующему входу второ1129617 го элемента ИЛИ блока управления,а вторые входы вторьх элементов И всех моделей узлов обьеИзобретение относится к вычислительной технике, в частности к устройствам для моделирования экстремальных путей на графе при решении задач оптимизации. 5 Известно устройство для моделирования кратчайших путей на графе, содержащее блок автоматического формирования топологии, блок управления, к первому входу которого подключен выход генератора, модели ветвей, включающие два задатчика адресов узлов, формирователь временных интервалов, схему индикации, две 5 схемы совпадения, схему разделения и триггер блокировки, причем первый выход блока управления соединен с блоком автоматического формирования топологии и задатчиков адресов узлов, второй выход подключен к схеме индикации моделек ветви, а третий выход - к формирователю временных интервалов моделей, один выход блока автоматического формирования топологии соединен с формирователями временных интервалов и с вторым входом блока управления, а другой его выход подключен к третьему входу блока управления, входы формирователей временных интервалов моделей соединены с выходами задатчиков адресов узлов и триггера блокировки, а их выходы подключены к схемам индика-. ции, триггеру блокировки и четвертому входу блока управления, входы первой и второй схем совпадения моделей ветвей подключены соответственно к выходам первого и второго задатчиков адресов и выходу триггера блокировки этих моделей, а выходы40 схем совпадения через схему разделения каждоц модели подключены соответственно к выходам первого и второго задатциков адреса и выходу триггера блокировки этих моделей, а выходы45 схем совпадения через схему разделения каждой модели подключены к входу динены и подключены к выходу второго элемента И блока управления. блока автоматического формирования и к пятому входу блока управления 11 .Однако данное устройство имеет низкое быстродействие за счет последовательной организации задания адресов при формировании топологии и за счет моделирования длины ветвей временными интервалами. При этом минимальное число импульсов, необходимых для моделирования одногоадреса, равно максимальному числу узлов графа, который может быть смонтирован на данном устройстве, а число импульсов моделирования длины ветвей зависит от ее длины и в худшем случае равно максимальной емкости счетчика формирования временного интервала модели ветви. Наиболее близким к предлагаемому является устройство для моделирования кратчайших путей на графах, содержащее блок из и моделей ветвейпо числу ветвей моделируемого графа, каждая из которьос состоит из задатчиков адресов начального и конечного узлов графа, формирователя временных интервалов, элемента И и триггера, блок формирования топологии, содержащий первый и второй элемент И, элемент ИЛИ и элемент НЕ, генератор импульсов, первый и второй выходы которого подключены к первому входу первого элемента И блока формирования топологии и первому входу второго элемента И блока Формирования топологии, выход элемента ИЛИ блока формирования топологии подключен к второму входу первого элемента И блока формирования топологии, через элемент НЕ - к второму входу второго элемента И блока формирования топологии, вьпсод второго элемента И блока формирования топологии соединен с информационными входами формирователей временных интервалов каждой модели ветви, выходы моделей ветвей подключены к соответствующим1123входам элемента ИЛИ блока формирова ния топологии. В блок Ьормирования топологии введены также группа изэлементов И (где и - число моделейн 11 ветвей) и узел выделения 1 старшего разряда кода адреса ветви графа, а в модели ветвей - группы из в элементов И (где в - число разрядов кода адреса узлов граЬа), причем каждый задатчик адреса начального и 1 р конечного узлов граЬа каждой модели ветви содержит регистр адреса и схему сравнения, первые входы ехем сравнения, являющиеся входами задатчиков адресов узлов графа, объедине. - ны и подключены к выходам элементов И групп каждой модели ветвй, вторые входы схем сравнения задатчиков адресов начальных узлов графа соедине-. ны с выходами регистров адреса начальных узлов граЬа, а выходами - с управляющими входами формирователей временных интервалов, вторые входы схем сравнения задатчиков адресов .конечных узлов граЬа подключены к выходам регистров адресов конечных узлов граЬа и первым входам элементов И групп соответствующей модели ветви, выходы схем сравнения задатчиков адресов конечных узлов граЬы каждой модели ветви соединены с входами триггеров, выходы которых подключены к первым входам элементов И соответствующей модели ветви, вторые входы которых соединены с выходами Ьорми 35 рователей временных интервалов, а ;выходы - с соответствующим входом узла выделения "1" старшего разряда кода адреса ветви граЬа блока Ьормирования топологии, объединенным с одноименным входом элемента ИЛИ блока Ьормирования топологии, выходы узла выделения " 1" старшего разряда кода адреса ветви граЬа соединены с первыми входами элементов И группы блока Ьормирования топологии, вторые входы которых подключены к выходу первого элемента И блока формирования топологии, а выходы соединены с вторыми входами элементов И групп50 соответствующих моделей ветвей граЬа 2 .Однако данное устройство имеет ,низкое быстродействие за счет моде пирования длины ветвей временньгми 55 интервалами, при этом число импульсов моделирования длины ветви зависит от ее длины и в худшем случае 9617 равно максимальной емкости счетчика формирователя временного интервала модели ветви, Наличие Ьормкрователя временных интервалов в моделях ветвей предполагает использование число-импульсного кода длины ветви, что ограничивает быстродействие при моделировании граЬа. Число импульсов .моделирования равно 2 , гдеР р - число двоичных разрядов кода длительности ветви. Таким .образом, чем больше точность моделирования (число разрядов р ), тем менее быстродействующее устройство для моделирования, Кроме того, известное устройство не позволяет определить максимальный путь между узлами моделируемого граЬа.Цель изобретенкя - увеличение быстродействия и расширение Ьункцкональных возможностей за счет обеспечения определения максимального пути в граЬе.Поставленная цель достигается тем, что в устройство для моделирования экстремальных путей на граЬе, содержащее .блок из о моделей ветвей по числу ветвей моделируемого граЬа, каждая из которых включает задатчики адресов начального к конечного узлов, содержащие регистр адреса и схему сравнения, первую группу из элементов И (где в - число разрядов кода адреса узла) и первый триггер, блок формирования топологии, содержащий элемент И, элемент ИЛИ, группу из и элементов И и узел выделения "1" старшего разряда кода адреса ветви, генератор импульсов, выход которого подключен к первому входу элемента И блока формирования топологии, выход элемента И блока Ьормирования топологии соединен с первыми входами элементов И группы блока формирования топологии, вторые входы которых подключены к соответствующим выходам узла выделения "1" старшего разряда кода адреса ветви блока Ьормирования топологии, входы узла выделения "1" старшего разряда кода адреса ветви блока Ьормирования топологии соединены с одноименными входами элемента ИЛИ блока формирования топологии и выходами соответствующих моделей ветвей, в каждой модели ветви выход регистра адреса задатчика адреса начального узла соединен с первым входом схемы срав."11293нения задатчика адреса наскального узла, второй вход которой соединен с выходами элементов И первой группы каждой модели ветви, первые входы которых соединены с выходами регист 5 ра адреса и первыми входами схемы сравнения задатчика адреса конечного узла соответствующей модели ветви, выход каждой схемы сравнения задатчика адреса конечного узла соединен с единичным входом первого триггера соответствующей модели ветви, дополнительно введены блок управления,содержащий узел выделения 1 старше го разряда кода адреса ветви гр аАаузел вьделения " 1 " стар ш . го разряда кода режима работы устройства, группу из п элементов И, дв а элемента ИЛИ и два элемента И, блок из . моделей уэлс в по числу узлов моделируемого гр айакаждая из которых содержит регистр кода адреса узла , регистр длины пути, три схемь 1 ср ав, нения, первую группу из в элементов И, вторую группу из ч элементов И ( где 5 - число разрядов кода длины пути) , триггер , два элемента И, сумматор и счетчик ветвей , в каждую модель ветви дополнительно введенырегистр длины ветви, вторая группа из р элементов И (где р - число разрядов кода длины ветви), третьягруппа из и элементов И, элемент ИЛИ и второй триггер, причем первый вход узла выделения "1" старшего разряда кода режима работы устройст. З 5 ва блока управления "оединен с выходом элемента ИЛИ блока Аормирования топологии, второй и третий входы узла выделения "1" старшего разряда кода режима работы устройства 4 О блока управления соединен с выходами соответственно первого и второго элементов ИЛИ блока управления, первый выход узла вьделения "1" старшего разряда кода режима работы уст ройства блока управления соединен с вторым входом элемента И блока Аормирования топологии, второй и третий выходы узла вьделения "1" старшего разряда кода режима работы 50 устройства блока управления подключены к первым входам соответственно первого и второго элементов И блока управления, вторые входы которых соединены с выходом генератора им пульсов, выход первого элемента И блока управления соединен с первыми входами элементов И группы блока б 17 6управления, вторые входы которых подключены к соответствующим выходам узла вьделения "1" старшего разряда кода адреса ветви граАа блока управления , входы узла выделения 1 старше го разряда кода адреса ветви гр аа блока управления объединены с соотв ет ствуюшими входами первого элемент а ИЛИ блока управления и подключены к единичным выходам первых тригге ров соответствующих моделей ветвей , выходы элементов И группы блока управления соединены с нулевыми входами первых триггер ов , первыми входами элементов ИЛИ и первыми входами элементов И второй и третьей групп соответствующих моделей ветвей , вторые входы элементов И первой группы к ажпой модели ветви со едине ны с выходом элемента ИЛИ модели в етв.и , вторые входы элементов И второй группы каждой модели ветви соединены с выходами регистра длины ветви модели ветви , вторые входы элементов И третьей группы каждой модели ветви соединены с выходами регистра адреса з адатчик а ,адр еса начального узла модели ветви , выход схемы сравнения з адатчика адре г,а нач ально го узла каждой модели ветви соединен с единичным входом второго триггера модели ветви, единичный выход которого является выходом модели ветви, нулевой вход второго триггера каждой модели ветви соединен с вторым входом элемента ИЛИ модели ветви и подключен к выходу соответствующего элемента И группы, блока Ьо рмирования топологии, выходы регистра кода адреса узла каждой модели узла соединены с первыми входами первой и второй схем сравнения и с первыми входами элементов И первой группы модели узла, выходы элементов, И первой группы каждой модели узла подключены к вторым входам схем сравнения задатчиков адр еса конечных узлов каждой модели в етви, вторые входы первой схемы сравнения каждой модели узла соединены с выходами элементов И первой группы каждой модели ветви , вторые входы второй схемы сравнения каждоймодели узла подключены к выходамэлементов И третьей группы каждоймодели ветви , выход первой . схемысравнения каждой моделиузла соединен с входом счетчика ветвей и первым входом первого элемента И моде 1129617 8ли узла, второй вход которого подключен к выходу третьей схемы сравнения модели узла, а выход - к управляющему входу регистра длины пути модели узла, выход второй схемы 5 сравнения каждой модели узла соединен с первыми входами элементов И второй группы модели узла, вторые вхоДы которых подключены к выходам регистра длины пути модели узла и первым входам третьей схемы сравнения модели узла, а выходы - к первым входам сумматора модели узла, вторые входы сумматоров каждой модели узла соединены с выходами элементов И 15 второй группы каждой модели ветви выходы сумматора каждой модели узла соединены с информационными входами регистра длины пути модели узла и вторыми входами третьей схемы срав нения модели узла, выход счетчика ветвей каждой модели узла соединен с единичным входом триггера модели узла, нулевой вход которого подключен к вторым входам .элементов И пер вой группы модели узла и выходу второго элемента И модели узла, единичный выход триггера каждой модели узла соединен с первым входом второго элемента И модели узла и подклю- З 0 чен к соответствующему входу второго 1элемента ИЛИ блока управления, а вторые входы вторых элементов И всех моделей узлов объединены и поцключены к выходу нторого элемента И35 блока управления,Введение блока управления позволяет чередовать три режима работы устройства, а именно: режим распространения волны в грайе, при котором 40 происходит поочередный спрос каждой модели ветви с передачей адреса конечного узла ветви 1,волновой алгоритм), этот режим имеет наименьший приоритет, режим определения экстре мального пути до узла, при котором происходит опрос модели ветви с выдачей данных о длине ветви и адресов начального и конечного узлов ветви, что в сваю очередь приводит 50 к выдаче экстремального расстояния до начального узла данной ветви и разрешения записи экстремального пути в регистр длины пути конечного узла данной ветви с выходом суммато ра, в котором суммируются экстремальное расстояние до узла и длина ветви, исходящей из этого узла, и режим опроса мгделей узлов, при которомпроисходит опрос той модели узла,в которой на данный момент установлена готовность передачи кода адреса этого узла для перевода работыустройства во второй режим. Последний режим имеет высший приоритет,Узлы выделения "1" старшего разрядакода адреса ветви граАа блока Ьормирования топологии и блока управления используются для определенияочередностей опроса моделей ветвейособенно н первом и втором режимахработы устройства. Очередность необходима вследствие использованияодних и тех же линий передачи адре -сон и данных для всех моделей устройства.Таким образом, задача определенияэкстремального пути решается путемопроса каждой модели ветви при волновом процессе опроса каждой моделиузла, когда нсе ветви да данногоузла пройдены (для возбуждения техмоделей ветвей, которые входят вданный узел), и, наконец, повторногоопроса каждой модели ветви, входящей в данньгй узел, при определенииэкстремального пути. Для грапа,имеющего о ветвей и 1, узлов, задачарешается за 2 и + с тактов и не зависит от точности моделирования весаветвей,Расширение функциональных возможностей достигается за спет того,что для данного алгоритма Функционирования устройства, т.е. при определении пути после прохождения всехвозможных путей до данного узла,можно определять как минимальный, таьи максимальный пути до данного узла,При этом меняется лишь режим работысхемы сравнения на больше-меньшеи первоначальная установка регистроврасстояний моделей узлов.На Лиг. 1 дана функциональнаясхема предлагаемого устройства наФиг. 2 - пример исследуемого грайа,на Фиг. 3 - временная диаграмма работы устройства для данного примера; на Фиг. 4 - узел выделения "1" старшега разряда кода режима работы для общего случая. Устройство содержит (Лиг, 1) и моделей 1 ветвей, задатчики адресов начального 2 и конечного 3 узлов вершин модели ветви, регистры 4 адреса узлов, схемы 5 сравнения и первую11296 50 55 группу элементов И Ь модели ветви,первый триггер 7 модели ветви, блок8 йормирования топологии, элементИ 9, элемент ИЛИ 10 и группу из иэлементов И 11 блока Аормированиятопологии, узел 12 выделения "1"старшего разряда кода адреса ветвиграАа блока Аормирования топологии,генератор 13 импульсов, регистр 14длины ветви модели ветви, вторуюгруппу из р элементов И 15 моделиветви, третью группу из в элементовИ 16 модели ветви, элемент ИЛИ 17модели ветви, второй триггер 18 модели ветви, ч, моделей 19 узлов, ре-гистр 20 кода адреса узла моделиузла, схемы 21 и 22 сравнения модели узла, первую группу из ю элементов И 23 модели узла, счетчик 24ветвей модели узла, триггер 25 модели узла, первый и второй элементыИ 26 и 27 модели узла, сумматор 28,регистр 29 длины пути модели узла,схему 30 сравнения модели узла, вторую группу из з элементов И 31 модели узла, узел 32 выделения "1"старшего разряда кода адреса ветвиграйа блока управления, узел 33 выделения "1" старшего разряда кодарежима работы блока управления, груп-,пу элементов И 34 блока управления,первый и второй элементы ИЛИ 35 и36 блока управления, первый и второй элементы И 37 и 38 блока управления, Узел 33 выделения "1" старшего разряда кода режима работыЭ 5(фиг. 4) включает группу из н элементов ИЛИ 39, группу из ( и - 1) элементов НЕ 40, группу из ( п - 1) элементов И 41.40Устройство работает следующим образом.(Лиг. 1),Первоначально в устройство заносится топология исследуемого грайапутем установки регистров 4 и 2045адресов узлов графа в состояние, солтветствующее кодам адресов узлов,В регистры 14 длин ветвей заносятся величины, пропорциональные длинам ветвей, а в счетчики 24 ветвей - число ветвей, входящих в данный узел, Кроме того, обнуляются все триггеры 7, 18 и 25 моделей и в зависимости от вида решаемой задачи устанавливается режим работы схем 30 сравнения на больше-меньше и состояния регистров 29 длины пути, при этом, если решается задача оп 10ределения кратчайшего пути, схема 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 блока Аормирования топологии 8. С приходом импульса от генератора 13 на выходе этого элемента И 9 также появляется импульс уровня логической единицы, который, пройдя через со,ответствующий элемент группы элементов И 11, производит опрос одной из моделей ветвей, Импульс опроса, проходя через элемент ИЛИ 17 модели ветви, поступает на вторые входы первой группы элементов И 6, при этом содержимое регистра 4 задатчика ,адреса конечного узла 3 появляетсяна объединенных входах задатчиковадресов начальных узлов моделейветвей, вызывая их срабатывание,Затем опрашивается следующая ветвьпо сигналу готовности и т.д, По заднему Фронту сигнала опроса происходит сброс триггера 18 готовности,Таким образом происходит процесс распространения. волны в модели грайа,В процессе распространения волны 10воды конечных узлов моделей 1 ветвей появляются на объединенных вторыхвходах первых схем 21 сравненияадресов узлов моделей 19 узлов, Приравенстве кода адреса конечного узла 15опрашинаемой модели ветви и кодаадреса соответствующего узла срабатывает схема 21 сравнения данноймодели 19 узла, из содержимогосчетчика 24 ветвей вычитается единица. Как только все пути до данногоузла будут пройдены, содержимое счетчика 24 станет равным нулю и сработает триггер 25, выдавая сигнал готовности на второй элемент ИЛИ 36. 25С выхода этого элемента ИЛИ сигналпоступает иа вход высшего приоритетаузла 33, а с его выхода - на первыйвход второго элемента И 38. Обслуживается только модель узла, все остальные сигналы готовностей моделейветвей. игнорируются, режим волновогораспространения и режим сравненияпутей временно приостанавливается,Опрашивается модель узла путем подачи импульса генератора 13 через элемент И 38 на второй вход второгоэлемента И 27, а с его ныхода - навторые входы первой группы элементовИ 23 модели узла. При этом код узлавыдается на входы задатчиков 3 адресов конечных узлов, т.е. на схему 5сравнения этих задатчиков моделейветвей. Срабатывают модели тех вет"вей, которые входят в модель данного узла. Триггеры 7 готовности этихмоделей устанавливаются в единичноесостояние. По заднему Фронту сигналаопроса модели узла, приходящего навторой вход триггера 25, происходитего сброс. Затем устройство переходит в режим сравнения путей,Режим сравнения путей имеет бопее низкий приоритет, чем режим оп- . роса узла, но более высокий, чем . 5 режим волнового распространения.Приоритетность режимов определяется входом подключения сигналов готовностей к узлу 33. Во время режима сравнения путей режим волнового распространения временно приостанавливается.Узел 33 блока управления по своей структуре и Аункционированию полностью аналогичен узлу выделения "1" старшего разряда кода адреса ветви грайа и отличается только числом входовПереходные процессы переключения логических цепей в устройстве должны полностью заканчиваться за период тактовой частоты генератора имиульсов, и во время действия следующего тактового импульса состояние выходов узлов выделения не должно меняться, в противном случае это может привести к сбою, выражающемуся в том, что во время дей ствия одного тактового импульса будут опрошены дне модели или даже устройство будет работать в двук режимах одновременно. Для устранения подобных сбоев в составе узлов следует применить выходной регистр (на Лиг, 1 не показан), стробируемый импульсами генератора 13.Сигналы готовности с триггеров 7 моделей ветвей попадают на входы узла 32 выделения "1" старшего разряда кода адреса ветви граАа и входы логического элемента ИЛИ 35 блокауправления, с выхода которого они поступают на вход узла 33, а с него на второй вход первого элемента И 37. Узел 32 определяет первую по очередности модель ветви, и импульс опроса, приходящий на первые входы второй группы элементов И 15 с выхода соответствующего элемента группы элементов И 34, поступает на эту модельветви. Импульс опроса модели ветвиприходит на входы второй 15, третьей 16 групп элементов И, а черезэлемент ИЛИ 17. - на входы первой группы элементов И. 6. При этом измодели ветви выдаются коды начального и конечного адресов ветви и код,пропорциональный ее длине. Код начального адреса ветви поступает на вторые входы вторых схем 22 сравнения адресов узлов всех моделей узлов, Схема 22 сравнения той модели ветви, из которой выходит опрашиваемая ветвь, срабатывает, помещая через вторую группу элементов И 31 содержимое регистра длины пути до;узла на первые входы сумматоров 28всех моделей узлов, на вторые входь,которых приходит код длины опрашиваемой ветви, В сумматорах 28 моделейузлов происходит суммирование этихкодов. Содержимое сумматоров сравнивается с содержанием регистра 29длины пути с помощью схемы 30 бравнения на больше-меньше. Из двухэтих значений выбирается экстремальное. Если экстремальное значение 10находится в регистре 29, схема 30сравнения не вырабатывает сигналазаписи, а если оно находится на выходах сумматора 28 (сумматор комбинационного типа без памяти), вырабатывается сигнал записи. С помощьюсхемы 21 сравнения, соединенной свыходами первой группы элементов И 6опрашиваемой модели ветви, в своюочередь соединенных с регистром 4 20задатчика 3 адреса конечного узла,выбирается модель узла, для которойданная ветвь является конечной. Сигнал выбора модели узла с выхода схемы 21 сравнения поступает на первый 25вход первого элемента И 26, Еслина выходе схемы 30 сравнения этоймодели. узла имеется импульс записи,он проходит через элемент И 26 навход записи регистра 29 длины пути. МЭкстремальное значение заноситсяв регистр. Задним фронтом опросамодели ветви происходит сброс триггера 7 готовности по второму входу.Устройство производит последовательный опрос всех моделей ветвей, входящих в данный узел, выбирая каждыйраз экстремальные значения изпредыдущего значения длины пути,находящегося в регистре 29, и текущего расстояния на выходе сумматора28, При вторичном опросе моделейветвей для нахождения экстремальногопути счетчик 24 ветвей моделей узлов не обнулится, так как число оп-45рашиваемых моделей ветвей не превысит число моделей, входящих в узел,а следовательно, максимальной емкости счетчика. Затем возобновляетсяволновой процесс распространениясигналов между моделями ветви.Таким образом, чередуя режимы работы устройства, вычисления длятся до тех пор, пока не будет просчитано экстремальное расстояние до ко нечного узла исследуемого графа или, если он не задан, до тех пор, пока идут импульсы опроса моделей устройства. Результатом вычислений будутзначения экстремальных путей от начального узла в регистрах 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 (фиг,3,эпюра е), поступают на вход узла 33.На втором входе элемента И 9 появляется уровень логической единицы, ас приходом импульса генератора 13(фиг. 3, эпюра а) на выходе элемента9 появляется импульс (фиг. 3, эпюра ж) опроса модели ветви. Этот импульс, проходя через первый элементгруппы элементов И 11, опрашиваетв порядке очередности первую модель