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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 9) 111 б Е 15/20 САНИЕ ИЗОБРЕТЕНИЯ ВИДЕТЕЛЬСТВ ВТОРСНО Баранов ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(7 1) Институт проблем моделированияв энергетике АН УССР(56) Авторское свидетельство СССРУ 758179, кл. С 06 Р 15/20, 1980.Авторское свидетельство СССРВ 805300, кл. С Об Р 7/00, 1981.(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯГРАФОВ(57) Изобретение относится к областицифровых вычислительных машин, аименно к устройствам для обработкицифровых данных. Изобретение можетбыть использовано в автоматике и воспециализированных вычислителях,для решения задач о кратчайшем пути,дискретных вариационных задач, задач оптимального управления и дифференциальных игр, Цель изобретенияупрощение процесса моделированияграфов. Устройство содержит блокуправления, триггер, три элемента Итри элемента ИЛИ, два ключевых элемента, регистр сдвига, сумматор,группу триггеров и три группы элементов И. Изобретение позволяет моделировать Ю ветвей с разными весами, В процессе построения сложныходнородных вычислительных структур,содержащих множество соединенных,между собой ячеек из моделей узлови моделей ветвей, эффект упрощенияпроцесса моделирования увеличивается пропорционально количеству ячеекоднородных вычислительных структур,причем блок управления является общим для всех ячеек однородной вычислительной структуры. 3 ил.Изобретение относится к вычислительной технике и может быть использовано в автоматике и в специализированных вьтчЕтслениях дпя решения задач о кратчайшем пути, дискрет-. ных вариационных задач, задач опти - мального управления и дифференциальи Устройство для моделирования графов работает следующим образом. Генератор 21 импульсов блока 3управления (фиг. 2) вырабатывает последовательность тактовых импульсов частоты 1, из которых распре, целитель 22 импульсов формируетпоследовательностей импУльсов частоты/ь ных игр.Цель изобретения - упрощение процесса моделирования графов. . ;На фиг. 1 изображена функциональная схема устройства для моделирования графов; на фиг. 2 - функциональная схема блока управления; на фиг. 3 - пример моделирования гра фа, поясняющий принцип работы устройства.Устройство для моделирования гра-. фов содержит регистр 1 сдвига, сумматор 2, блок 3 управления, триггер д 4, группу триггеров 5(1) - 5(д), элементы И 6-8, перву 10 группу элементов И 9(1) - 9(г), вторую группу элементов И 10(1) - 10(г), третью группу элементов И 11(1) - 11(ъ), 5 элементы ИЛИ 12-14, ключевые элементы 15 и 16, информационные входы 17(1) - 17 моделей ветвей, Выход 18 фмодели узла, индикацион.ные тзходь 19 (1) - 19( ) моделей ветвей, ин - тт дикационные выходы 20(1) - 20(д) моделей ветвей.Блок 3 управления (фиг. 2) содержит генератор 2 1 импульсов, распределители 22 и 23 импульсов, генератор 24 одиночныхо импульсов, первый и второй кнопочные коммутаторы 25 и 26, переключатели 27 и 28 триггер 29, элементы И 30 и 31 элементы ИЛИ 32 и 33, элемент НЕ 34,Цифрами В скобках слсдую 1 Цими за номером позиции без скобки обозначены порядковые номера одинаковьгх по своему техническому исполнению и назначению блоков, узлов и элементов. Цифрами В с,кобкахстоящими у контура соответствующего блока узла или элемента, показаны порядковые номера входов и выходов этого блока, узла или элемета. где - количество разрядов гтредстав - .тенин весов моделей Ветвей, сдвинутых црг Относительно друга на время / Из пбследсватегьности импульс.ов ь -го разряда распределителя 22 икгтуттеСОВ расп;Рдслитель 23 имттуле - ссВ формируетпос.тедовательностей импульсов длительнос.тью ,/, дейстВуютцих с частотои /., н сдвгптутьтх ДРУГ ОТНСЕСИТЕЛЬНО ИРУГа На ВРЕМЯ ь /Е .режиме В 130 да Весов,сделей Вет= Вей в регистт-. 1 сдвига пооеключатедем 27 олока 3 управления подключается выход генератора 2-; Одиночных импульсов к единичному Входу триггера 29. С помощью коммутатора 25 и1уттрав 1 ЕНИЯ 3 ад 1 Е ТС а тто тогтеттттеггь;тьтй гвоич;пгй код Всса модели ветви и номер модели Ветви соответственно. Коьгмутатор 25 ттодключаст В единичных разрядах пополнительтОГО ЦВОНгНОГС КОДа ВЕСа МОДЕЛИ ВЕТВИ соответствующие Выходы рас.пределителя 22 им ,Еьссв к Входам элемента ИЛИ 32, на выходе косорого формируется последовательный догтолнительпый код Веса модели Ветви, Например. если Вес модели Ветви равен пяти (дополнительный двоичнь:й код 1,:0 1 1); то вьг 1 оды В ех раз рялсВ; :,рогте третьето разряда. распределителя 22 импульсов подключаются ком;, тагором 25 к Входа 1 злеента ИЛИ 32С помощью коммутатора 26 блокаупретв 1 ени 51 3 вдается номер моделиветви. Например, если выполняетсяВвод веса В седьмук модель ветви, то Вьгход седьмого,.азряда распредеИЕЕЛЛ3 ИМПУЛЬСОВ гтодКЛ 0 Чагтея К з,соду элемента ИПИ 33, на Выходе которого формируегся импугтьсный сиг- Н 11 ДЛИТСЬВОСТЬ 0 / Е Совнадат 01 ЦИИ по фазе с временем сдвига с Выхода регис.тра 1 сдвтлга под действием гактсвых импульсов генератора 21импульсов-разрядного двоичного кода Веса для седьмой мопели ветВи, Ввод последовательного дополнительного кода веса модели Встьчт В регистр 1 сдвига осуществляетсяпосле подачи единичного сигнала с Выхода. элементов НЕ 34 через перекюча;ель 28 на управляюцпти Вход генератора 24 единичных импульсов, который выделяет из последователь - вост импульсов элемент И 30, дей - СТВУКЩИХ С ЧаСТОТОй/т ь, ОДИОЧНЫй типу; ьс, устанавливающитт через тте 124( 1 10реключатель 27 триггер 29 в единичное состояние на время г /,Триггер 29 сбрасывается в нулевое состояние следующим импульсомпоследовательности сигналов элемента И 30, Триггер 29 в единичном состоянии открывает сигналом единичноговыхода элемент И 31, через которыйна управляющий вход регистра 1 сдвига поступает одиночный импульсныйсигнал с выхода элемента ИЛИ 33,задающий номер модели ветвиПоддействием тактовых импульсов генератора 2 1 импульсов блока 3 управления последовательный дополнительный двоичный код веса модели ветвизаписывается с выхода элемента ИЛИ32 последовательно во времени, начиная с младших разрядов, в регистр1 сдвига во время действия на выходеэлемента ИЛИ 33 импульса, задающегономер модели ветви.Одиночный импульс 24 одиночныхимпульсов через переключатель 27 устанавливает также триггеры 4 и 5 в 10 15 40 нулевое состояние.Аналогичным образом в регистр .1 сдвига записывают дополнительные двоичные коды весов всех моделей ветвей с первой по п -ю. Устройство (фиг.1) 30 моделирует н, моделей ветвей графа, входящих в модель одного узла. С целью моделирования сложных графов устройства коммутируют между собой в соответствии с топологией решаемой задачи, формируя структуры, моделирующие графы. Например, выход 18 модели одного узла графа подключают к информационным входам 17 моделей ветвей других узлов графа. При этом индикационные выходы 20 моделей одних ветвей подключаются к индикационным входам 19 моделей других ветвей.оПример модели графа, содержащей 45 три модели узла, каждая из которых содержит с моделей ветвей, изображен на фиг. 3 (на фиг. 3 а изображен моделируемый граф, на фиг.З Б - устройство, его моделирующее). 50В режиме моделирования переключателем 27 блоха 3 управления (фиг.2) подключается выход генератора 24 одиночных импульсов к входу ключевого элемента 16, с помощью которого за дается начальная модель узла. Пуск устройства осуществляется переключателем 28, с помощью которого на управляющий вход генератора 24 одиночных импульсов подается единичный сигнал выхода элемента НЕ 34. Одиночный импульс генератора 24 одиночных импульсов блока 3 управления поступает через ключевой элемент 16 и элемент ИЛИ 12 на единичный вход тригоера 4 модели начального узла и устанавливает его в единичное состояние. Единичный сигнал прямого выхода триггера 4 поступает по шине 18 на информационные входы 17 моделей ветвей других узлов.Предположим, что на первый информационный вход 17 первой модели ветви поступил единичный сигнал с единичного выхода триггера 4 предыдущей модели. В этом случае через первый элемент И 9 данной модели проходит последовательность импульсов первого разряда распределителя 23 импульсов блока 3 управления, Последовательность импульсов с выхода первого элемента И 9 поступает на выход элемента ИЛИ 14, выходной сигнал которого открывает элемент И во время фазы сдвига с выхода регистра 1 сдвига (под действием тактовых импульсов генератора 21 импульсов блока 3 управления) дополнительного двоичного кода веса первой модели ветви.Последовательность импульсов первого разряда распределителя 22 импульсов блока 3 управления поступает через элемент И 7 на вход сумматора 2, на другой вход которого сдвигается с выхода регистра 1 сдвига дополнительный двоичный код веса первой модели ветви. Сумматор 2 выполняет последовательно во времени, начиная с младших разрядов, суммирование дополнительного двоичного кода веса первой модели ветви с последовательностью единиц младшего разряда, представленных последователь-костью импульсов выхода элемента И 7. За время ь ь тактов дополнительный двоичный код веса первой модели ветви увеличивается на единицу младшего разряда и результат с выхода суммы сумматора 2 вновь сдвигается под действием тактовых импульсов генератора 21 импульсов блока 3 управления в регистр 1 сдвига.Спустя время р тактов, где Р, - вес первой модели ветви, на выходе переноса сумматора 2 сформиру55 ется сигнал переноса из г 1 -го разряда текущего двоичного кода первой модели ветви, который через элемент И 8, тактируемый последовательностью импульсов к -го разряда распределителя 22 импульсов, поступает через элемент ИЛИ 12 на единичный вход триггера 4 и через первый элемент И 11, открытый в это время сигналом первого разряда распределителя 23 импульсов блока 3 управления, на единичный вход первого триггера 5.Триггер 4 модели узла и первый триггер 5 первой модели ветви устанавливаются в единичные состояния. Триггер 4 в единичном состоянии блокирует сигналом инверсного выхода элемент И 7, и процесс суммирования в сумматоре 2 прекращается.В том случае, когда на все информационные входы 17 моделей ветвей одновременно поступают единичные сигналы с выходов 18 моделей других узлов графа, через элементы И 9 и ИЛИ .14 последовательно во времени поступают последовательности импульсов с выходов всех разрядов распределителя 23 импульсов, которые открывают ,элемент И 7, Последовательность импульсов первого разряда распределителя 22 импульсов блока 3 управления поступает через элемент И 7 на вход сумматора 2 во время сдвига с выхода регистра 1 сдвига дополнительных кодов весов всех моделей ветвей. Каждые т,тактов допапнительные коды весов ь, моделей ветвей последовательно во времени, начиная с младших разрядов, увеличиваются на единицу младшего разряда и с выхода суммы сумматора 2 вновь записываются в регистр 1 сдвига. Спустя время Р; 1тактов, где Р - наименьший вес из всех моделей ветвей, принадлежащий, например.,-й модели ветви ца выходе сумматора 2 из текущего дополнительного двоичного кода веса-й модели ветви сформируется сигнал переноса из-го разряда, который через элементы И 8, ИЛИ 12 и элемент И 8,-й элемент И 11 поступает соответственно на единичные входы триггеров 4 и 1 -го триггера 5, устанавливая их в единичные состояния, Триггер 5 запоминаетномер модели ветви, принадлежащий дереву кратчайших путей (в рассматриваемом случае-й модели ветви). Триггер 4 в единичном состоянии возбуждает по выходу 18 модели узла вычислительный процесс в моделях ветвей следуЬщих моделей узлов графа, а также блокирует сигналом инверсного выхода элемент И 7 и процесс вычислений в рассматриваемой модели узла графа.Вычислительный процесс распространяется от одной модели к другой до тех пор, пока не. достигнет модели конечного узла.В режиме индикации кратчайшего пути, выделяемого из дерева кратчайших путей, в модели конечного узла с помощью ключевого элемента 15 подключается единичный выход триггера 4 модели конечного узла к одному из входов элемента ИЛИ 13, Единичный сигнал с выхода триггера 4 проходит через элементы ИЛИ 13, И 6 на первые входы элементов И 10, вторые входы которых управляются триггерами 5 моделей ветвей. Из всей группы элементов И 10 откроется элемент И 10 той модели ветви, для которой триггер 5 находится в единичном состоянии, Единичный сигнал триггера 5 модели ветви, принадлежащей кратчайшему пути, проходит через соответствующий элемент И 10 на индикационный вь 1 ход 20 модели ветви и далее поступает на индикационные входы 19 других моделей узлов, возбуждая процесс распространения единичного сигнала индикации от модели конечного узла к модели начального узла вдолькратчайшего пути. Формула изобретения устройство для моделирования графов, содергкащее триггер, первый, второй и третий элементы И, первьгй, второй и третий элементы ИЛИ, первый и второй ключевые элементы, единичный и нулевой выходы триггера подключены к первым входам соответ- ственьЬ первого и второго элементов И, едицичцый вход триггера соединен с выходом первого элемента ИЛИ,первый вход которого подключен к выходу третьего элемента И, выход второго элемента ИЛИ соединен с вторым входом второго элемента И, о т л и ч аю щ е е с я тем, что, с целью упрощения тгроцесса моделирования графов, в него введены блок управле12 ч 611 О 5 1 О 15 20 25 30 35 40 45 50 55 чевой элемент соединен с вторым входом первого элемента ИЛИ устройства. 7ния, включающий генератор импульсов, первый и второй распределители импульсов, генератор одиночных импульсов, первый и второй кнопочные коммутаторы, первый и второй переключатели, триггер, первый и второй элементы И, первый и второй элементы ИЛИ и элемент НЕ, а также регистр сдвига, сумматор, .группа триггеров и три группы элементов И по . элементов в каждой, где и - количество ветвей моделируемого графа, причем выход генератора импульсов блока управления соединен с входом первого распределителя импульсов блока управления, выходы которого с первого по и -й (П - количество разрядов представления весов ветвей граФа) соединены через первый кнопочный коммутатор с соответствующими входами первого элемента ИЛИ блока управления,-й выход первого распределителя импульсов блока управления соединен с входом второго распределителя импульсов блока управления, первыми входами первого элемента И блока управления третьего элемента И устройства, выходы второго распределителя импульсов блока управления с первого пог -й соединены через второй кнопочный коммутатор блока управления с соответствующими входами второго элемента ИЛИ блока управления, ъ -й выход второго распределителя импульсов блока управления подключен к второму входу первого элемента И блока управления, выход которого соединен с тактовым входом генератора одиночных импульсов блока управления и нулевым входом триггера блока управления, выход генератора одиночных импульсов блока управления через размыкающий контакт первого переключателя блока управления соединен с единичным входом триггера блока управления, единичный выход которого подключен к первому входу второго элемента И блока управления, второй вход которого сое,цинен с выходом второго элемента.ИЛИблока, управления, управляющий вход генератора одиночных импульсов блока управления через второй переключатель соединен с выходом элемента НЕ блока управления, вход которого подключен к нулевой шине устройства, выход генератора импульсов, блока управления соединен с входом синхронизации регистра сдвига, информационный .и управляющий входы которогоподключены соответственно к выходампервого элемента ИЛИ и второго элемента И блока управления, первыевходы элементов И первой группы являются информационными входами устройства, вторые входы элементов Ипервой группы соединены с соответствующими выходами второго распределителя импульсов блока управления,выходы элементов И первой группысоединены с входами третьего элемента ИЛИ, выход которого подключен квторому входу второго элемента Иустройства, третий вход которогосоединен с первым выходом первогораспределителя импульсов блока управления, выход второго элемента Иустройства соединен с первым входомсумматора, второй вход которогоподключен к выходу регистра сдвига,выходы суммы и переноса сумматорасоединены соответственно с информационным входом регистра сдвига ивторым входом третьего элемента И устройства, единичный выход триггера является выходом устройства и соединен через первый ключевой элемент с одним входом второго элемента ИЛИ, другие входы которого являются индикационными входами устройства, выход первого элемента И устройства соединен с первыми входамиэлементов И второй группы, выходыкоторых являются индикационными выходами устройства, вторые входы эле. ментов И второй группы соединены сединичными выходами соответствующих триггеров группы, единичныевходы которых соединены с выходамисоответствующих элементов И третьей группы, первые входы которыхподключены к выходу третьего элемента И, вторые входы элементов Итретьей группы соединены с соответствующими выходами второго распределителя импульсов блока управления, а нулевые входы триггеров группы объединены и подключены к размыкающему контакту первого переключателя блока управления, замыкающий контакт которого через второй клю 1261101, 46110 Составитель С.Назарова Техред О.Гортвай Корректор А,Обруч едактор Н.Т Заказ ого ком ении и от РаушскаПроизводственно-полиграфическое предприятие, г. Ужгород роектная 3/43 Тираж 67ВНИИПИ Государствпо делам изобре 13035, Москва, ЖПодпис тета ССС рытий наб., д