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

(50 4 С 06 Р 15/2 ОПИСАНИЕ ИЗОБРЕТЕНИЯ М ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ ТОРСНОМУ СВИДЕТЕЛЬСТВУ(46) 07.06.87. Бил. 9 21 (71) Институт проблем моделирования в энергетике АН УССР(56) Авторское свидетельство СССР 9 805300, кл. С 06 3 7/00, 1978.Авторское свидетельство СССР В 1246110, кл. С 06 Р 15/20, 1984, (54) УСТРОЯСТВО ДЛЯ ОДЕЛИРОВАНИЯ ГРАФОВ(57) Изобретение относится к облас ти вычислительной техники, в частности к устройствам для обработки ин формации специального назначения. Цель изобретения состоит в расширении функциональных возможностей устройства за счет моделирования как входящих, так и исходящих ветвей узла графа. Устройство для моделирова" ния графов содержит два регистра сдвига, сумматор, два триггера, две группы триггеров, два коммутатора, шесть элементов И, пять групп элементов И, три элемента ИЛИ, группу элементов ИЛИ, ключ, группу элементов индикации и блок управления.Устройство позволяет моделировать как группы из ш ветвей графа, входя щих в узел, так и группы из ш ветвей, исходящих из этого узла и входя. сФ щих в группу из ш узлов. 3 ип.13Изобретение относится к цифровымвычислительным машинам, в частностик устройствам обработки информацииспециального назначения, и можетбыть использовано как специализированное вычислительное устройство длянаучно-исследовательских целей имоделирования задач о кратчайшем пути, дискретных вариационных задач,.задач оптимального управления и дифференциальных игр, а также для управления некоторыми технологическимипроцессами в различных отраслях промьциленности.Цель изобретения - расширениеФункциональных возможностей устройства путем моделирования как входящих, так и исходящих ветвей узловграфа.На Фиг.1 изображена функциональ-.ная схема устройства для моделирования графов," на фиг.2 - функциональная схема блока управления; наФиг.З - пример моделирования графов.Устройство для моделирования графов содержит регистры 1 и 2 сдвига,сумматор 3, блок 4 управления, триггеры 5 и 6, группы триггеров 7 и 8,коммутаторы 9 и 10, элементы И 1 в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 вырабатывает последовательность тактовых импульсов частоты 2, на которой распределитель43 вырабатывает и последовательностей импульсов частоты й/и (где и -количество разрядов представлениявесов моделей ветвей), сдвинутыхдруг относительно друга на время/Е,Из последовательности импульсов и-го разряда распределителя 43 импульсов распределитель 42 вырабатыва 5993 50 5 О 5 20 25 30 35 40 ет ш последовательностей импульсов длительностью пЯ, действующих с частотой Г/шп и сдвинутых друг относительно друга на время и/Й.В режиме ввода весов моделей ветвей в регистры 1 и 2 сдвига коммутатором 47 подключают выход генератора 44 одиночных импульсов к единичному входу триггера 50. Коммутатором 49 выбирают один из регистров 1 или 2 путем подключения управляющего входа соответствующего регистра 1 и 2 к выходу элементы И 52. С помощью коммутаторов 45 и 46 задают до полнительный двоичный код веса модели ветви и номер модели ветви соответственно. Коммутатор 45 подключают в единичных разрядах дополнительного кода веса модели ветви соответствующие выходи распределителя 43 импульсов к входам элемента ИЛИ 54, на выходе которого Формируется после. довательный дополнительный код веса модели ветви. Например,если вес модели ветви равен пяти (дополнительный двоичный код 111011), то выходы всех разрядов, кроме третьего разряда, распределителя 43 импульсов подключается коммутатором 45 к входам элемента ИЛИ 54.С помощью коммутатора 46 задают номер модели ветви. Например, если выполняется ввод веса в седьмую модель ветви, то выход седьмого разряда распределителя 42 подключают к входу элемента ИЛИ 53, на выходе которого формируется импульсный сигнал длительностью и/2, совпадающий по фазе с временем сдвига с выходов регистров 1 и 2 под действием такто. вых импульсов генератора 42 п-разрядного двоичного кода для седьмой модели ветви.В регистры 1 и 2 сдвига, по шп разрядов каждый, записываются соответственно веса моделей ветвей, входящих в узеп и исходящих из узла.Если выполняют запись весов моделей,ветвей, входящих в узел, то коммутатором 49 подключают выход элемента И 52 к управляющему входу регистРасдвига. В процессе записи весов моделей ветвей, исходящих из узла, коммутатором 49 подключают управляющий вход регистра 2 сдвига к выходу элемента И 52,Ввод последовательного двоичного кода веса модели ветви в регист13 5993 4да регистрасдвига через коммутатор 9 и сумматор 3 на информационный.вход регистра 1 сдвига, а также с выхода регистра 2 сдвига на его информационный вход через коммутатор 1 О.Устройство моделирует ш моделейветвей графа, входящих в модель узла, из которого исходит ш моделейветвей графа, каждая из которых оканчивается моделью узла (фиг.З). Всего устройство моделирует 2 ш ветвейграфа и ш + 1 узел и представляет собой один модуль моделирующей структурыС целью моделирования более сложных графов множество модулей моделирующих структур коммутируют междусобой в соответствии с топологиейрешаемой задачи, формируя сложныеструктуры, моделирующие графы. Например, информационные выходы 29 моделей узлов одного модуля подключают к информационным входам 28 моделей ветвей других модулей, индикационные выходы 31 моделей ветвей которых подключают к индикационнымвходам 30 данного модуля. Неиспользованные информационные входы 28 ииндикационные входы 30 соединяютсяс шиной логического "0.Пример моделирующей структуры,содержащей три модуля, изображен наФиг.З. На фиг.За изображен моделирующий граф (где Н - начальный узел гра-.фа; К - конечный узел графа), нафиг,Зб - моделирующая структура,содержащая три модуля.Блок 4 управления для всех модулей моделирующей структуры являетсяобщим.В режиме моделирования графов коммутатором 47 подключают выход генератора 44 одиночных импульсов к входуключа 26, с помощью которого задаютначальный узел графа. Конечный узелграфа задается путем соединения одного из информационных выходов 29устройства с соответствующим индикационным входом 30. Например, нафиг, изображена пунктиром связьинформационного выхода 29(1),подключенного к прямому выходу триггера 8(1),моделирующего конечный узелграфа, с индикационным входом 30(1.1) ры 1 или 2 сдвига осуществляется после подачи единичного сигнала с выхода элемента НЕ 55 через коммутатор 48 на управляющий вход генератора 44 одиночных импульсов, который выделяет из последовательности импульсов элемента И 51, действующих с частотой Г/ш и, одиночный импульс, устанавливающий через коммутатор 47 триггер 50 в единичное состояние на 10 время и и/Е. Триггер 50 сбрасывается в нулевое состояние следующим импульсом последовательности элемента И 51. Триггер 50 в единичном состоянии открывает сигналом прямого вы хода элемент И 52. Импульсный сигнал последовательности элемента ИЛИ 53, задающий номер модели ветви, выцеляется на выходе элемента И 52 в виде одиночного импульса и через коммута тор 49 поступает на управляющий вход, например, регистра 1 сдвига. Под действием тактовых импульсов генератора 41 последовательный дополнительный двоичный код веса модели ветви запи сывается с выхода элемента ИЛИ 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 сдвига динамическим способом путем циркуляции кодов под действием тактовых импульсов генератора 41 с выхдВ режиме моделирования осуществляется поиск кратчайшего пути между начальным и конечным узлами графа следующим образом.5 131Пуск устройства осуществляют коммутатором 48, с помощью которого на управляющий вход генератора 44 одиночных импульсов подают единичный сигнал с выхода элемента НЕ 46. Одиночный импульс генератора 44 одиночных импульсов поступает через замкйутый ключ 26 и элемент ИЛИ 23 на. единичный вход триггера 5 модели начального узла и устанавливает его в единичное состояние, Единичный сигнал прямого выхода триггера 5 открывает элемент И 14, через который проходит импульс с выхода элемента И 51, и устанавливает триггер 6 в единичное состояние. Единичный сигнал прямого выхода триггера 6 открывает элемент И 15 и через элемент ИЛИ 22 элемент И 11, а также переключает коммутаторы 9 и 10 в состояние, при котором выход регистра 2 сдвига под-, ключается через коммутатор 9 к второ. му информационному входу сумматора 3, а информационный вход регистра 2 сдвига через коммутатор 10 подключается к выходу суммы сумматора 3. Таким образом, в цепь циркуляции кодов регистра 2 сдвига подключается сум" матор 3, на первый информационный вход которого начинает поступать последовательность импульсов с выхода первого разряда распределителя 43. В это время под действием тактовых импульсов генератора 41 с выхода регистра 2 последовательно во времени сдвигаются дополнительные двоичные коды весов моделей ветвей, исходящих из начального узла.Сумматор 3 выполняет последова.тельно во времени, начиная с младших разрядов, суммирование дополнительных кодов весов моделей ветвей с последовательностью импульсов на выходе элемента И 11. За время шп тактов дополнительные, двоичные коды весов моделей ветвей увеличиваются на единицу младшего разряда, а результат с выхода суммы сумматора 3 ,сдвигается под действием тактовых импульсов генератора 41 в регистр 2 сдвига. Спустя время Р; ш н тактов, где Р - вес, -й модели ветви, имеющей наименьший вес, на выходе переноса сумматора 3 формируется сигнал пере" носа из и-го разряда текущего двоич" ного кода ь-й модели ветви, исхоцящей из начального узла. Последова 5993 Допустим, что согласно топологиимоделируемого графа информационный - .выход 29 (х) данного моделирующегомодуля соединен с информационным вхо дом 28 (1) следующего моделирующегомодуля, в котором все триггеры 5 - 7находятся в нулевом состоянии,Предположим также, что на все информационные входы 28 следующего 35моделирующего модуля единичные сигналы с информационных выходов 29других моделирующих модулей поступают одновременно. В этом случае через элементы И 17 и элемент ИЛИ 22последовательно во времени поступают последовательности импульсов с выходов всех разрядов распределителя42, кокоторые открывают элемент И 11.Последовательность импульсов пер вого разряда распределителя 43 поступает через элемент И 1 на первый ин "Формационный вход сумматора 3, на втовторой информационный вход которогопод действием тактовых импульсов ге нератора 41 с выхода регистра 1 сдвига через коммутатор 9 сдвигаютсяпоследовательно во времени, начинаяс младших разрядов, дополнительныедвоичные коды весов всех моделей вет 5 О 5 20 25 тельность импульсов и-го разряда распределителя 43, поступая на вход сброса сумматора 3, блокирует цепь переноса, запрещая передачу сигнала переноса в следующий 1+1-й двоичный код веса +1-й модели ветви.Сигнал переноса из и-го разряда двоичного кода -й модели ветви через элемент И 12, который открыт импульсом и-го разряда распределителя 43, поступает на вход элемента И 15, открытого единичным сигналом прямого выхода триггера 6, Импульс с выхода элемента И 15 поступает на входы элементов И 20, из которых открыт только элемент И 20 Д),находящийся под действием импульсного сигнала -го разряда распределителя 42. Импульсный сигнал элемента И 15 через элемент И 20устанавливает в единичное состояние триггер 8 (1), единичный сигнал прямого выхода которого поступает на информационный выход 29 (1) устройства. вей, входящих в узел, Каждые шп тактов дополнительные коды весов моделей ветвей последовательно во времени увеличиваются на единицу младшего разряда и с выхода суммы суммато 135993 85 10 15 20 25 30 35 40 45 50 55 ра 3 вновь записывается в регистрсдвига. Спустя время Р шп тактов где Р, - наименьший вес из всех моделей ветвей, принадлежащий, например, К-й модели ветви) из и-го разряда текущего дополнительного двоичного кода К-й модели ветви на выходе переноса сумматора 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. Спустя время Р шп тактов (где Р - вес 1 -й модели ветви, имеющей найменьший вес) на выходе пе реноса сумматора 3 формируется сигнал переноса из и-го разряда текущего двоичного кода 1-й модели ветви, исходящей из узла данного модели рующего модуля. Сигнал переноса из и-го разряда через элементы И 12, 15 и 20 (1) устанавливает триггер 8(1) в единичное состояние. Единичный сигнал прямого выхода триггера 8(1) поступает на информационный выход 29 (1) и далее согласно топологии моделируемого графа на информационные входы 28 других моделирующих моделей, возбуждая в них вычислительный процесс, который выполняется аналогичным образом.Вычислительный процесс распространяется от одного моделирующего модуля к другому согласно топологии графа до тех пор, пока не достигнет модели конечного узла, В этом случае один из триггеров 8 устанавливается в единичное состояние и единичный сигнал его прямого выхода (связь показана пунктиром) через соответствующий элемент ИЛИ 25 открывает элемент И 21, единичный сигнал с выхода которого с помощью элемента 27 индикации индуцирует модель ветви, принадлежащей кратчайшему пути, и поступает далее 4 ерез элементы ИЛИ 24, И 13 на входы элементов И 18. Из всех элементов И 18 открывается тот элемент, который управляется одним иэ триггеров 7. Сигнал, действующий на соответствующем выходе 31 устройства, можно использовать для индикации (с помощью элемента индикации) модели ветви, входящей в узел и принадлежащей .кратчайшему пути. Далее единичный сигнал с выхода элемента И 8 распространяется вдоль кратчайшего пути от конечного узла к начальному, что позволяет выделить и индицировать с помощью элементов индикации кратчайший путь на моделируемом графе между начальным и конечными узлами. Формула изобретения Устройство для моделирования гра" фов, содержащее первый регистр сдвига, сумматор, первый триггер, первую группу триггеров и три группы элементов И, по ш элементов в каждой, где щ - колнчество моделируемых ветвей, входящих в узел, три элемента И, три элемента ИЛИ, ключ и блок управления, содержащий генератор импульсов, два распределителя импульсов, генератор одиночных импульсов, четыре коммутатора, триггер, два элемента И, два элемента ИЛИ и элемент НЕ, причем выход генератора им" пульсов блока управления соединен с входом первого распределителя импульсов, выходы разрядов которого с первого по п-й, где и - количество разрядов представления весов моделей ветвей, соединены с входамипервого коммутатора блока управления выходы первого коммутатора блока управления соединены с входами первого элемента ИЛИ блока управления, выход и-го разряда первого распределителя импульсов соединен с входом второго распределителя импульсов, выходы разрядов которого с первого по ш-й соединены с входами второго коммутатора блока управления, выходы ко- Ю торого соединены с входами второго элемента ИЛИ блока управления, тактовый вход генератора одиночных импульсов соединен с выходом первого элемента И блока управления, первый 15 и второй входыкоторого соединены соответственно с выходом п-,го разряда первого распределителя импульсов и с выходом ш-го разряда второго распределителя импульсов, выход гене ратора одиночных импульсов соединен с информационным входом третьего коммутатора блока управления, первый выход которого соединен с единичным входом триггера блока управления, 25 прямой выход которого соединен с первым входом второго элемента И блока управления, выходы первого элемента И и второго элемента ИЛИ блока управления соединены соответственно О с нулевым входом триггера и вторым входом второго элемента И блока управления, вход запуска генератора одиночных импульсов соединен с ,выходом четвертого коммутатора блока 35 управления, вход которого соединен с выходом элемента НЕ, вход которого соединен с нулевой шиной устройства, выход генератора импульсов блока управления соединен с входом син 1хронизации первого регистра сдвига, вход ввода данных которого соединен с выходом первого элемента ИЛИ бло ка управления, информационные входы моцелей ветвей с первого по т-й соединены соответственно с первыми входами элементов И, первой группы, вторые входы которых соединены соответственно с выходами с первого по ш-й 5 О разрядов второго распределителя импульсов блока управления, выходы первой группы элементов И соединены соответственно с входами первого элемента ИЛИ, выход которого соединен 55 с первым входом первого элемента И, первый информационный вход сумматора соединен с выходом первого элемента И, второй вход которого соединен с выходом первого разряда первогораспределителя импульсов блока управления, выходы суммы и переноса сумматора соединены соответственно с инФормационным входом первого регистра сдвига и с первым входом второгоэлемента И,второй вход которого соединен с выходом и-го разряда первогораспределителя импульсов блока управления, выход второго элемента Исоединен с первым входом второго эле.мента ИЛИ, второй вход которого соединен через ключ с вторым выходомтретьего коммутатора блока управления, выход втооого элемента ИЛИ соединен с единичным входом первоготриггера, нулевой вход которого объ"единен с нулевыми входами первойгруппы триггеров и соединен с первым выходом третьего коммутатораблока управления, выход третьегоэлемента ИЛИ соединен с первым входом третьего элемента И, выход которого соединен с первыми входамиэлементов И второй группы, выходыкоторых являются выходами индикацииугла графа, принадлежащего кратчайшему пути устройства, вторые входыэлементов И второй группы соединенысоответственно с прямыми выходамитриггеров первой группы, единичныевходы которых соединены соответственно с выходами элементов И третьейгрупгы, первые входы которых соединены соответственно с первого пош-й разрядами второго распределителя блока управления, о т л и ч а ющ е е с я тем, что, с целью расширения функциональных возможностей засчет моделирования входящих и исходящих ветвей узлов графа, введенывторой регистр сдвига, второй триггер, вторая группа из ш триггеров,два коммутатора, четвертый, пятый ишестой элементы И, группа из ш элементов ИЛИ, четвертая и пятая группыэлементов И по ш элементов в каждой,группа элементов индикации из ш элементов, и в блок управления - пятыйкоммутатор, информационный вход которого соединен с выходом второгоэлемента И блока управления, а первый и второй выходы соединены соот-,ветственно с входами управления записью первого и второго регистровсдвига, причем выходы первого и второго регистров сдвига соединены соответственно с первым и вторым информационными входами первого коммута 1315993 1 гтора, выход которого соединен с вторым информационным входом сумматора,информационный вход второго регистра сдвига соединен с выходом второго коммутатора, первый и второй информационные входы которого соединены соответственно с выходом второгорегистра сдвига и выходом суммы сумматора, вход сброса которого соединен с выходом и-го разряда первогораспределителя импульсов блока управления, выход генератора импульсовблока управления соединен с входомсинхронизации второго регистра сдвига, вход ввода данных которого соеди.нен с выходом первого элемента ИЛИблока управления, прямой выход первого триггера соединен с первым входом четвертого элемента И, второйвход которого соединен с выходомпервого элемента И блока управления,выход четвертого элемента И соединен с единичным входом второго триггера, прямой выход которого соединенс входом первого элемента ИЛИ, суправляющими входами первого и второго коммутаторов, с первым входомпятого элемента И и вторым входомтретьего элемента И, инверсный выходвторого триггера соединен с первымвходом шестого элемента И, второй вход которого соединен с выходомвторого элемента И, выход шестогоэлемента И соединен с вторыми входа.ми элементов И третьей группы, выход второго элемента И соединен с-вторым входом пятого элемента И,выход которого соединен с первымивходами элементов И четвертой группы, вторые, входы которой соединены 10 соответственно с первого по ш-й разрядами второго распределителя импульсов блока управления, выходы элементов И четвертой группы соединенысоответственно с единичными входа ми триггеров второй группы, прямыевыходы которых являются информацион чными выходами устрОЙства и соединены соответственно с первыми входами элементов И пятой группы, вторые 20 входы которых соединены соответствен.но с выходами группы элементов ИЛИ,входы которых являются входами задания устройства, выходы элементов Ипятой группы подключены к входамтретьего элемента ИЛИ и к входамэлементов индикации труппы, нулевые,.входы второго триггераи триггероввторой группы объединены и соединены с первым выходом третьего 30,коммутатора блока управления.