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

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

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

На фиг. 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 могут применяться переключатели различных типов или групп электронных ключей, управляемые внешними сигналами .

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

0

0

5

0

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

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

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

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

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

5

0

5

0

5

разрядов веса для седьмой ветви, то выход седьмого разряда распределителя 28 импульсов подключают к входу элемента ИЛИ 39, на выходе которого формируется импульсный сигнал длительностью P/f, совпадающий по фазе с временем сдвига с выхода регистра 1 под действием тактовых импульсов ге25

нератора 26 импульсов. Р младших раз- ю ветви. Если вводятся Р старших разрядов дополнительного кода для последней Т-й ветви, то на переключателе 31 устанавливается номер первой ветви.

Ввод последовательного дополнительного .кода Р старших разрядов веса М-й ветви осуществляется после поступления единичного сигнала с выхода элемента НЕ 40 ч.ерез переключа- с выхода эле- 20 тель 33 на вход генератора 29 импульсов, который выделяет из последовательности импульсов с выхода элемента И 36, действующих с частотой f/TP, одиночный импульс, устанавливающий через переключатель 32 триггер 35 в единичное состояние. Триггер 35 в единичном состоянии сигналом со своего прямого выхода открьша- ет элемент И 37, через который на

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

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

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

рядов двоичного кода для седьмой модели ветви. Ввод последовательного дополнительного кода Р младших разрядов веса ветви в регистр 1 сдвига осуществляется после подачи единично- is го сигнала с выхода элемента НЕ 40 через переключатель 33 на управляющий вход генератора 29 одиночных импульсов, который выделяет из последовательности импульсов мента И 36, действующих с частотой f/TP, одиночный импульс, устанавливающий через переключатель 32 триггер 35 в единичное состояние на время TP/f. Триггер 35 сбрасывается в нулевое состояние следующим импульсом с выхода элемента И 36. Триггер 35 в единичном состоянии открывает сигналом прямого выхода элемент И 37, через который на регистр 1 сдвига поступает одиночный импульсный сигнал с выхода элемента ИЛИ 39, задающий номер модели ветви. Под действием тактовых импульсов генератора 26 импульсов последовательный дополнительный двоичный код младших разрядов веса ветви записывается с выхода элемента ИЛИ 38, начиная с младших разрядов, в регистр 1 сдвига, во время действия на выходе элемента ИЛИ 39 импульса, задающего номер модели ветви.

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

Аналогичным образом в регистр сдвига записьшают дополнительные двоичные коды Р младших разрядов сов всех ветвей с первой по Т-ю. Затем переключателем 34 подключают регистр 21 сдвига к выходу элемента И 37 блока 3 управления и аналогичным образом записывают Р старших разрядов дополнительных кодов весов для всех Т ветвей. Особенность процесса записи кодов в регистр 21 сдвига заключается в том, что Р старших разрядов для некоторой М-й ветви (,

35

40

1

ве55

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

25

0

is

30

s

35

30

is

40

Заречраздляса заз1,

ве5Q

55

5

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

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

0

5

5

0

5

0

5

0

5

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

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

25задержки вновь поступает на вход слагаемого полусумматора 22 во время сдвига с выхода регистра 21 (К-ь1)-го разряда дополнительного кода группы cTapunix разрядов веса первой ветви. Если в процессе суммирования полусумматором 22 формируется сигнал признака переноса из Р-го разряда группы старших разрядов текущего кода веса первой ветви, то он откроет элемент 23 И, тактируемый последовательностью импульсов Р-ГО разряда распределителя 27 и через элемент ИЛИ 12 установит триггер 4 в единичное состояние, а через элемент 11(1) И, тактируемый последовательностью импульсов второго разряда распределителя 28 импульсов, установит триггер 5(1) в. единичное состояние. Триггер 4 в единичном состоянии блокирует сигналом со своего инверсного выхода элемент

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

В том случае, если на все информационные входы 17 одновременно поступают единичные сигналы через элемен

ты И 9 и ИЛИ 14, последовательности импульсов с выходов распределителя 28 импульсов открывают элемент И 7. Последовательность импульсов первого выхода распределителя 27 импульсов поступает через элемент И 7 на вход сумматора 2 во время сдвига с выхода регистра 1 Р младших разрядов дополнительных кодов весов всех ветвей. Каждые Т-Р тактов дополнительные коды младших разрядов весов Т ветвей последовательно во времени, начиная с младших разрядов, увеличиваются на единицу младшего разряда и с выхода суммы сумматора 2 вновь записываются в регистр 1 сдвига.

Если в процессе суммирования на выходе признака переноса сумматора 2 появится единичный сигнал переноса из Р-го разряда группы младших р аз- рядов текущего кода М-й ветви, то этот сигнал через элементы И В, ИЛИ 24 и элемент 25 задержки будет поступать на вход слагаемого полусум матора 22 во время сдвига с выхода регистра 21 первого разряда группы старших разрядов текущего кода М-й ветви. За время Р тактов полусумматор 22 прибавит сигнал переноса из группы младших разрядов к текущему коду группы старших разрядов, и результат с выхода суммы полусумматора 22 сдвинется в регистр 21 сдвига. Последовательность импульсов Р-го разряда распределителя 27, поступая на вход сброса сумматора 2, блокирует цепь переноса, запрещая передачу сигнала переноса в код следующей ветви. Спустя время Вм-Т Р тактов, где BM - наименьший вес из всех ветвей графа, принадлежащий М-й ветви, на выходе переноса полусумматора 22 во время фазы сдвига с выхода регистра 21 текущего кода группы старших разрядов М-й ветви сформируется сигнал переноса из Р-го разряда, который, проходя через элементы 23 И и 12 ИЛИ установит триггер 4 в единичное состояние, а через элементы И 23 и 11(М тактируемый последовательностью импульсов (М+1)-го разряда распределителя 28 импульсов, устанавливает тригер 5(М) в единичное состояние.

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

Триггер 4 в единичном состоянии возбуждает по выходу 18 вычислитель

0

5

0

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

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

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

35

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

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

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

го подключен к М-му входу пятого эле

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

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

2Q элемента И второй группы, выход кото- рога является М-м индикационным выходом устройства, отличающееся тем, что, с целью повышения точности моделирования, в него введе25 ны второй регистр сдвига, полусумматор, шестой элемент И, шестой элемент Ш1И, элемент задержки и шестой переключатель, причем выход первого элемента ИЛИ подключен к первому ин30 формационному входу второго регистра сдвига, выход второго элемента И подключен к входу шестого переключателя, первый выход которого подключен к входу выбора информационного выхода первого регистра сдвига, а второй выход подключен к входу выбора информационного входа второго регистра сдвига, выход которого подключен к входу первого слагаемого полусуммадц тора, выход суммы которого подключен к второму информационному входу второго регистра сдвига, Р-й выход первого распределителя импульсов подключен к входу сброса последовательного

.(- сумматора и к первому входу шестого элемента И, выход пятого элемента И подключен к первому входу шестого элемента ИЛИ, выход которого подключен к входу элемента задержки, вы35

50

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

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

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

(Pus. 2

т

20(Т)

т

WZg

Ячейка

А//

Ш

20(1)

///fj

т

Яиейка N2

т

18

т)

Ш

Ш

а

Ячейка

A J

5 Старшие разряды первой детSu

Составитель А. Мишин Редактор Е. Копча Техред А.Кравчук Корректор М.. Пожо

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

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

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

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

Регистргг -

Младшие разряды перйой ветви