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

125

образующих путь максимального произведения длин соответствующих дуг графа-. Устройство содержит блок формирователей пути- 12, генератор 1 тактовых импульсов, первый элемент И 2, первый счетчик 3, дешифратор 7 первую группу регистров IS, группу элементов ИЛИ 16,. треугольную наддиагональнук матрицу 22, включающую (п-1) Г1/2 1 (где К| число вершин в графе групп, состоящих из регистра и блока элементов И,

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

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

На фиг.1 представлена структурная схема устройства для моделирования сетевых графов j на фиг. 2 - структур- ная с хема блока поиска максималь« - кого кода; на фиг.З - структурная схема блока формирователей пути,

Устройство для моделирования сетевых графов (фиг.1 содержит гене- рэ.тор 1 тактовых импульсов, элемент И 25Сче.тчик 3, триггер 4 элемент И 5, счетчик 6, дешифратор 7, элемент И 8,-сдвигающий регистр 9, группу триггеров 1 0,. . 51 О f,. j., блок II поиска максимального кода., блок 12 формирователей пути, блок 3 задержки, группу блоков I4g ,... 514 умножения, вторую группу (сдвигающих) регистров I 5, ,... , 15,., группу эле- ментов ИЛИ 1 6 ,. . . , 16,,, 5 вторую группу элементов И 1Т ,, . ., 1 7, j первую группу регистров IB, . о , 18(, первую группу блоков элементов И 1 9 , , .. , I 9, , группу регистров ,. . , , ,w и группу элементов И 5.. . ,2 1 у , : наддиагональной матрицы 22, вход 23 запуска.

99

группьт блоков элементов И 17,19. Дополнительно введена вторая группа регистров 15, группа блоков 14 умножения, блок 13 задержки, блок П поиска максш- зльного кода, второй и третий 5, 8 элементы И, регистр 9, группа триггеров 10, второй счетчик . 6, Предложенное устройство позволяет одновременно производить операцию умножение над Ц кодами чисел при определении параметров сетевых гра- :фов. 3 шт.

Блок 1I поиска максимального.ко да (фиг.«2) содержит блок элементов ИЛИ 24, сдвигающие регистры ... 25f, 5 элемент ИЛИ 26, первую групп элементов И 27 5,..,27„, , регист р 28, вторую группу элементов И 29 ,. ч. ,29f, , блок 30 элементов И, третий, четвертый, второй и первый вкодь 31,32, 33 и 34,- первую группу выходов 35j,.,.,35я,( , выход 36 и вторзпо группу выходов 37,

Блок 12 формирователей пути (фиг.З содержит триггеры 38 38(ц.4)п 9 первую, вторую и третью группы элементов И ,,,. ,39(„,,., 40„ ,...,40(,)„ и ,.,.,41 („.,„ первую и вторую группь элементов RTli 42, ,. ..,42ц,, и 43,,...,43j,, регистр 44, группы входов 45,- , о . . , 45и-,и 46,. , ,46j,, вход 47.

Устройство для моделирования сетевых графов работает следу сщим образом.В исходном состоянии регистры 38,,, i ,18,, триггеры lOg, . .., 10„. регистры 15,... ,15,,, счетчики 3 и 6, регистры 25 ,.. . ,, (фиг.2), триггеры 38 ,... ,38(„, (фиг.З) и триггеры регистра 44 устаноапены в нулевое состояние (установочные ВКОДЬ на фиг.1 - 3 не показаны), триггер 4, триггер младшего разряда регистра 9, триггер регистра 28 и -грнггер 38,2 в единичное состояние . На регистры , ,,, , ,20 (,,/у-) матрицы 22 записаны коды весов соот ветствующ1-1Х дуг графа, при этом код

3125

веса пути из нерпой вершкны графа во вторую записан на регистр 18. Если отсутствует путь из i -и вершины j-ro (i 1 ,n-l , j 3,n, i j), .

TO регистр

20:

устанавливается

в нулевое состояние ..,

Работа устройства начинается пос-пе подачи на вход 23 сигнала высокого уровня. По этому сигналу первый импульс с генератора 1 через открытый элемент И 2 записывает единицу в счетчик 3, а через открытый элемент И 5 устанавливает в нуль триггер 4, записьшает единицу в счетчик 6, поступает на первые входы регистров 1 5 ,. .. ,15f,, разрешающих прием кодов, а также сдвигает код единицы из первого разряда регистра 9 во второй. Сигналом с выхода триггера второго разряда регистра 9 устанавливается в единичное состояние триггер Ю,, с выхода которого сигналом высокого уровня открьгаается . блок элементов И 19, после чего код с выхода регистра IS подается на первый вход блока lAj умножения. Одновременно сигнал высокого уровня с первого выхода дешифратора 7 поступает на первый вход блока 12 и на первые входы блоков элементов И 1/э,

21

Ъ

и 212э в результате чего коды

с регистров 20 и через соответствующие блоки элементов И 21(j и 212Э . ИЛИ 16( и 16 записываются на регистры 15 и ISj. С приходом второго импульса с выхода генератора 1 содержимое счетчика 3 увеличивается на единицу, через открытьш элемент И 8 высокий потенциа подается на регистры 15, блок 11 и блок 14 умножения, т.е. начинается процесс умножения кода, поданного на первый вход блока 14 умножения, на код, записанньш в регистре 15г. Результат умножения с регистра 15 через блок 13 задержки подается в блок 11 определения максимального кода.

Блок 11 функционирует следующим образом. Сравниваемые числа поступаю последовательными кодами на соот- ветстсующие им регистры 25 по входу 31 (см.фиг.2). Прямой выход первого триггера (не показан) старшего разряда регистра 25; (,п-1) подключен к i-му входу элемента ИЛИ 26, а инверсный - к второму входу элемента И 27.

10

15 О

20

5

5 Q 5

5

0994

Пусть при поступлении разрядов кодов, среди которых имеется хотя бы одна единица например в i-м, i 1,п-1), на прямом выходе триггера перво о разряда регистра 25 устанавливается высокий уровень сигнала (код единицы). Этот сигнал поступает на 1 й вход элемента ИЛИ 26, на выходе которого формируется код единицы, поступающрт на первые входы всех элементов И 27. Элементы И 27k- (k I ,п-1 , ) открыты, так как на их вторые входы поступают высокие уровни сигналов с инверсных выходов соответствующих первых триггеров регистров 25. Сигналом высокого уровня с выходов элементов И 27( устанавливаются в нулевое состояние k-e триггеры регистра 28, и этот же сигнал поступает в цепи сброса реги- стров 25ц. Триггер i (i 1,п-1) регистра 28 остается в е,циничном состоянии. Кроме того, сигналы высокого уровня поступают в цепи сброса k-x регистров 15, При поступлении на регистры 25 кодов нуля на выходе элемента ИЛИ 26 формируется код нуля. В результате все элементы И 27 закрыты. При поступлении разрядов кодов, среди которых несколько единиц, на выходе элемента ИЛИ 26-формируется сигнал высокого уровня, вследствие чего устанавливаются в нулевое состояние триггеры регистра 28 тех кодов, разряды которых равны нулю, кроме того, устанавливаются в нулевое состояние соответствующие этим кодам регистры 25 и 15.

В результате сравнения в единичном состоянии остается 1 -и триггер регистра 28, а максимальньй код формируется на выходе блока элементов ИЛИ 24.

Умножение и сравнение кодов производится за щ тактов. По (т+1)-му импульсу формируется сигнал переполнения счетчика 3, который устанав- ливает в единичное состояние триггер 4 и поступает по входу 33 Гсм. фиг.2 на вторые входы элементов И 29. По этому сигналу с выходов 35 снимается код с единицами в разрядах, соответствующих позиционным номерам максимальных кодов. Этот код поступает на блок 12 формирователей пути, а через блок 30 элементов И максимальный код с регистра 25; через блок элементов ИЛИ 24

поступает на входы блоков элементов И 17.

В рассмотренном случае значащие. коды поступают на первый и второй вхо.дь блока 1 1 (пусть первый код больше второго). В результате сравнения первый триггер регистра 28 остается в единичном состоянии, По импульсу переполнения счетчика 3 разрешается прием кодов в регистры 15, по этому же сигналу происходит вьздача максимального кода, который далее з аписывается в регистр 18g (через открытый блок элементов И 7 а также выдается сигнал высокого уровня по входу 34 на блок 11 (установка в единичное состояние регистра 28).

Блок 12 формирователей пути, слу- жит для идентификадии вершин моделируемого графа, составляющих максимальный путь. Блок функционирует следующим образом. Пусть на i-м гааге работы схемы (происходит опрос 1-го столбца матрицы 22) высокий потенциал появляется на k-м (k 1,п-1) выходе блока П. Этот сигнал подается по входу 45 на вторые входы элементов И ,, , . ,40 « . Одновременно сн -го выхода дешифратора 7 на вход Д6 поступает высокий уровень сигнала которым уста- навл1шается в единичное состояние триггер 38) ;. Это свидетельствует о том, что максимальньм путь проходит через k-ю вершину графа. Если, например, на входы 45 ; и 45 j поступают одинаковые (максимальные) коды, то устанавливаются в единичное состоя- ние триггеры 38ц,; и 38 ц j (k j).

На следующем шаге работы устройства по первому импульсу записывается очередная единица в счетчик 6, со сдвигающего регистра 9 устанав- ливается в единичное состояние триггер 10, подготовлены-к приему кодов регистры 5 н установлен в нулевое состояние триггер 4. С выхода дешифратора 7 открывается блок элементов И 174, опрашиваются блоки элементов И 21,2.4 и 21 и .коды, записанные в регистрах 20,J4 j 202 и 20-)у4, через соответствугацие элементы ИШ1 16 записьгоаются в ре- гистры 15,, 15, и 5з. Затем происходит процесс умножения и сравнения кодов. Далее процесс повторяется д

g O 5

0 5 о д

- 5

0

появления высокого уровня сигнала на (п-) )-м выходе дешифратора 7..

На (n-l)-M шаге работы устройства с дешифратора 7 подается сигнал высокого уровня для опроса форг гировате- лей путей. Он поступает по входу 47 на вторые входы элементов И и 41 . Первый вход каждого элемента 39 подсоединен к инвepcнo y выходу соответствующего ему триггера 38, а ггервый вход элемента 40 - к прямому выходу данного триггера. Если триггер 38 JJ, находится в нулевом состоянии, то сигнал опроса через элемент И 39(f, поступает на опрос элементов И 397ц 2. т.д., пока не будет .найден триггер 38 |,, установ- ленньй в единичное состояние, В этом случае через элемент И.ПИ 43 f устанавливается в единичное состоя - ние п й триггер регистра 44j а через элемент ИЛИ 42 сигнал опроса поступает на опрос i -го столбца матрицы триггеров Если в п-м столбце нет триггера 38, установленного в единичное состояние, то сигнал опроса через элемент. ИЛИ 42(,;, нос- тупает на опрос (п-)-го столбца. Если в J -м столбце триггеры 40 и (k j) установлены в единичное состояние, то выбирается вершина с меньшим (k) номером. Опрос продо.лжается до тех пор, пока не будет найден триггер 38 |, установ- .леннный в единичное состояние. В этом случае устанавливаются в ничное состояние k-и и первый триггеры регистра 44, что сигнализи рует об окончании моделирования,

€ ормула изобретени;,

Устройство для моделирования сетевых графов, содержащее блок формирователей пути, генератор тактовых мпульсов, первый элемент И, первый счетчик, дешифратор, первую группу регистров, группу триггеров; первую и вторую группы блоков элементов И, группу элементов ИЛИ,, треугольную наддиагональную матрицу, включающую группу из (п-1),п/2-1 регистров и группу из (п-) блоков элементов И (где число вершин графа) 5 выходы каждого регистра группы треугольной наддиагональной матри- Щз1 соединены с информационными входами одноименных блоков элементов И

7 группы треугольной наддиагональной матршщ, выходы деши})ратора подключены к yпpaвляratt им входам блоков элементов И группы треугольной наддиагональной матрицы, к первой груп пе входов и входу блока формирователей пути и к управляю1п;им входам блоков элементов И второй группы, выходы блоков элементов И группы каждой строки треугольной наддиаго- нальной матрицы соединены с входаз-га одноименного элемента ИЛИ группы, выход генератора тактовых импуль сов соединен с информационным входо первого элемента И, управляющий вхо которого является входом запуска устройства, выход первого элемента И подключен к входу первого счет- чика, выходы i-x блоков элементов И второй группы (i 3,п) соедине- ны соответственно с входами регистров первой группы, выходj -го регистра первой группы ( п-1) соединен с информационным входом (-го блока элементов И. первой группы, отличающееся TeMj что, с целью расширения функциональных возможностей устройства за счет определения вершин, образую- 1цих путь максимального произведения длин соответствующих дуг графа, в устройство введены вторая группа регистров, группа блоков умножения, блок задержки, второй и третий элементы И,; регистр, триггер, второй счетчик и блок поиска максимального кода, включагсщий блок элементов ИЛИ, группу сдвигающих регистров, элемент ИЛИ,- первую и вторую группы эл ементов И, регистр и блок элементо И, причем выход старшего разряда -го сдьиг ающего регистра группы

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

5

51 5 Ю 15 20 0 5 0

5

(i

099

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

триггера подключен к второму входу I.

второго элемента И, выход которого

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

поиска максимального кода соединен с информационными входами элементов И второй группы, вторая группа выходов блока поиска максимального кода подключена к второй группе входов блока формирователей пути, первый и второй входы i -го блока умножения (, п-1) группы соединены соответственно с выходом одноименного элемента И первой группы и выходом одноименного регистра второй группы, 1-й (,п-1) выход регистра подключен к единичному входу

-го триггера группы, выход которого соединен с управляющим входом ч-го блока элементов И первой группы, выход -го элемента ИЛИ группы ( п-2) подключен к информационному входу j -го pei HCTpa второй группъ), первая группа выходов блока

поиска максимального кода соехщнена с входами установки в О регистра второй группы, информационный вход (п-1)-го регистра второй группы соединен с выходом блока элементов И группы (п-1) п-й строки треугольной наддиагональной матрицы.

Составитель И.Дубинина Редактор И.Рыбченко Техред М.Ходанич . Корректор А,0бручар

Заказ 4413/47 Тираж 671Подписное

ВНИИПИ Государственного комйте та СССР

по делам изобретений и открытий 113035, Москва, Ж-ЗЗ, Раушская наб., Д.4/5

Производственно-полиграфическое предприятие jr.Ужгород, ул. Проектная, 4

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