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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУЬЛИН

„„SU„„112961

g(sg G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

Ф

О у

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ .ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3581228/18-24 (22) 08.04.83 (46) 15.12.84. Бкл. ¹ 46 (72) В.К.Попков и В.К.Репин . (71) Вычислительный центр СО АН СССР (53) 681.333(088.8) (56) 1. Авторское свидетельство СССР

¹ 485451, кл. G 06 F 15/20, 1975.

2. Авторское свидетельство СССР по заявке № 3470598/18-24, кл. 5 06 F 15/20, 14.07.82. (54)(57) УСТРОЙСТВО ДПЯ МОДЕЛИРОВАНИЯ

ЭКСТРЕМАЛЬНЫХ ПУТЕЙ НА ГРА ьЕ, содержащее блок из n ìîäåëåé ветвей по числу ветней моделируемого графа, каждая из которых включает задатчики адресов начального и конечного узлов, содержащие регистр адреса и схему сравнения, перзую группу из

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

"1" старшего разряда кода режима работы устройства, группу из и элементов И, два элемента ИЛИ и два элемента И, блок из q, моделей узлов по числу узлов моделируемого графа, каждая из которых содержит регистр кода адреса узла, регистр длины пути, три схемы сравнения, первую группу из ю элементов И, вторую группу из 5 элементов И (где s — число разрядов кода длины пути), триггер, два элемента И, сумматор и счетчик ветвей, в каждую модель ветви дополнительно введены регистр длины ветви, вторая группа из Р эле11296 ментов И (где р — число разрядов кода длины ветви), третья группа из

rn элементов И, элемент ИЛИ и второй триггер, причем первый вход узла выделения "1" старшего разряда кода режима работы устройства блока управления соединен с выходом элемента

ИЛИ блока формирования топологии, второй и третий входы узла выделения

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

"1" старшего разряда кода адреса ветви графа блока управления объединены с соответствующими входами первого элемента ИЛИ блока управления и подключены к единичным выходам первых триггеров соответствующих моделей ветвей, выходы элементов И группы блока управления соединены с ну левыми входами первых триггеров, первыми входами элементов ИЛИ и первыми входами элементов И второй и третьей групп соответствующих моделей ветвей, вторые входы элементов

И первой группы каждой модели ветви соединены с выходом элемента ИЛИ . модели ветви, вторые входы элементов

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

17 регистра модели ветви, единичный выход которого является выходом модели ветви, нулевой вход второго триггера каждой модели ветви соединен с вторым входом элемента ИЛИ модели ветви и подключен к выходу соответствующего элемента И группы блока формирования топологии, выходы регистра кода адреса узла каждой модели узла соединены с первыми входами первой и второй схем сравнения и с первыми входами элементов И первой группы модели узла, выходы элементов И первой группы каждой модели узла подключены к вторым входам схем сравнения задатчиков адресов конечных узлов каждой модели ветви, вторые входы первой схемы сравнения каждой модели узла соединены с выходами элементов И первой группы каждой модели ветви, вторые входы второй схемы сравнения каждой модели узла подключены к выходам элементов И третьей группы каждой модели ветви, выход первой схемы сравнения каждой модели узла соединен с входом счетчика ветвей и первым входом первого элемента И модели узла, второй вход которого подключен . к выходу третьей схемы сравнения модели узла, а выход — к управляющему входу регистра длины пути модели узла, выход второй схемы сравнения каждой модели узла соединен с первыми входами элементов И второй груп-. пы модели узла, вторые входы кото— рых подключены к выходам регистра длины пути модели узла и первым входам третьей схемы сравнения модели узла, а выходы — к первым водам сумматора модели узла, вторые входы сумматоров каждой модели узла соединены с выходами элементов И второй группы каждой модели ветви, выходы сумматора каждой модели узла соеди(нены с информационными входами регистра длины пути модели узла и вторыми входами третьей схемы сравнения модели узла, выход счетчика вет-. вей каждой модели узла соединен с единичным входом триггера модели узла, нулевой вход которого подключен к вторым входам элементов И первой группы модели узла и выходу второго элемента И модели узла, единичный выход триггера каждой модели узла соединен с первым входом второго элемента И модели узла и подключен к соответствующему входу второ1129617 го элемента ИЛИ блока управления, а вторые входы вторь|х элементов И всех моделей узлов обьеИзобретение относится к вычислительной технике, в частности к устройствам для моделирования экстремальных путей Hà rpaAe при решении задач оптимизации. 5

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

40 схем совпадения через схему разделения каждоц модели подключены соответственно к выходам первого и второго задатчиков адреса и выходу триггера блокировки этих моделей, а выходы

45 схем совпадения через схему разделения каждой модели подключены к входу динены и подключены к выходу второго элемента И блока управления. блока автоматического формирования и к пятому входу блока управления 11 ).

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

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

112

3 входам элемента ИЛИ блока формирова. ния топологии. В блок формирования топологии введены также группа из элементов И (где л — число моделей

I1 l1 ветвей) и узел выделения 1 старшего разряда кода адреса ветви графа, а в модели ветвей — группы из е элементов И (где rn — число разрядов кода адр е с а узлов гр aha), пр ыr ем каждый задатчик адреса начального и 1п конечного узлов графа каждой модели ветви содержит регистр адреса и схе му сравнения, первые входы ехем сравнения, являющиеся входами задатчиков адресов узлов графа, объедине.— ны и подключены к выходам элементов

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

И групп соответствующей модели ветви, выходы схем сравнения задатчиков адресов конечных узлов графы каждой модели ветви соединены с входами триггеров, выходы которых подключены к первым входам элементов И соответствующей модели ветви, вторые входы которых соединены с выходами форми35 рователей временных интервалов, а

;выходы — с соответствующим входом узла выделения "1" старшего разряда кода адреса ветви графа блока формирования топологии, объединенным с одноименным входом элемента ИЛИ блока формирования топологии, выходы узла выделения " 1" старшего разряда кода адреса ветви графа соединены с первыми входами элементов И группы блока формирования топологии, вторые входы которых подключены к выходу первого элемента И блока формирования топологии, а выходы соединены с вторыми входами элементов И групп

50 соответствующих моделей ветвей графа (23.

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

9617 равно максимальной емкости счетчика формирователя временного интервала модели ветви. Наличие формирователя временных интервалов в моделях ветвей предполагает использование число-импульсного кода длины ветви, что ограничивает быстродействие при моделировании графа. Число импульсов .моделирования равно ?, где

P р — число двоичных разрядов кода длительности ветви. Таким .образом, чем больше точность моделирования (число разрядов р ), тем менее быстродействующее устройство для моделирования. Кроме того, известное устройство не позволяет определить максимальный путь между узлами модели— даруемого графа.

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

Поставленная цель достигается тем, что в устройство для моделирования экстремальных путей íà rpahe, содержащее .блок из и моделей ветвей по числу ветвей моделируемого графа, каждая из которых включает задатчики адресов начального к конечного узлов, содержащие регистр адреса и схему сравнения, первую группу из элементов И (где m — число разрядов кода адреса узла) и первый триггер, блок формирования топологии, содержащий элемент И, элемент ИЛИ, группу из и элементов И и узел выделения

"1" старшего разряда кода адреса ветви, генератор импульсов, выход которого подключен к первому входу элемента И блока формирования топологии, выход элемента И блока формирования топологии соединен с первыми входами элементов И группы блока формирования топологии, вторые входы которых подключены к соответствующим выходам узла выделения "1" старшего разряда кода адреса ветви блока формирования топологии, входы узла выделения "1" старшего разряда кода адреса ветви блока формирования топологии соединены с одноименными входами элемента ИЛИ блока формирования топологии и выходами соответствующих моделей в"òâåé, в каждой модели ветви выход регистра адреса задатчика адреса начального узла соединен с первым входом схемы срав"

1129

3 нения задатчика адреса наскального узла, второй вход которой соединен с выходами элементов И первой группы каждой модели ветви, первые входы которых соединены с выходами регист5 ра адреса и первыми входами схемы сравнения задатчика адреса конечного узла соответствующей модели ветви, выход каждой схемы сравнения задатчика адреса конечного узла соединен с единичным входом первого триггера соответствующей модели ветви, дополнительно введены блок управления, 11 1! содержащий узел выделения 1 старшего разряда кода адреса ветви графа, узел выделения "1" старш го разряда кода режима работы устройства, группу из п элементов И, два элемента ИЛИ и два элемента И, блок из . моделей узлсв по числу узлов моделируемого rpaha, каждая из которых содержит регистр кода адреса узла, регистр длины пути, три схемы срав,нения, первую группу из в элементов

И, вторую группу из ч элементов И (где 5 — число разрядов кода длины пути), триггер, два элемента И, сумматор и счетчик ветвей, в каждую модель ветви дополнительно введены регистр длины ветви, вторая группа из р элементов И (где p — число разрядов кода длины ветви), третья группа из rn элементов И, элемент

ИЛИ и второй триггер, причем первый вход узла выделения "1" старшего разряда кода режима работы устройст З5 ва блока управления "оединен с выходом элемента ИЛИ блока формирования топологии, второй и третий входы узла выделения "1" старшего разряда кода режима работы устройства блока управления соединен с выходами соответственно первого и второго элементов ИЛИ блока управления, первый выход узла выделения "1" старшего разряда кода режима работы уст- 4> ройства блока управления соединен с вторым входом элемента И блока формирования топологии, второй и третий выходы узла выделения "1" старшего разряда кода режима работы устройства блока управления подключены к первым входам соответственно первого и второго элементов И блока управления, вторые входы которых соединены с выходом генератора импульсов, выход первого элемента И блока управления соединен с первыми входами элементов И группы блока

617 6 управления, вторые входы которых подключены к соответствующим выходам узла выделения "1" старшего разряда кода адреса ветви rpaAa блока управ11 11 ления, входы узла выделения 1 старшего разряда кода адреса ветви графа блока управления объединены с соответствующими входами первого элемента ИЛИ блока управления и подключены к единичным выходам первых тригге ров соответствующих моделей ветвей, выходы элементов И группы блока управления соединены с нулевыми входами первых триггеров, первыми входами элементов ИЛИ и первыми входами элементов И второй и третьей групп .соответствующих моделей ветвей, вторые входы элементов И первой группы кажной модели ветви соединены с выходом элемента ИЛИ модели ветви, вторые входы элементов И второй группы каждой модели ветви соединены с выходами регистра длины ветви модели ветви, вторые входы элементов И третьей группы каждой модели ветви соединены с выходами регистра адреса задатчика,адреса начального узла модели ветви, выход схемы сравнения задатчика адреса начального узла каждой модели ветви соединен с единичным входом второго триггера модели ветви, единичный выход которого является выходом модели ветви, нулевой вход второго триггера каждой модели ветви соединен с вторым входом элемента ИЛИ модели ветви и подключен к выходу соответствующего элемента И группы, блока формирования топологии, выходы регистра кода адреса узла каждой модели узла соединены с первыми входами первой и второй схем сравнения и с первыми входами элементов

И первой группы модели узла, выходы элементов, И первой группы каждой модели узла подключены к вторым входам схем сравнения задатчиков адреса конечных узлов каждой модели ветви, вторые входы первой схемы сравнения каждой модели узла соединены с выходами элементов И первой группы каждой модели ветви, вторые входы второй схемы сравнения каждой модели узла подключены к выходам элементов И третьей группы каждой модели ветви, выход первой. схемы сравнения каждой модели узла соединен с входом счетчика ветвей и первым входом первого элемента И моде11?9617

8 ли узла, второй вход которого подключен к выходу третьей схемы сравнения модели узла, а выход — к управляющему входу регистра длины пути модели узла, выход второй схемы 5 сравнения каждой модели узла соединен с первыми входами элементов И второй группы модели узла, вторые вхоДы которых подключены к выходам регистра длины пути модели узла и первым входам третьей схемы сравнения модели узла, а выходы — к первым входам сумматора модели узла, вторые входы сумматоров каждой модели узла соединены с выходами элементов И 15 второй группы каждой модели ветви„ выходы сумматора каждой модели узла соединены с информационными входами регистра длины пути модели узла и вторыми входами третьей схемы срав- 20 нения модели узла, выход счетчика ветвей каждой модели узла соединен с единичным входом триггера модели узла, нулевой вход которого подключен к вторым входам .элементов И пер- 25 вой группы модели узла и выходу второго элемента И модели узла, единичный выход триггера каждой модели узла соединен с первым входом второго элемента И модели узла и подклю- З0 чен к соответствующему входу второго

1 элемента ИЛИ блока управления, а вторые нходы вторых элементов И всех моделей узлов объединены и поцключены к выходу нторого элемента И

35 блока управления.

Введение блока управления позволяет чередовать три режима работы устройства, а именно . режим распространения волны в графе, при котором 40 происходит поочередный спрос каждой модели ветви с передачей адреса конечного узла ветви (волновой алгоритм), этот режим имеет наименьший приоритет, режим определения экстре- 45 мального пути до узла, при котором происходит опрос модели ветви с выдачей данных о длине ветви и адресов начального и конечного узлов ветви, что в сваю очередь приводит 50 к выдаче экстремального расстояния до начального узла данной ветви и разрешения записи экстремального пути в регистр длины пути конечного узла данной ветви с выходом суммато- 55 ра, в котором суммируются экстремальное расстояние до узла и длина ветви, исходящей из этого узла, и режим опроса мгделей узлов, при котором происходит опрос той модели узла, в которой на данный момент установлена готовность передачи кода адреса этого узла для перевода работы устройства во второй режим. Последний режим имеет высший приоритет.

Узлы выделения "1" старшего разряда кода адреса ветви графа блока формирования топологии и блока управления используются для определения очередностей опроса моделей ветвей особенно н первом и втором режимах работы устройства. Очередность необходима вследствие использования одних и тех же линий передачи адре— сон и данных для всех моделей устройства.

Таким образом, задача определения экстремального пути решается путем опроса каждой модели ветви при вол— новом процессе опроса каждой модели узла, когда нсе ветви да данного узла пройдены (для возбуждения тех моделей ветвей, которые входят в данный узел), и, наконец, повторного опроса каждой модели ветви, входящей в данньгй узел, при определении экстремального пути. Для rpaAa, имеющего ве-вей и q, узлов, задача решается за 2 n + с тактов и не зависит от точности моделирования веса ветвей, Расширение функциональных возможностей достигается за спет того, что для данного алгоритма функционирования устройства, т.е. при определении пути после прохождения всех возможных путей до данного узла, можно определять как минимальный, таь и максимальный пути до данно.- о узла.

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

На фиг. 1 дана функциональная схема предлагаемого устройства„ на и, . 2 пример исследуемого графа, на фиг. 3 — временная диаграмма работы устройства для данного примера; на фиг. 4 — узел выделения "1" старшега разряда кода режима работы для общего случая.

Устройс во содержит (фиг. 1) и моделей 1 ветвей, задатчики адресов начального 2 и конечного 3 узлов вершин модели ветви, регистры 4 адреса узлов, схемы 5 сравнения и первую

11296

55 группу элементов И Ь модели ветви, первый триггер 7 модели ветви, блок

8 формирования топологии, элемент

И 9, элемент ИЛИ 10 и группу из и элементов И 11 блока формирования топологии, узел 12 выделения "1" старшего разряда кода адреса ветви графа блока формирования топологии, генератор 13 импульсов, регистр 14 длины ветви модели ветви, вторую группу из р элементов И 15 модели ветви, третью группу из rn элементов

И 16 модели ветви, элемент ИЛИ 17 модели ветви, второй триггер 18 модели ветви, ч, моделей 19 узлов, ре- гистр 20 кода адреса узла модели узла, схемы 21 и 22 сравнения модели узла, первую группу из vn элементов И 23 модели узла, счетчик 24 ветвей модели узла, триггер 25 модели узла, первый и второй элементы

И 26 и 27 модели узла, сумматор 28, регистр 29 длины пути модели узла, схему 30 сравнения модели узла, вторую группу из s элементов И 31 модели узла, узел 32 выделения "1" старшего разряда кода адреса ветви

rpaha блока управления, узел 33 выделения "1" старшего разряда кода режима работы блока управления, груп-, пу элементов И 34 блока управления, первый и второй элементы ИЛИ 35 и

36 блока управления, первый и второй элементы И 37 и 38 блока управления. Узел 33 выделения "1" старшего разряда кода режима работы

35 (фиг. 4) включает группу из н элементов ИЛИ 39, группу из (n — 1) элементов HE 40, группу из (n — 1) элементов И 41.

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

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

4S адресов узлов графа в состояние, солтветствующее кодам адресов узлов.

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

1129617

$0

Режим сравнения путей имеет бопее низкий приоритет, чем режим оп- . роса узла, но более высокий, чем режим волнового распространения.Приоритетность режимов определяется входом подключения сигналов готовностей на объединенных входах задатчиков адресов начальных узлов моделей ветвей, вызывая их срабатывание.

Затем опрашивается следующая ветвь по сигналу готовности и т.д. По заднему фронту сигнала опроса происходит сброс триггера 18 готовности.

Таким образом происходит процесс распространения. волны в модели графа.

В процессе распространения волны 10 воды конечных узлов моделей 1 ветвей появляются на объединенных вторых входах первых схем 21 сравнения адресов узлов моделей 19 узлов. При равенстве кода адреса конечного узла опрашинаемой модели ветви и кода адреса соответствующего узла срабатывает схема 21 сравнения данной модели 19 узла, из содержимого счетчика 24 ветвей вычитается едини- 20 ца. Как только все пути до данного узла будут пройдены, содержимое счетчика 24 станет равным нулю и сработает триггер 25, выдавая сигнал готовности на второй элемент ИЛИ 36. 2s

С выхода этого элемента ИЛИ сигнал поступает ««а вход высшего приоритета узла 33, а с его выхода — на первый вход второго элемента И 38. Обслуживается только модель узла, все остальные сигналы готовностей моделей ветвей. игнорируются, режим волнового распространения и режим сравнения путей временно приостанавливается.

Опрашивается модель узла путем подачи импульса генератора 13 через элемент И 38 на второй вход второго элемента И 27, а с его ныхода — на вторые входы первой группы элементов

И 23 модели узла. При этом код узла 40 выдается на входы задатчиков 3 адресов конечных узлов, т.е. на схему 5 сравнения этих задатчиков моделей ветвей. Срабатывают модели тех ветвей, KOTQPb«e Bxo+HT B MQPeJIb PBHHo 45 го узла. Триггеры 7 готовности этих моделей устанавливаются в единичное состояние. По заднему фронту сигнала опроса модели узла, приходящего на второй вход триггера 25, происходит его сброс. Затем устройство переходит в режим сравнения путей. к узлу 33. Во время режима сравнения путей режим волнового распространения временно приостанавливается.

Узел ЗЗ блока управления по своей структуре и функционированию полностью аналогичен узлу выделения

"1" старшего разряда кода адреса ветви графа и отличается только числом входов °

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

Для устранения подобных сбоев в сос таве узлов следует применить выходной регистр (на фиг. 1 не показан), стробируемый импульсами генератора 13.

Сигналы готовности с триггеров 7 моделей ветвей попадают на входы узла 32 выделения "1" старшего разряда кода адреса ветви rpaAa и входы логического элемента ИЛИ 35 блока управления, с выхода которого они поступают на вход узла 33, а с него на второй вход первого элемента И 37.

Узел 32 определяет первую по очередности модель ветви, и импульс опроса, приходящий на первые входы второй группы элементов И 15 с выхода соответствующего элемента группы элементов И 34, поступает «r; эту модель ветви. Импульс опроса модели ветви приходит на входы второй 15, третьей 16 групп элементов И, а через элемент ИЛИ 17. — на входы первой группы элементов И. 6. При этом из модели ветви выдаются коды начального и конечного адресов ветви и код, пропорциональный ее длине. Код начального адреса ветви поступает на вторые входы вторых схем 22 сравнения адресов узлов всех моделей узлов. Схема 22 сравнения той модели ветви, из которой выходит опрашиваемая ветвь, срабатывает, помещая через вторую группу элементов И 31 содержимое регистра длины пути до

;узла на первые входы су«в«аторов 28

1129617

14 всех моделей узлов, на вторые входь; которых приходит код длины опрашиваемой ветви. В сумматорах 28 моделей узлов происходит суммирование этих кодов. Содержимое сумматоров сравнивается с содержанием регистра 29 длины пути с помощью схемы 30 бравнения на больше-меньше. Из двух этих значений выбирается экстремальное. Если экстремальное значение 10 находится в регистре 29, схема 30 сравнения не вырабатывает сигнала записи, а если оно находится на выходах сумматора 28 (сумматор комбинационного типа без памяти), выраба- 15 тывается сигнал записи. С помощью схемы 21 сравнения, соединенной с выходами первой группы элементов И 6 опрашиваемой модели ветви, в свою очередь соединенных с регистром 4 20 задатчика 3 адреса конечного узла, выбирается модель узла, для которой данная ветвь является конечной. Сигнал выбора модели узла с выхода схемы 21 сравнения поступает на первый 25 вход первого элемента И ?6. Если на выходе схемы 30 сравнения этой модели узла имеется импульс записи, он проходит через элемент И 26 на вход записи регистра 29 длины пути. З0

Экстремальное значение заносится в регистр. Задним фронтом опроса модели ветви происходит сброс триггера 7 готовности по второму входу.

Устройство производит последовательный опрос всех моделей ветвей, входящих в данный узел, выбирая каждый раз экстремальные значения из предыдущего значения длины пути, находящегося в регистре 29, и теку- 40 щего расстояния на выходе сумматора

28. При вторичном опросе моделей ветвей для нахождения экстремального пути счетчик 24 ветвей моделей узлов не обнулится, так как число оп- 45 рашиваемых моделей ветвей не превысит число моделей, входящих в узел, а следовательно, максимальной емкости счетчика. Затем возобновляется волновой процесс распространения сигналов между моделями ветви.

Таким образом, чередуя режимы работы устройства, вычисления длятся . до тех пор, пока не будет просчитано экстремальное расстояние до ко- 55 нечного узла исследуемого графа или, если он не задан, до тех пор, пока идут импульсы опроса моделей устройства. Результатом вычислений будут значения экстремальных путей от начального узла в регистрах 29 длины пути каждой модели узлов, связанной с начальным узлом.

Для пояснения работы устройства рассмотрим пример моделирования кратчайшего пути на графе. На фиг. 2, где представлен исследуемый граф, римскими цифрами обозначены номера узлов, в числителях арабских цифр номера ветвей, в знаменателях — их длины. На фиг. 3 дана временная диаграмма устройства.

Первоначально в устройство заносится топология исследуемого графа.

При этом в регистрах 4 задатчиков адреса начального ? и конечного 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, опрашивает в порядке очередности первую модель

1129617 ветви. Импульсы опроса, проходя через элемент ИЛИ 17, поступают на вторые входы первой группы элементов И 6 этой модели ветви. При этом адрес конечного узла этой модели 5 ветви ("2") появляется на входах задатчиков 2 адресов начальных узлов моделей ветвей (фиг. 3, эпюра б), Это приводит к срабатыванию задатчика 2 последней третьей модели ветви, а,следовательно, триггера 18 готовности этой модели ветви (фиг. 3, эпюра з), а также к срабатыванию первой схемы 21 сравнения модели второго узла и из счетчика 24 этой модели вьг- 15 читается единица. По заднему фронту сигнала опроса (фиг. 3, эпюра ж) сбрасывается триггер 18 готовности первой модели ветви (фиг. 3, эпюра в). 20

Так как имеется готовность от оставшихся трех моделей ветвей, сигнал с выхода первого элемента HJIH 10 не исчезает (фиг. 3, эпюры г, д, з, е) и происходит опрос. следующей по очередности второй модели ветви посредством подачи импульса опроса с выхода элемента И 9 (фиг. 3, эпюра ж) через соответствующий элемент группы

11. При этом на входе задатчиков 2.

ЗО начальных узлов выдается код адреса конечного узла второй модели ветви— "2" (фиг. 3, эпюра б). В этот момент времени из счетчика 24 ветвей модели

19 второго узла вычитается послед- 35 няя единица и срабатывает триггер 25 готовности (фиг. 3, эпюра и). На выходе второго элемента ИЛИ 36 появляется сигнал логической единицы, который, проходя через узел 33, под- 40 готавливает к срабатыванию второй элемент И 38. Для устранения состояний в логических цепях узел выделения старшего по приоритету необходимо выполнить в памятью, стробируемой 4 каждый раз импульсом генератора 13.

С приходом импульса тактового генератора 13 на выходе элемента 38 появляется импульс опроса модели узла (фиг. 3, эпюра к). Импульс опро- $0 са проходит через элемент И 27 модели второго узла, на первом входе которого имеется разрешающий уровень с выхода триггера 25 готовности, и проводит опрос регистра 20 адреса 5s

:узла через первую группу элементов

И 23. На входе задатчиков З,адреса конечных узлов моделей ветвей появ- ляется код данного узла — "?" (фиг. 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, эпюра A) который будет сравниваться с максимальным числом

1129617

18 регистров 29, и схемы сравнения выдадут сигналы на запись (фиг. 3, эпюра х). Первая схема 21 сравнения модели второго узла сработает и импульс записи через элемент И 26 модели второго узла пройдет на вход записи регистра 29, в регистр занесется код 3" (для устранения состязаний в логической цепи записи регистр

29 необходимо выполнить с двойной памятью, при этом информация с выхода сумматора по переднему фронту сигнала записи записывается в первую ступень регистра, а по заднему фронту — во вторую). Произошел .опрос модели первой ветви, в результате чего в регистре 29 второго узла занеслось число "3". По заднему фронту сигнала опроса (фиг. 3 эпюра п) сбрасывается триггер 7 готовности модели первой ветви (фиг. 3, эпюра

M), но имеется еще сигнал готовности

:;модели второй ветви, и в следующем такте происходит опрос этой модели ветви (фиг. 3, эпюра г), при этом на входе вторых схем 22 сравнения

f1411 адресов узлов появится код 1, на

"4" втором входе сумматора 28 — код (вес второй ветви), на входе первых схем 21 сравнения — код "2", на перл тг вом входе сумматора — код 0, а следовательно,на выходе сумматора— код "4" (соответственно эпюры р, с, т, у, ф на фиг. 3). Импульс записи схемой 30 сравнения модели второго узла сформирован не будет, так как в регистре 29 этой модели находится число, меньше числа на выходе сумматора, и состояние регистра не изменится. По заднему импульсу опроса сбрасывается триггер 7 готовности модели второй ветви и устройство переходит в режим распространения волны

В этом режиме происходит опрос моделей третьей и четвертой ветвей, после чего сработает триггер готовности третьего узла, а следовательно, элемент ИЛИ 36 (фиг. 3, эпюра и) ЗО

40 дели ветви сумма будет 0 + 7 = 7, импульса записи не возникнет.

Результатом вычисления являются значения кратчайших путей от первого узла в регистре расстояния второго узла — 3, третьего — 6 °

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

1ветви и Расстояния до узла, из которого она выходит, и сравнением этой суммы с результатом предыдущих срав- нений. Следовательно, задача нахождения экстремального пути в графе решается за 2 и + g тактов работы устройства и не зависит от степени точности моделирования веса ветви.

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

Следующим импульсом будет импульс оп роса модели третьего узла, в результате которого на входах задатчиков

3 адресов конечных узлов появится

5 код "3" (соответственно эпюры к, л на фиг. 3). Сработают задатчики адре= сов конечных узлов третьей и четвертой моделей ветвей, а следовательно, триггеры 7 этих моделей ветвей. При этом на выходе элемента ИЛИ 35 появится сигнал готовности (фиг. 3, эпюра о) режима сравнения. В начале произойдет опрос третьей модели ветви, в результате чего в регистр

15 29 модели третьего узла занесется сумма длины третьей ветви и кратчайшего расстояния до второго узла

3 + 3 = 6 ° При опросе четвертой мо1129617

Ри

Фиг. Z

1129Ы7

2 1

Фиг.Я

Фиг.4

Составитель С.Назаров

Редактор М.Петрова Техред Ж.Кастелевич Корректор Н.Король

> Заказ 9454/39 Тираж 698 Подписное

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

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

Ю

8 д е

Ж

Ll

К

Л

Н

О

П

Р

С

Я

Ф

Филиал .ППП "Патент", г. Ужгород, ул. Проектная, 4