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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК Р. 15/20 ОТНРЫТИЙЭОБРЕТЕНДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И(56) 1 Авторское свидетельство СССРР 525454, кл. 6 06 Р 15/20, 1977.2. Авторское свидетельство СССР.по заявке Р 2830339/18-24,кл. С 06 Р 15/20, 27.07.79 (прототип).54) (57) 1 е УСтРОЯСтВО ДЛЯ МОДЕЛИРОВд,яия СятКВЫХ ГРаФОВ, содержащеепервую группу из Ц регистров,. обРа- .вуниаих треутольнуи нанииамнальнум -матрицу х1, й;),+1,щ), пер-,.вую группу элементов ИЛИ, блок управ-ления и вторую группу регистров, вы-:Моды 1-го регистров второй группыподключены к первым входам 1-х элементов И первой группы, .вторые входыкоторых соединены с .соответствующимразрядом первой выходной шины блокауправления,. 1-и разряд второй выходной шины которого подключен к первым входам 1-х элементов И второйгруппын выходы которых соединены свходами 1 у-го регистра второй группы,о т"л-и ч- а,ю щ е е с .я тем, что,с целью повышения быстродействия,в него введены сумматор, блок форми-рователей.пути блок выбора,.максимального кода, вторая группа элементов.ИЛИ, третья группа регистров, третьячетвертая и пятая группы элементов. И, элементыИ и элемент.ИЛИ, выходкоторого подключен к первым входамэлементов И, вторые входы которыхсоединены с соответствующимиразрядами первой выходной шины блокауправления, выход 1-го элемента Иподключен к первым входам 1-.х элементов И третьей группй, .выходы которых соединены с выходами 1-го регистра третьейгруппы, выходы которого подключены к первым входам 1-х элементов И четвертой группы, выходы которых соединены с входами 3:-й группы блока выбара;максимального кода, выходы первой группы которого.подключены,к вторым входам соответствующих элементов И второй группй, вйходы второй группы блока выбора максималь- . ного кода соединены с входами первой группы блока формирователей пути, входы второй группы которого подклю- , чены.к соответствующим разрядамвторой выходной шины блока,управле- ния, первый выход которого соединен с входом блока. формирователей пути, установочные входы регистров третьей группы подключены к второму выходублока управления, третий выход которого соединен с вторымИ входами эле- . ментов И четвертой группы, выходы Ц-го регисзра первой группы. подключены к первым входам Ц.-х элементов И пятой группыа выходыкоторых сое- Я дииены с Ц-ми входами соответсъвую щих элементов ИЛИ первой группы, вы ходы которых подключейы к входам элемента ИЛИ и к входам первой гру пы сумматора, выходы которого соеди иены с вторыми входами соответствую щих элементов И третьей группы, Ц" разряд третьей выходной шиныблока управлейия подключен к вторым входам Ц-х элементов И пятой группы, выхо +х элементов:И первой группы соеди нены с 1-ми входами соответствующих элементон ИЛИ второй группы, выходы которых подключены к входам второй группы сумматора, четвертый вход блока управления является управляющим входом устройства.2. Устройство по п.1, о т л и -. ч аю щ е е с я тем, что, . блок Формирователей пути содержит регистр, первую и вторую группу элементов ИЛИ и треугольную наддиагональную матрилу йорьирователей лутн квилый 11-й (1=1 й ща 1; 1= д+1,щ) формирова 10139651013965 иг 006/58 Тираж 704 Подп ВНИИПИ Государственного комитета ССС по.делам изобретений и открытий. 113035, Москва, Ж, Раушская наб., д10139 б 5 10 тель пути содержит три элемента И и триггер, вход которого соединен с выходом первого элемента И, единичный и нулевой выходы триггера подключены к первым входам второго и третьего элементов И соответственно, выход третьего элемента И (1,1+1 )-го формирователя пути соединен с вторыми входами второго и третьего элементов И (3.+1, 1+ )-го формирователя пути, выход третьего элемента И (,+1 )-го формирователя пути подключен к входу -го элемента ИЛИ первой группы выход которого соединен с вторыми входами второго и третьего элементов И(1, )-го формирователя пути, выход второго элемента И (1, )-го формирователя пути подключен к входу 1-го элемента ИЛИ перной группы и к входу 1-го элемента ИЛИ второй группы, выход которого соединен с входом одноименного разряда регистра, выход первого элемента ИЛИ первой группы подключен к входу первого разряда регистра, вторые входы второго и третьего элементов И (1,щ )-го формирователя соединены с входом блока, -й вход первой группы входов которого подключен к первым входам первых элементов И формирователей пути -й строки, -й вход второй группы входов блока подключен к вторым входам первых элементов И формирователей пути 1-го столбца,3. Устройство по п.1 о т л и ч а ю щ е е с я тем, что блок управления содержит й+2 триггера, четыре группы элементов И, группу инверторов, элемент ИЛИ, элемент И, инвертор, регистор, счетчик, схему управления, дешифратор и генератор, выход которого подключен к первому входу элемента"И, второй вход которого соедиИзобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графов.Задача определения кратчайшего 5 пути в графе заключается в определении значений критического минимального времени для каждой вершины графа и индентификации вершин, составляющих кратчайший путь.Известно устройство для формирования кода кратчайшего пути н цифро-, вой сети связи, содержащее генератор, счетчик, три группы элементов И, элемент ИЛИ, узел опроса, два регистра кода адреса, буферный и выходной регистры Г 13. нен с четвертым входом блока, выходэлемента И подключен к синхронизирующим входам триггеров, выход (в+2 )-готриггера соединен с вторым входомблока, с информационным входом первого триггера и со счетным входом счетчика, выходы которого подключены квходам первой группы схемы сравненияи к входам дешифратора, - 1 й (1= 1,а: ) ныход дешифратора соединен спервым входом -го (1= 1+1,в ) элемента И первой группы, с первыми входами(х+ )-го триггера, выход 1-го триггера соединен с вторыми входами 1-хэлементов И третьей и четвертой группы, с вторыми входами (1, )-х элементов И второй группы и с 1-м разрядом первой выходной шины блока,выход(1, )-Го элемента И второйгруппы подключен к (1, )-му разрядутретьей выходной шины блока, выходыэлементов И третьей группы и выходщ-го триггера соединены,с соответствующими входами элемента ИЛИ, выходкоторого подключен к информационномувходу (в+ )-го триггера, выход которого соединен с информационным входом (в+2 )-го триггера, с третьим выходом блока и с вторыми входами элементов И первой группы, выходы которых подключены к соответствующимразрядам второй выходной шины блока,выходы регистра соединены с входамивторой группы схемы сраннения, выходкоторой подключен к перному выходублока и через инвертор к третьемувходу элемента ИУказанное устройство обладает ограниченными функциональными возможностями, обеспечивает только определение кратчайшего пути.Наиболее близким техническим решением к изобретению является устройство, содержащее первую группу изрегистров, образующих треугольную наддиагональную матрицу (1= 1,к;= +1,в ), первую группу элементов ИЛИ, блок управления и вторую группу регистров,выходы -ого регистра второй .группы подключены к первым входам 1-ых элементов И первой группы, вторые входы которых соединены с соответ ствующим разрядом первой выходной шины блока управления, -й разрядтов И, группу инверторов, элементИЛИ,элемент И, инвертор, регистор, счетчик, схему управления, дешифратор,и генератор, выход которого подклю"чен к первому входу элемента И,второйвход которого соединен с четвертымВходом блока, выход элемента И под"ключен к синхронизирующим входам 65 второй выходной шины которого подклечен к первым входам -х элементов И второй группы, выходы которых соеди-, нены с входами -го регистра второй группы 2.Недостатком известного устройства является низкое быстродействие из-за необходимости двоекратного заполнения счетчиков "весов" дуг матричной модели тактовыми импульсами и последующего сравнения результатов двух просчетов.Целью изобретения является повышение быстродействия устройства,Указанная цель достигается тем, что в устройство для моделирования сетевых графов, содержащее первую группу из Ц регистров, образующих треугольную наддиагональную матрицу (з.= 1,в; 1= д+1,ю ), первую группу элементов ИЛИ, блок управления и вторую группу регистров, выходы 1-го регистра второй группы подключены к первым входам 1-х элементов И первой группы, вторые входы которых соединены с соответствующим разрядом первой 25 выходной шины блока управления, 1-йразряд второй выходной шины которого подключен к первым входам -х элементов И второй группы, выходы которых соединены с входами -го регистра второй группы, введены сумматор, блок формирователей пути, блок выбора максимального кода, вторая группа эле" ментов ИЛИ,.третья группа регистров,: третья, четвертая и пятая группы элементов И, элементы И и элемент ИЛИ, выход которого подключен к первым входам элементов И, вторые входы ко- торых соединены с соответствующими разрядами первой выходной шины блока. управления, выход 1-го элемента И под 40 ключен к первым входам 1-х элементов И третьей группы, выходы которых ,соединены с входами 1-го регистра третьей группы, выходы которого подключены к первым входам 1-х элемен тов И червертой группы, выходы кото-. рых соединены с входами 1-й группы блока выбора максимального кода, выходы первой группы которого подключены к вторым входам соответствующих элементов И второй группы, выходы второй группы блока выбора максимального кода соединены с входами, первой группы блока Формирователей пути, входы второй группы которого подключены к соответствующим разрядам второй выходной шины блока управления, первый выход которого соединен с входом блока формирователей пути, установочные входы регистров третьей группы подключены 60 к второму выходу блока управления, третий выход которого соединен с вторыми входами элементов И четвертой группы, выходы Ц-го регистра первой группы подключены к первым входам 1-х элементов И пятой группы, выходы которых соединены с 11-ми входами соответствукицих элементовИЛИ первой группы, выхОды которых подключены к входам элемента ИЛИ и к входам первой группы сумматора, выходы которого соединены с вторыми входами соответствующих элементов И третьей группы, Ц-й разряд третьей выходной шины блока управления подключен к вторым входам Ц-х элементов И пятой группы, выходы 3-х элементов;И первой ".руппы соединены с -ми входами соответствующих элементов ИЛИ второй группы, выходы которых подключены к входам второй группы сумматора, четвертый вход блока управления является управляющим входом устройства.Кроме того, блок формирователей пути содержит регистр, первую и вторую группу элементов ЙЛИ и треугольную наддиагональную матрицу Фооррователей пути, каждый Ц-й 1= 1, в-,1;1= 1+1,щ ) форьарователь пути содержит три элемента И и триггер, входкоторого соединен с выходом первого элемента И, единичный и нулевой выходы триггера подключены к первым входам второго и третьего элементов И соответственно, выход третьего элемента И (х,+1 )-го формирователя пути соединен с вторыми входами второго и третьего элементов И (3.+1),+1)-го формирователя пути, выход третьего элемента И Я,1+1 )-ого формирователя пути подключен к входу )-го элемента ИЛИ первой группы, выход которого. соединен с вторыми входами второго и третьего элементов И (,у )-го формирователя пути, выход второго элемента И (1,1 )-го формирователя пути подключен к входу 1-го элемента ИЛИ первой группы и к входу 1-го элемента ИЛИ второй группы, выход которого соединен с входом одноименного разряда регистра выход первого элемента ИЛИ первой группы подключен к входу первого разряда регистра, вторые входы второго и третьего элементов И (1,а )-го формирователя соединены с входом блока, -й вход первой группы входов которого подключен к первым входам первых элементов И формирователей. пути 1-й.строки, -й вход второй группы входов блока подключен к вторым входам первых элементов И формирователей пути -го столбца.Причем блок управления содержит в+2 триггера, четыре группы элемен20 на вход вентиля 9, а на выходе 46+появляется высокий потенциал, поступающий на входы вентильной группыЗ . В результате код, записанныйна регистре 2, через открытую вентильную группу 31 поступает через5группу элементов ИЛИ 4 на первыйвход сумматора 5 и элемент ИЛИ б.В зависимости от содержимого регистра 2 на выходе элемента ИЛИ бФормируется высокий или низкий Опотенциал, разрешающий или запрещающий запись результата суммирования в регистры 7. Если код ненулевой,навыходе элемента ИЛИ 6 Формируется сигнал логической единицы, разрешающий запись результата, если .коднулевой - Фбрмируется сигнал логического нуля, запрещающий запись результата. На второй вход сумматора5 с выхода элемента 11 поступаетв данном случае код числа нуль Результат суммирования (если на регистре 2 ненулевой код ), парафазнымкодом через открытую вентильнуюгруппу 8 записывается на регистр7; В блоке 17 сигнал логическойединицы с выхода триггера 32 черезэлемент 33 и элемент 36 поступаетна вход триггера 32, С приходомвторого тактового импульса триггер32 щ ,устанавливается в единичное состояйие, а триггер 32. - в нулевое.На выходе 47 блока появляется высо 4кий потенциал, поступающий на входывентильных групп 10, в результатеобратные коды чисел, записанных на 35регистрах 7 поступают на входы узла26 блока 16.Блок 16 работает следующим образом.На входы элементов .ИЛИ 28 и, И 29схем 27+27,27(ш )и поступает 40(в) кодов, каждый из которых представлен и разрядами, с обратных выходов триггеров регистров 7 черезвентильные группы 10. В первый момент анализируются старшие разряды 45всех кодов. Если хотя бы один изстарших разрядов кодов равен 1,на выходе элемента ИЛИ-НЕ 25 появ.ляется низкий потенциал (код 0 ),который соответствует сигналу запрета при анализе остальных разрядовкодов, старшие разряды которых равныО. Этй сигналы формируются на выходахэлементов ИЛИ 28 и поступают на входыэлементов И 29, Те коды, старшие раз ряды которых равны 1, проходят черезэлементы И 29 узла 26 . Если старшиеразряды всех чисел равны О, на выходе элемента ИЛИ-НЕ 25 формируется1, благодаря чему обеспечивается раз-.решение на прохождение остальныхразрядов всех кодов через элементыИ 29 узла 26,. Аналогичным образоманализируются вторые по старшинствуразряды всех кодов и т.д , в результате чего на выходах 30, ЗОа, 65 ЗОщФормируется позиционный код номера максимального кода, а на выходах 31,3131 и формируется обратный код максимального из всех анализируемых кодов, .т.е. код минимального из чисел. записанных на регистрах 7. В рассмотренном случае код минимального числа был записан на регистре 7, поэтому после айа- лиза этот.код формируется на выходах 31 ,31,,31 л блока 16, а на выходе 30 формируется код 1, сигнализирующий о том, что минимальный код записан на регистре 7 .Одновременно с появлением высокого потенциала на выходе 47 блока 17 формируется сигнал 1 на выходе 4727 который поступает на вход вентильной группы 14, в результате чего код минимального числа с выходов 31 блока 16 записывается (парафазным кодом) .на регистр 12 и на вход элемента И 19 матрицы 15, На другие входы элементов И 19 поступает сигнал с выход 30 блока 16, в результате триггер 18 матрицы 15 устанавливается в единичное состояние,С приходом следующего тактового импульса триггер 32,+ блока 17 устанавливается в нулевое состояние, а триггер 3", - в единичное, сигнал с выхода которого устанавливает в единичное состояние триггеры регистров 7 и поступает на вход счетчика 39, содержимое которого увеличивается на единицу. В результате на второй . выходной шине дешифратора 40 появляется высокий потенциал. С приходом очередного импульса триггер 32 бло 1 ка 17 устанавливается в единичное состояние, поэтому на выходах 46 и 465 высокие потенциалы, результат суммирования кода, записанного на регистре 2 матрицы 1 ( если этот код .не нулевой), .с кодом, образуемым на выходе группы элементов 11, записывается на регистр 7 . С приходом следующего импульса триггер 32 блока 17 устанавливается в единичное состояние, и высокие потенциалы на выходах 46 и 46. Результат суммирования кода с выхода регистра 2 матрицы 1 с кодом регистра 12, аппо сигналу 46 открывается вентильная группа 13 1 записывается на регистр 7 .С приходом следующего тактового импульса триггер 32, блока 17 устанавливается в нулевое состояние, а триггер 32+- в единичное. В результате высокие потенциалы появляются на выходах 47, и 47 . Эти потен циалы обеспечивают выдачу обратных кодов с регистров 7 в блок 16, запись кода минимального из этих кодов на регистр 13 и установку в единич-.Ъное состояние одного из триггеров 183 или 18 щ, в зависимости от того, на0 5 каком из регистров 7 или 7 записы 2вается меньший код.С приходом очередного тактовогоимпульса триггер 32устанавливается в .нулевое состояйие, а триггер32 - в единичное, в результате триг 5геры регистров 7 устанавливаются вединичное состояние и добавляетсяединица в младший разряд счетчика 39и на третьем выходе дешифратора 40формируется сигнал 1. 10Далее работа устройства происходит аналогично рассмотренному. Например, в 1-ом цикле работы устройства производят суммирование содержимого регистров 2 (1+1 )-го столбца 15матрицы 1 с содержимым регистров12,1212,; ( содержимое регистра 21+суммируется с кодом нуля),.определяют минимальную из сумм и кодее записывают на регистр 12 н)ф а 20один из триггеров 181(+,О, 18 цй 1.1%(н)блока 15 или несколько триггеровв случае, если на некоторых из регистров 7 ,7 7; записаны одинаковые коды,.что означает - черезданные вершины исследуемого графапроходят одинаковые по величине минимальные пути) устанавливаетсяв единичное состояние.Работа устройства продолжаетсяаналогичным образом до тех пор,пока содержимое счетчика 39 не становится равным коду, записанномуна регистре 41. В этом случае навыходе схемою 42 появляется высокийпотенциал, а на выходе элемента 43низкий, поэтому импульсы с генератора 45 не поступают на входы триггеров 32. Сигнал с выхода схемы 42является также сигналом опросаблока 15 для определения кратчайшего пуФи. Этот сигнал с выхода 49поступает на выходы вентилей 20,и 21, блока 15.Единичные выходы триггеров 18соединены с первыми входами элемента 20, а нулевые выходы - с первыми.входами элементов 21, Таким образомесли триггер 18 установлен в единичное состояние, то соответствующиеему элемент 20 открыт, а элемент 21закрыт, и наоборот, Сигнал опросас выхода 49 проходит через открытыевентили 21,2121, т.е.сначала опрашиваются триггеры в-гостолбца блока 15, пока не находитсяпервый триггер 18 щ, установленный 55в единичное состояние, у которогозакрыт элемент 21 и открыт элемент20. Высоким потенциалом с выходаэлемента 20 через элемент 23, устанавливается в единичное состояние 60в-й триггер регистра 24. Это означает, что щ-я вершина исследуемогографа, входит в кратчайший путь, ичерез элемент 221.1 сигнал опроса проходит на опрос (1-1 )-го столбца бло ка 15, т.е. поступает на вторые входы элементов 20 и 21; ). Если же в щ-ом столбце матрицы 15 ни один из триггеров 18 не находится в единичном состоянии, высокий потенциал с выхода элемента 21 щ через элемент 22 поступает на опрос (в )-го столбца, т.е. поступает на вторые входы элементов 20 и 21Аналогичным образбм опрос продолжается до тех пор, пока не найдется триггер 18,1, установленный в единичное состояние, Это означает, что из 3-й вершины в первую вершину исследуемого графа имеется кратчайший путь, В этом случае устанавливаются в единичное состояние )-ый и 1-ый триггеры регистра 24, что сигнализирует об окончании моделирования.П р и м е р. Пусть задан однонаправленный граф с нагруженными дугами, описываемый матрицей где элементы а = О, если нет дугииз 1-ой в 3-ую вершину.В исходном состоянии на регистры2"матрицы 1 заносятся коды "весов" дуг графасоответствунициезначениям а . Все триггеры регистров 7 устанавливаются в единичноесостояниеВ блоке 17 управления нарегистр 41 заносится код числа 7,триггер 32устанавливается в единичное состояние, на счетчик 39заносится код единицы, Все остальные триггеры блока 17 установлены в .нулевое состояние.В блоке 15 все триггеры 18 и триггеры регистра 24 установлены в нулевое состояние. Все триггеры всех остальных регистров устройства установлены в нулевоесостояние.Работа устройства начинается с подачейуправляющего сигнала на вход 50 блока 17.На первом шаге (после поступления первых трех тактовых импульсов) происходит суммирование содержимого регистра 2 кода числа 5) с кодом нуля и занесение результата на регистр 7, далее через блок 16 - на регистр 122. Триггер,18, блока 15 устанавливается в единичное состояние.На втором шаге (после поступления очередных четырех тактовых импульсов) происходит суммирование содержимого регистра 24 з(кода числа 4) с кодом нуля и занесение результата нарегистр 7, затем суммирование содержимого регистра 2 (кода числа О) с содержимым регистра 12(кодом числа 3), но так как на регистре 2 код нуля, результат суммирования не заносится на регистр 7. Далее проис 5 ходит занесение результата суммирования с регистра 7 через блок 16 на регистр 12и установка в единичное состояние триггера 184 блока 15.На третьем шаге, после поступления очередных пяти импульсов, происходит суммирование содержимого реги-. стра 2,(4(код 0 ) с кодом нуля - резуль- тат никуда не заносится содержимого)регистра 224(код числа 3) с содержи мым регистра 124 (код числа 5) и занесение результата (код числа 8) на регистр 7 ; содержимого регистра 234 (код числа 2) с содержимым регистра 124 код числа 4) и занесение результата (код числа 6) на регистр 73 .Далее происходит выбор минимального из кодов, занесенных на регистры 7 (код числа 6 на регистре 7) с помощью блока 16, занесение его на регистр 124.и установка в единичное состояние триггера 184.С приходом очередного импульса с выхода генератора 45 работа устройства происходит аналогично.После выполнения четвертого шага на регистр 12 заносится код числа 8 и триггер 18, блока 15 устанавливается в единичное состояниеПосле выполнения пятого шага на регистр 126 заносится код числа 9 и триггер 184,6 блока 15 устанавливается в единичное состояние. После выполнения шестого шага на регистр 127 заносится код числа 12 и триггер 18 ь 7 блока 15 устанавливается в единичное состояние; на выходе схемы 42 сравнения формируется высокий потенциал, запрещающий дальнейшее поступленйе импульсов с выхода 45 генератора 45 на входы .триггеров 32 блока 17 и служащий сигналом опроса триггеров блока 15. сигнал опроса проходит через открытые элементы И 21 блока 15 на входы элементов И 207 и 216, к первым входам которых подключены соответственно прямой и инверсный выходы триггера 18 . Высокий потенциал с выхода элемента 20 поступает на один из входов элемента 23 т, с выхода которого устанавливается в единичное состоя- ние триггер седьмого разряда регистра 24. Далее происходит опрос триггеров шестого столбца, в котором установлен в единичное состояние триггер 184. Сигнал опроса проходит через открытые элементы 21 шестого столбца и через открытый элемент 20 поступает на один из входов элемента 236 , сигналом с выхода которого устанавливается в единичное состояние триггер шестого разряда регистра 24, и дичее на опрос четвертого столбца, в котором установлен в единичное состояние триггер 184, Сигналом с выхода элемента 2034 устанавливается через элемент 234 триггер четвертого разряда регистра 24, и продолжается опрос. В третьем столбце установлен в единичное состояние триггер 184 з, поэтому сигналом с выхода элемента 204 через .элемент 233 устанавливается в единичное состояние триггер третьего разряда регистра 24, а через элемент.224 - триг-. гер первого разряда регистра 24.Процесс поиска минимального пути на этом заканчивается.Таким образом, на регистр 127 заносится код длины минимального пути в седьмую вершину графа (на остальные регистры 12,,12 ь заносятся коды длины минимального пути в соответствующие вершины). В регистре 24 устанавливаются в единичное состояние триггеры, номера которых соответствуют номерам вершин графа, образующих кратчайший пусть, т.е. триггеры 1,3,4,6,7.Благодаря введенным элементам и связям между ними, повысилось быстродействие устройства.