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

 

Изобретение относится к области вычислительной техники, в частности к устройствам для обработки информации специального назначения. Цель изобретения состоит в расширении функциональных возможностей устройства за счет моделирования как входящих, так и исходящих ветвей узла графа. Устройство для моделирования графов содержит два регистра .. сдвига, сумматор, два триггера, две группы триггеров, два коммутатора, шесть элементов И, пять групп элементов И, три элемента ИЛИ, группу элементов ИЛИ, ключ, группу элементов индикации и блок управления. Устройство позволяет моделировать., как группы из m ветвей графа, входящих в узел, так и группы из m ветвей , исходящих из этого узла и входящих в группу из m узлов. 3 ип. (Л :о ел со ;о 00

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

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

РЕСПУБЛИК

„.,SU ÈÄÄßßÄ А 1 (дц.4 G 06 F 15/20

У 4,./p

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ и 1 ,l

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ (21 ) 3986466/24-24 (22) 02.12,85 (46) 07.06.87. Бюл. N- 21 (71) Институт проблем моделирования в энергетике АН УССР (72) В.В.Васильев и В.Л.Баранов (53) 681.3 (088.8) (56) Авторское свидетельство СССР

Ф 805300, кл. G 06 J 7/00, 1978.

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

И 1246110, кл. G 06 F 15/20, 1984. (54) УСТРО 1СТВО ДЛЯ МОДЕЛИРОВАНИЯ

ГРАФОВ (57) Изобретение относится к области вычислительной техники, в частности к устройствам для обработки информации специального назначения.

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

Устройство позволяет моделировать., как группы из ш ветвей графа, входя. щих в узел, так и группы из m ветвей, исходящих из этого узла и входя

<0 щих в группу из ш узлов. 3 ип.! 13!

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

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

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

Устройство для моделирования графов содержит регистры 1 и 2 сдвига, сумматор 3, блок 4 управления, триг геры 5 и 6, группы триггеров 7 и 8, коммутаторы 9 и 10, элементы И ll—

16, группы элементов И 17-21, элементы ИЛИ 22-24, группу элементов

ИЛИ 25, ключ 26, группу элементов

27 индикации, информационные входы

28, информационные выходы 29, индикационные входы 30 и индикационные выходы 31. Блок 4 имеет входы и выходы 32-40.

Блок 4 управления (фиг ° 2) содержит генератор 41 импульсов, распределители 42 и 43 импульсов, генератор

44 одиночных импульсов, коммутаторы

45-49, триггер 50, элементы И 51 и 52, элементы ИЛИ 53 и 54 и элемент

НЕ 55.

Устройство для моделирования графов работает следующим образом.

Генератор 41 вырабатывает последовательность тактовых импульсов частоты f, на которой распределитель

43 вырабатывает п последовательностей импульсов частоты f/n (где и— количество разрядов представления весов моделей ветвей), сдвинутых друг относительно друга на время !

/f.

Из последовательности импульсов

n-ro разряда распределителя 43 импульсов распределитель 42 вырабатыва5993

5 !

О !

40 ет m последовательностей импульсов длительностью п/f действующих с частотой f/mn и сдвинутых друг относительно друга на время n/f.

В режиме ввода весов моделей ветвей в регистры 1 и 2 сдвига коммутатором 47 подключают выход генератора 44 одиночных импульсов к единичному входу триггера 50. Коммутатором 49 выбирают один из регистров 1 или 2 путем подключения управлякицего входа соответствующего регистра

1 и 2 к выходу элементы И 52. С помощью коммутаторов 45 и 46 задают до. полнительный двоичный код веса модели ветви и номер модели ветви соответственно. Коммутатор 45 подключают в единичных разрядах дополнительного кода веса модели ветви соответствующие выходи распределителя 43 импульсов к входам элемента ИЛИ 54, на выходе которого формируется последовательный дополнительный код веса модели ветви. Например, если вес модели ветви равен пяти (дополнительный двоичный код 11...1011), то выходы всех разрядов, кроме третьего разряда, распределителя 43 импульсов подключается коммутатором 45 к входам элемента ИЛИ 54.

С помощью коммутатора 46 задают номер модели ветви. Например, если выполняется ввод веса в седьмую модель ветви, то выход седьмого разряда распределителя 42 подключают к входу элемента ИЛИ 53, на выходе которого формируется импульсный сигнал длительностью n/f, совпадающий по фазе с временем сдвига с выходов регистров 1 и 2 под действием такто- вых импульсов генератора 42 п-разрядного двоичного кода для седьмой модели ветви.

В регистры 1 и 2 сдвига, по m.n разрядов каждый, записываются соответственно веса моделей ветвей, входящих в узеп и исходящих из узла.

Если выполняют запись весов моделей, ветвей, входящих в узел, то коммутатором 49 подключают выход элемента И 52 к управляющему входу регистра сдвига. В процессе записи весов моделей ветвей, исходящих из узла, коммутатором

49 подключают управляющий вход регистра 2 сдвига к выходу элемента И 52, Ввод последовательного двоичного кода веса модели ветви в регистl 3! 5993 4 да регистра сдвига через коммутатор 9 и сумматор 3 на информационный .вход регистра 1 сдвига, а также с выхода регистра 2 сдвига на его информационный вход через коммутатор 10.

Устройство моделирует m моделей ветвей графа, входящих в модель узла, из которого исходит m моделей ветвей графа, каждая из которых оканчивается моделью узла (фиг.З . Всего устройство моделирует 2 m ветвей графа и m + 1 узел и представляет собой один модуль моделирующей структуPbj

С целью моделирования более сложных графов множество модулей моделирующих структур коммутируют между собой .в соответствии с топологией решаемой задачи, формируя сложные структуры, моделирующие графы. Например, информационные выходы 29 моделей узлов одного модуля подключают к информационным входам 28 моделей ветвей других модулей, индикационные выходы 31 моделей ветвей которых подключают к индикационным входам 30 данного модуля. Неиспользованные информационные входы 28 и индикационные входы 30 соединяются с шиной логического "0".

Пример моделирующей структуры, содержащей три модуля, изображен на фиг.3. На фиг.За изображен моделирующий граф (где Н вЂ” начальный узел гра-. фа; К вЂ” конечный узел графа), на фиг.Зб — моделирующая структура, содержащая три модуля.

Блок 4 управления для всех модулей моделирующей структуры является общим.

В режиме моделирования графов коммутатором 47 подключают выход генератора 44 одиночных импульсов к входу ключа 26, с помощью которого задают начальный узел графа. Конечный узел графа задается путем соединения одного из информационных выходов 29 устройства с соответствующим индикационным входом 30. Например, на фиг.1 изображена пунктиром связь информационного выхода 29{1),подключенного к прямому выходу триггера 8(1),моделирующего конечный узел графа, с индикационным входом 30(1.!) ры 1 или 2 сдвига осуществляется после подачи единичного сигнала с выхода элемента НЕ 55 через коммута— тор 48 на управляющий вход генератора 44 одиночных импульсов, который выделяет из последовательности импульсов элемента И 51, действующих с частотой f/m п, одиночный импульс, устанавливающий через коммутатор 47 триггер 50 в единичное состояние íà 10 время m п/f. Триггер 50 сбрасывается в нулевое состояние следующим импульсом последовательности элемента И 51. Триггер 50 в единичном состоянии открывает сигналом прямого вы- 15 хода элемент И 52. Импульсный сигнал последовательности элемента ИЛИ 53, задающий номер модели ветви, выделяется на выходе элемента И 52 в виде одиночного импульса и через коммута- 20 тор 49 поступает на управляющий вход, например, регистра 1 сдвига. Под действием тактовых импульсов генератора

41 последовательный дополнительный двоичный код веса модели ветви запи- 25 сывается с выхода элемента ИЛИ 54 последовательно во времени, начиная с младшего разряда, в регистр 1

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

Импульс с выхода генератора 44 одиночных импульсов через коммутатор 47 устанавливает триггеры 5 — 8 в нулевое состояние. 35

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

Затем подключают коммутатором 49 40 выход элемента И 52 к управляющему входу регистра 2 сдвига и записывают в него аналогичным образом дополнительные двоичные коды весов моделей ветвей, исходящих из узла. . 45

Триггер 6 в нулевом состоянии подключает коммутатором 9 выход регистра 1 сдвига к второму информационному входу сумматора 3, а с помощью коммутатора 10 соединяет выход 50 регистра 2 сдвига с его информационным входом.

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

5 131

Пуск устройства осуществляют коммутатором 48, с помощью которого на управляющий вход генератора 44 одиночных импульсов подают единичный сигнал с выхода элемента НЕ 46. Одиночный импульс генератора 44 одиночных импульсов поступает через замкйутый ключ 26 и элемент ИЛИ 23 на. единичный вход триггера 5 модели начального узла и устанавливает его в единичное состояние. Единичный сигнал прямого выхода триггера 5 открывает элемент И 14, через который проходит импульс с выхода элемента И 51, и устанавливает триггер 6 в единичное состояние. Единичный сигнал прямого выхода триггера 6 открывает элемент И 15 и через элемент ИЛИ 22 элемент И ll, а также переключает коммутаторы 9 и 10 в состояние, при котором выход регистра 2 сдвига под-. ключается через коммутатор 9 к второму информационному входу сумматора

3, а информационный вход регистра 2 сдвига через коммутатор 10 подключается к выходу суммы сумматора 3. Таким образом, в цепь циркуляции кодов регистра 2 сдвига подключается сум" матор 3, на первый информационный вход которого начинает поступать последовательность импульсов с выхода первого разряда распределителя 43.

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

Сумматор 3 выполняет последова.тельно во времени, начиная с младших разрядов, суммирование дополнительных кодов весов моделей ветвей с последовательностью импульсов на выходе элемента И ll. За время mn тактов дополнительные, двоичные коды весов моделей ветвей увеличиваются на единицу младшего разряда, а результат с выхода суммы сумматора 3 .сдвигается под действием тактовых импульсов генератора 41 в регистр 2 сдвига.

Спустя время P; m n тактов, где

P — вес, i-й модели ветви, имеющей наименьший вес, на выходе переноса сумматора 3 формируется сигнал переноса из и-ro разряда текущего двоич" ного кода i-й модели ветви, исхоцящей из начального узла. Последова5993

Допустим, что согласно топологии моделируемого графа информационный = .выход 29 (i) данного моделирующего модуля соединен с информационным вхо30 раМ 28 (1) следующего моделирующего модуля, в котором все триггеры 5 — 7 находятся в нулевом состоянии.

Предположим также, что на все информационные входы 28 следующего

35 моделирующего модуля единичные сигналы с информационных выходов 29 других моделирующих модулей поступают одновременно. В этом случае че- -: рез элементы И 17 и элемент ИЛИ 22 последовательно во времени поступают последовательности импульсов с выходов всех разрядов распределителя

42, кокоторые открывают элемент И 11.

Последовательность импульсов первого разряда распределителя 43 поступает через элемент И ll на первый ин " формационный вход сумматора 3, на втовторой информационный вход которого под действием тактовых импульсов ге5О нератора 41 с выхода регистра 1 сдвига через коммутатор 9 сдвигаются последовательно во времени, начиная с младших разрядов, дополнительные двоичные коды весов всех моделей вет.

l5

25 тельность импульсов и-го разряда распределителя 43, поступая на вход сброса сумматора 3, блокирует цепь переноса, запрещая передачу сигнала переноса в следующий i+1-й двоичный код.. веса i+1-й модели ветви.

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

43, поступает на вход элемента И 15, открытого единичным сигналом прямого выхода триггера 6. Импульс с выхода элемента И 15 поступает на входы элементов И 20, из которых открыт только элемент И 20(i),находящийся под действием импульсного сигнала

i-го разряда распределителя 42. Импульсный сигнал элемента И 15 через элемент И 20 (i) устанавливает в единичное состояние триггер 8 (i), единичный сигнал прямого выхода которого поступает на информационный выход 29 (i) устройства. вей, входящих в узел. Каждые шп тактов дополнительные коды весов моделей ветвей последовательно во времени увеличиваются на единицу младшего разряда и с выхода суммы суммато1315993 8

55 ра 3 вновь записывается в регистр сдвига. Спустя время P„ mn тактов где P, — наименьший вес из всех моделей ветвей, принадлежащий, например, К-й модели ветви) из и-го разряда текущего дополнительного двоичного кода К-й модели ветви на выходе переноса сумматора 3 формируется сигнал переноса, который через элементы И 12, ИЛИ 23 устанавливает триггер 5 в единичное состояйие, а также через элементы И 12 и

16 и элемент И 19 (К), открытый импульсом К-го разряда распределителя

42, устанавливает триггер 7 (К) в единичное состояние. Триггер 7(К) запоминает номер модели ветви, принадлежащий дереву кратчайших путей (в рассматриваемом случае К-й модели ветви, входящей в узел).

Триггер 5 в единичном состоянии открывает элемент И 14, через который импульс с выхода элемента И 51 устанавливает триггер 6 в единичное состояние . Триггер 6 в единичном

1состоянии блокирует элемент И 16, открывает элемент И 15 и через элемент ИЛИ 22 элемент И 11, а также с помощью коммутатора 9 подключает выход регистра 2 сдвига к второму информационному входу сумматора 3,выход суммы которого через коммута- тор 10 соединяется с информационным входом регистра 2 сдвига. Сумматор 3 выполняет последовательно во

1 времени, начиная с младших разрядов, суммирование дополнительных двоичных кодов весов моделей ветвей,сдвигаемых с выхода регистра 2 сдвига с последовательностью единиц младшего разряда, представленных последовательностью импульсов на выходе элемента И 11. Спустя время P mn так0 тов (где Р— вес 1 -й модели ветви, имеющей найменьший вес} на выходе пе. реноса сумматора 3 формируется сигнал переноса из n-ro разряда текущего двоичного кода 1-й модели ветви, исходящей из узла данного модели. рующего модуля. Сигнал переноса из и-ro разряда через элементы И 12, 15 и 20 (1) устанавливает триггер 8(1) в единичное состояние. Единичный сигнал прямого выхода триггера 8(1) поступает на информационный выход

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

Вычислительный процесс распространяется от одного моделирующего модуля к другому согласно топологии графа до тех пор, пока не достигнет модели конечного узла. В этом случае один из триггеров 8 устанавливается в единичное состояние и единичный сигнал era прямого выхода (связь показана пунктиром) через соответствующий элемент ИЛИ 25 открывает элемент И 21, единичный сигнал с выхода которого с помощью элемента

27 индикации индуцирует модель ветви, принадлежащей кратчайшему пути, и поступает далее 1ерез элементы

ИЛИ 24, И 13 на входы элементов

И 18. Из всех элементов И 18 открывается тот элемент, который управляется одним иэ триггеров 7.

Сигнал, действующий на соответствующем выходе 31 устройства, можно использовать для индикации (с помощью элемента индикации) модели ветви, входящей в узел и принадлежащей .кратчайшему пути. Далее еди1 ничный сигнал с выхода элемента И 18 распространяется вдоль кратчайшего пути от конечного узла к начальному, что позволяет выделить и индицировать с помощью элементов индикации кратчайший путь на моделируемом графе между начальным и конечными узлами. формула изобретения

Устройство для моделирования rpa" фов, содержащее первый регистр сдвига, сумматор, первый триггер, первую группу триггеров и три группы элементов И, по ш элементов в каждой, где m — колнчество моделируемых ветвей, входящих в узел, три элемента

И, три элемента ИЛИ, ключ и блок управления, содержащий генератор импульсов, два распределителя импульсов, генератор одиночных импульсов, четыре коммутатора, триггер, два элемента И, два элемента ИЛИ и элемент НЕ, причем выход генератора им" пульсов блока управления соединен с входом первого распределителя импульсов, выходы разрядов которого с первого по п-й, где и — количество разрядов представления весов моделей ветвей, соединены с входами

1315993 первого коммутатора блока управления выходы первого коммутатора блока управления соединены с входами первого элемента ИЛИ блока управления, выход n-ro разряда первого распределителя импульсов соединен с входом второго распределителя импульсов, выходы разрядов которого с первого по

m-й соединены с входами второго коммутатора блока управления, выходы ко- Ю торого соединены с входами второго элемента ИЛИ блока управления, тактовый вход генератора одиночных импульсов соединен с выходом первого элемента И блока управления, первый 15 и второй входы которого соединены со1 ответственно с выходом n-ro раз ряда первого распределителя импульсов и с выходом m-ro разряда второго распределителя импульсов, выход гене- 20 ратора одиночных импульсов соединен с информационным входом третьего коммутатора блока управления, первый выход которого соединен с единичным входом триггера блока управления, 25 прямой выход которого соединен с первым входом второго элемента И блока управления, выходы первого элемента И и второго элемента ИЛИ блока управления соединены, соответственно с нулевым входом триггера и вторым входом второго элемента И блока управления, вход запуска генератора одиночных импульсов соединен с,выходом четвертого коммутатора блока 35 управления, вход которого соединен с выходом элемента НЕ, вход которого соединен с нулевой шиной устройства, выход генератора импульсов блока управления соединен с входом син1 хронизации первого регистра сдвига, вход ввода данных которого соединен с выходом первого элемента ИЛИ бло-ка управления, информационные входы моцелей ветвей с первого no m-й соединены соответственно с первыми входами элементов И, первой группы, вторые входы которых соединены соответI ственно с выходами с первого по m-й 5g разрядов второго распределителя импульсов блока управления, выходы первой группы элементов И соединены соответственно с входами первого элемента ИЛИ, выход которого соединен с первым входом первого элемента И, первый информационный вход сумматора соединен с выходом первого элемента

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

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

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

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

10 соответственно с первого по ш-й разрядами второго распределителя импуль.

I сов блока управления, выходы элементов И четвертой группы соединены соответственно с единичными входа15 ми триггеров второй группы, прямые выходы которых являются информацион« ными выходами устрОЙства и соединены соответственно с первыми входами элементов И пятой группы, вторые

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

30,коммутатора блока управления. з з (//

131 5993

ФИ2. 7

1315993

Составитель M.Kóäpÿøîâ

Редактор О.Головач ТехредН.Глущенко Корректор Г.Решетник

Заказ 2365/52 Тираж 672 Подписное

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

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

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