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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН А С 06 Р 15/20 ИСАНИ РЕТЕНИЯ ван нко,СССР1979,ССР 1982 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНЯТИИ ВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Институт проблем моделв энергетике АН УССР(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯНАПРАВЛЕННЫХ ГРАФОВ(57) Изобретение относится к вычислительной технике и может быть использовано для решения задач организационного управления и теории графов.Цель изобретения - повышение достоверности работы устройства за счетконтроля наличия контуров на графе.Поставленная цель достигается тем,что устройство содержит блок управления, первый и второй блоки формирования технологии, блок моделей ветвей, генератор тактовых импульсов3 ил17 132 30 фа устройства подключен к третьемуЮ входу блока управления, выход меток 15 делирования,Описанные процессы подготовкиветвей к моделированию, временное моделирование и анализ ветвей, моделирование которых окончено (при моделировании сети в обратном направлении), продолжается до тех пор, покане окончится моделирование всех ветвей, входящих и свершившиеся узлы.В этом случае при обработке прерывания от модели ветви, которая последней окончила процесс моделирования,сигнал проверки свершения нетви сполюса 37 поступает на первый нходэлемента И 24, на второй вход указанного элемента - сигнал отсутствия за-ЗОнятых моделей ветвей с полюса 51, ана третий вход через элемент НЕ 28нулевая метка свершения из узла 7памяти. С выхода элемента И 24 сигнал наличия цикла поступает на выход ной полюс 70. При этом в узле 6 памяти останутся метки по тем адресам,которые соответствуют номерам узлов,принадлежащих контуру сети.Для определения номеров узлов се Оти, принадлежащих контуру, необходимо подать их на входной полюс 68, который поступает на вход считыванияузла 6 памяти. Наличие метки "1" поопределенным адресам определит номера узлов, принадлежащих контуру. Устройство для моделированйя направленных графов, содержащее блок управления, первый блок формирования топологии, блок моделирования ветвей, генератор тактовых импульсов, вход запуска устройства подключен к входу 55 запуска первого блока формирования топологии, вход кода номера начальной ветви графа устройства подключен сматринаемого узла, продолжается потех пор, пока не обнаружится ветвьс нулевой меткой свершения, или пока не проанализируются все исходящиеветви. В первом случае продолжается процесс временного моделирования домомента окончания процесса моделирования следующей моделью ветви. В случае, если все анализируемые ветви.имеют единичные метки свершения, производится подготовка к процессу моделирования ветвей, входящих в рассматриваемый узел. После этого продолжается процесс временного моФормула изобретения к первому информационному входу п рного блока формирования топологии,вход считывания номеров узлов контура графа устройства подключен к первому входу блока управления, входметок контура графа устройства подключен к второму входу блока управления, вход меток свершения ветвей граконтура пути на графе устройства подключен к первому выходу блока управления, выход признака наличия циклаустройства подключен к второму выходу блока управления, выход значения наидлиннейшего пути на графе устройства подключен к третьему выходублока управления, первый выход генератора тактовых импульсов подключенк первому тактовому входу первогоблока формирования топологии и четвертому входу блока управления, второй выход генератора тактовых импульсов подключен к второму тактовомувходу первого блока формирования топологии, выход номера модели блокамоделей ветвей подключен к пятомувходу блока управления, выход признака отсутствия занятых моделей ветвиблока моделей ветвей подключен к шестому входу блока управления, выходпрерывания блока моделей ветвей подключен к седьмому входу блока управления, выходы с четвертого по седьмой блока управления подключены соответственно к информационным входамс перого по четвертый блока моделирования ветвей, выход проверки свершения ветви графа первого блока формирования топологии подключен к восьмому входу блока управления, выходпризнака результата расчета длиннейшего пути первого блока формированиятопологии подключен к девятому входу блока управления, выход номера анализируемой ветви графа первого блокаформиронания топологии подключен кдесятому входу блока управления, выход номера подготовляемой к моделированию ветви первого блока формирования топологии подключен к одиннадцатому входу блока управления, выходпоиска свободной ветви графа первогоблока формирования топологии подключен к двенадцатому входу блока управления, выход поиска прерывания первого блока формирования топологииподключен к тринадцатому входу блока1 р, в ( ц я %х с 1, ц(г р;а р ж;Ъмо ГО узццрафа г рвого бл к формирования топоцо ци цодк.очсц к четырнадцатому вхоу бпока управления, восьмой,девнтыц и десятый выходы блока управления подклкиены соответственнок второму, третьему и четвертому инФормационным входам первого блока формирования топологии, при этом блок управления содержит четыре узла па мяти, пять элементов И, два триггера, элемент НЕ, три элеьецта задержки и узел измерения длццейшего пути,причем в блоке упр влеция входы с первого по пятый блока управления подклю чень соответственно к входу чтения первого узла гамяти, информационному входу второго узла памяти, информационному входу первого узла памяти,первому входу первого элемента И и ад ресцому входу третьего узла памяти, шестой вход блока управления подключен к первым входам второго и третьего элементов И, седьмой вход блока управления подключен к входу чтения третьего узла памяти, входу первого элемента задержки и входу установки в ноль первого триггера, восьмой вход блока управления подключен к второму входу второго элемента И, девятый 30 вход блока управления подключен к первому входу четвертого элемента И, первый выход блока управления подключен к выходу первого узла памяти,выход третьего элемента И подключен к З 5 входу установки в ноль первого триггера и второму выходу блока управления, третий выход которого подключен к выходу четвертого элемента И, четвертый выход блока управления подключен к выходу четвертого узла памяти, выход первого элемента И подключен к входу узла измерения длиннейшего пути и пятому выходу блока управления, шестой выход блока управления подклю-ф 5 чен к счетному входу второго триггера, седьмой выход блока управления подключен к входу считывания четвертого узла памяти, адресному входу первого узла памяти и входу второго элемента 5 ф задержки блока управления, выход третьего узла памяти подключен к восьмому выходу блока управления, выход второго узла памяти подключен к входу элемента НЕ и девятому вьмоду блока управления, десятый выход блока управления подключен к выходу пятого элемента И, инверсный выход первого триггера полк ь 1 ц ь ц рвом входпятого элемента И, выход первого элемента задержки по;к.ю 1 ец к вхолу записи второго у.ца памяти ц входу третьего элемента задержки, выход второго триггера цодклнчен к второму входу первого элемента И,выход второго элемента задержки подключен к информационному входу третьего узла памяти, выход третьего элемента задержки подключен к второму входу пятого элемента И, выход элемента НЕ подключен к третьему входу второго и второму входу третьего элементов И, выход второго элемента И подключен к счетному входу первого триггера, выход узла измерения длиннейшего пути подключенк второму входу четвертого элемента И, о т л и ч а ю щ е е с я тем, что с целью повышения достоверности работы устройства за счет контроля наличия контуров на графе, оно дополнительно содержит второй блок формирования топологии, первый и второй выходы генератора тактовых импульсов подключены соответственно к первому и второму тактовым входам второго блока формирования топологии, выход номера подготавливаемой к моделированию ветви второго блока формирования топологии подключен к пятнадцатому входу блока управления, выход поиска свободной ветви второго блока формирования топологии подключен к шестнадцатому входу блока управления, выход номера анализируемой ветви второго блока формирования топологии подключен к семнадцатому входу блока управления, выход проверки свершения ветви второго блока формирования топологии подключен к восемнадцатому входу блока управления, выход поиска прерывания второго блока формирования топологии подключен к девятнадцатому входу блока управления сети, выход номера загружаемого узла графа второго блока формирования топологии подключен к двадцатому входу блока управления, вход номера конечной ветви графа устройства подключен к первому информационному входу второго блока формирования топологии, одиннадцатый, двенадцатый и тринадцатый выходы блока управления подключены соответственно к второму, третьему и четвертому информационным входом второго блока формирования топологии, четырнадцатый выход блока управления подключенк входу запуска второго блока форми-рования топологии, при этом в блокуправления дополнительно введены шестой элемент И и семь элементов ИЛИ,причем в блоке управления одиннадцатый и пятнадцатый входы блока управления подключены соответственно кпервому и второму входам первого элемента ИЛИ, двенадцатый и шестнадцатыйвходы блока управления подключены со ответственно к первому и Второму входам второго элемента ИЛИ, десятый исемнадцатый входы блока управленияподключены соответственно к первомуи второму входам третьего элемента 15ИЛИ, восьмой вход блока управленияподключен к первому входу четвертогоэлемента ИЛИ, восемнадцатый вход блока управления подключен к второмувходу четвертого элемента ИЛИ и третьему входу третьего элемента И, четырнадцатый и двадцатый входы блокауправления подключены соответственнок первому и второму входам пятогоэлемента ИЛИ, тринадцатый и девятнадцатый входы блока управления подподключены соответственно к первому и второму входам шестого элемента ИЛИ, прямой выход первого триггера подключен к первому входу шестого элемента И, выход третьего элемента задержки подключен к второму входу шестого элемента И, выход первого элемента ИЛИ блока управления подключен к адресному входу четвертого узла памяти и входу записи третьего узла памяти, выходы элементов ИЛИ с второго по седьмой подключены соответственно к входу второго элемента задержки, первому входу седьмого элемента ИЛИ, входу чтения второго узла памяти, входу запнси первого узла памяти, счетному входу второго триггера и адресному входу второгоузла памяти, выход третьего узла памяти подключен к второму входу седьмого элемента ИЛИ и одиннадцатому выходу блока управления, выход второго узла памяти подключен к двенадцатому выходу блока управления, выход шестого элемента И подключен к тринадцатому выходу блока управления, выход второго элемента И подключен к четырнадцатому выходу блока управления .1322304 Составитель В.СмирновРедактор Н.Рогулич Техред И.Попович Корректор Г. Рещетник Заказ 2866/46 Тирад 672 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раущская наб., д.4/5 Производственно-полиграфическое предприятие, г.ужгород, ул. Проектная, 4Изобретение относится к ычислительной технике и может быть исполь 50 зовано для решения задач организационного управления и теории графов.Цель изобретерия - повышение достоверности работы устройства за счет контроля наличия контуров на графе.На фиг,1 изображена структурная схема устройства; на фиг.2 - струк О турная схема блока формирования топологии; на фиг,3 - структурная схема блока моделей ветвей.Устройство содержит блок 1 управления, первый блок 2 формирования то пологии, второй блок 3 формирования топологии, блок 4 моделей ветвей, ге нератор 5 тактовых импульсов.Блок 1 управления содержит с первого по четвертый узлы 6-9 памяти, 20 первый и второй триггеры 10 и 11, с первого по седьмой элементы ИЛИ 12 18, с первого по третий элементы 19-21 задержки, с первого по шестой элементы И 22-27, элемент НЕ 28, узел25 29 измерения длиннейшего пути, вход 30, меток контура графа устройства, вход 30 меток свершения ветвей графа устройства, выходы 31 и 32 номера подготавливаемой к моделированию ветви блоков 2 и 3, выходы 33 и 34 поиска свободной ветви блоков 2 и 3, выходы 35 и 36 номера анализируемой ветви блоков 2 и 3, выходы 37 и 38 проверки свершения ветви блоков 2 и 35 3, выходы 39 и 40 поиска прерывания блоков 2 и З,выходы 41 и 42 номера загружаемого узла графа блоков 2 и 3, информационные входы 43-48 блоков 2 и 3, выход 49 признака результата расчета длиннейшего пути блока 2, выход 50 номера модели блока 4, выход 51 отсутствия занятых моделей ветвей, выход 52 прерывания блока 4, информационные входы 53-55 блока 4, первые 45 и вторые тактовые входы 56 и 57 блока 2, первые и вторые тактовые входы 58 и 59 блока 3, информационный вход 60 блока 4, первый и второй выходы 61 и 62 генератора 5, управляющий вход 63 блока 1, вход 64 запуска блока 2, ход 65 номера начальной ветви графа устройства, вход 66 запуска блока 3, вход 67 кода номера конечной ветви графа устройства, вход 68 55 считывания номеров узлов контура графа устройства, выход 69 меток контура пути на графе устройства, выход 70 призака нппичия цикла устройста, ыход 71 знач пия аидлиннейшего пути на графе.Блоки 2 и 3 формирования топологии каждый содержит узел 72 памятиномеров начальных узлов ветвей сети,узел 73 памяти номеров конечных узлов ветвей сети, узел 74 памяти номеров выходящих ветвей узлов сети,узел 75 памяти номеров входящих ветвей узлов сети, узел 76 памяти номеров первой выходящей ветви узлов сети, узел 77 памяти номеров первойвходящей ветви узлов сети, регистр78 номера выходящей ветви, регистр79 номера ветви, регистр 80 номераконечного узла ветви, регистр 81 конечного узла сети, триггеры 82 и 83,дешифраторы 84 и 85, дешифратор 86сравнения кодов, линии 87 и 88 задержки, элементы ИЛИ 89-95, элементыИ 96-101, элемент НЕ 102,Узлы 72-77 памяти предназначеныдля хранения информации о топологиипри моделировании сети в прямом направлении, узел 72 памяти - для хранения номера начального узла ветвипо адресу номера этой ветви, узел73 памяти - для хранения номера конечного узла ветви по адресу номераданной ветви, узел 76 памяти - дляхранения номера первой из спискаветвей, выходящих иэ данного узла,по адресу номера узла, узел 77 памяти - для хранения номера первой изсписка ветвей, входящих в данныйузел, по адресу номера узла, узел74 памяти - для хранения, в видесписков, номеров ветвей, выходящихиз узлов сети, узел 75 памяти - дляхранения, в виде списков, номеровветвей, входящих в узлы сети.Регистр 78 предназначен для промежуточного хранения номера ветви приопределении ветвей, выходящих из узла, регистр 79 - для промежуточногохранения номеров ветвей, входящих вузел, регистр 80 - для хранения номера анализируемого узла сети, регистр81 - для постоянного хранения номераконечного узла сети.Дешифраторы 84 и 85 состояния предназначены для сравнения поступающихна них кодов с кодовой комбинациейХ, заданной постоянно в схеме, а дешифратор 86 сравнения кодов - дляпоразрядного сравнения кодов из регистров 80 и 81.13223Каждая члель 103 ветви содержит формирователь 104 временного интервала, триггерь 105 и 106, элементы И 107-112, элемент ИЛИ 113 и элементы 114 и 115 задержки.5Схема 116 поиска моделей ветвей содержит шифратор 117 адреса и элементы ИЛИ 118-120.Работу устройства рассматривают на примере контроля наличия контуров в 10 рассчитываемой сети и определения номеров узлов сети, которые принадлежат замкнутым путям.Устройство работает следующим образом. 15В узлы 72-77 памяти блока 2 формирования топологии в виде списков заносится информация о топологии моделируемой сети. Регистры 78-80 обнуляются, а н регистр 81 заносится код 20 номера конечного узла сети, Триггеры 82 и 83 блока 2 формирования топологии устанавливаются н нулевое состояние. В узлы 72-77 памяти блока 3 формирования топологии н виде списков . 25 заносится информация о топологии сети, которая является зеркальным отображением моделируемой сети, т.е. в узле 72 памяти по адресу каждой ветви записывается номер ее конечного узла,30 н узел 73 памяти по адресу каждой ветви - номер ее начального узла, в узел 74 памяти в виде списков номера входящих ветвей, в узел 75 памяти в виде списков - номера выходящих ветвей, в узел 76 памяти по адресу каждого узла - номер первой входящей ветви, в узел 77 памяти по адресу номера каждого узла - номер первой выходящей ветви. 40Регистры 78-81 обнуляются, Триггеры 82 и 83 устанавливаются в нулевое состояние. В узел 8 памяти блока 1 управления записывается информация о длительности каждой ветви модели руемой сети. Узел 7 памяти обнуляется. В узел 6 памяти записываются метки по тем адресам, номера узлов которых есть н моделируемой сети, Триггеры 11 и 10 блока 1 управления устанавли.50 ваются в нулевое состояние. Триггеры 105(1), 105(2), , 105(п) и 106(1), 106(2)106(п) блока 4 моделей ветвей устанавливаются в нулевое состояние. 55После начального установа на полюс 65 блока 2 формирования топологии подается код номера ветви, выхо 04 4дящей из начального узла сети, а на полюс 63 блока 3 формирования топологии - код номера ветви, входящей н конечный узел сети.В некоторый момент времени сигнал "Пуск", поступающий на полюс 64 блока 2 формирования топологии, проходит через элемент ИЛИ 95 и устанавливает триггер 83 в единичное состояние, что разрешает прохождение серии импульсов ГИ 1 (полюс 57) и ГИ 2 (полюс 56) соответственно через элементы И 100 и 101, Кроме этого, сигнал "Пуск" поступает на вход элемента 87 задержки и на вход считывания узла 72 памяти начальных узлов. При поступлении сигнала считывания н узле 72 памяти происходит считывание ячейкипамяти по адресу номера ветви, поступающего с полюса 65, Так как ветвь выбрана как выходящая иэ начального узла моделируемой сети, на выходе узла 72 памяти появляется код начального узла, который поступает через элемент ИЛИ 90 на адресный вход узла 76 памяти первой выходящей ветви,Через время задержки, достаточное для считывания информации из узла 72 памяти, сигнал Пуск появляется на выходе элемента 87 задержки и поступает через элемент ИЛИ 89 на вход считынания узла 76 памяти. По этому сигналу происходит считывание из узла 76 памяти кода номера ветни,являющейся первой в списке ветвей, выходящих из начального узла сети. Код первой выходящей ветви с выхода узла 76 памяти через элемент ИЛИ 91 поступает на информационный вход регистра 78 выходящей ветви и записывается в него по первому импульсу ГИ 1, поступившему на управляющий вход регистра с выхода элемента И 100.Записанный код первой выходящей ветви с выхода регистра 78 поступает на адресный вход узла 74 памяти, а также через выходной полюс 31 блока 2 формирования топологии и элемент ИЛИ 12 блока 1 управления - на адресный нход узла 9 памяти и информационный вход узла 8 памяти блока 1 управления.Затем импульс ГИ 2, сдвинутый относительно импульса ГИ 1, поступает на вход считывания узла 74 памяти, осуществляя выборку, по адресу первой выходящей из начального узла ветви, номера второй ветви, выходящей иэ того же узла. Одновременно по им 1322304пульсу ГИ 2 с и ца. псцс ка с цссццсцоймодели через выходной цолнц 33 блока2 формирования топологии и элементИЛИ 13 блока 1 управления поступаетна вход считывания узла 9 памяти, на 5вход элемента 20 задержки, на входзаписи узла 6 памяти блока 1 управления и на входной полюс 60 поиска свободной модели блока 4 моделей ветвей.Одновременно код номера загружаемогоузла сети через выходной полюс 61 блока 2 формирования топологии и элементИЛИ 16 блока 1 управления подаетсяна адресный вход узла 6 памяти. Осуществляется считывание кода длительности загружаемой ветви сети с узла9 памяти. Этот код через выходнойполюс 53 блока 1 управления поступаетв блок 4 моделей ветвей,Сигнал поиска свободной модели 20ветви с полюса 60 поступает на входыэлементов И 109(1) и 110(1) первоймодели 103(1) ветви блока 4 моделейветвей. Так как все модели ветвейсвободные, триггер 105(1) находитсяв нулевом состоянии и сигнал с выхода элемента 110(1) через элемент115(1) задержки поступает на вход установки единичного состояния триггера 105(1). Триггер через время задерж 30ки, достаточное для срабатывания всехэлементов, устанавливается в единичное состояние, что означает занятостьданной модели процессом моделирования. Одновременно сигнал с выхода эле мента И 110 поступает на первый входэлемента И 111, и через элемент ИЛИ 113на вход шифратора адреса. На второйвход элемента И 111 через входной полюс 53 поступает код длительности вет 40ви. Этот код записывается в качествеисходной информации в формирователь104(1) временного интервала. С выходашифратора 117 адреса код номера модели ветви через полюс 50 поступает на 45адресный вход узла 9 памяти блока 1управления. Через время, достаточноедля организации описанных процессов,в блоке 4 моделей ветви на выходеэлемента 20 задержки блока 1 управления появляется сигнал, поступающийна вход записи узла 9 памяти номеровмоделируемых ветвей, Происходит запись номера загружаемой ветви сетипо адресу выбранной модели ветви. На 55этом заканчивается подготовка первойветви, выходящей из начального узласети, к процессу моделирования,1 рц сссгОтоцкс встс к с 1 сЛссирс)наццю ныполцяется с читыание ее номераиз блока 2 моделирования топологии,считывание ее длительности из ЗУ плительности блока 1 управления, поиск свободной от вычислений модели ветви блока 4 моделей ветвей, запись в формирователь временного интервала свободной модели кода длительности ветвей, запись цомера ветви сети по адресу модели ветви в узле 8. Кроме того, производится запись "0" в узел 6 памяти по адресу начального узла загружаемой ветви,Далее считанный из узла 72 памяти выходящих ветвей блока 2 формирования топологии по адресу номера первой выходящей из узла ветви код номера следующей ветви поступает через элемент ИЛИ 91 на информационный вход регистра 78 и с приходом второго импульса ГИ записывается в укаэанный регистр, Записанный в регистр78 код снова поступает на адресный вход узла 74 памяти, а также через полюс 31 и элемент ИЛИ 12 - на адресный вход узла 9 памяти и информационный вход узла 8 памяти блока 1 управления. С приходом второго импульса ГИ 2 иэ узла 9 памяти длительностей считывается длительность второй исходящей иэ узла ветви и поступает через полюс 53 на входы элементов И 111(1), 111(2)111(п) всех моделей ветвей блока 3 моделей ветвей. Одновременно через полюс 60(1)на входы элементов И 109 и 110 поступает сигнал поиска свободной моделиветви, Так как триггер 105(1) первоймодели ветви находится в единичном состоянии, сигнал поиска свободной модели с выхода элемента И 109(1) через полюс 60(2) поступает на входы элементов И 109(2) и 110(2) второй модели ветви. Так как триггер 105(2) этой модели ветви находится в нулевом состоянии, сигнал с выхода элемента И 110 поступает на вход элемента И 111. На второй вход элемента И 111 поступает код длительности ветви, который и записывается в формирователь 104(2) временного интервала. Одновременно сигнал с выхода элемента И 110 через элемент 115(2) задержки устанавливает триггер 105(2) в единичное состояние.Кроме того, сигнал с выхода элементаИ 110 через элемент ИЛИ 113 поступа1 122 30 40 с т цд шифр,тт р17,;рд, г; фр - мцруетгя ьтд цм рдццой мдс тц ветви. Этот кол чс рсз цолюг 50 птс ту - цдг цд ддрсгный вход уззпа 8 памяти цмероц мопсругмьтх ветвей блскд 1 управления. По приходу гигцдта здпиги с элемента 20 задержки происходит запись номера ветви сети но адресу номера модели ветви.Описанный процесс подготовки вет вей сети к моделированию продолждется до тех пор, пока не подготовлена последняя ветвь, выходящая из данно го узла, В этом случае по адресу ее номера из узла 74 памяти гчитывается код Х, который эаписывдетг.я в регистр 78, Выход региг.тра 78 подключен к дешифратору 84 состояния, поэтому на выходе последнего появляется сигнал, Этот сигнал погтупдет на 20 вход триггера 83, сбрасывая его в нулевое состояние. Кроме того,сигнал с выхода дешифратора через злемент ИЛИ 92 поступает на полюс 39, с25 которого сигнал поиска прерывания через элемент ИЛИ 17 пОступает на вход триггера 11 блока 1 управления, устанавливая его в единичное состояние. Одновременно сигнал поиска прерывания поступает на полюс 55 блока 4 моделей ветвей. Так как в описываемый момент (подготовлены все ветви, исходящие из начального узла сети) нет моделей ветвей, которые закончили моделирование, сигнала прерывания из блока моделей ветвей на полюсе 52 не будет,и триггер 11 блока 1 управления остается в единичном состоянии. Единичное состояние триггера прерывания 11 разрешает прохождение импульсов серии ГИ 2 через элемент И 22 на счетный вход узла 29 измерения длиннейшего пути блока 1 управления45 и через полюс 54 на элементы И 112(1), 112(2)112(п) всех моделей ветвей блока 4 моделей ветвей. У тех моделей ветвей, у которых триггер 105 находится в единичном состоянии, импульсы серии ГИ 2 поступают на вход формирователей 104 временного интервала, Так продолжается до тех пор, пока хотя бы один изформирователей 104 временного интервала не выдает сигнал об окончании процесса временного моделирования длительности ветви. 8Втм г ч 1 тгигд и г тыходд ф 1 рьттр звдт гц 104 (1), 10 ( 1 104 (тт) врг",с нного цнтс рва цд погтупд - ют цд глинн цьн дтригтеров106 (11, 106 (2) 106 (и), утдтдв - итдя цх вдттцичцсогтоянтте. Олцо - врсьтто гтг;тт г выкс;тн фрмттрсвд - телей 10 (1), 10 (2 104 (и) погтупдют черелгмецт ИПИ 118 на вход поигка нрерывдцня (1,1) первой модели ветви, В глучде, егт триггер 106(1) первой модели ветви находится в единичном состоянии, гигцал прерываниявыхода злгментд И 08(1) поступает через злгмгцт ИЛИ 119 и полюс 52 в блок 1 управления. Кроме того, гцгнал прерывания г выхода элемента И 108(1) поступает ца вход триггера 105(1), устанавливая его в цулевое состояние, Одновременно гитцал прерывания г выхода злеметд И 108(1) через элемент ШП 1 113(1) по. ступает на вход шифратора 117, а через элемент 114(1) задержки устанавливает триггер 106(1) в нулевое согтояние, С шифратора 117 код номера модели ветви, окончившей моделирование, через полюс 50 поступает на адрег.цый вход узла 8 памяти номеров моделируемых ветвей блокауправления, На вход считывания указаццого узла памяти с полюса 52 поступает сигнал прерывания. Происходит считывание, по номеру модели ветви, номера ветви сети. Этот код поступает на полюса 43 и 44, а через элемент ИЛИ 18 на адресный вход узла 7 памяти. Через время, достаточное для считывания номера ветви, на вход записи узс ла 7 памяти через элемент 19 задержки поступает сигнал, и по адресу номера ветви в узел 7 памяти записывается "1", характеризующая завершение процесса моделирования данной ветви, Через время, достаточное для записи метки свершения, сигнал с выхода элемента 21 задержки поступает на первые входы элементов И 26 и 27. Так как триггер 24 обратного хода в данный момент находится в нулевом состоянии, на втором входе элемента И 26 присутствует разрешающий потенциал, и сигнал начала анализа свершения ветви поступает с его выхода на полюс 47 и далее в блок 2 формирования топологии. На втором входе элемента И 27 присутствует запрещающий потенциал с единичного выходатриггера 10, поэтому сигнал начала анализа ветви в блок 3 формирования топологии не поступает, Это исключа-, ет включение блока 3 формирования топологии на этапе моделирования сети в прямом направлении.В блоке 2 формирования топологии код номера ветви с полюса 43 поступает на адресный вход узла 73 памяти конечного узла, а сигнал начала ана лиза ветви с полюса 47 поступает на вход триггера 82 и устанавливает его в единичное состояние, Единичное состояние триггера 82 разрешает прохождение импульсов ГИ 1 через элемент 15 И 98, а импульсов ГИ 2 - через элемент И 99, Кроме того, сигнал начала анализа поступает на вход элемента 88 задержки и на вход считывания узла 73 памяти. Происходит считывание,. 20 ячейки памяти по адресу номера свершившейся ветви, т,е. считывание номера конечного узла ветви. Код считанного номера узла с выхода узла 73 памяти поступает на адресные входы узла 77 памяти первой выходящей ветви и на информационные входы регистра 80 конечного узла. Через время задержки,достаточное для считывания информации из узла 73 памяти, сигнал наЗ 0 чала анализа ветви поступает на управляющий вход регистра 80 конечного узла и на вход считывания узла 77 памяти. По этому сигналу происходит запись номера конечного узла ветви в 35 регистр 80 и считывание номера первой, входящей в этот узел, ветви с узла 77 памяти. Код номера первойФ входящей ветви с выхода узла 77 памяти поступает через элемент ИЛИ 93 40 на информационный вход регистра 79 входящей ветви и записывается в него по первому импульсу ГИ 1, поступающему на управляющий вход регистра с выхода элемента И 98. С выхода регистра 79 45 код номера первой входящей ветви поступает через полюс 35 и элементы ИЛИ 14 и 18 на адресный вход узла 7 памяти блока 1 управления, на адресный вход узла 75 памяти входящих ветвей и на дешифратор 85. По первому импульсу ГИ 2 сигнал проверки свершения ветви с выхода элемента И 99 поступает через элемент ИЛИ 96 на вход считывания узла 75 памяти, а через полюс 37 и элемент ИЛИ 15 - на вход считывания узла 7 памяти блока 1 управления. Метка свершения, считанная по адресу первой ветви, с выхода узла 7 памяти поступает через полюс 45 в блок 2 формирования топологии, а через полюс 46 - в блок 3 формирования топологии. Если метка отсутствует, нулевой сигнал метки с полюса 45 через элемент НЕ 102 и элемент ИЛИ 94 сбрасывает триггер 94 в нулевое состояние. Кроме того, сигнал с выхода элемента НЕ 102 поступает через элемент ИЛИ 92 на полюс 39 поиска прерывания. Наличие нулевого сигнала метки свершения ветви означает, что хотя бы одна из входящих в данный узел ветвей не свершилась и, следовательно, в данном узле не сформирована функция И для всех входящих в него ветвей.В этом случае сигнал поиска прерывания с полюса 39 через элемент ИЛИ 17 поступает на единичный вход триггера 11 и одновременно через полюс 55 на вход элемента ИЛИ 118 узла 116 поиска моделей ветвей блока 4 моделей ветвей. С выхода элемента ИЛИ 118 сигнал поступает на входы элементов И 107(1) и 108(1) первой модели ветви. Если модель ветви закончила процесс моделирования ветви, которая еще не анализировалась, триггер 106 находится в единичном состоянии, и тогда сигнал с выхода элемента И 108 снова поступает на вход шифратора адреса 117, а также через элементИЛИ 120 выдает сигнал прерывания. Блок 1 управления, получив номер модели ветви и сигнал прерывания, повторяет все описанные операции, связанные с анализом свершения ветви. Если же в блоке 4 моделей ветвей не имеется моделей, у которых триггер 106 находится в единичном состоянии, процесс анализа не проводится и импульсы серии ГИ 1 продолжают поступать через элемент И 22 в узел 29 определения длиннейшего пути блока 1 управления и в формирователи временного интервала моделей ветвей блока 4 моделей ветвей.Если сигнал метки свершения ветви с полюса 45 имеет единичное значение, т.е, моделирование данной ветви закончилось, этот сигнал выдает разрешение на прохождение импульса ГИ 2 через элемент И 96 на вход считывания узла 75 памяти входящих ветвей. На адресные входы последнего в это время поступает код номера первой входящейветви с вьюода регистра 79. По апресу первой входящей ветви из узла 75 памяти считывается код номера второй входящей в данный узел ветви. Этот код поступает через элемент ИЛИ 93 на информационные входы регистра 79 и записывается в него с приходом второго импульса ГИ 1, Далее осуществляется опрос метки свершения данной ветви. Если ветвь свершилась, осуще ствляется переход к опросу свершения следующей ветви, входящей в рассматриваемый узел, и т.д.Описанный процесс анализа свершения ветвей продолжается до тех пор, 15 пока не опрошены все ветви, входящие в рассматриваемый узел. В этом случае по адресу последнего номера ветви из узла 75 памяти считывается код Х, определяющий конец списка входящих 20 в данный узел ветвей. Код Х записывается в регистр 79 входящей ветви и далее поступает на вход дешифратора 85 состояния, вырабатывая сигнал конца списка, который проходит через 25 элементы ИЛИ 94 и 95 и устанавливает триггеры 82 и 83 соответственно в нулевое и единичное состояние. Сигнал с выхода дешифратора 85 поступает также на первый вход элемента И 86,вто рой вход которого связан с выходом дешифратора 86 сравнения кодов, который сравнивает коды, хранящиеся в регистре 81 конечного узла сети и в регистре 80 конечного узла ветви. Регистр 81 хранит код конечного узла сети, а регистр 80 - код рассматриваемого узла сети, сформировавшего функцию коньюнкции в данный момент времени. Если значение этих кодов не 40 совпадает, сигнал с выхода дешифратора 85 поступает через элемент ИЛИ 89 на вход считывания узла 76 памяти первой выходящей ветви, на адресный вход которого в этот момент времени ф 5 поступает код номера сформированного узла сети. Начинается процесс подготовки к моделированию тех ветвей, которые выходят иэ данного сформированного узла. 50Если в сети отсутствуют циклы (контуры), описанный процесс подготовки ветвей к моделированию, времен- ное моделирование и анализ ветвей, моделирование которых закончено, че редуются в укаэанном порядке и повторяются до тех пор, пока не сформируется конечный узел сети, В этом случае дешифратор 86 сравнения кодов блока 2 формирования топологии выдает разрешение на прохождение сигнала с выхода дешифратора 85 через элемент И 97 на выходной полюс 49, что соответствует концу моделирования заданной сети. Сигнал с полюса 49 поступает на вход элемента И 12 блока 1управления и разрешает выдачу на внешнее устройство величины длиннейшего пути сети с узла 7, сигнал наличия циклов с выхода элемента И 24 отсутствует. Все ячейки узла 6 памяти обнулены.Если в топологии сети есть контур, описанный процесс моделирования сети в прямом направлении остановится в момент отработки прерывания от последней ветви, моделирование которой окончено. Отличительной чертой указанного момента является отсутствие моделей ветвей занятых процессом моделирования, при наличии несвершенных узлов сети, При этом при проверке свершения узла, во время обработки прерывания от последней модели ветви, которая занята процессом моделирования, сигнал проверки свершения ветви с полюса 37 поступает на первый вход элемента И 23 блока 1 управления. На второй вход этого элемента поступает разрешающий потенциал с выхода элемента ИЛИ 120 блока 4 моделей ветвей, что сигнализирует об отсутствии занятый моделей ветвей, Так как в рассматриваемый узел входят ветви, моделирование которых еще не происходило, наступает момент, когда нулевой сигнал метки свершения ветви с узла 7 памяти блока 1 управления через элемент НЕ 28 поступает на третий вход элемента И 23. На выходе последнего появляется сигнал, который поступает на вход триггера 10, устанавливая его в единичное состояние. Кроме того, сигнал с выхода элемента И 23 поступает в блок 3 формирования топологии. Начинается процесс моделирования сети в обратном направлении. При этом в узле 6 памяти останутся метки по тем адресам, которые соответствуют номерам узлов, принадлежащих контуру сети, и по тем адресам, которые соответствуют номерам узлов, связанных с узлами контура цепочкой входящих ветвей.Сигнал с полюса 64 проходит через элемент ИЛИ 95 и устанавливает триггер 83 бпока 3 формирования топологии в единичное состояние. Единичное состояние триггера 83 разрешает прохожление серии импульсов ГИ через элемент И 100, а серии импульсов ГИ 2 через элемент И 101. Кроме того, сигнал с полюса 64 поступает на вход элеэлемента 87 задержки и на вход считывания узла 72 памяти.На адресные входы последнего поступает код номера 0 ветви, входящей в конечньй узел сети. Так как в узле 72 памяти по адресу ветвей моделируемой сети записаны их конечные узлы, по приходу сигнала считывания из узла 72 памяти считыва ется код конечного узла сети. Этот код поступает через элемент ИЛИ 90 на адресный вход узла 76 памяти первой входящей ветви. Через время, достаточное для считывания информации 20 из узла 72 памяти, сигнал с полюса 64 появляется на выходе элемента 87 задержки и поступает через элемент ИЛИ 89 на вход считывания узла 76 памяти.По этому сигналу происходит считывание кода номера первой ветви, входящей в конечный узел сети, Код номера первой входящей ветви с выхода узла 76 памяти поступает через элемент ИЛИ 91 на информационный 30 вход регистра 78 и записывается в него по первому импульсу ГИ 1, поступающего на управляющий вход регистра с выхода элемента И 100.Записанный код первой входящей 35 в конечный узел ветви с выхода регистра 78 поступает на адресный вход узла 74 памяти, а также через полюс 31 и элемент ИЛИ 12 - на адресный вход узла 9 памяти и информационный 40 вход узла 8 памяти номеров моделируемых ветвей блока 1 управления,Импульс ГИ 2, сдвинутый относительно импульса ГИ 1, поступает на вход считывания узла 74 памяти бло ка 3 формирования топологии, и по адресу первой входящей в конечный узел ветви считывается в код номера второй ветви, входящей в тот же узел. Одновременно по импульсу ГИ 2 сигнал 50 поиска свободной модели с выхода элемента И 101 через полюс 33 и элемент ИЛИ 13 поступает на вход считывания узла 9 памяти,на вход записи узла 6 памяти,на элемент 20 задержки бло Вка управления, на полюс 60 поиска свободной модели блока 4 моделей ветвей. По сигналу считывания и адресу номера первой входящей в коненый узел ветви осуществляется считывание кода длительности этой ветви из узла 5. По этому же сигналупроисходит запись метки 0 в узел6 памяти по адресу номера загружаемого узла, поступаемого с выхода элемента ИЛИ 21 блока 3 формированиятопологии через полюс 42. Одновременно сигнал поиска свободной моделис полюса 60 поступает на входы элементов И 109(1) и 109(2) блока 4 моделей ветвей, Так как все моделиветвей свободные, триггер 105(1) первой модели находится в нулевом состоянии и сигнал с выхода элемента110(1) через элемент 115 задержки поступает на вход триггера 105(1) и устанавливает его в единичное состояние, что означает занятость процессом моделирования первой модели ветви. Одновременно сигнал с выхода элемента И 110(1) поступает на первыйвход элемента И 110(1) и через элемент ИЛИ 113(1) на вход шифратора адреса 117. На второй вход элементаИ 111(1) через полюс 53 поступаеткод длительности ветви, который и записывается в формирователь 104(1)временного интервала. С выхода шифратора 117 адреса код адреса моделиветви поступает на адресный входузла 7 памяти номеров моделируемыхветвей блока 1 управления. По поступлению сигнала с выхода элемента 20задержки происходит запись номераветви (в данном случае первой ветви,входящей в конечный узел сети) поадресу выбранной модели ветви. Наэтом заканчивается подготовка первой,входящей в конечный узел сети, ветви к процессу моделирования. Далеесчитанный по адресу номера первой,входящей в конечный узел, ветви изузла 74 памяти блока 3 формированиятопологии код номера второй, входящей в конечный узел, ветви поступает на информационный вход регистра43 и с приходом второго импульса ГИзаписывается в него. После этогоопять происходит поиск свободной отвычислений модели ветви, запись кода длительности в ее формировательвременного интервала, запись номера моделируемой ветви по адресу номера выбранной моделив узел 8 памяти блокауправления.Процесс подготовки ветвей, входящих в конечный узел сети, к процессу моделирования осуществляется дотех пор, пока не считывается последняя ветвь иэ списка входящих ветвей. 5По адресу ее номера в узле 74 памя -ти считывается код Х, который записывается в регистр 78 блока 3 формирования топологии,Сигнал поиска прерывания с полюсом 40 поиступает на вход триггера 11блока 1 управления и устанавливаетего в единичное состояние. Так как врассматриваемый момент нет моделейветвей, окончавших моделирование,сигнал прерывния отсутствует и триггер11 остается в единичном состоянии.Единичное состояние тирггера 11 разрешает прохождение импульсов серииГИ 1 на счетный вход узла 29 измерения длиннейшего пути и через полюс 54на все формирователи 104 временногоинтервала, триггера 105 которых находятся в единичном состоянии. Такпродолжается до тех пор, пока хотябы один из формирователей 104 временного интервала не выдает сигнал обокончании процесса временного моделирования,Сигналы с выхода формирователей104(1), 104(2) 104(п) временногоинтервала поступают на единичные входы триггеров 106 ( 1), 106 (2), , 106(п)и устанавливают их в единичное состояние. Одновременно сигналы с выходов 35формирователей 106(1), 106(2),.,106(п) поступают через элемент ИЛИ 118на вход поиска прерываний (1,1) первой модели ветви. Начинается этапобработки прерывания, аналогично эта пу обработки прерывания при моделировании сети в прямом направлении. Определяется номер модели ветви, окончившей моделирование.По этому номеру определяется код номера свершившейся ветви, записывается метка " 1"в узел памяти свершения по адресуномера ветви. Код номера свершившейся ветви поступает на полюса 43 и 44и далее в блоки формирования топологии. Сигнал прерывания с полюса 52поступает на вход элемента 19 задержки, и после времени задержки на элементах 19 и 21 появляется на выходеэлемента 21 задержки блока 1 управления, Этот сигнал поступает на первые входы элементов И 26 и 27. Таккак триггер 10 находится в единичномФ состоянии, на втором входе элемента И 26 присутствует запрещающий потенциал с нулевого выхода триггера 10. Поэтому сигнал с выхода элемента 21 задержки через элемент И 26 не проходит и на полюсе 47 присутствует запрещающий потенциал. Этим исключается запуск блока 2 формирования то" пологии при моделировании сети в обратном направлении. На втором входе элемента И 27 присутствует разрешающий потенциал с единичного выхода триггера 10. Поэтому сигнал начала анализа свершения ветви с выхода элемента И 27 поступает на полюс 48 и дальше на блок 3 формирования топологии.В блоке 3 формирования топологии код номера свершившейся ветви с полюса 43 поступает на адресный вход узла 73 памяти, а сигнал начала анализа свершения ветви с полюса 47 поступает на вход триггера 82 и устанавливает его в единичное состояние.Кроме того, сигнал с полюса 43 поступает на вход элемента 88 задержки и на вход считывания узла 73 памяти, где происходит считывание (по адресу номера свершившейся ветви) номера начального узла ветви. Код считанного номера узла с выхода узла 73 памяти поступает на адресные входы узла 77 памяти первой выходящей ветви и на информационные входы регистра 80 начального узла, Через время задержки, достаточное для считывания информации иэ узла 73 памяти, сигнал начала анализа свершения ветви поступает на управляющий вход регистра 80 начального узла и на вход считывания узла 77 памяти. По этому сигналу происходит запись номера начального узла ветви в регистр 80 и считывание из узла 77 памяти (по адресу номера начального узла ветви) кода номера первой выходящей иэ этого узла ветви. Далее этот код поступает в блок 1 управления, где проверяется свершение считанной ветви. Если ветвь не свершилась, процесс временного моделирования продолжается дальше. Если же первая ветвь,исходящая из рассматриваемого узла, имеет единичную метку свершения, из узла 75 памяти считывается код следующей ветви и производится проверка ее свершения. Процесс проверки свершения ветвей, исходящих из рас