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

 

Изобретение относится к вычислительной технике и может быть использовано для решения задач организационного управления и теории графов. Цель изобретения - повышение достоверности работы устройства за счет контроля наличия контуров на графе. Поставленная цель достигается тем, что устройство содержит блок управления , первый и второй блоки формирования технологии, блок моделей ветвей , генератор тактовых импульсов.- 3 ил.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕО.(ИХ

РЕСПУБЛИН (1У (11) А1 (51) 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМУ СВИ4ЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4021779/24-24 (22) 17.02.86 (46) 07.07.87. Бюл. У 25 (71) Институт проблем моделирования в энергетике АН УССР (72) А.Г.Додонов, А.А.Котляренко, В.П.Приймачук и А.М.Щетинин (53) 681.325(088.8) (56) Авторское свидетельство СССР

Ф 744593, кл. С 06 F 15/20, 1979.

Авторское свидетельство СССР

1(1161951, кл. С 06 F 15/20, 1982. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

НАПРАВЛЕННЫХ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач организационного управления и теории графов.

Цель изобретения — повышение достоверности работы устройства за счет контроля наличия контуров на графе.

Поставленная цель достигается тем, что устройство содержит блок управления, первый и второй блоки формирования технологии, блок моделей ветвей, генератор тактовых импульсов..

3 ил..

1322304

И обретение относится к «ычислительной технике и может быть исполь50 зовано для решения задач организационного управления и теории графов.

Цель изобретерия — повышение достоверности работы устройства за счет контроля наличия контуров на графе.

На фиг.1 изображена структурная схема устройства; на фиг.2 — струк- 10 турная схема блока формирования топологии; на фиг.Э вЂ” структурная схема блока моделей ветвей.

Устройство содержит блок 1 управления, первый блок 2 формирования то- 15 пологии, второй блок 3 формирования топологии, блок 4 моделей ветвей, re нератор 5 тактовых импульсов.

Блок 1 управления содержит с первого по четвертый узлы 6-9 памяти, первый и второй триггеры 10 и 11, с первого по седьмой элементы ИЛИ 12

18, с первого по третий элементы

19-21 задержки, с первого по шестой элементы И 22-27, элемент НЕ 28, узел

29 измерения длиннейшего пути, вход

30, меток контура графа устройства, вход 30 меток свершения ветвей графа устройства, выходы 31 и 32 номера подготавливаемой к моделированию ветви блоков 2 и 3, выходы 33 и 34 поиска свободной ветви блоков 2 и Э, выходы 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 считывания номеров узлов контура графа устройства, выход 69 меток контура пути на графе устройства, выход 70 прп3«BK« нппичия Illfh. a vcT р<>йст«а, «ыход 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 предназначен для промежуточного хранения номера ветви при

1 определении ветвей, выходящих из узла, регистр 79 — для промежуточного хранения номеров ветвей, входящих в узел, регистр 80 — для хранения номера анализируемого узла сети, регистр

81 — для постоянного хранения номера конечного узла сети.

Дешифраторы 84 и 85 состояния предназначены для сравнения поступающих на них кодов с кодовой комбинацией

Х, заданной постоянно в схеме, а дешифратор 86 сравнения кодов — для поразрядного сравнения кодов из регистров 80 и 81.

13223

Каждая модель 103 ветви содержит формирователь 104 временного интервала, триггеры 105 и 106, элементы И

107-112, элемент ИЛИ .113 и элементы

114 и 115 задержки.

Схема 116 поиска моделей ветвей содержит шифратор 117 адреса и элементы ИЛИ 118-120.

Работу устройства рассматривают на примере контроля наличия контуров в 10 рассчитываемой сети и определения номеров узлов сети, которые принадлежат замкнутым путям.

Устройство работает следующим образом. 15

В узлы 72-77 памяти блока 2 формирования топологии в виде списков заносится информация о топологии моделируемой сети. Регистры 78-80 обнуля-. ются, а н регистр 81 заносится код 20 номера конечного узла сети. Триггеры

82 и 83 блока 2 формирования топологии устанавливаются н нулевое состояние. В узлы 72-77 памяти блока 3 формирования топологии н виде списков заносится информация о топологии сети, которая является зеркальным отображением моделируемой сети, т.е. в узле 72 памяти по адресу каждой ветви записывается номер ее конечного узла,30 н узел 73 памяти по адресу каждой ветви — номер ее начального узла, в узел 74 памяти в виде списков номера входящих ветвей, в узел 75 памяти в виде списков — номера вы- 35 ходящих ветвей, в узел 76 памяти по адресу каждого узла — номер первой входящей ветви, в узел 77 памяти по адресу номера каждого узла — номер первой выходящей ветви. 40

Регистры 78-81 обнуляются. Триггеры 82 и 83 устанавливаются в нулевое состояние. В узел 8 памяти блока

1 управления записывается информация о длительности каждой ветви модели- 45 руемой сети. Узел 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 nalt II мяти, сигнал Пуск появляется на выходе элемента 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 памяти, на вход элемента 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). Триггер через время àðåðà ки, достаточное для срабатывания всех элементов, устанавливается в единичное состояние, что означает занятость данной модели процессом моделирования. Одновременно сигнал с выхода эле-35 мента И 110 поступает на первый вход элемента И 111, и через элемент ИЛИ !13 на вход шифратора адреса. На второй вход элемента И 111 через входной полюс 53 поступает код длительности вет 40 ви. Этот код записывается в качестве исходной информации в формирователь

104(1) временного интервала. С выхода шифратора 117 адреса код номера модели ветви через полюс 50 поступает на 45 адресный вход узла 9 памяти блока 1 управления. Через время, достаточное для организации опысанных процессов, в блоке 4 моделей ветви на выходе элемента 20 задержки блока 1 управле- 50 ния появляется сигнал, поступающий на вход записи узла 9 памяти номеров моделируемых ветвей. Происходит запись номера загружаемой ветви сети по адресу выбранной модели ветви. На 55 этом заканчивается подготовка первой ветви, выходящей из начального узла сети, к процессу моделирования.

1(рн подго1 Рнк< RE тнн к моле пирона нин ныполня TcH считывание ее номера из блока 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(n) всех моделей ветвей блока 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 )22 10 »

40 с т ня шифр,» t.< р 17,»;<р«.ë, гд< ф< р— м»<рус т< я н од лом< )»

Описанный процесс подготовки вет- 10 вей сети к моделированию продолжяется до тех пор, пока не подготовлена последняя ветвь, выходящая из данно го узла. В этом случае по адресу ее номера из узла 74 памяти гчитывается код Х, который эаписывяетгя R ре— гистр 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 временного интервала не выдает сигнал об окончании процесса временного моделирования длительности ветви.

В»т«лччяс <.игнялы г»<ы.<с»<тя ф< рмир явят< лей 104 (1), 10 » (2),..., 104 (n) временного интс рва ля логтупян т ня глинн «ньн t»h<»fIt I триггеров

106 (1), 106 (),..., 106 (n?, у< тяняв— линяя их в < диничн<н < с гтояние. Одн<—

Бргмен!<о с иг»<ял Г ныхс<д<»н формирс»ня телей 104(1), 10»(2),..., 104(n) погтупают чере» .»лгмент И1И 118 на вход поигкя прерывания (1,1) первой модели ветви. В глучяе, егли триггер

106(1) первой модели ветви находится н единичном сс стоянии, гиг«taft прерывания < выходя злементя И 108(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 присутствует запрещающий потенциал с единичного выхода

1322304!

0 триггера 10, поэтому сигнал начала анализа ветви в блок 3 формирования топологии не поступает. Это исключа-, ет включение блока 3 формирования топологии на этапе моделирования сети в прямом направлении.

В блоке 2 формирования топологии код номера ветви с полюса 43 поступает на адресный вход узла 73 памяти конечного узла, а сигнал начала ана- 10 лиза ветви с полюса 47 поступает на вход триггера 82 и устанавливает его в единичное состояние. Единичное состояние триггера 82 разрешает прохождение импульсов ГИ1 через элемент

И 98, а импульсов ГИ2 — через элемент

И 99. Кроме того, сигнал начала анализа поступает на вход элемента 88 задержки и на вход считывания узла

73 памяти. Происходит считывание . 20 ячейки памяти по адресу номера свершившейся ветви, т.е. считывание номера конечного узла ветви. Код считанного номера узла с выхода узла 73 памяти поступает на адресные входы узла 77 памяти первой выходящей ветви и на информационные входы регистра 80 конечного узла. Через время задержки,достаточное для считывания информации из узла 73 памяти, сигнал наз0 чала анализа ветви поступает на управляющий вход регистра 80 конечного узла и на вход считывания узла 77 памяти. По этому сигналу происходит запись номера конечного узла ветви в 35 регистр 80 и считывание номера первой, входящей в этот узел, ветви с узла 77 памяти. Код номера первой

Ф входящей ветви с выхода узла 77 памяти поступает через элемент ИЛИ 93 4О на информационный вход регистра 79 входящей ветви и записывается в него по первому импульсу ГИ1, поступающему на управляющий вход регистра с выхода элемента И 98. С выхода регистра 79 4 код номера первой входящей ветви поступает через полюс 35 и элементы

ИЛИ 14 и 18 на адресный вход узла 7 памяти блока 1 управления, на адресный вход узла 75 памяти входящих ветвей и на дешифратор 85. По первому импульсу ГИ2 сигнал проверки свершения ветви с выхода элемента И 99

1 поступает через элемент ИЛИ 96 на вход считывания узла 75 памяти, а че->> рез полюс 37 и элемент ИЛИ 15 — на вход считывания узла 7 памяти блока

1 управления. Метка свершения, считанная по адресу первой ветви, < выхода узла 7 памяти поступает через полюс 45 в блок 2 формирования топологии, а через полюс 46 — в блок 3 формирования топологии. Если метка отсутствует, нулевой сигнал метки с полюса 45 через элемент HE 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 памяти входящих ветвей. На адресные входы последнего в это время поступает код номера первой входящей

1322304 !2 ветви с вьюс да регистра 79. По адресу первой входящей ветви из узла 75 памяти считывается код номера второй входящей в данный узел ветви. Этот код поступает через элемент ИЛИ 93 на информационные входы регистра 79 и записывается в него с приходом второго импульса ГИ1. Далее осуществляется опрос метки свершения данной ветви. Если ветвь свершилась, осуще- !О ствляется переход к опросу свершения следующей ветви, входящей в рассматриваемый узел, и т.д.

Описанный процесс анализа свершения ветвей продолжается до тех пор, 1э пока не опрошены все ветви, входящие в рассматриваемый узел. В этом случае по адресу последнего номера ветви из узла 75 памяти считывается код

Х, определяющий конец списка входящих20 в данный узел ветвей. Код Х записывается в регистр 79 входящей ветви и далее поступает на вход дешифратора 85 состояния, вырабатывая сигнал конца списка, который проходит через элементы ИЛИ 94 и 95 и устанавливает триггеры 82 и 83 соответственно в нулевое и единичное состояние. Сигнал с выхода дешифратора 85 поступает также на первый вход элемента И 86,вто- 30 рой вход которого связан с выходом дешифратора 86 сравнения кодов, который сравнивает коды, хранящиеся в регистре 81 конечного узла сети и в регистре 80 конечного узла ветви. Ре-35 гистр 81 хранит код конечного узла сети, а регистр 80 — код рассматриваемого узла сети, сформировавшего функцию коньюнкции в данный момент времени. Если значение этих кодов не 40 совпадает, сигнал с выхода дешифратора 85 поступает через элемент ИЛИ 89 на вход считывания узла 76 памяти первой выходящей ветви, на адресный вход которого в этот момент времени поступает код номера сформированного узла сети. Начинается процесс подготовки к моделированию тех ветвей, которые выходят иэ данного сформированного узла. 50

Если в сети отсутствуют циклы (контуры), описанный процесс подготовки ветвей к моделированию, времен- ное моделирование и анализ ветвей, моделирование которых закончено, че- 5S редуются в укаэанном порядке и повторяются до тех пор, пока не сформируется конечный узел сети. В этом случае дешифратор 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 и устанавливает триг13

1322304

rep 83 блока 3 формирования топологии в единичное состояние. Единичное состояние триггера 83 разрешает прохождение серии импульсов ГИ! через элемент И 100, а серии импульсов ГИ2 через элемент И 101. Кроме того, сигнал с полюса 64 поступает на вход элеэлемента 87 задержки и на вход считывания узла 72 памяти.На адресные входы последнего поступает код номера !0 ветви, входящей в конечный узел сети. Так как в узле 72 памяти по адресу ветвей моделируемой сети записаны их конечные узлы, по приходу сигнала считывания из узла 72 памяти считыва- 15 ется код конечного узла сети. -Этот код поступает через элемент ИЛИ 90 на адресный вход узла 76 памяти первой входящей ветви. Через время, достаточное для считывания информации 20 из узла 72 памяти, сигнал с полюса

64 появляется на выходе элемента 87 задержки и поступает через элемент

ИЛИ 89 на вход считывания узла 76 памяти.По этому сигналу происходит считывание кода номера первой ветви, входящей в конечный узел сети, Код номера первой входящей ветви с выхода узла 76 памяти поступает через элемент ИЛИ 91 на информационный вход регистра 78 и записывается в него по первому импульсу ГИ1, поступающего на управляющий вход регистра с выхода элемента И 100.

Записанный код первой входящей 35 в конечный узел ветви с выхода регистра 78 поступает на адресный вход узла 74 памяти, а также через полюс

31 и элемент ИЛИ 12 — на адресный вход узла 9 памяти и информационный 40 вход узла 8 памяти номеров моделируемых ветвей блока 1 управления, Импульс ГИ2, сдвинутый относительно импульса ГИ1, поступает на вход считывания узла 74 памяти бло- 45 ка 3 формирования топологии, и по адресу первой входящей в конечный узел ветви считывается в код номера второй ветви, входящей в тот же узел.

Одновременно по импульсу ГИ2 сигнал поиска свободной модели с выхода элемента И 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 и с приходом второго импульса ГИ! записывается в него. После э1ого опять происходит поиск свободной от вычислений модели ветви, запись кода длительности в ее формирователь временного интервала, запись номера моделируемой ветви по адресу номера выбранной модели в узел 8 памяти блока управления.

1322304

Процесс подготовки ветвей, входящих в конечный узел сети, к процессу моделирования осуществляется до тех пор, пока не считывается последняя ветвь иэ списка входящих ветвей. 5

По адресу ее номера в узле 74 памя— ти считывается код Х, который записывается в регистр 78 блока 3 формирования топологии.

Сигнал поиска прерывания с полюсом 40 поиступает на вход триггера 11 блока 1 управления и устанавливает его в единичное состояние. Так как в рассматриваемый момент нет моделей ветвей, окончавших моделирование,сиг- 15 нал прерыв.:ния отсутствует и триггер

11 остается в единичном состоянии.

Единичное состояние тирггера 11 разрешает прохождение импульсов серии

ГИ1 на счетный вход узла 29 измерения длиннейшего пути и через полюс 54 на все формирователи 104 временного интервала, триггера 105 которых находятся в единичном состоянии. Так продолжается до тех пор, пока хотя бы один из формирователей 104 временного интервала не выдает сигнал об окончании процесса временного моделирования.

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

104(1), 104(2),..., 104(n) временного интервала поступают на единичные входы триггеров 106 (1), 106 (2), ..., 106(п) и устанавливают их в единичное состояние. Одновременно сигналы с выходов 35 формирователей 106(1), 106(2),..., 106(n) поступают через элемент ИЛИ 118 на вход поиска прерываний (1,1) первой модели ветви. Начинается этап обработки прерывания, аналогично эта-40 пу обработки прерывания при моделировании сети в прямом направлении. Определяется номер модели ветви, окончившей моделирование. По этому номеру определяется код номера свершившейся ветви, записывается метка " 1" в узел памяти свершения по адресу номера ветви. Код номера свершившейся ветви поступает на полюса 43 и 44 и далее в блоки формирования тополо- 5О гии. Сигнал прерывания с полюса 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 управления, где проверяется свершение считанной ветви.

Если ветвь не свершилась, процесс временного моделирования продолжается дальше. Если же первая ветвь,исходящая из рассматриваемого узла, имеет единичную метку свершения, xs узла 75 памяти считывается код следующей ветви и производится проверка ее свершения. Процесс проверки свершения ветвей, исходящих иэ рас17

132? 304 фа устройства подключен к третьему

10 входу блока управления, выход меток

t5 делирования.

Описанные процессы подготовки ветвей к моделированию, временное моделирование и анализ ветвей, моделирование которых окончено (при моделировании сети в обратном направле- 29 нии), продолжается до тех пор, пока не окончится моделирование всех ветвей, входящих и свершившиеся узлы.

В этом случае при обработке прерывания от модели ветви, которая последней окончила процесс моделирования, сигнал проверки свершения нетви с полюса 37 поступает на первый нход элемента И 24, на второй вход указанного элемента — сигнал отсутствия за-ЗО нятых моделей ветвей с полюса 51, а на третий вход через элемент НЕ 28 нулевая метка свершения из узла 7 памяти. С выхода элемента И 24 сигнал наличия цикла поступает на выход-35 ной полюс 70. При этом в узле 6 памяти останутся метки по тем адресам, которые соответствуют номерам узлов, принадлежащих контуру сети.

Для определения номеров узлов се- 4О ти, принадлежащих контуру, необходимо подать их на входной полюс 68, который поступает на вход считывания узла 6 памяти. Наличие метки "1" по определенным адресам определит номе- 45 ра узлов, принадлежащих контуру.

Устройство для моделирования направленных графов, содержащее блок управления, первый блок формирования топологии, блок моделирования ветвей, генератор тактовых импульсов, вход запуска устройства подключен к входу 55 запуска первого блока формирования топологии, вход кода номера начальной ветви графа устройства подключен сматринаемого узла, продолжается до тех пор, пока не обнаружится вет.вь с нулевой меткой свершения, или пока не проанализируются все исходящие ветви. В первом случае продолжается процесс временного моделирования до момента окончания процесса моделирования следующей моделью ветви. В случае, если все анализируемые ветви.имеют единичные метки свершения, производится подготовка к процессу моделирования ветвей, входящих в рассматриваемый узел. После этого продолжается процесс временного моформула изобретения к первому информационному входу п рного блока формирования топологии, вход считывания номеров узлов контура графа устройства подключен к первому входу блока управления, вход меток контура графа устройства подключен к второму входу блока управления, вход меток свершения ветвей граконтура пути на графе устройства подключен к первому выходу блока управления, выход признака наличия цикла устройства подключен к второму выходу блока управления, выход значения наидлиннейшего пути на графе устройства подключен к третьему выходу блока управления, первый выход генератора тактовых импульсов подключен к первому тактовому входу первого блока формирования топологии и четвертому входу блока управления, второй выход генератора тактовых импульсов подключен к второму тактовому входу первого блока формирования топологии, выход номера модели блока моделей ветвей подключен к пятому входу блока управления, выход признака отсутствия занятых моделей ветви блока моделей ветвей подключен к шестому входу блока управления, выход прерывания блока моделей ветвей подключен к седьмому входу блока управления, выходы с четвертого по седьмой блока управления подключены соответственно к информационным входам с пер ого по четвертый блока моделирования ветвей, выход проверки свершения ветви графа первого блока формирования топологии подключен к восьмому входу блока управления, выход признака результата расчета длиннейmего пути первого блока формирования топологии подключен к девятому входу блока управления, выход номера анализируемой ветви графа первого блока формиронания топологии подключен к десятому входу блока управления, выход номера подготовляемой к моделированию ветви первого блока формирования топологии подключен к одиннадцатому входу блока управления, выход поиска свободной ветви графа первого блока формирования топологии подключен к двенадцатому входу блока управления, выход поиска прерывания первого блока формирования топологии подключен к тринадцатому входу блока

1322 30<<

v1lp,«<я««<я, «l,1õ«Л н«н р;«а< ружа< мого

Yç«;< I рафа гн рвого бл <к» ф рмирования топ«но<чьи подключен к четырнадцат<му вх««у блока управления, восьмой,девнтыи и десятый выходы блока управления подкл«<иены соответственно к второму, третьему и четвертому информационным входам первого блока формирования топологии, при этом блок управления содержит четыре узла па- 10 мяти, пять элементов И, два триггера, элемент HF., три эле <ента задержки и узел измерения дл»ннейшего пути,причем в блоке упрзвления входы с первого по пятый блока управления подклю- 15 чень< соответственно к входу чтения первого узла гамяти, информационному входу второго узла памяти, информационному входу первого узла памяти,первому входу первого элемента И и ад- 20 рес«ому входу третьего узла памяти, шестой вход блока управления подключен к первым входам второго и третьего элементов И, седьмой вход блока управления подключен к входу чтения третьего узла памяти, входу первого элемента задержки и входу установки в ноль первого триггера, восьмой вход блока управления подключен к второму входу второго элемента И, девятый 30 вход блока управления подключен к первому входу четвертого элемента И, первый выход блока управления подключен к выходу первого узла памяти,выход третьего элемента И подключен к З5 входу установки в ноль первого триггера и второму выходу блока управления, третий выход которого подключен к выходу четвертого элемента И, четвертый выход блока управления подклю-40 чен к выходу четвертого узла памяти, выход первого элемента И подключен к входу узла измерения длиннейшего пути и пятому выходу блока управления, шестой выход блока управления подклю- 5 чен к счетному входу второго триггера, седьмой выход блока управления подключен к входу считывания четвертого узла памяти, адресному входу первого узла памяти и входу второго элемента 5 задержки блока управления, выход третьего узла памяти подключен к восьмому выходу блока управления, выход второго узла памяти подключен к входу элемента НЕ и девятому выходу блока управления, десятый выход блока управления подключен к выходу пятого элемента И, инверсный выход первого триггера и< дь ««< в ь в рв«м <3xo+i пятого элемент» И, выход первого элемента задержки подь.<ночев к входу записи второг» у-< 1;l памяти и входу трР тьего элемента задержки, выход второго триггера подклн1чен к второму входу первого элемента И,выход второго элемента задержки подклк>чен к информационному входу третьего узла памяти, выход третьего элемента задержки подключен к второму входу пятого элемента И, выход элемента НЕ подключен к третьему входу второго и второму входу третьего элементов И, выход второго элемента И подключен к счетному входу первого триггера, выход узла измерения длиннейшего пути подключен к второму входу четвертого элемента

И, о т л и ч а ю щ е е с я тем, что с целью повышения достоверности работы устройства за счет контроля наличия контуров на графе, оно дополнительно содержит второй блок формирования топологии, первый и второй выходы генератора тактовых импульсов подключены соответственно к первому и второму тактовым входам второго блока формирования топологии, выход номера подготавливаемой к моделированию ветви второго блока формирования топологии подключен к пятнадцатому входу блока управления, выход поиска свободной ветви второго блока формирования топологии подключен к шестнадцатому входу блока управления, выход номера анализируемой ветви второго блока формирования топологии подключен к семнадцатому входу блока управления, выход проверки свершения ветви второго блока формирования топологии подключен к восемнадцатому входу блока управления, выход поиска прерывания второго блока формирования топологии подключен к девятнадцатому входу блока управления сети, выход номера загружаемого узла графа второго блока формирования топологии подключен к двадцатому входу блока управления, вход номера конечной ветви графа устройства подключен к первому информационному входу второго блока формирования топологии, одиннадцатый, двенадцатый и тринадцатый выходы блока управления подключены соответственно к второму, третьему и четвертому информационным входом второго блока формирования топологии, четырнадцатый выход блока управления подключен

21

22

1 322 304 к входу запуска второго блока форми рования топологии, при этом в блок управления дополнительно введены шестой элемент И и семь элементов ИЛИ, причем в блоке управления одиннадцатый и пятнадцатый входы блока управления подключены соответственно к первому и второму входам первого элемента ИЛИ, двенадцатый и шестнадцатый входы блока управления подключены со- 10 ответственно к первому и Второму входам второго элемента ИЛИ, десятый и семнадцатый входы блока управления подключены соответственно к первому и второму входам третьего элемента 15

ИЛИ, восьмой вход блока управления подключен к первому входу четвертого элемента ИЛИ, восемнадцатый вход блока управления подключен к второму входу четвертого элемента ИЛИ и тре- 20 тьему входу третьего элемента И, четырнадцатый и двадцатый входы блока управления подключены соответственно к первому и второму входам пятого элемента ИЛИ, тринадцатый и девятнадцатый входы блока управления подподключены соответственно к первому и второму входам шестого элемента

ИЛИ, прямой выход первого триггера подключен к первому входу шестого элемента И, выход третьего элемента задержки подключен к второму входу шестого элемента И, выход первого элемента ИЛИ блока управления подключен к адресному входу четвертого узла памяти и входу записи третьего узла памяти, выходы элементов ИЛИ с второго по седьмой подключены соответственно к входу второго элемента задержки, первому входу седьмого элемента ИЛИ, входу чтения второго узла памяти, входу запнси первого узла памяти, счетному входу второго триггера и адресному входу второго узла памяти, выход третьего узла памяти подключен к второму входу седьмого элемента ИЛИ и одиннадцатому выходу блока управления, выход второго узла памяти подключен к двенадцатому выходу блока управления, выход шестого элемента И подключен к тринадцатому выходу блока управления, выход второго элемента И подключен к четырнадцатому выходу блока управления .

132230«

1322304

Составитель В.Смирнов

Редактор Н.Рогулич Техред И.Попович

Корректор Г. Решетник

Заказ 2866/46 Тирам 672 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5

Производственно-полиграфическое предприятие, г.ужгород, ул. Проектная, 4