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

 

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

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

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

РЕСПУБЛИН

„„Я0„„1251

Al (д1) 4 С 06 F 15/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA фс / у г >

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

H A BTGPCHGMY СВИДЕТЕЛЬСТВУ

«ИБЛИОТЕЫА (21) 3830183/24-24 (22) 25.12,84 (46) 15. 08.86. Бил. № 30 (72) С.М.Баженов, B,Ë.Ãàéäóêîâ, М.Г.Донов и В.A.Òèòîâ (53) 681.333 (088.8) (56) Авторское свидетельство СССР

¹ 1065858, кл.G 06 F 15/20, 1982.

Авторское свидетельство СССР

¹- 1151979, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

СЕТЕВЫХ ГРАФОВ (57) Изобретение относится к области вычислительной техники и может быть использовано при исследовании параметров сетевых графов, а также при исследовании показателей надежности сложных систем. Цель изобретения— расширение функциональных возможностей за счет определения вершин, l2

Образующих путь Mяксимального произ ведения длин соответствующих дуг графа. Устройство содержит блок формирователей пути: 12, генератор 1 тактовых импульсов, первый элемент

И 2, первый счетчик 3, дешифратор 7 первую группу ре -истров 18, группу элементов ИЛИ 16,. треугольную наддиагональную матрицу 22; вкгпач акицую (и- I ) ° n/2-1 (где n — ч исло вершин в графе групп, состоящих из регистра и блока элементов И, 51099 группы блоков элементов И 17,19. Дополнительно введена вторая группа регистров 15, группа блоков 14 умножения, блок 13 задержки, блок 11 оиска максимального кода, второй и третий 5, 8 элементы И, регистр 9, группа триггеров 10, второй счетчик

6. Предложенное устройство позволяет одновременно производить операцию умножение над 1.кодами чисел при определении параметров сетевых гра.фов ° 3 ил, Изобретение относится к вычислительной технике, может быть использовано при исследовании параметров сетевых графов, а также при исс.педовании показателей надежности сложных систем.

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

На фиг.l представлена структурная схема устройства для моделирования сетевых графов на фиг.2 -- структур-ная схема блока поиска максималь--ного кода; на фиг.3 — структурная схема блока формирователей пути.

Устройство для моделирования сетевых графов (фиг.11 содержит гене- уО ратор ll тактовых импульсов, элемент

И 2 счетчик 3, триггер 4, элемент

И 5, счетчик 6, дешифратор 7, элемент И 8;сдвигающий регистр 9, группу три1 геров 10 ....10 > <, блок 11 25 поиска максимального кода., блок 12 формирователей пути, блок 13 задержки, группу блоков 14,....,,14 умножения, вторую группу (сдвигающих) регистров 15,,...,15„ „, группу элементов ИЛИ 16,...,16„,, вторую группу элементов И 17,...„17,„... первую группу регистров 18,...,.I8>, первую группу блоков элементов

И 19,...,19„,,группу регистров

20», °,10()„ и группу элементов

И 21»,...,21 „ „)и напдиагональной матрицы 22, вход 23 запуска.

Блок II поиска максимального.кода (Фиг.2) содержит блок элементов

ИЛИ 24, сдвигающие регистры 25»,...,.

25 „ », элемент ИЛИ 26, первую группу элементов И 271,...,27„, регистр

28, вторую группу элементов

И 29„,...,29, блок 30 элементов

И, третий, четвертый, второй и первый входь. 31,32, 33 и 34, первую группу выходов 35,,...,35,, выход

36 и вторую группу выходов 37, Блок 12 формирователей пути (фиг.3) содержит триггеры 381, ° .., 38» „ ), первую, вторую и третью группы элементов И 39;,...,39(40 g у ° e ° 940(q-„) „41(g у e o 4 41 (и «1л р первую и вторую группы элементов

ИЛИ 42< ° ° °,42и, и 43, ° * °,43, регистр 44,: группы входов 45»,..., 45,и 46,...,46„, вход 47.

Устройство для моделирования сетевых графов работает следующим образом, В исходном состоянии регистры я р 8,,..., l „, триггеры 10,...,10»,, регистры 15,...,15„,, счетчики 3 и

6, регистры 25»,...,35 4 (Фиг.2), триггеры 38„»...,38<„,1„1фиг,3) и триггеры регистра 44 установлены в нулевое состояние (установочные входы на Фиг.l — 3 не показаны), триггер 4, триггер младшего разряда регистра 9, триггер регистра 28 и триггер 38.1 — в единичное состояние. На регистры 20» ...,,20»„,) матрицы 22 записаны коды весов соответствующих дуг графа, при этом код

1251099 веса пути из первой вершины графа во вторую записан на регистр 18 .

Если отсутствует путь из i -й вершины

j-ю (i = l,n-l, j = З,п, i P j),, то регистр 20; устанавливается в нулевое состояние.

Работа устройства начинается после подачи на вход 23 сигнала высокого уровня. По этому сигналу первый импульс с генератора 1 через открытый элемент И 2 записывает единицу в счетчик 3, а через открытый элемент И 5 устанавливает в нуль триггер 4, записывает единицу в счетчик 6, поступает на первые входы регистров 15,...,15> „, разрешающих прием кодов, а также сдвигает код единицы из первого разряда регистра, 9 во второй. Сигналом с выхода триггера второго разряда регистра 9 ус- 2о танавливается в единичное состояние триггер 10, с выхода которого сигналом высокого уровня открывается . блок элементов И 19, после чего код с выхода регистра 18 подается 25 на первый вход блока 14 умножения.

Одновременно сигнал высокого уровня с первого выхода дешифратора 7 поступает на первый вход блока 12 и на первые входы блоков элементов И 17>, щ

21 . и 21, в результате чего коды с регистров 20 и 20 э через соответствующие блоки элементов И 21 и 21 . ИЛИ 16 и 16 записываются на регистры 15, и 15<. С приходом второго импульса с выхода генератора 1 содержимое счетчика 3 увеличивается на единицу, через открытый элемент И 8 высокий потенциаа подается на регистры 15, блок 11 и блоки „

14 умножения, т.е. начинается процесс умножения кода, поданного на первый вход блока 14< умножения, на код, записанный в регистре 15, Результат умножения с регистра 15 4 через блок 13 задержки подается в блок 11 определения максимального кода.

Блок 11 функционирует следующим образом. Сравниваемые числа поступают б последовательными кодами на соответстсующие им регистры 25 по входу

31 (см.фиг.2). Прямой выход первого триггера (не показан) старшего разряда регистра 25; (1.=1,n-l) подключен к -му входу элемента ИЛИ 26, а инверсный — к второму входу элемента И 27.

Пусть при поступлении разрядов кодов, среди которых имеется хотя бы одна единица (например в i-M, i = l,п-l), на прямом выходе триггера перво о разряда регистра 25, устанавливается высокий уровень сигнала (Kop, единицы ). .Этот сигнал поступает на -й вход элемента ИЛИ 26, на выходе которого формируется код единицы, поступающий на первые входы всех элементов И 27. Элементы И 27 (k = 1,п-l, k g i) открыты, так как на их вторые входы поступают высокие уровни сигналов с инверсных выходов соответствующих первых триггеров регистров 25„. Сигналом высокого уровня с выходов элементов И 27 устанавливаются в нулевое состояние

k-e триггеры регистра 28, и этот же сигнал поступает в цепи сброса регистров 25„. Триггер i (i = 1,п-1) регистра 28 остается в единичном, состоянии. Кроме того, сигналы высокого уровня поступают в цепи сброса

k-х регистров 15, При поступлении на регистры 25 кодов нуля на выходе элемента ИЛИ 26 формируется код нуля. В результате все элементы И 27 закрыты. При поступлении разрядов кодов, среди которых несколько единиц, на выходе элемента ИЛИ 26 формируется сигнал высокого уровня, вследствие чего устанавливаются в нулевое состояние триггеры регистра

28 тех кодов, разряды которых равны нулю, кроме того, устанавливаются в нулевое состояние соответствующие этим кодам регистры 25 и 15.

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

Умножение и сравнение кодов производится за щ тактов. По (m+1)-му импульсу формируется сигнал переполнения счетчика 3, который устанав— ливает в единичное состояние триггер 4 и поступает по входу 33 (см. фиг.2) на вторые входы элементов

И 29, По этому сигналу с выходов

35 снимается код с единицами в разрядах, соответствующих гозиционным номерам максимальных кодов. Этот код поступает на блок 12 формирователей пути, а через блок 30 элементов И максимальный код с регистра 25, через блок элементов ИЛИ 24

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

И 17.

В рассмотренном случае значащие коды поступают на первый и второй

I" входы блока 11 (пусть первый коц бопьше второго) . В результате сравнения первый триггер регистра 28 остается в единичном состоянии.

По импульсу переполнения счетчика 3 10 разрешается прием кодов в регистры

15, по этому же сигналу происходит выдача максимального кода, который далее записывается в регистр 18 > (через открытый блок элементов И 17 ), а также выдается сигнал высокого уровня по входу 34 на блок 11 (установка в единичное состояние регистра 28) .

Блок 12 формирователей пути, слу- 2О жит для идентификации вершин моделируемого графа, составляющих максимальный путь. Блок функционирует следующим образом. Пусть на i-м шаге работы схемы 1происходит опрос 25

1-ro столбца матрицы 22) высокий потенциал появляется на 1 -м (k =

l,п-l) выходе блока 11. Этот сигнал подается по входу 45 на вторые входы элементов И 40 „„,...,40 „.

Одновременно с,1 -ro выхода дешифратора 7 на вход 4б„ поступает высокий уровень сигнала, которым устанавливается в единичное состояние триггер 38„ . Это свидетельствует о

М, 5 том, что максимальный путь проходит через k-ю вершину графа. Если, например, на входы 45 < и 45 поступают одинаковые (максимальные) коды, то устанавливаются в единичное состоя- 1О ние триггеры 38, и 38, (1< а)).

На следующем шаге работы устройства по первому импульсу записывается очередная единица в счетчик б, Д со сдвигающего регистра 9 устанавливается в единичное состояние триггер 10, подготовлены к приему кодов регистры 15 и установлен в чулевое состояние триггер 4. С выхода дешифратора 7 открывается блок элементов И 17, опрашиваются блоки элементов И 21, 21 < и 21э и коды, записанные в регистрах 20, 20 и 20, через соответствующие элементы ИЛИ 16 записываются в регистры 15,, 15 и 15 . Затем происходит процесс умножения и сравнения кодов. Далее процесс повторяется до появления высокого уровня сигнала на (n- l ) -м вьгходе дешифр атора 7 .

На (n-1) -м шаге работы устройства с дешифратора 7 подается сигнал высокого уровня цля опроса формирователей путей. Он поступает по входу 47 на вторые входы элементов И 391„ и 41 . Первый вход каждого элемента

39 подсоединен к инверсному выходу соответствующего ему триггера 38, а -,.ервый вход элемента 40 — к прямому вьгходу данного триггера. Если триггер 38 „ находится в нулевом состоянии, то сигнал опроса через элемент

И 391 поступает на опрос элементов И 39 и 41 „ и т.д., пока не будет найден триггер 38,„, установ" ленный в единичное состояние. В этом случае через элемент ИЛИ 43 устанавливается в единичное состояние и -й триггер регистра 44> а через элемент ИЛИ 42 сигнал опроса поступает на опрос 1 -го столбца матрицы триггеров. Если в И-м столбце нет триггера 38, установленного в единичное состояние, то сигнал опроса через элемент ИЛИ 42 „ пос-. тупает на опрос (п-1)-ro столбца.

Если в -м столбце триггеры 40 и 40„ „ (k а1) установлены в единичное состояние, то выбирается вершина с меньшим (k) номером. Опрос продолжается до тех пор, пока не будет найден триггер 38 И,, установленнный в единичное состояние ° В этом случае устанавливаются в единичное состояние k --й "и первый триггеры регистра 44, что сигнализи рует об окончании моделирования. формула из обретени устройство для моделирования сетевых графов, содержащее блок формирователей пути, генератор тактовых

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

1251

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

И подключен к входу первого счетчика, выходы 1. -х блоков элементов

И второй группы (i - "З,n) соедине- 20 ны соответственно с входами регистров первой группы, выход 1 --ro регистра первой группы (i 2, и-1) соединен с информационным входом -ro блока элементов И.первой груп пы, отличающееся тем, что, с целью расширения функциональньтх возможностей устройства эа счет определения вершин, образуюЩих путь максимального произведения ЗО цлин соответствующих дуг графа, в устройство введены вторая группа регистров, группа блоков умножения, блок задержки, второй и третий элементы И, регистр, триггер, второй счетчик и блок поиска максимального кода, включающий блок элементов

ИЛИ, группу сдвигающих регистров, элемент ИЛИ первую и вторую группы элементов И, регистр и блок элемент6в О г

И, причем выход старшего разряда

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

099 8

И второй г руппы, выходы I(QTophlx RB ляются второй группой выходов блока поиска максимального кода, выход каждого сдвигающего регистра группы подключен к одноименному входу блока элементов ИЛИ, вьгхоп которого соединен с первым входом блока элементов

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

45 g 4б

Составитель И.Дубинина

Редактор И.Рыбченко Техред М.Ходанич

Корректор A,Îáðó÷àð

Заказ 4413/47 Тираж 671

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

rro делам изобретений и открытий

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

Подписное

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

9 1251 го триггера группы, выход которо го соединен с управляющим входом

«-го блока элементов И первой группы, выход ) -ro элемента ИЛИ группы (j=l, n-2) подключен к информационному входу j --го регистра второй группы; первая группа выходов блока

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

И группы (n-1) и-й строки треугольной наддиагональной матрицы.