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

(21) 383 (22) 25. (46) 15. ластибыть аидуко пара льство СССР 15/20, 1982, ство СССР 15/20, 1983,я -ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ Ъ.ТОРСЯОМУ СВИДЕТЕПЬСТ 0183/24-2412,8408.86, Бил. К .Баженов, В.Лв и В.А,Титов(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВСЕТЕВЫХ ГРАФОВ(57) Изобретение относится квычислительной техники и можеиспользовано при исследованииметров сетевых граЪов, а такжисследовании показателей надесложных систем. Дель изобретерасширение Функциональных вознастей за счет определения ве12 образующих путь максимальнОго произ ведения длин соответствующих дуг граФа. Устройство содержит блок формирователей пути 12, генератор 1 таКтоВЫХ ИМПУЛЬСОВр ПЕРВЫЙ ЭЛЕМЕНТ И 2, первый счетчик 3, дешиФратор 7 первую группу реьистров 18, группу элементов ИЛИ 16,. треугольную наддиагональную матрицу 22; включакюцую (и) и/2-1 (где и - число вершин в граФе групп, состоящих иэ регистра и блока элементов И,51099группы блоков элементов И 17,19. Дополнительно введена вторая группарегистров 15, группа блоков 14 умножения, блок 13 задержки, блок 11поиска максимального кода, второй итретий 5, 8 элементы И, регистр 9,группа триггеров 10, второй счетчик6. Предложенное устройство позволяетодновременно производить операциюумножение над 1,кодами чисел приопределении параметров сетевых гра.Фов 3 ил, Изобретение относится к вычислительной техникер может быть использовано при исследовании параметров сетевых граФов, а также при исс,педовании показателей надежности сложных систем.Целью изобретения является расширение Функциональных возможностей устройства за счет определения вершин, .образующих путь максимального щ произведения длин соответствующих дуг граФа.На Фиг.1 представлена структурная схема устройства для моделированиясетевых граФов на фиг.2 -. структур-. ная схема блока поиска максималь-" ного кода; на фиг.З - структурная схема блока Формирователей пути.Устройство для моделирования сетевых граФов (Фиг.1) содержит гене ратор 1 тактовых импульсов, элемент И 2,счетчик 3, триггер 4, элемент И 5, счетчик 6, дешиФратор 7, элемент И 8;сдвигающий регистр 9, группу три 1 геров 10 р 10, р блок 11 25поиска максимального кода блок 12 Формирователей пути, блок 13 задержки группу блоков 1414,умножения, вторую группу сдвигающих)регистров 15, 15 , группу эле- Зоментов ИЛИ 16 рр 16, р вторуюгруппу элементов И 1,7 ,17, первую группу регистров 18 , р 18, первую группу блоков элементов И 19 р,19,ргруппу регистров 20 ер,,10) и группу элементов И 21 рэ р ,21 п 1, наддиагональной матрицы 22, вход 23 запуска. Блок 11 поиска максимального.кода Фиг,2) содержит блок элементовИЛИ 24, сдвигающие регистры 25 .25р элемент ИЛИ 26, первую группуэлементов И 271 р,р 271.ь р регистр28, вторую группу элементовИ 29 рр 29, р р блок 30 элементовИ, третий, четвертый, второй и первый входы 31,32, 33 и 34, первуюгруппу выходов 35 , р 35., р выход36 и вторую группу выходов 37,Блок 12 Формирователей пути,Фиг.З) содеРжит тРиггеРы 381 рр381,.р 1 р первую, вторую и третьюгруппы элементов И 39;р р,р 39 1,рь ь р 0(рр)д И 1 я рь ь ь р 1 ц 1 впервую и вторую группы элементовИЛИ 4242, и 43 43регистр 44,: группы входов 45,45 в 1 и Абрр 46 вход 47.Устройство для моделированиясетевых граФов работает следующимобразом,В исходном состоянии регистры я (р8 р ь ь ь р 1 вр триггеры 10 рь ь р 10 ьь регистры 15 р. .,15 счетчики 3 и б, регистры 25 рр 35(Фиг,2)ртриггеры 38 рр 38,-11 1 Фиг,З) и триггеры регистра 44 установлены в нулевое состояние 1 установочные входы на Фиг,1 - 3 не показаны)р триггер 4, триггер младшего разряда регистра 9, триггер регистра 28 и триггер 38 р - в единичное состояние. На регистры 20 рр 20(1-р) л матрицы 22 записаны коды весов соответствующих дуг граФа, при этом код1 51099 веса пути из нерпой вершины графа во вторую записан на регистр 18. Если отсутствует путь из-й вершины 3-ю (1 = 1,п, 1 = З,п, 11) то регистр 20; устанавливается в нулевое состояние.Работа устройства начинается после подачи на вход 23 сигнала высокого уровня. По этому сигналу первый импульс с генератора 1 через 10 открытый элемент И 2 записывает единицу в счетчик 3, а через открытый элемент И 5 устанавливает в нуль триггер 4, записывает единицу в счетчик 6, поступает на первые входы регистров 15 15 разрешающих прием кодов, а также сдвигает код единицы из первого разряда регистра , 9 во второй. Сигналом с выхода триггера второго разряда регистра 9 ус танавливается в единичное состояние триггер 102, с выхода которого сигналом высокого уровня открывается . блок элементов И 192, после чего код с выхода регистра 18 подается 25 на первый вход блока 142 умножения. Одновременно сигнал высокого уровня с первого выхода дешифратора 7 поступает на первый вход блока 12 и на первые входы блоков элементов И 17, ЗО 21. и 212, в результате чего коды с регистров 20 и 20 э через соответствующие блоки элементов И 211 и 21 . ИЛИ 16 и 16 записываются на регистры 15, и 15, С приходом второго импульса с выхода генератора 1 содержимое счетчика 3 увеличивается на единицу, через открытый элемент И 8 высокий потенциаа подается на регистры 15, блок 11 и блоки 4 О 14 умножения, т.е. начинается процесс умножения кода, поданного на первый вход блока 14 умножения, на код, записанный в регистре 15, Ре" зультат умножения с регистра 15 4 через блок 13 задержки подается в блок 11 определения максимальногокода. Блок 11 функционирует следующим образом. Сравниваемые числа поступаютО последовательными кодами на соответстсующие им регистры 25 по входу 31 (см,фиг.2), Прямой выход первого триггера (не показан) старшего разряда регистра 25; (1=1,п) подключен 55 к 1 -му входу элемента ИЛИ 26, а инверсный - к второму входу элемента И 27. 4Пусть при поступлении разрядов кодов, среди которых имеется хотя бы одна единица (например в д-м, з = 1,п), на прямом выходе триггера перво о разряда регистра 25, устанавливается высокий уровень сигнала (код единицы ). Этот сигнал поступает на-й вход элемента ИЛИ 26, на выходе которого формируется код единицы, поступающий на первые входы всех элементов И 27. Элементы И 27 (1 с = 1,п, 1 с) открыты, так как на их вторые входы поступают высокие уровни сигналов с инверсных выходов соответствующих первых триггеров регистров 25. Сигналом высокого уровня с выходов элементов И 27 устанавливаются в нулевое состояние 1-е триггеры регистра 28, и этот же сигнал поступает в цепи сброса регистров 25. Триггер 1 (1 = 1,и) регистра 28 остается в единичном, состоянии. Кроме того, сигналы высокого уровня поступают в цепи сброса 1-х регистров 15, При поступлении на регистры 25 кодов нуля на выходе элемента ИЛИ 26 формируется код нуля. В результате все элементы И 27 закрыты. При поступлении разрядов кодов, среди которых несколько единиц, на выходе элемента ИЛИ 2 б формируется сигнал высокого уровня, вследствие чего устанавливаются в нулевое состояние триггеры регистра 28 тех кодов, разряды которых равны нулю, кроме того, устанавливаются в нулевое состояние соответствующие этим кодам регистры 25 и 15,В результате сравнения в единичном состоянии остается-й триггер регистра 28, а максимальный код формируется на выходе блока элементов ИЛИ 24. Умножение и сравнение кодов производится за п 1 тактов. По (щ+1)-му импульсу формируется сигнал переполнения счетчика 3, который устанав - ливает в единичное состояние триггер 4 и поступает по входу 33 (см. фиг.2) на вторые входы элементов И 29, По этому сигналу с выходов 35 снимается код с единицами в разрядах, соответствующих гозиционным номерам максимальных кодов. Этот код поступает на блок 12 формирователей пути, а через блок 30 элементов И максимальный код с регистра 25, через блок элементов ИЛИ 24поступает на входы блоков элементовИ 17.В рассмотренном случае значащиекоды поступают на первый и второй1"входы блока 11 (пусть первый коцбопьше второго), В результате сравнения первый триггер регистра 28остается в единичном состоянии.По импульсу переполнения счетчика 3 10разрешается прием кодов в регистры15, по этому же сигнапу происходитвыдача максимального кода, которыйдалее записывается в регистр 18 э(через открытый блок элементов И 17 ),а также выдается сигнал высокогоуровня по входу 34 на блок 11 (установка в единичное состояние регистра 28),Блок 12 формирователей пути, служит для идентификации вершин моделируемого графа, составляющих максимальный путь. Блок функционируетследующим образом. Пусть на -мшаге работы схемы происходит опрос 251-го столбца матрицы 22) высокийпотенциал появляется на 1-м (1 с =1,и) выходе блока 11. Этот сигнал подается по входу 45 на вторыевходы элементов И 40 ,40 и,в30Одновременно с,1 -го выхода дешифратора 7 на вход 4 б поступает высокий уровень сигнала, которым устанавливается в единичное состояниетриггер 38 , Это свидетельствует оМ, 5том, что максимяльный путь проходитчерез 1-ю вершину графа. Если, например, на входы 45и 45 поступаютодинаковые максимальные) коды, тоустанавливаются в единичное состояние триггеры 38, и 38 , (1 с (.1),На следующем шаге работы устройства по первому импульсу записывается очередная единица в счетчик б, со сдвигающего регистра 9 устанавливается в единичное состояние триггер 1 Оэ, подготовлены к приему кодов регистры 15 и установлен в нулевое состояние триггер 4. С выхода дешифратора 7 открывается блок элементов И 17, опрашиваются блоки элементов И 21, 21 и 21 э и .коды, записанные в регистрах 20,1, 20 и 20, через соответствующие элементы ИЛИ 16 записываются в регистры 15 15 и 15, Затем происходит процесс умножения и сравнения кодов. Далее процесс повторяется до появления высокого уровня сигнала на п) -м вьгходе дешифр атора 7 .На (и) -м шаге работы устройства с дешифратора 7 подается сигнал высокого уровня цля опроса формирователей путей. Он поступает по входу 47 на вторые входы элементов И 391 и 41 . Первый вход каждого элемента 39 подсоединен к инверсному выходу соответствующего ему триггера 38, а дервый вход элемента 40 - к прямому вьгходу данного триггера. Если триггер 38 находится в нулевом состоянии, то сигнал опроса через элемент И 391 поступает на опрос элементов И 39 и 41 и т.д., пока не будет найден триггер 38 установ" ленный в единичное состояние, В этом случае через элемент ИЛИ 43устанавливается в единичное состояние и -й триггер регистра 44 а через элемент ИЛИ 42 сигнал опроса поступает на опрос 1 -го столбца матрицы триггеров. Если в И-м столбце нет триггера 38, установленного в единичное состояние, то сигнал опроса через элемент ИЛИ 42пос-. тупает на опрос (и)-го столбца. Если в-м столбце триггеры 40 и 40(1 с с 1) установлены в единичное состояние, то выбирается вершина с меньшим (Тс) номером. Опрос продолжается до тех пор, пока не будет найден триггер 38 г, установленнный в единичное состояниеВ этом случае устанавливаются в единичное состояние 1 г -й и первый триггеры регистра 44, что сигнализи рует об окончании моделирования,формула из обретениустройство для моделирования сетевых графов, содержащее блок формирователей пути, генератор тактовых импульсов, первый элемент И, первый счетчик, дешифратор, первую группу регистров, группу триггеров, первую и вторую группы блоков элементов И, группу элементов ИЛИ треугольную наддиагональную матрицу, включающую группу из (и)п/2-1 регистров и группу из (и)и/2-1 блоков элементов И где и - число вершин графа, выходы каждого регистра группы треугольной наддиагональной матрицы соединены с информационными входами одноименных блоков элементов И125173 группы треугольной наддиагональнои матрицы, выходы дешифратора подключены к управляющим входам блоков элементов И группы треугольной наддиагональной матрицы, к первой группе входов и входу блока Формирователей пути и к управляющим входам блоков элементов И второй группы, выходы блоков элементов И группы каждой строки треугольной наддиаго О нальной матрицы соединены с входами одноименного элемента ИЛИ группы,. выход генератора тактовых импульсов соединен с информационным входом первого элемента И, управляющий вход 15 которого является входом запуска устройства, выход первого элемента И подключен к входу первого счетчика, выходы 1,-х блоков элементов И второй группы (1 - "З,п) соедине ны соответственно с входами регистров первой группы, выход 1 -го регистра первой группы (х 2, и) соединен с информационным входом -го блока элементов И.первой груп пы, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства эа счет определения вершин, образующих путь максимального произведения 30 цлин соответствующих дуг графа, в устройство введены вторая группарегистров, группа блоков умножения, блок задержки, второй и третий элементы И, регистр, триггер, второй 3 счетчик и блок поиска максимального кода, включающий блок элементов ИЛИ, группу сдвигающих регистров, элементИЛИ первую и вторую группы элементов И, регистр и блок элементов 40 И, причем выход старшего разряда 1 -го сдьигаинего регистра группы у 1 ь= 1, и) соединен с-м анодом элемента ИЛИ, выход которого под- . ключен к первым входам элементов И первой группы, второй вход каждого из которых соединен с обратным выходом старшего разряда одноименного сдвигающего регистра группы, выходы элементов И первой группы являются первой группой выходов блока поиска максимального кода и подключены к входам сброса сдвигающих регистров группы и к установочным входам ре-гистра, вход сброса которого являет ся первым входом блока поиска максимального кода, выходы регистра соединены с первыми входами элементов 099 8И второй группы, выходы которых являются второй группой выходов блока поиска максимального кода, выход каждого сдвигающего регистра группы подключен к одноименному входу блока элементов ИЛИ, выход которого соединен с первым входом блока элементов И, выход которого являются выходом блока поиска максимального кода, вторым входом которого являются объединенные вторые входы элементов И второй группы и второй вход блока элементов И, третьим входом блока поиска максимального кода являются информационные входы сдвигающих регистров группы четвертым входом блока поиска максимального кода являются входы сдвигающих регистров группы, выход первого элемента И устройства соединен с первыми входами второго и третьего элементов И, выход первого счетчика подключен к второму входу блока поиска максимального кода и к единичному входу триггера, первый выход которого соединен с вторым входом третьего элемента И, второй выход триггера подключен к второму входувторого элемента И, выход которого соединен с нулевым входом триггера, с входом второго счетччка, с входом регистра, с входами разрешения записи регистров второй группы и с первым входом блока поиска максимального кода, выход второго счетчика подключен к входу дешифратора, выход третьего элемента И соединен с тактирующими входами блоков умножения группы, с первым входом блока задержки, с тактирующим входом 1 -го регистра второй группы (х=1 рп) и с четвертым вхо- дом блока поиска максимального кода, третий вход которого подключен к выходу блока задержки и к выходам блоков умножения группы, выход блокапоиска максимального кода соединен с информационными входами элементов И второй группы, вторая группа выходов блока поиска максимального кода подключена к второй группе входов блока формирователей пути, первый и второй входы-го блока умножения (=2, и) группы соединены соответственно с выходом одноименного элемента И первой группы и выходом одноименного регистра второй группы, д-и (1.=2,п) выход регистра подключен к единичному входуСоставитель И.Дубининаехред М.Ходанич Корректор А,О И.Рыбче еда ака 4413/47 Тираж б 71ВНИИПИ Государственного комитета Спо делам изобретений и открытий11 ЗР 35, Москва, Ж-З 5, Раушская наб Подписно р роизводственно-полиграФическое предприятие,г.ужгород, ул. Проектная,9-го триггера группы, выход которого соединен с управляющим входом -го блока элементов И первой группы, выход-го элемента ИЛИ группы Ц=1, и) подключен к инФормацнонному входу 1 -го регистра второй группы; первая группа выходов блока1 099 1 Опоиска максимального кода соединена с входами установки в О регистфф ра второй группы, инФормационный вход (и) -го регистра второй группы соединен с выходом блока элементов И группы (и) и-й строки треугольной наддиагональной матрицы.