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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК ЯО 1348847 4 С 06 Р 15/20 ЕНИЯ ИСАНИЕ ИЗОБРЕ ТОРСКОМУ СВИДЕТЕЛЬСТВУ ования ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(71) Институт проблем моделир в энергетике АН УССР(56) Авторское свидетельство СССР М 805300, кл. С 06 Р 15/20, 1979.Авторское свидетельство СССР У 1246110, кл. С 06 Р 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ВЕТВИ ГРАФА(57) Изобретение относится к вычис лительной технике и может быть использовано для моделирования задач кратчайшем пути, задач оптимальног управления и задач управления неко рыми технологическими процессами в различных отраслях промышленности.Цель изобретения - повышение точностимоделирования, Для этого несколькоустройств соединяются в моделирующуюструктуру согласно топологии графа.В памяти каждого устройства записана информация о весах всех предыдущихветвей графа, смежных данной ветви.После запуска устройства, моделирующего начальную ветвь, все последующиеустройства подсчитывают вес всех путей в данную ветвь из предыдущих,выбирают наименьший из путей и вьщают код веса пути на входы всех последующих устройств. Таким образом,процесс последовательно распространяется от начальной к конечной ветви,при этом вьщеляется наикратчайший иэвозможных путей. 4 ил.45 50 55 Изобретение относится к вычислительной технике и может быть использовано как специализированное вычислительное устройство для моделирования задач о кратчайшем пути, задачоптимального управления и задач управления некоторыми технологическимипроцессами в различных отраслях промьппленности.Целью изобретения является повышение точности моделирования.На фиг. 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 могут применяться переключатели раз личных типов или групп электронныхключей, управляемые внешними сигналами.Устройство работает следующимобразом,5 10 15 20 25 30 35 40 Генератор 26 вырабатывает последовательность тактовых импульсов частоты Г, из которых распределитель 27 формирует Р последовательностей импульсов частоты 1/Р, где Р - количество разрядов регистров 1 и 21 сдвига, сдвинутых друг относительно друга на время 1/Г, Из последовательности импульсов Р-го выхода распределителя 27 распределитель 28 импульсов формирует Т последовательностей импульсов длительностью Р/Г, действующих с частотой Г/Р Т и сдвинутых друг относительно друга на время Р/Г.В режиме ввода весов моделей ветвей в регистры 1 и 21 переключателем 32 подключают выход генератора 29 одиночных импульсов к входу установки в единицу триггера 35. Переключателем 34 выбирают один из регистров (1 или 21) .Регистры 1 и 21 сдвига содержат по Р Т разрядов каждый. В регистр 1 сдвига записывают Р младших разрядов дополнительных двоичных кодов веса для Т ветвей, входящих в один узел. В регистр 21 сдвига записывают Р старших разрядов дополнительных двоичных кодов веса для Т ветвей, входящих в один узел. Следовательно, вес или длина ветви моделируемого графа представляется на 2 Р двоичных разрядах. Запись в регистры 1 и 21 осуществляется следующим образом.Переключателем 34 блока подключают вход выбора информационного направления регистра 1 сдвига к выходу элемента И 37. С помощью переключателей 30 и 31 блока 3 управления задают Р младших разрядов дополнительного двоичного кода веса ветви и номер ветви соответственно.Переключателем 30 в единичных разрядах дополнительного двоичного кода веса ветви подключают соответствующие выходы распределителя 27 к входам элемента ИЛИ 38, на выходе которого формируется последовательный дополнительный код Р младших разрядов веса ветви. Например, если дополнительный двоичный код Р младших разрядов 111011, то выходы всех разрядов, кроме третьего разряда, распределителя 27 импульсов подключаются переключателем 30 к входам элемента ИПИ 38. С помощью переключателя 31 задают номер ветви. Например, если выполняется ввод Р младшихразрядов веса для седьмой ветви, то вьжод седьмого разряда распределителя 28 импульсов подключают к входу элемента ИЛИ 39, на вьжоде которого формируется импульсный сигнал длительностью Р/Г, совпадающий по фазе с временем сдвига с выхода регистра 1под действием тактовьж импульсов генератора 26 импульсов. Р младших разрядов двоичного кода для седьмой модели ветви. Ввод последовательного дополнительного кода Р младших разрядов веса ветви в регистр 1 сдвигаосуществляется после подачи единичного сигнала с выхода элемента НЕ 40 через переключатель 33 на управляющий вход генератора 29 одиночных импульсов, который выделяет из последовательности импульсов с выхода элемента И 36, действующих с частотой Г/ТР, одиночный импульс, устанавливающий через переключатель 32 триггер 35 в единичное состояние на время ТР/Г. Триггер 35 сбрасывается в нулевое состояние следующим импульсом с выхода элемента И 36. Триггер 35 в единичном состоянии открываетсигналом прямого выхода элемент И 37,через который на регистр 1 сдвига поступает одиночный импульсный сигнал с выхода элемента ИЛИ 39, задающий номер модели ветви. Под действием тактовых импульсов генератора 26 импульсов последовательный дополнительный двоичный код младших разрядов веса ветви записывается с выхода элемента ИЛИ 38, начиная с младших разрядов, в регистр 1 сдвига, во время действия на выходе элемента ИЛИ 39 импульса, задающего номер модели ветви.Одиночный импульс генератора 29 через переключатель 32 устанавливает триггеры 4 и 5(1)5(Т) в нулевое состояние.Аналогичным образом в регистр 1 сдвига записывают дополнительные двоичные коды Р младших разрядов весов всех ветвей с первой по Т-ю. Затем переключателем 34 подключают регистр 21 сдвига к выходу элемента И 37 блока 3 управления и аналогичным образом записывают Р старших разрядов дополнительных кодов весов для всех Т ветвей. Особенность процесса записи кодов в регистр 21 сдвига заключается в том, что Р старших разрядов для некоторой М-й ветви (М=1Т) записываются в регистр 21 вовремя сдвига в регистре 1 Р младшихразрядов дополнительного кода веса 5(+1)-й ветви. Это реализуется следующим образом. Переключателем 30 задают Р старших разрядов дополнительного кода веса М-й ветви, а на переключателе 31 устанавливают номер (М+1)-йветви. Если вводятся Р старших разрядов дополнительного кода для последней Т - й ветви, то на переключателе31 устанавливается номер первойветви.5 Ввод последовательного дополнительного кода Р старших разрядов веса М-й ветви осуществляется послепоступления единичного сигнала с выхода элемента НЕ 40 через переключатель 33 на вход генератора 29 импульсов, который выделяет из последовательности импульсов с выхода элемента И 36, действующих с частотойГ/ТР, одиночный импульс, устанавли вающий через переключатель 32 триггер 35 в единичное состояние. Триггер 35 в единичном состоянии сигналом со своего прямого выхода открывает элемент И 37, через который на З 0 вход регистра 21 сдвига с выхода элемента ИЛИ 39 поступает импульсныйсигнал, задающий номер (М+1)-й ветви. Под действием тактовых импульсовгенератора 26 последовательный дополнительный код Р старших разрядов веса М-й ветви записывается с выходаэлемента ИПИ 38 в регистр 21 сдвигаво время действия на выходе элемента39 ИЛИ импульса, задающего номер 40 (М+1)-й ветви. Аналогичным образом врегистр 21 сдвига записывают дополнительные коды Р старших разрядов весов для всех ветвей с первой по Т-ю,После записи дополнительные коды 45 весов ветвей хранятся в регистрах 1и 21 сдвига динамическим способом,т.е. путем циркуляции кодов соответственно через сумматор 2 и полусумматор 22, причем во время сдвига Р 50 младших разрядов дополнительного кода М-й модели ветви с входа регистра 21 сдвига считываются Р старшихразрядов дополнительного кода (М)-ймодели ветви. Например, если с выхо да регистра 1 сдвига считываются Рмладших разрядов кода веса второйветви, то с выхода регистра 21 сдвига - Р старших разрядов кода первойветви.Изображенное на фиг. 1 устройство моделирует Т ветвей. С целью моделирования более сложных графов множества модулей устройства коммутируют между собой в соответствии с топологией решаемой задачи, формируя сложные графы, содержащие узлы, соединенные между собой ветвями. Например, выход 18 одного устройства подключают к входам 17 других устройств, индикационные выходы 20 которых подключают к индикационным входам 19 данного устройства. Пример моделирующей структуры изображен на фиг. 3 (на фиг. За изображен моделируемый граф, а на фиг. Зб - моделирующая структура, содержащая три модуля).В режиме моделирования переключателем 32 (фиг. 2) подключают выход генератора 29 одиночных импульсов к входу переключателя 16, с помощью которого задают начальный узел. Пуск устройства осуществляют переключателем 33, с помощью которого на управляющий вход генератора 29 одиночных импульсов подают единичный сигнал выхода элемента НЕ 40. Одиночный импульс генератора 29 поступает через переключатель 16 и элемент ИЛИ 12 на вход установки в "1" триггера устройства начального узла и устанавливает его в единичное состояние.Единичный сигнал прямого выхода триггера 4 поступает на входы 17 других устройств. Предположим, например,.что на первый вход 17 первого устройства поступил единичный сигнал с прямого выхода триггера 4 предыдущего устройства. В этом случае через элемент И 9 данного устройства проходит последовательность импульсов первого разряда распределителя 28 импульсов. Последовательность импульсов с выхода первого элемента И 9 поступает на выход элемента ИЛИ 14, выходной сигнал которого открывает элемент И 7 во время фазы сдвига дополнительного двоичного кода Р младших разрядов веса первой ветви. Последовательность импульсов первого выхода распределителя 27 поступает через элемент И 7 на вход слагаемого сумматора 2, на вход второго слагаемого которого с выхода регистра 1 сдвигается дополнительный двоичный код Р младших разрядов веса первой ветви, Сумматор 2 последовательно во времени, начиная с младших разрядов, выполняет сумми 1 О 15 20 25 30 35 40 45 50 55 рование дополнительно.го двоичногокода Р младших разрядов веса первойветви с последовательностью единицс выхода элемента И 7. За время ТРтактов дополнительный двоичный код Рмладших разрядов веса первой ветви увеличивается на единицу младшегоразряда и результат с выхода суммысумматора 2 вновь сдвигается под действием тактовых импульсов генератора 26 в регистр 1 сдвига. Если в процессе суммирования на выходе признака переноса сумматора 2 формируетсяединичный сигнал через элемент И 8,тактируемый последовательностью импульсов Р-го разряда распределителя 27, он поступает через элемент24 ИЧИ и элемент 25 задержки на входслагаемого полусумматора 22 к моменту сдвига с выхода регистра 21 Рстарших разрядов дополнительного кода веса первой ветви. Полусумматор 22суммирует единичный сигнал признакапереноса из группы Р младших разрядов текущего кода первой ветви с дополнительным кодом Р старших разрядов веса первой ветви. Если в процессе суммирования полусумматором 22 наего выходе признака переноса формируется единичный сигнал переноса иэК-го разряда (К=1, ,Р), то этотсигнал через элемент ИЛИ 24 и элемент25 задержки вновь поступает на входслагаемого полусумматора 22 во времясдвига с выхода регистра 21 (К+1)-горазряда дополнительного кода группыстарших разрядов веса первой ветви,Если в процессе суммирования полусумматором 22 формируется сигнал признака переноса из Р-го разряда группыстарших разрядов текущего кода весапервой ветви, то он откроет элемент23 И, тактируемый последовательностью импульсов Р-го разряда распределителя 27 и через элемент ИЛИ 12 установит триггер 4 в единичное состояние, а через элемент 11(1) И, тактируемый последовательностью импульсов второго разряда распределителя 28импульсов, установит триггер 5(1) вединичное состояние, Триггер 4 в единичном состоянии блокирует сигналомсо своего инверсного выхода элементИ 7, и процесс суммирования прекращается,К том случае, если на все информационные входы 17 одновременно поступают единичные сигналы через элемен1348847 10 15 20 30 35 40 45 ты И 9 и ИЛИ 14, последовательности импульсов с выходов распределителя 28 импульсов открывают элемент И 7. Последовательность импульсов первого выхода распределителя 27 импульсов поступает через элемент И 7 на вход сумматора 2 во время сдвига с выхода регистра 1 Р младших разрядов дополнительных кодов весов всех ветвей. Каждые Т Р тактов дополнительные коды младших разрядов весов Т ветвей последовательно во времени, начиная с младших разрядов, увеличиваются на единицу младшего разряда и с выхода суммы сумматора 2 вновь записываются в регистр 1 сдвига.Если в процессе суммирования на выходе признака переноса сумматора 2 появится единичный сигнал переноса из Р-го разряда группы младших разрядов текущего кода М-й ветви, то этот сигнал через элементы И 8, ИЛИ 24 и элемент 25 задержки будет поступать на вход слагаемого полусум матора 22 во время сдвига с выходарегистра 21 первого разряда группыстарших разрядов текущего кода М-йветви. За время Р тактов полусумматор 22 прибавит сигнал переноса изгруппы младших разрядов к текущемукоду группы старших разрядов, и результат с выхода суммы полусумматора22 сдвинется в регистр 21 сдвига.Последовательность импульсов Р-горазряда распределителя 27, поступаяна вход сброса сумматора 2, блокирует цепь переноса, запрещая передачу сигнала переноса в код следующеи ветви, Спустя время Вн Т Р тактов, гдеВм - наименьший вес из всех ветвейграфа, принадлежащий М-й ветви, навыходе переноса полусумматора 22 вовремя фазы сдвига с выхода регистра21 текущего кода группы старших разрядов М-й ветви сформируется сигналпереноса из Р-го разряда, который,проходя через элементы 23 И и 12 ИЛИ, установит триггер 4 в единичное состояние, а через элементы И 23 и 11(М),50 тактируемый последовательностью импульсов (М+1)-го разряда распределителя 28 импульсов, устанавливает триггер 5(М) в единичное состояние,Триггер 5(М) запоминает номер М-й модели ветви, принадлежащий дереву кратчайших путей.Триггер 4 в единичном состоянии возбуждает по выходу 18 вычислительный процесс в следующих устройствах моделирующей структуры и, кроме того, блокирует сигналом со своего инверсного выхода элемент И 7, после чего процесс вычислений в рассматриваемом устройстве моделирующей структуры прекращается.Аналогичным образом вычислительный процесс распространяется от одного устройства моделирующей структуры к другому до тех пор, пока не достигнет устройства конечного узла.В режиме индикации кратчайшего пути выделяемого из дерева кратчайших путей, в устройстве конечного узла графа с помощью переключателя 15 прямой выход триггера 4 подключают к одному из входов элемента ИЛИ 13. Единичный сигнал с прямого выхода триггера 4 проходит через элементы ИЛИ 13, И 6 на первые входы элементов И 10. Из всей группы элементов И 1 О откроется элемент И 10 той ветви, для которой триггер 5 находится в единичном состоянии, Единичный сигнал триггера 5 ветви, принадлежашей кратчайшему пути, проходит через соответствующий элемент И 1 О на индикационный выход 20 ветви и далее поступает на индикационные входы 19 других устройств модулей моделирующей структуры, возбуждая процесс распространения единичного сигнала индикации от модели конечного узла к модели начального узла вдоль кратчайшего пути. Формула изобретения Устройство для моделирования ветви графа, содержащее регистр сдвига, последовательный сумматор, два триггера, пять элементов И, пять элементов ИЛИ, элемент НЕ, группу триггеров, три группы элементов И, генератор импульсов, генератор одиночных импульсов, два распределителя импульсов и пять переключателей, причем выход генератора импульсов подключен к входу синхронизации регистра сдвига и тактовому входу первого распределителя импульсов, К-й выход которого (К=1Р, где Р - количество разрядов представления массы ветви) подключен к К-му информационному входу первого переключателя, К-й выход которого подключен к К-му входу первого элемента ИЛИ, выход которого под 1348847 1 Оключен к первому информационномувходу первого регистра сдвига, выходкоторого подключен к входу первогослагаемого последовательного сумма 5тора, выход суммы которого подключенк второму информационному входу первого регистра сдвига, выход Р-го разряда первого распределителя импульсов подключен к первому входу первого элемента И и к тактовому входувторого распределителя импульсов,М-й выход которого (М=1, , Т,где Т - количество ветвей в графе)подключен к первому входу М-го элемента И первой группы и к М-му информационному входу второго переключателя, М-й выход которого подключенк М-му входу второго элемента ИЛИ,выход которого подключен к первому 2 Овходу второго элемента И, Т-й выходраспределителя импульсов подключенк второму входу первого элемента И,выход которого подключен к тактовомувходу генератора одиночных импульсов 25и к входу установки в "О первоготриггера, вход управления записьюмассы устройства подключен к входуопроса генератора одиночных импульсов, выход которого подключен к информационному входу второго переключателя, первый выход которого подключен к входу установки в "О второготриггера, к входам установки в "О"всех триггеров группы и к входу устаз35новки в 1 первого триггера, выходкоторого подключен к второму входувторого элемента И, второй выходвторого переключателя подключен квходу третьего переключателя, выходкоторого подключен к первому входутретьего элемента ИЛИ, выход которого подключен к входу установки в "1"второго триггера, прямой выход которого подключен к первому входу третьего элемента И, к информационномувходу четвертого переключателя и является информационным выходом устройства, выход четвертого переключателяподключен к (Т+1)-му входу четверто 50го элемента ИЛИ, М-й вход которогоявляется М-м индикационным входомустройства, а выход подключен к второму входу третьего элемента И, выход которого подключен к первым входам всех элементов И второй группы,М-й информационный вход устройстваподключен к второму входу М-го элемента И первой группы, выход которого подключен к М-му входу пятого элемента ИЛИ, выход которого подключенк входу второго слагаемого последовательного сумматора, выход признака переноса которого подключен к первому входу пятого элемента И, Р-й выход первого распределителя импульсовподключен к второму входу пятого элемента И и к тактовому входу сумматора, первый выход первого распределителя импульсов подключен к второму входу четвертого элемента И, инверсный выход второго триггера подключен к третьему входу четвертого элементаИ, выход М-го элемента И третьейгруппы подключен к входу установки в"1" М-го триггера группы, выход которого подключен к второму входу М-гоэлемента И второй группы, выход которого является М-м индикационным выходом устройства, о т л и ч а ю щ ее с я тем, что, с целью повышенияточности моделирования, в него введены второй регистр сдвига, полусумматор, шестой элемент И, шестой элемент ИЛИ, элемент задержки и шестой переключатель, причем выход первого элемента ИЛИ подключен к первому информационному входу второго регистра сдвига, выход второго элемента И подключен к входу шестого переключатели, первыи выход которого подключен к входу выбора информационного выходапервого регистра сдвига, а второйвыход подключен к входу выбора информационного входа второго регистра сдвига, выход которого подключен к входу первого слагаемого полусумма- тора, выход суммы которого подключен к второму информационному входу второго регистра сдвига, Р-й выход первого распределителя импульсов подключен к входу сброса последовательногосумматора и к первому вхОду шестого элемента И, выход пятого элемента И подключен к первому входу шестого элемента ИЛИ, выход которого подключен к входу элемента задержки, выход которого подключен к входу второго слагаемого полусумматора, выход признака переноса которого подключен к второму входу шестого элемента ИЛИи к второму входу шестого элемента И,выход которого подключен к первымвходам всех элементов И третьей группы, М-й выход второго распределителяимпульсов подключен к вторым входамвсех элементов И третьей группы.1348847 б Ьпаьшце рцря 0 ы псйсц МщЬ -- Рггтпр 21 СдЮце Ипо 5 шцю роюрябылАОоц Уют Составитель А. МишинРедактор Е. Копча Техред А.Кравчук Корректор М Пожо Заказ 4803/49 Тираж 670 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5