Модель ребра графа

(71) Институт проблем моделирования . в энергетике АН УССР(56) 1. Авторское свидетельство СССР Р 714402, кл. С 06 Г 15/20, 1977.2. Авторское свидетельство СССР Р 708367, кл. 6 06 6 7/48, 1977 (,прототип ) .(541 (57) МОДЕЛЬ РЕБРА ГРАФА, содер- жащая первый и второй регистры, первую и вторую схемы сравнения, два элемента И, информационные входы регистров объединены и являются группой информационных входов модели, выходы первого и второго регистров соединены с первыми входами соответственно первой и второй схем сравнения, о т л и ч а ю щ а я с я тем, что, с целью расширения функциональных возможностей путем обес-, печения моделирования оператора" отображения, в модель введены пер-: вая и вторая группы элементов И и группа элементов ИЛИ, причем выходы первого и второго регистров соединены с первыми входами элементов И соответственно первой и второй групп, первые входы элементов ИЛИ группы соединены с выходами элементов И первой группы, а вторые вхо-, ды - с выходами элементов И второй группы, выходы элементов ИЛИ группы являются группой информационных выходов модели, вторые входы схем сравнения подключены к информационным входам регистров, выходы схем сравнения подключены соответствен, но к первым входам первого и второго элементов И, вторые входы которыхай объединены и являются синхронизи" рующим входом модели, выход первого элемента И соединен с объединенными вторыми входами элементов И второй . группы, выход второго элемента И соединен с объединенными вторыми входами элементов И первой группы, ;а входы записи регистров являются :первым и вторым управляющими входами модели.Изобретение относится к вычислительной технике и может быть использовано при построении специализированных цифровых вычислительныхустройств для исследования графов,в частности для реализации оператора отображения.Известна модель ветви графа, содержащая счетчик импульсов, счетчикрегенерации, триггера, элементы И,элемент НЕ и блок индикации, кото Орая может использоваться при моделировании графов с циклическими участками 1 Д.Недостатком указанного устройстваявляется низкое быстродействие, 15обусловленное последовательным вовремени процессом формирования связей моделируемого графа.Наиболее близкой к предлагаемойявляется модель ветви графа, содержащая первый и второй задатчики адресов, выполненные в виде сдвиговыхрегистров, формирователь временныхинтервалов, триггеры, первый и второй блоки сравнения, элементы ИЛИ,элемент И, элемент НЕ, причем ин-.формационные входы регистров объединены и являются группой информационных входов модели, выходы каждого регистра соединены с первымивходами схем сравнения, выход второго задатчика адреса подключен к первому входу первого элемента И, выход которого соединен с первымвходом элемента ИЛИ, второй входкоторого подключен к выходу элемента НЕ, вход которого соединен свыходом второго задатчика адреса,первого триггера, первый выход которого подключен к второму входупервого элемента И, второй выход 40первого триггера соединен с первымвходом второго элемента И, выходкоторого подключен к первому входуформирователя временных интервалов 23.45Недостатком известного устройства является невозможность моделирования оператора отображения,Цель изобретения - расширениефункциональных воэможностей устройства путем обеспечения моделирования оператора отображения исследуемого графа.Поставленная цель достигаетсятем, что в модель ребра графа,содержащую первый и второй регистры, первую и вторую схемы сравнения,два элемента И, информационные входы регистров объединены и являютсягруппой информационных входов модели, выходы первого и второго регистров соединены с первыми входамисоответственно первой и второй схемсравнения, дополнительно введены первая и вторая группы элементов Ии группа элементов ИЛИ, причем вы ходы первого и второго регистров соединены с первыми входами элементов И соответственно первой и второй групп, первые входы элементов ИЛИ группы соединены с выходами элементов И первой группы, а вторые входы - с выходами элементов И второй группы, выхоДы элементов ИЛИ группы являются группой информационных выходов модели, вторые входы схем сравнения подключены к информационным входам регистров, выходы схем сравнения подключены соответственно к первым входам первого и второго элементов И, вторые входы которых объединены и являются син" хронизирующим входом модели, выход первого элемента И соединен с объединенными вторыми входами элементов И второй группы, выход второго элемента И соединен с объединенными вторыми входами элементов И первой группы, а входы записи регистров являются первым и вторым управляющими входами модели.На чертеже представлена функциональная схема модели ребра графа,Модель ребра содержит регистры 1 и 2, схемы 3 и 4 сравнения, элементы И 5 и 6, группы элементов И 7 и 8, группу элементов ИЛИ 9. Полюса 10-14 являются входами и выходами модели.В качестве регистров 1 и 2 могут быть применены регистры с параллельным входом и выходом, причем занесение информации должно быть возможно только при наличии разрешающего сигнала на полюсах 10 или 11.Схемы 3 и 4 сравнения предназначены для выдачи сигнала сравнения в случае, если код, хранимый в одном из регистров 1 или 2, совпадает с кодом, установленным на вход" ных полюсах.Входными полюсами 13 модель ребра подключена к информационному входу устройства, а выходными 14 к информационному выходу. Количество шин К .в магистралях входа и выхода устройства зависит от размерности моделируемого графа и должно быть равноК=Со 2 Мгде Й - количество узлов.Каждая шина магистрали служит для передачи одного разряда кода номера узла графа. Первая магистраль, с которой соединены входные полюса моделей ребер, служит для передачи кода узла, для которого моделируется оператор отображения, Вторая магистраль, с которой соединены выходные полюса всех моделей ребер, передает коды узлов, которые являются отображением.Устройство работает следующимобразом.1064281 20 оставитель С.Назароехред Ж.Кастелевич едактор А.Власенк ектор Г.Ршетник Заказ 10533 50 аж 70 бсударственногм изобретенийосква, Ж,Подписнкомитета СССРи открытийаушская наб., д. Ти НИИПИ Г по дел 13035, Филиал ППП "Патент", г. Ужгород, ул. ПроектнаяПредварительно в регистры моделей ребер по первой магистрали заносятся коды номеров узлов, которые связывают каждое ребро граа. Осуществляется это с помощью сигналов записи на полюсах 10 и 11.В процессе, моделирования на первую магистраль поступает код номера узла,для которого необходимо выпол- . нить операцию отображения. Схемы 3 и 4 сравнения сравнивают .эту инФормацию с содержимым регистров 1 и 2. Если сравнение произошло, то выходной сигнал одной иэ схем сравнения проходит через один из эле" ментов И 5 или б при наличии сигнала на полюсе 12 и разрешает выдачу кода, хранимого в одном из регистров, через группу элементов И иИЛИ на вторую магистраль, с которойсоединены выходные полюса моделейребер.5Сигнал на полюсе 12 предназначендля разнесения во времени моментоввыдачи кодов на выходные полюса сразу от нескольких моделей ребер в 0 случае, когда узел, для котороговыполняется операция отображения,имеет связь с несколькими узлами.Использование изобретения позволяет сократить время моделированияпутем распараллеливания решения приреализации оператора отображения,