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

 

Изобретение относится к вычислительной технике и может быть использовано для моделирования задач кратчайшем пути, задач оптимального управления и задач управления некоторыми технологическими процессами в различных отраслях промышленности. Цель изобретения - повышение точности моделирования. Для этого несколько устройств соединяются в моделирующую структуру согласно топологии графа, В памяти каждого устройства записана информация о весах всех предыдущих ветвей графа, смежных данной ветви. После запуска устройства, моделирующего начальную ветвь, все последующие устройства подсчитывают вес всех путей в данную ветвь из предыдущих, наименьший из путей и выдают код веса пути на входы всех последующих устройств. Таким образом, процесс последовательно распространяется от начальной к конечной ветви, при этом выделяется наикратчайший из возможных путей, 4 ил. (Л 00 4 00 00 4

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

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

РЕСПУБЛИК (51) 4 С 06 F 15/20

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

К А BTOPCKOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4019301/24-24 (22) 11.02.86 (46) 30. 10.87. Бюл. Р 40 (71) Институт проблем моделирования в энергетике АН УССР (72) В.В. Васильев и В.Л. Баранов (53) 681.333(088.8) (56) Авторское свидетельство СССР

М 805300, кл. С 06 F 15/20, 1979.

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

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

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

ÄÄSUÄÄ 1348847 А1 различных отраслях промьппленности.

Цель изобретения — повьппение точности моделирования. Для этого несколько устройств соединяются в моделирующую структуру согласно топологии графа.

В памяти каждого устройства записана информация о весах всех предыдущих ветвей графа, смежных данной ветви.

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

1348847

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

Целью изобретения является повышение точности моделирования.

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

Устройство содержит регистр 1 сдвига, сумматор 2, блок 3 управления, триггер 4, группу триггеров

5(1) — 5(Т), где Т вЂ” количество ветвей в графе, элементы И 6-8, три группы элементов И 9(1) — 9(Т), 10(1)-10(Т), 11(1) — 11(Т), элементы

ИЛИ 12-14, переключатели 15 и 16, информационные входы 17(1) — 17(Т) устройства, информационный выход 18, индикационные входы 19(1) — 19(Т) устройства, индикационные выходы

20(1) — 20(Т) устройства, регистр 21 сдвига, полусумматор 22, элемент

И 23, элемент ИЛИ 24, элемент 25 задержки.

Блок 3 управления содержит генератор 26 импульсов, распределители 27 и 28 импульсов, генератор 29 одиночных импульсов, переключатели 30-34, триггер 35, элементы И 36 и 37, элементы ИЛИ 38 и 39, элемент НЕ 40.

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

В качестве сумматора 2 могут быть применены последовательные двоичные сумматоры.

В качестве переключателей 30-34 могут применяться переключатели различных типов или групп электронных ключей, управляемые внешними сигналами.

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

Генератор 26 вырабатывает последовательность тактовых импульсов частоты f, из которых распределитель 27 формирует P последовательностей импульсов частоты f/Р, где P — количество разрядов регистров 1 и 21 сдвига, сдвинутых друг относительно друга на время 1/f. Из последовательности импульсов P — го выхода распределителя 27 распределитель 28 импульсов формирует Т последовательностей импульсов длительностью Р/f, действующих с частотой f/Ð Т и сдвинутых друг относительно друга на время Р/f

В режиме ввода весов моделей ветвей в регистры 1 и 21 переключателем

32 подключают выход генератора 29 одиночных импульсов к входу установки в единицу триггера 35. Переключателем 34 выбирают один из регистров (1 или 21) .

Регистры 1 и 21 сдвига содержат по Р Т разрядов каждый. В регистр 1 сдвига записывают P младших разрядов дополнительных двоичных кодов веса для Т ветвей, входящих в один узел.

В регистр 21 сдвига записывают P старших разрядов дополнительных двоичных кодов веса для Т ветвей, входящих в один узел. Следовательно, вес или длина ветви моделируемого графа представляется на 2Р двоичных разрядах. Запись в регистры 1 и 21 осуществляется следующим образом.

Переключателем 34 блока подключают вход выбора информационного направления регистра 1 сдвига к выходу элемента И 37. С помощью переключателей 30 и 31 блока 3 управления задают P младших разрядов дополнительного двоичного кода веса ветви и номер ветви соответственно.

Переключателем 30 в единичных разрядах дополнительного двоичного кода веса ветви подключают соответствующие выходы распределителя 27 к входам элемента ИЛИ 38, на выходе которого формируется последовательный дополнительный код Р младших разрядов веса ветви. Например, если дополнительный двоичный код Р младших разрядов 11...1011, то выходы всех разрядов, кроме третьего разряда, распределителя 27 импульсов подключаются переключателем 30 к входам элемента ИПИ 38. С помощью переключателя 31 задают номер ветви. Например, если выполняется ввод P младших

1348847 разрядов веса для седьмой ветви, то вьжод седьмого разряда распределителя 28 импульсов подключают к входу элемента ИЛИ 39, на вьжоде которого формируется импульсный сигнал длительностью Р/f, совпадающий по фазе с временем сдвига с выхода регистра 1 под действием тактовьж импульсов генератора 26 импульсов. P младших разрядов двоичного кода для седьмой модели ветви. Ввод последовательного дополнительного кода P младших разрядов веса ветви в регистр 1 сдвига осуществляется после подачи единичного сигнала с выхода элемента НЕ 40 через переключатель 33 на управляющий вход генератора 29 одиночных импульсов, который выделяет из последовательности импульсов с выхода элемента И 36, действующих с частотой

f/ТР, одиночный импульс, устанавливающий через переключатель 32 триггер 35 в единичное состояние на время TP/f. Триггер 35 сбрасывается в нулевое состояние следующим импульсом с выхода элемента И 36. Триггер

35 в единичном состоянии открывает сигналом прямого выхода элемент И 37, через который на регистр 1 сдвига поступает одиночный импульсный сигнал с выхода элемента ИЛИ 39, задающий номер модели ветви. Под действием тактовых импульсов генератора 26 импульсов последовательный дополнительный двоичный код младших разрядов веса ветви записывается с выхода элемента ИЛИ 38, начиная с младших разрядов, в регистр 1 сдвига, во время действия на выходе элемента

ИЛИ 39 импульса, задающего номер модели ветви.

Одиночный импульс генератора 29 через переключатель 32 устанавливает триггеры 4 и 5(1),...,5(Т) в нулевое состояние.

Аналогичным образом в регистр 1 сдвига записывают дополнительные двоичные коды P младших разрядов весов всех ветвей с первой по Т-ю. Затем переключателем 34 подключают регистр 21 сдвига к выходу элемента

И 37 блока 3 управления и аналогичным образом записывают P старших разрядов дополнительных кодов весов для всех Т ветвей. Особенность процесса записи кодов в регистр 21 сдвига заключается в том, что Р старших разрядов для некоторой M-й ветви (M=1, ...,Т) записываются в регистр 21 во время сдвига в регистре 1 P младших разрядов дополнительного кода веса

5 (+1)-й ветви. Это реализуется следующим образом. Переключателем 30 задают P старших разрядов дополнительного кода веса М-й ветви, а на переключателе 31 устанавливают номер (М+1)-й ветви. Если вводятся P старших разрядов дополнительного кода для последней Т вЂ” и ветви, то на переключателе

31 устанавливается номер первой ветви. !

5 Ввод последовательного дополнительного кода P старших разрядов веса M-й ветви осуществляется после поступления единичного сигнала с выхода элемента НЕ 40 через переключа20 тель 33 на вход генератора 29 импульсов, который выделяет из последовательности импульсов с выхода элемента И 36, действующих с частотой

f/ÒÐ, одиночный импульс, устанавли25 вающий через переключатель 32 триггер 35 в единичное состояние. Триггер 35 в единичном состоянии сигналом со своего прямого выхода открывает элемент И 37, через который на

gp вход регистра 21 сдвига с выхода элемента ИЛИ 39 поступает импульсный сигнал, задающий номер (М+1)-й ветви. Под действием тактовых импульсов генератора 26 последовательный дополнительный код P старших разрядов ве35 са M-й ветви записывается с выхода элемента ИПИ 38 в регистр 21 сдвига во время действия на выходе элемента

39 ИЛИ импульса, задающего номер

4р (М+1)-й ветви. Аналогичным образом в регистр 21 сдвига записывают дополнительные коды P старших разрядов весов для всех ветвей с первой по Т-ю.

После записи дополнительные коды

45 весов ветвей хранятся в регистрах 1 и 21 сдвига динамическим способом, т.е. путем циркуляции кодов соответственно через сумматор 2 и полусумматор 22, причем во время сдвига P

5р младших разрядов дополнительного кода M-й модели ветви с входа регистра 21 сдвига считываются P старших разрядов дополнительного кода (М-1)-й модели ветви. Например, если с выхо55 да регистра 1 сдвига считываются Р младших разрядов кода веса второй ветви, то с выхода регистра 21 сдвига — P старших разрядов кода первой ветви.

1348847

Изображенное на фиг. 1 устройство моделирует Т ветвей. С целью моделирования более сложных графов множества модулей устройства коммутируют между собой в соответствии с топологией решаемой задачи, формируя сложные графы, содержащие узлы, соединенные между собой ветвями. Например, выход 18 одного устройства подключают xq входам 17 других устройств, индикационные выходы 20 которых подключают к индикационным входам 19 данного устройства. Пример моделирующей структуры изображен на фиг.3 (на фиг.3а изображен моделируемый граф, а на фиг. Зб — моделирующая структура, содержащая три модуля).

В режиме моделирования переключателем 32 (фиг. 2) подключают выход генератора 29 одиночных импульсов к входу переключателя 16, с помощью которого задают начальный узел. Пуск устройства осуществляют переключателем 33, с помощью которого «а управляющий вход генератора 29 одиночных импульсов подают единичный сигнал выхода элемента НЕ 40. Одиночный импульс генератора 29 поступает через переключатель 16 и элемент ИЛИ 12 на вход установки в "1" триггера 4 устройства начального узла и устанавливает его в единичное состояние.

Единичный сигнал прямого выхода триггера 4 поступает на входы 17 других устройств. Предположим, например,. что на первый вход 17 первого устройства поступил единичный сигнал с прямого выхода триггера 4 предыдущего устройства. В этом случае через элемент И 9 данного устройства проходит последовательность импульсов первого разряда распределителя 28 импульсов.

Последовательность импульсов с выхода первого элемента И 9 поступает на выход элемента ИЛИ 14, выходной сиг— нал которого открывает элемент И 7 во время фазы сдвига дополнительного двоичного кода P младших разрядов веса первой ветви. Последовательность импульсов первого выхода распределителя 27 поступает через элемент И 7 на вход слагаемого сумматора 2, на вход второго слагаемого которого с выхода регистра 1 сдвигается дополнительный двоичный код P младших разрядов веса первой ветви. Сумматор 2 последовательно во времени, начиная с младших разрядов, выполняет сумми10

55 рование дополнительного двоичного кода Р младших разрядов веса первой ветви с последовательностью единиц с выхода элемента И 7. За время Т Р тактов дополнительный двоичный код P младших разрядов веса первой ветви увеличивается на единицу младшего разряда и результат с выхода суммы сумматора 2 вновь сдвигается под действием тактовых импульсов генератора 26 в регистр 1 сдвига. Если в процессе суммирования va выходе признака переноса сумматора 2 формируется единичный сигнал через элемент И 8, тактируемый последовательностью импульсов P-ro разряда распределителя 27, он поступает через элемент

24 И IH и элемент 25 задержки на вход слагаемого полусумматора 22 к моменту сдвига с выхода регистра 21 P старших разрядов дополнительного кода веса первой ветви. Полусумматор 22 суммирует единичный сигнал признака переноса из группы P младших разрядов текущего кода первой ветви с дополнительным кодом Р старших разрядов веса первой ветви. Если в процессе суммирования полусумматором 22 на его выходе признака переноса формируется единичный сигнал переноса иэ

К-го разряда (К=1,...,P), то этот сигнал через элемент ИЛИ 24 и элемент

25 задержки вновь поступает на вход слагаемого полусумматора 22 во время сдвига с выхода регистра 21 (К+1)-ro разряда дополнительного кода группы старших разрядов веса первой ветви.

Если в процессе суммирования полусумматором 22 формируется сигнал признака переноса из Р-го разряда группы старших разрядов текущего кода веса первой ветви, то он откроет элемент

23 И, тактируемый последовательностью импульсов P-го разряда распределителя 27 и через элемент HJIH 1? установит триггер 4 в единичное состояние, а через элемент 11(1) И, тактиpyemiA последовательностью импуль— сов второго разряда распределителя 28 импульсов, установит триггер 5(1) в. единичное состояние. Триггер 4 в единичном состоянии блокирует сигналом со своего инверсного выхода элемент

И 7, и процесс суммирования прекращается.

К том случае, если на все информа ционные входы 17 одновременно поступают единичные сигналы через элемен1348847 ты И 9 и ИЛИ 14, последовательности импульсов с выходов распределителя

28 импульсов открывают элемент И 7.

Последовательность импульсов первого выхода распределителя 27 импульсов поступает через элемент И 7 на вход сумматора 2 во время сдвига с выхода регистра 1 P младших разрядов дополнительных кодов весов всех ветвей.

Каждые Т P тактов дополнительные коды младших разрядов весов Т ветвей последовательно во времени, начиная с младших разрядов, увеличиваются на единицу младшего разряда и с выхода суммы сумматора 2 вновь записываются в регистр 1 сдвига.

Если в процессе суммирования на выходе признака переноса сумматора 2 появится единичный сигнал переноса из P-го разряда группы младших разрядов текущего кода М-й ветви, то этот сигнал через элементы И 8, ИЛИ 24 и элемент 25 задержки будет

20 поступать на вход слагаемого полусум- 25 матора 22 во время сдвига с выхода регистра 21 первого разряда группы старших разрядов текущего кода M-й ветви. За время Р тактов полусумматор 22 прибавит сигнал переноса из группы младших разрядов к текущему коду группы старших разрядов, и результат с выхода суммы полусумматора

22 сдвинется в регистр 21 сдвига.

Последовательность импульсов P-го разряда распределителя 27, поступая на вход сброса сумматора 2, блокирует цепь переноса, запрещая передачу

35 сигнала переноса в код следующеи ветви. Спустя время Вн. Т P тактов, где

Вм — наименьший вес из всех ветвей графа, принадлежащий M-й ветви, на выходе переноса полусумматора 22 во время фазы сдвига с выхода регистра

21 текущего кода группы старших разрядов M-й ветви сформируется сигнал переноса из P-ro разряда, который, 40

45 проходя через элементы 23 И и 12 ИЛИ, установит триггер 4 в единичное состояние, а через элементы И 23 и 11(М),50 тактируемый последовательностью импульсов (М+1)-го разряда распределителя 28 импульсов, устанавливает триггер 5(M) в единичное состояние.

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

Триггер 4 в единичном состоянии возбуждает по выходу 18 вычислительный процесс в следующих устройствах моделирующей структуры и, кроме того, блокирует сигналом со своего инверсного выхода элемент И 7, после чего процесс вычислений в рассматриваемом устройстве моделирующей структуры прекращается.

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

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

Единичный сигнал с прямого выхода триггера 4 проходит через элементы

ИЛИ 13, И 6 на первые входы элементов И 10. Из всей группы элементов

И 10 откроется элемент И 10 той ветви, для которой триггер 5 находится в единичном состоянии. Единичный сигнал триггера 5 ветви, принадлежашей кратчайшему пути, проходит через соответствующий элемент И 10 на индикационный выход 20 ветви и далее поступает на индикационные входы 19 других устройств модулей моделирующей структуры, возбуждая процесс распространения единичного сигнала индикации от модели конечного узла к модели начального узла вдоль кратчайшего пути.

Формула из о бре тения

Устройство для моделирования ветви графа, содержащее регистр сдвига, последовательный сумматор, два триггера, пять элементов И, пять элементов ИЛИ, элемент НЕ, группу триггеров, три группы элементов И, генератор импульсов, генератор одиночных импульсов, два распределителя импульсов и пять переключателей, причем выход генератора импульсов подключен к входу синхронизации регистра сдвига и тактовому входу первого распределителя импульсов, К-й выход которого (К=1,...,P, где Р— количество разрядов представления массы ветви) подключен к К-му информационному входу первого переключателя, К вЂ” и выход которого подключен к К-му входу первого элемента ИЛИ, выход которого под1348847

10 ключен к первому информационному входу первого регистра сдвига, выход которого подключен к входу первого слагаемого последовательного сумма5 тора, выход суммы которого подключен к второму информационному входу первого регистра сдвига, выход P-го разряда первого распределителя импульсов подключен к первому входу первого элемента И и к тактовому входу второго распределителя импульсов, M-й выход которого (М=1, ..., Т, где Т вЂ” количество ветвей в графе) подключен к первому входу М-го элемента И первой группы и к M-му информационному входу второго переключателя, М-й выход которого подключен к М-му входу второго элемента ИЛИ, выход которого подключен к первому 2р входу второго элемента И, Т-й выход распределителя импульсов подключен к второму входу первого элемента И, выход которого подключен к тактовому входу генератора одиночных импульсов 25 и к входу установки в "0 первого триггера, вход управления записью массы устройства подключен к входу опроса генератора одиночных импульсов, выход которого подключен к информационному входу второго переключателя, первый выход которого подключен к входу установки в "0 второго триггера, к входам установки в "0" всех триггеров группы и к входу уста1I I1 3

35 новки в 1 первого триггера, выход которого подключен к второму входу второго элемента И, второй выход второго переключателя подключен к входу третьего переключателя, выход которого подключен к первому входу третьего элемента ИЛИ, выход которого подключен к входу установки в "1" второго триггера, прямой выход которого подключен к первому входу третьего элемента И, к информационному входу четвертого переключателя и является информационным выходом устройства, выход четвертого переключателя подключен к (Т+1)-му входу четверто50 го элемента ИЛИ, M-й вход которого является M-м индикационным входом устройства, а выход подключен к второму входу третьего элемента И, выход которого подключен к первым входам всех элементов И второй группы, M-й информационный вход устройства подключен к второму входу М-го элемента И первой группы, выход которого подключен к M-му входу пятого элемента ИЛИ, выход которого подключен к входу второго слагаемого последовательного сумматора, выход признака переноса которого подключен к первому входу пятого элемента И, P-й выход первого распределителя импульсов подключен к второму входу пятого элемента И и к тактовому входу сумматора, первый выход первого распределителя импульсов подключен к второму входу четвертого элемента И, инверсный выход второго триггера подключен к третьему входу четвертого элемента

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

"1" M-го триггера групггы, выход которого подключен к второму входу М-го элемента И второй группы, выход котоporn является M-м индикационным выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения точности моделирования, в него введены второй регистр сдвига, полусумматор, шестой элемент И, шестой элемент ИЛИ, элемент задержки и шестой переключатель, причем выход первого элемента ИЛИ подключен к первому информационному входу второго регистра сдвига, выход второго элемента И подключен к входу шестого переключатели, первыи выход которого подключен к входу выбора информационного выхода первого регистра сдвига, а второй выход подключен к входу выбора информационного входа второго регистра сдвига, выход которого подключен к входу первого слагаемого полусумматора, выход суммы которого подключен к второму информационному входу второго регистра сдвига, P-й выход первого распределителя импульсов подключен к входу сброса последовательного сумматора и к первому вхОду шестого элемента И, выход пятого элемента И подключен к первому входу шестого элемента ИЛИ, выход которого подключен к входу элемента задержки, выход которого подключен к входу второго слагаемого полусумматора, выход признака переноса которого подключен к второму входу шестого элемента HJIH и к второму входу шестого элемента И, выход которого подключен к первым входам всех элементов И третьей группы, М-й выход второго распределителя импульсов подключен к вторым входам всех элементов И третьей группы.

1348847

1348847

О Ьпавшуе ртряды пыбсй Hem//u — — Рггостр21 сд&е

NnaO ue Pu pzd

neDdau Рюютли

Составитель А. Мишин

Редактор E. Копча Техред А.Кравчук

Корректор M.. Пожо

Заказ 4803/49 Тираж 670 Подписное

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

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

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