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

 

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВ, содержащее генератор тактовых импульсов, выход которого соединен с информационньм входом элемента И, управляющий вход которого является входом .запуска устройства, выход элемента И соединен с входом первого триггера группы триггеров, выход счетчика соединен с входом дешифратора, первую группу элементов И, блок формирователей пути, первая группа входов которого соединены с первой группой выходов шифратора, первую группу регистров, выходы всех, кроме последнего, регистров которой подключены к информационным входам элементов И второй группы, трэуголь-ную наддиагонапьную матрицу, включающую группу (г)-1)п/2 регистров и группы из (п-1)п/2 элементов И (где П - количество, вершин графа ) , выходы каждого регис.тра группы треугольной наддиагональной матрицы соединены с информационными входами одноименных элементов и группы треугольной наддиагональной матрицы, выходы элементов И группы каждой строки треугольной наддиагональной матрицы соединены с входами одноименного элемента ИЛИ группы И, отлич ающе е ся тем, что, с целью упрощения устройства, оно содержит группу элементов И-НЕ и группу сумматоров, причем выходы всех, кроме первого, элементов ИЛИ группы соединены с первыми входами соответствующих сумматоров группы, вторые входы которых подключены к выходам соответств5пощих элементов И второй группы, выходы сумматоров группы соединены с группой информационных входов шифратора, информационньй вход которого соединен с выходом первого элемента ИЛИ группы, вторая группа выходов шифратора соединена с информационными входами соответствующих элементов И-НЕ группы , выходы всех элементов И-НЕ группы подключены к входам всех, кроме первого, регистров группы, выходы дешифратора подключены к второй группе входов блока формирователей СП пути, к управляющим входам элементов И группы треугольной наддиагональной со матрицы, к управляющ ™ входам элеvj ментов И-НЕ группы, выход элемента И соединен с входом;счетчика с инсо формационньыи входами лементов И первой группы и с злпфавляю1цим входом первого элемента И второй группы , выходы элементов И первой группы соединены с управляювщми входами остальных элементов И второй группы и с входами соответствующих триггеров , выход J -го триггера группы подключен к управляющему входу Cj+1) - го элемента и первой группы.

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

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

РЕСПУ БЛИН (19) (11) 4(5ц G Об F 15/20

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

Н АВТ0РСНОМУ СВИДЕТЕЛЬСТВЪ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTMA (21),3563842/24-24. (22) 09.03.83 (46) 23.04.85, Бюл. И- 15. (72) В.А.Титов и С.М.Баженов (53) 681. 333 (088. 8) (56) 1. Авторское свидетельство СССР

Ф 842842, кл. G Об С 7/122, 1980.

2. Авторское свидетельство СССР по заявке Р 3341571, кл. G 06 Р 15/20, 1981 (прототип) ° (54) (57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВ, содержащее генератор тактовых импульсов, выход которого соединен с информационным входом элемента И, управляющий вход которого является входом запуска устройства, выход элемента И соединен с входом первого триггера группы триггеров, выход счетчика соединен с входом дешифратора, первую группу элементов И, блок формирователей пути, первая группа входов которого соединены с первой группой выходов шифратора, первую группу регистров, выходы всех, кроме последнего, регистров которой подключены к информационным входам элементов И второй группы, треугольную наддиагональную матрицу, включающую группу (1)-1) ° 11/2 регистров и группы из (rl-1) 11/2 элементов и (где Ь. — количество. вершин графа), выходы каждого регистра группы треугольной наддиагональной матрицы соединены с информационными входами одноименных элементов И группы треугольной наддиагональной матрицы, выходы элементов И группы каждой строки треугольной наддиагональной матрицы соединены с входами одноименного элемента ИЛИ группы И, отличающееся тем, что, с целью упрощения устройства, оно содержит группу элементов И-НЕ и группу сумматоров, причем выходы всех, кроме первого, элементов ИЛИ группы соединены с первыми входами соответствующих сумматоров группы, вторые входы которых подключены к выходам соответствующих элементов

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

И группы треугольной наддиагональной матрицы, к управляющим входам элементов И-НЕ группы, выход элемента

И соединен с входом счетчика с информационными входами элементов

И первой группы и с управляющим входом первого элемента И второй группы, выходы элементов И первой группы соединены с управляющими входами остальных элементов И второй группы и с входами соответствующих триггеI ров, выход . 1 -го триггера группы подключен к управляющему входу (+1)ro элемента и первой группы.

1151

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

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

Недостатком данного устройства является его сложная функциональная структура.

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

ixj регистров, образующих треугольную наддиагональную матрицу(=1,а-1, ; j =1+1,м), первую группу элементов ИЙИ, .блок управления и вторую группу регистров, выходы 1 -горегистра второй группы подключены к первым входам j -ых элементов И первой группы, вторые входы которых сое- Зо .динены с соответствующим разрядом первой выходной шины блока управления, 1 -й разряд второй выходной шины которого подключен к нервыч входам j -х элементов И второй группы, выходы которых соединены с

35 входами -го регистра второй группы, сумматор, блок формирователей шума, блок выбора максимального кода, вторая группа элементов ИЛИ, третья группа регистров, третья, четвертая и пятая группа элеиентав И, элементы

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

i-га элемента.И подключен к первым входам 1 -х элементов И третьей группы, выходы которых соединены с выходами q --го регистра третьей группы, выходы которого подключены к первым входам < -х элементов И четвертой группы, выходы которых соединены с входами i -й группы блока выбора максимапьнага хода, выходы первой груп- пы которога подключены к втарыю входам соответствующих элементов И второй группы„ выходы второй

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

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

\ с s3 -ми входами соответствующих элементов ИЛИ первой группы, выходы которых подключены к входам элемента

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

-х элементов И первой группы соеФ динены с 1 -ми входами соответствующих элемейтов ИЛИ второй группы, выходы которых подключены к входам второй группы сумматора, первый вход блока управления является управляющим входом блока управления, кроме того, блок формирователей пути содержит регистр, первую и вторую группу элементов ИЛИ и треугольную наддиагональную матрицу формирователей пути, каждый 3 ) -й (l =1 %=1 1 = +1,tb) формирователь пути содержит три элемента И и триггер, вход которого соединен с выходам первого элемента И, единичный и нулевой выходы триггера подключены к первым входам второго и третьего элементов И соответственно, выход третьего элемента И (l,1 +1)-ro формирователя пути соединей с вторьии входами второго и . третьего элементов И (j+1, 1+1)-го формирователя пути, вход третьего элемента И (1, 1 +1)-га фармироватеI ля пути подключен к входу 1 -rî элемента ИЛИ первой группы, выход которого соединен с вторьии входами второго и третьего элементов И формирователя пути, выход второго элемента И () )-ro формирователя пути

I подключен к входу -га элемента ИЛИ

1 первой группы н к входу 1 -го эле- мента ИЛИ второй группы, выход кото1151979

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

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

1-и (i=1,rn-1) выход дешифратора соединен с первымвходом 1 -ro(1=i+1,в ) элемента И первой группы, с первыми входами (!j )-х элементов И второй группы, с первым входом 1 -го з5 элемента И третьей группы и через

4"й инвертор группы с первым входом -го элемента И четвертой группы, выход которого подключен к информационному входу (i+1)-го триггера, 4 выход 1 -го триггера соединен с вторычи входами 1 -х элементов И третьей и четвертой группы, с вторьг ми входами (!j )-х элементов И второй группы н с 1 --м разрядом первой 45 выходной шины блока, выход (ij )-го элемента И второй группы подключен к (jI )-му разряду третьей выходной шины блока, выходы элементов И третьей. группы и выход tn-го тригге- 50 ра соединены с соответствующими входами элемента ИЛИ, выход которого подключен к информационному входу (@+1)-ro триггера, выход которого подключен к информационному входу (А+2)-го триггера, выход которого соединен с информационным входом (ю+2)-rо триггера,. с третьим выхо4 дом блока и с вторыми входами элементов И первой группы, выходы которьтх подключены к соответствующим разрядам группы, выходы которых подключены к соответствующим разрядам второй выходной шины блока, выходы регистра соединены с входами второй выходной шины блока, выходы регистра соединены с входами второй выходной шины блока, выходы регистра соединены с входами второй группы схемы сравнения, выход которой подключен к первому выходу блока и через инвертор к третьему входу элемента И (2) .

Недостатком известного устройства является сложная функциональная структура.

Цель изобретения — упрощение устройства.

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

1 сумматоров группы, вторые входы ко- .

1151979 торык подключены к выходам соответствующих элементов И второй группы, выходы сумматоров группы соединены с группой информационных входов шифратора, информационный вход которого соединен с выходом первого элемента ИЛИ группы, вторая группа выходов шифратора соединена с информационными входами соответствующих элементов И-НЕ-группы, выходы всех

t0 элементов И-НЕ группы подключены к входам всех, кроме первого, регистров группы, выходы дешифратора подключены к второй группе входов блока формирователей пути, к управляющим входам, элементов И треугольной наддиагональной матрицы к управляющим входам элементов И-ЙЕ группы, выход элемента И соединен с входом счетчика, информационными входами элементов И первой группы и с управляющим входом первого элемента И второй группы соединены с управляющими входами остальных элементов И второй группы и с входами соответствующих триггеров группы, выход j— го триггера группы подключен к управляющему входу (j +1)-го элемента и первой группы.

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

Устройство содержит генератор 1 тактовых импульсов, элемент И 2, 15 блок 3 формирователей пути, счетчик

4, дешифратор 5, сумматоры 6,..., 6 „ где q — максимальное количество вершин в графе, группу элементов

ИПИ 71. ..,7ь.1, группу элементов И-НЕ40

8» а ° е, 8 „у группу регистров 9 у ° ° ° у

9„„группу элементов И 10,...,1Од, > треугольную наддиагональную матрицу

1 1 р состоящую из группы регистров

29...,12(л.1„и группы элженто И 45

13, ° ° °,131ь,)„, группу триггеров

14, ° ° ., 14, ãpóïïó элементов И

151, ° ° °, 15, шиФратор 16, вход 17.

Блок 3 формирователей пути (фиг.2) включает триггеры 18<>„... 18<„. „, 5о первый 19<1,...,19(„.,1Д, вторые 20

20(„.,)„и третьи элементы И 21,..., 21 .,)„, первую 221,...,22я.< и вто. рую 231,...,23„. группы элементов

ИЛИ, регистр 24, входы 25 ° ° °,25я 55

261,...,26я и 27.

Шифратор 16 (фиг.3) включает эле-менты ИЛИ 28 и элементы И 29, входящие в состав узлов 30 1,...,30д, анализа разрядов (в — число разрядов в кодах), включающих схемы поразрядного переноса 31 „ ...,31„,„, элементы ИЛИ-НЕ 32,...,32, выходы 33 1,..., 33 „„и 34 „..., 34„„1„, ) входы 35«.....35 „1,„, В исходном состоянии регистры ц григгеры 14 ... ° 14 (фиг.1) установлены в нулевое состо; яние. На регистрах 12,1. ° .. 12<„,1„ матрицы 11 записаны обратные коды

"весов" соответствующих дуг графа, при этом обратный код "веса" пути из первой вершины во вторую записан в регистре 9 . Если дуги между какими-либо вершинами графа отсутствуют, то на соответствующих регистрах записаны коды нуля.

Триггер 18 > (фиг.2) установлен в единичное состояние, а триггеры

1811,..., 18(>., „ и триггеры регистра

24 установлены в.нулевое состояние.

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

10<. Код с выхода счетчика 4 {в данном случае код единицы) поступает на вход дешифратора 5, на первом выходе которого появляется высокий потенциал. Этот сигнал подается на вторые входы элементов -HE 3

И 1311 и 1323 а также по входу 25 (фиг.2) на .первые входы элементов

И 19 и 19 1 блока 3. По этому сигналу код с регистра 1211 поступает через группу элементов И 1311 и группу элементов ИЛИ 71 на первую группу входов шифратора 16, на вторые входы которого поступает с сумматора б результат сложения кодов с регистра 9> и с регистра 13 1, на другие входы - нулевые коды с выходом сумматоров 6,...,6 » шифратор работает следующим обpBsoM

На входы элементов ИЛИ 28 и И 29 схем первого поразрядного узла перекоса по входам 35и" 35ия, поступает (И-1) кодов, каждый из которых представлен а разрядаии. Н первый момент анализируются старшие разряды.

1151979 всех кодов. Если хотя бы один из старших разрядов кодов равен единице, то на выходе элемента. ИЛИ-НЕ 32 появляется низкий потенциал (код

"0"), который соответствует сигналу запрета при анализе остальных разрядов кодов, старшие разряды которых равны "0". Эти. сигналы форми- руются на выходах элементов ИЛИ 28

10 и поступают на входы элементов .И 29.

Коды, старшие разряды которых равны "1", проходят через элементы И

29 узла 30 . Если старшие разряды всех. чисел равны "0", то на выходе элемента ИЛИ-НЕ 321 сформируется "1" благодаря чему обеспечивается разрешение на прохождение остальных разрядов всех кодов через элементы

И 29 узла 30 . Аналогичным образом анализируются вторые по старшинству разряды всех кодов и т.д., в результате чего на выходах 34,...,34 „ 1 сформирован позиционный код номера максимального кода, а на выходах

33,33,...,33 „ сформируется обрат-

25 ный код максимального из всех анализируемых кодов, т.е. в данном случае код минимального из чисел, .поступивших на первый и второй входы шифратора 1. Полученный код через ®О группу элементов И-НЕ Зз записывает ся в регистр 9 . Сигналы с выходов

34 шифратора 16 подаются на входы

26 блока 3.

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

Пусть на -м шаге работы схемы высокий потенциал появляется на к -м выходе шифратора 16.. Этот сигнал подается по входу 26 к на вторые входы элементов И 19к, с, 19„

19!,„. Одновременно с 1 -го выхода де- 45 шифратора 5 иа вход 25;,„ поступает высокий потенциал. Этим сигналом устанавливается в единичное состояние триггер 18 <,,<. Это свидетельствует о том, что минимальный путь про- 50 ходит через (g,q +1)-ю вершину графа. Если например, иа -й и k -й входы шифратора 16 поступают одинаковые (минимальные). коды, то на

1-м и k -м .выходах шифратора !6 ноя- 55 вятся высокие потенциалы, которые подаются на входы 26j и 26 блока

3, после чего устанавливаются в единичное состояние триггеры 18 ;„! и 18„(,„1.

На следующем такте работы устройства устанавливается в единичное состояние триггер 14 . Высокий потенциал подается на вторые входы групп элементов И 10 и 1О 1, с второго выхода дешифратора 5 высокий потенциал подается на вторые входы элементов H 1344, 13>4, 1ЗЗ4 и на первые входы элементов 19,4 19 4, 19 4 блока 3 (фиг.2) . В результате на первую, вторую и третью группы входов шифратора 16 поступают следующие коды: код с выхода регистра

12 4, результат сложения кодов с регистров 9 н 12 4, результат сложения кодов с регистров 9у и 1214.

В зависимости от результата сравнения на шифраторе 16 устанавливается в единичное состояние триггер 18;4, (т=.1,2,3) блока 3 (фиг.2), а код минимального числа записан на регистр 94.

Далее работа устройства происходит аналогично рассмотренному. Например, в 1 -м такте- работы устройства произведено .суммирование содержимого регистров 12 (f+f)-го столбца матрицы 11 с содержимым регистров

91,...,9 1), содержимое регистра

12, ;,,) подается на вход шифратора !

6 чреез группу элементов ИЛИ 7 определен минимальный иэ- кодов и записан на регистр 9, а один из триггеров 181(„„), 18 <„ц ...,18+(,„) блока 3 (или несколько триггеров в случае, если на несколько входов шифратора 16 поступят одинаковые коды, что означает - через соответствующие вершины исследуемого графа проходят одинаковые по величине минимальные пути) устанавливается в единичное состояние.

Работа устройства продолжается до появления иа и -ом выходе дешифратора высокого потенциала, который поступает по входу 27 блока 3 (фиг.2) на вторые входы элементов

И 201„и 21»,.

Единичные выходы триггеров 18 соединены с первыми входами элементов И 20, а нулевые выходы — с первыми входами элементов И 21. Таким образом если триггер 18 установлен в единичное состояние, то соответствующие ему элемент И 20 открыт, а элемент И 21 закрыт, и на9 11 оборот. Сигнал опроса, поступаюший на вход 27, проходит через открытые элементы И 211,,,...,21,,, т.е. сначала спрашиваются триггеры A --ro столбца блока 3 до тех пор, пока не найден первый триггер 18,„, установленный в единичное состояние, у которого закрыт элемент И 21;„ и открыт элемент И 20;„. Высоким потенциалом с выхода элемента И 20„, через элемент ИЛИ 23 д установлен в единичное состояние и -й триггер регистра 24. Это означает, что и -я вершина моделируемого графа входит в кратчайший путь, и через элемент

ИЛИ 22; сигнал опроса поступает на опрос (-1)-ro столбца блока 3 (т.е. поступает на вторые входы элементов 20((,y<) и 21 („ „ . Если же в И -м столбце матрицы 3 ни

51979

10 один из триггеров 18 не находится в единичном состоянии, то высокий потенциал с выхода элемента И 211Ä, 11-1) К через элемент 22„„поступит на опрос (и-1) -го столбца (т. е. поступит на вторые входы элементов

20„(n- 1 и 21<(n „) .

Аналогичным образом опрос продолжается до тех пор, пока не найден

10 триггер 18 >, устан6вленный в единичное состояние. Это означает, что

1 из 1 -й вершины в первую вершину моделируемого графа имеется кратчайший путь. В этом случае установлены .

15 в единичное состояние -й и первый триггеры регистра 24, что сигнализирует об окончании моделирования.

Введение новых блоков и связей между ними позволяет упростить функ20 циональную схему устройства.

1I51979

1151979

Составитель А.Колчин

Редактор А.Шандор Техред T.Ôàíòà Корректор А.Обручар

Заказ 2325/38 Тираж 710 Подписное

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

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

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