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

 

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

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (И) 42 А1 (51)4 С 06 Г 1 /20

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

К ABTOPCHCNVIY СВИДЕТЕЛЬСТВУ

1

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) . 4155409/24-24 (22) 03.12.86 (46) 30.12.89. Бюл. И 48 (71) Институт проблем моделирования в энергетике AH УССР (72) А.Г.Додонов, А.А.Котляренко, С.П.Пелехов, В.И.Приймачук и А.M.Ùåòèíèí (53) 681.333 (088 ° 8) (56) Авторское свидетельство СССР и 907552, кл. G 06 F 1 5/20, 1980.

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

И 1161951, кл. С 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА ПАРАМЕТР0В ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано для исследования параметИзобретение относится к вычислительной технике и может быть использовано для исследования параметров сетевых графиков.

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

На Фиг.1 представлена функциональная схема устройства; на фиг.2функциональная схема многократного таймера; на фиг.3 - функциональная схема многоканального блока вводавывода; на фиг.4 - функциональная схема блока регистрации и сложения массивов; на фиг.5 - функциональная

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

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

Устройство содержит многоканальный таймер 1, многоканальный блок 2 ввода-вывода, блок 3 регистрации и сложения массивов, блок 4 регистрации и сравнения массивов, блок 5 памяти номеров каналов, блок 6 сравнения, первый и второй регистры 7 и 8 соот-. ветственно, первый и второй элементы

9 и 10 задержки, первый и второй блоки 11 и 12 элементов ИЛИ и с первого по третий элементы ИЛИ 13-15. Кроме того, на фиг.1 цифровые обозначения имеют вход. 16 задания номера начального узла графа устройства, вход 17 пуска устройства, выход 18 веса пути з

15329 графа устройства, вход 19 задания номера конечного узла графа устройства, вход 20 начальной установки устройства, выход 21 величины потребного ресурса устройства, выход 22 признака выдачи величины ресурса устройства и выход 23 признака окончания работы устройства, блок 24 синхронизации, выход 25 времени работы, выход 26 номера канала, выход 27 признака прерывания счета, выход 28 номера подготавливаемой к моделированию ветви, выход 29 признака выдачи слова, выход

30 признака конца списка., выход 31 признака неравенства массивов, выход

32 признака равенства массивов, первый выход 33 синхронизации, второй выход 34 синхронизации.

Многоканальный таймер 1 (фиг.2) содержит и каналов 35 моделирования

20 длительности ветви, узел 36 поиска канала моделирования, узел 37 загрузки канала, канал 38 измерения пути.

В свою очередь, каждый канал 35 моделирования длйтельности ветви содержит формирователь 39 временного интервала, триггеры 40, 41, элементы

42...46 И, блок 47 элементов И, элемент ИЛИ 48, элементы 49, 50 задержки. Узел 36 поиска канала моделирования содержит шифратор 51 адреса, элементы ИЛИ 52 и 53. Узел 37 загрузки канала содержит узел 54 памяти длительности ветвей, узел 5$ памяти номеров модулируемых ветвей, элементы -5

56 и 57 задержки. Канал 38 измерения пути содержит счетчик 58 длины пути, триггер 59, элемент И 60, блоки 61 и

62 элементов И.

Многоканальный блок 2 (фиг.3) ввода-вывода содержит узел 63 памяти адресов выходящих ветвей узлов сети, узел 64 памяти адресов первой выходящей ветви узлов сети, регистр 65 адреса выходящей ветви, триггер 66, дешиФратор 67 состояния Х, элементы

И 68 и 69, блок 70 элементов ИЛИ.

Блок 3 регистрации и сложения массивов (фиг.4) содержит узел 71 памяти величины ресурса ветвей, узел 72 памяти меток моделируемых ветвей, счетчик 73 поиска номеров моделируемых ветвей, сумматор 74 величины ресурса, регистр 75 - накопитель сумматора, триггер 76 определения величины суммарного ресурса, элементы

И,77 и 78, блок 79 элементов И, блок

G0 элементов ИЛИ, элемент ИЛИ Bl, элементы 82-84 задержки.

Елок 4 регистрации и сравнения массивов (Фиг.5) содержит узел 85 памяти меток исполнения ветвей, узел

86 памяти адресов входящих ветвей узлов сети, узел 87 памяти адресов первой входящей ветви узлов сети, регистр 88 адреса входящей ветви, дешифратор 89 состояния Х, триггер

90, элементы И 91 и 92, блоки 93 и

94 элементов ИЛИ, элемент ИЛИ 95, элемент НЕ 96.

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

Перед началом работы узлы загрузки канала таймера 1 загружают одами чисел, значения которых соответствуют весу ветвей графа, номера которых совпадают с номерами адресов узла загрузки каналов таймера, каналы блока 2 ввода" вывода загружают списками ветвей, исходящих из узлов, номера которых совпадают с номерами каналов блока 2, обнуляют память признаков принадлежности операндов массиву блока 3 регистрации и сложения массивов, а aего память значений операндов заносят значения ресурсов, необходимых для исполнения ветви графа, номер которой совпадает с адресом памяти значений операндов, и обнуляют память признаков налиция элементов рабочего массива блока 4 регистрации и сравнения массивов, а его каналы загружают списками ветвей, входящих в узлы графа, номера которых совпадают с номерами каналов блока 4„, в блок 5 памяти номеров каналов заносят номера конечных узлов для ветвей, номера которых совпадают с адресами блока 5, в регистр 8 заносят код номера конечного узла графа.

На вход 16 устройства подают код начального узла графа, на вход 17 пуска устройства - импульсный сигнал уровня логической единицы. При этом блок 2 ввода-вывода выдает на выход 28 список ветвей, исходящих из начальной вершины графа, сопровождая каждое слово списка импульсным сигналом уровня логической единицы на выходе 29 признака выдачи слова °

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

5 153

37 загрузки канала таймера 1. В память признаков принадлежности операндов массиву блока 3 регистрации и сложения массивов через выходы 28 и 29 заносятся единичные метки по тем адресам, которые соответствуют номерам ветвей, исходящих из начального узла графа ° После ввода номеров всех ветвей начального узла графа блок 2 формирует сигнал уровня логической единицы на своем выходе 30 признака конца списка.При этом за-. пускается блок 3 и через время, необходимое для арифметического сложения всех операндов (величины ресурса), отмеченных в памяти признаком принад-, лежности операндов массиву единичными метками, выдает на выход 21 величину потребного ресурса для начала пути графа, сопровождая ее импульсным сигналом на выходе 22. В это же время на выход 35 таймера 1 выдается код отрезка временного моделирования графа, для которого вычислен суммарный ресурс. Сигнал с выхода 22 запускает таймер 1, и те его каналы, которые переведены в рабочее состояние, начинают отсчет текущего времени. Тем самым моделируется исполнение ветвей, исходящих из начального узла графа. Через время, равное весу кратчайшей из ветвей один или несколько каналов прерывают счет таймера, на выходе 27 прерывания счета и выходе 26 номера исполненной ветви появляются соответственно импульсный сигнал уровня логической единицы и код номера ветви графа, прервавшей счет таймера (или код номера ветви с наивысшим приоритетом из числа прервавших счет таймера). При этом из памяти признаков принадлежности операндов массиву блока 3 исключается метка принадлежности по .адресу ветви, моделирование которой закончено. В память признаков наличия элементов рабочего массива блока 4 по адресу ветви заносят метку исполнения ветви. В регистр 7 из блока 5 памяти заносится код номера узла, в который входит исполненная ветвь, после чего запускается блок 4 регистрации и " сравнения массивов. Указанный блок проверяет наличие меток исполнения у всех ветвей, входящих в достигну. тую вершину графа (ее код занесен в регистр.:-7). В этом случае, если име. ются неисполненные ветви, на выходе

2942

31 признака неравенства массивов блока 4 появляется импульсный сигнал уровня логической единицы, который .

5 запускает блок 3. После этого работа устройства повторяется.

В этом случае, если все ветви исполнены, импульсный сигнал уровня логической единицы появляется на выходе 32 признака равенства массивов блока 4. Это возможно в том случае, если закончено моделирование всех ветвей, входящих в узел графа. Сигнал на выходе 32 признака равенства массивов разрешает в .блоке 6 сравнение кодов достигнутого и конечного ysлов пути. В том случае, есди достигнутый узел не является конечным, на выходе признака неравенства блока

20 6 появляется импульсный сигнал уровня логической единицы. Этот сигнал через элемент ИЛИ 13 запускаетблок 2 ввода-вывода, и каналы таймера 1, свободные для моделирования ветвей, 25 исходящих из достигнутого узла графа, переводятся в рабочее состояние.

Затем продолжается временное моделирование графа. В том случае, если достигнут конечный узел пути, сигнал

Z0 уровня логической единицы появляется на выходе 23 признака окончания работы устройства. По этому сигналу в таймере 1 на выходе 18 выдается код величины веса пути. В процессе, 35 решения задачи для каждого временного отрезка моделирования на выходе

25 выдается его величина, а на выходе 21 — величина потребного ресурса для исследуемого графа °

Многоканальный таймер 1 работает следующим образом.

На этапе подготовки ветвей графа к временному моделированию после определения каждой исходящей ветви на вход 29 с многоканального блока 2 ввода-вывода поступает сигнал признака выдачи слова, а на вход 28 - код номера подготавливаемой ветви. С входа 29 сигнал признака выдачи слова поступает на вход чтения узла 54 памяти длительности ветвей узла 37 загрузки канала и на входы элементов

И 44 и 45 первого канала 35(1) моделирования длительности ветви. Если триггер 41 первого канала 35 (1) моделирования длительности ветви находится в единичном состоянии (канал занят), сигнал единичного уровня с выхода элемента и 44 поступает на

1532942 входы элементов И 44 и 45 второго канала 35 (2) моделирования длительности ветви. Если триггер 41 и второго канала 35 (2) находится в единичном состоянии, сигнал единичного уровня с выхода элемента И 44 второго канала 35 (2) поступает на входы элементов И 44 и 45 третьего канала 35 (3) моделирования длитель, ности ветви и т.д., po первого своi бодного канала 35 (k), 8 первом своI бодном канале 35 (k) сигнал с выхода элемента И 45 через элемент И 48 по, ступает на вход шифратора 51 адреса узла 36 поиска канала моделирования.

С выхода шифратора 51 адреса код но; мера свободного канала поступает на

; адресный вход узла 55 памяти номеров, моделируемых ветвей узла 37 загрузки канала. На информационный вход, узла 55 памяти поступает код номера подготавливаемой ветви с входа 28,, а на вход записи с выхода элемента

56 задержки поступает сигнал признаl,êà выдачи слова. Происходит запись кода номера подготавливаемой ветви по адресу номера свободного канала

37 (k) моделирования длительности ветви. Кроме этого, сигнал с выхода элемента И 45 свободного канала

35 (k) моделирования длительности ветви поступает на первый. вход блока

47 элементов И, на второй вход которого поступает код длительности подготавливаемой ветви, считанный с узла 54 памяти дли-.".. lbHocTH ветвей узла 37 загрузки канала. Указанный код длительности ветви с выхода блока

47 элементов И поступает на установочный вход формирователя 39 временного интервала и заносится в него в качестве исходной информации. На этом заканчивается подготовка данной ветви к процессу временного моделирования ее длительности. При подготовке следующей ветви на вход 29 таймера 1 опять поступает сигнал признака выдачи слова, а на вход 28код номера новой ветви. Описанный процесс подготовки ветви повторяется.

После подготовки всех ветвей, исходящих из начального (исполненного) узла графа на вход 30, а при анализе исполнения узла при неисполнении л обой входящей ветви, на вход 31 из многоканального блока 2 ввода-вывода поступает сигнал высокого

55 уровня. С выхода элемента ИЛИ 15 этот сигнал через элемент ИЛИ 53 узла 36 поиска канала моделирования поступает на входы элементов И 42 и 43 первого канала 35 (1) моделирования длительности ветви. Если триггер 40 первого канала 35 (1) находится в нулевом состоянии (канал не окончил моделирования длительности ветви), сигнал с выхода элемента И 42 первого канала 35 (1) поступает на входы элементов И 42 и 43 второго канала

35 (2) моделирования длительности ветви. Если триггер 40 и второго канала 35 (2) находится в нулевом состоянии, сигнал с выхода элемента И 42 этого канала поступает на входы элементов И 42 и 43 третьего канала

35 (3) моделирования длительности ветви и т.д. до того канала 35 (m), триггер 40 которого находится в единичном состоянии (канал окончил моделирование длительности ветви).

Сигнал с выхода элемента И 43 этого канала поступает на нулевой вход триггера 41 этого канала, сбрасывая его в нулевое состояние. Данный канал становится свободным и готов для моделирования длительности другой ветви. Кроме того, сигнал с выхода weмента И 43 через элемент ИЛИ 48 поступает на вход шифратора 51 адреса узла 36 поиска канала моделирования.

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

35 (m) поступает на адресный вход узла 55 памяти номеров моделируемых ветвей узла 37 загрузки канала. На вход чтения узла 55 памяти поступа- . ет сигнал с выхода элемента ИЛИ 52 узла 36 поиска канала моделирования.

Считанный из узла 55 памяти код номера ветви графа, моделирование длительности которой окончено (исполнено), поступает на выход 26.На выход 27 с выхода элемента 57 поступает сигнал признака окончания иоделирования ветви. Начинается этап анализа исполнения узла и подготовки к моделированию исходящих ветвей.

После подготовки всех ветвей, исходящих из. всех исполненных в данный момент узлов графа, на вход 22 иэ блока 3 регистрации и сложения массивое поступает сигнал признака выдачи величины ресурса. С входа 22 указанный сигнал поступает на единичный вход триггера 59 канала 38 измерения

1532942

30 пути, а также на вход блока 61 элементов И. На второй вход блока 61 элементов И поступает код отрезка пути с выхода счетчика 58 длины пути.

С выхода блока 61 элементов И код отрезка длины пути поступает на выход

25. Единичное состояние триггера 59 разрешает прохождение тактовых импульсов на вхолсчетчика 58длины пути.

С приходом каждого импульса код счетчика увеличивается на "!", такимобразом формируется величина отрезка пути. Кроме того, сигнал с выхода элемента И 60 канала 38 измерения пути поступает на входы элементов И 46 всех каналов

35 моделирования длительности ветви.

У тех каналов, которые заняты моделированием длительности ветвей, на второй вход элементов И 46 поступает разрешающий потенциал с выхода триггера 41. С выхода элементов И 46 сигналы измерительной серии поступают на счетный вход формирователей,39 временного интервала. Формирователи 25

39 работают на вычитание, с приходом количества импульсов, равного минимальному коду, занесенному в формирователь, последний обнуляется, и на его выходе формируется сигнал переполнения. Это означает, что данный канал 35 окончил моделирование дли тельности ветви. С выхода формирователя 39 сигнал поступает на единичный вход триггера 40, устанавливая его в единичное состояние, а также на вход элемента ИЛИ 53 узла 36 поиска канала моделирования. С выхода элемен- .-q та ИЛИ 53 сигнал высокого уровня поступает на входы элементов И 42 и 43 40 первого канала 35 (1) моделирования.

Если триггер 40 первого канала 35 (1) находится в нулевом состоянии (канал не окончил моделирования длительности ветви), си нал с выхода элемента

И 42 этого канала поступает на входы элементов И 42 и 43 второго канала

35 (2) моделирования длительности ветви. Если триггер 40 и второго канала 35 (2) моделирования длительнос50 ти ветви находится в нулевом состоянии, сигнал с выхода элемента И 42 этого канала 35 (2) поступает на входы элементов И 42 и 43 третьего канала 35 (3) и т.д., до первого канала, который окончил моделирование дли55 тельности ветви. Сигнал с выхода элемента И 43 этого канала через элемент

ИЛИ 52 узла 36 поиска канала моделирования поступает на вход чтения узла 55 памяти номеров моделируемых ветвей узла 37 загрузки канала. Кро-, ме того, сигнал с выхода элемента

И 43 канала 35 моделирования длительности ветви через элемент ИЛИ 48 . поступает на вход шифратора 51 адреса узла 36 поиска канала моделирования. С выхода шифратора 51 код номе ра канала поступает на адресный вход узла 55 памяти. Считанный из узла памяти код номера исполненной ветви графа поступает на выход 26 многоканального таймера 1. На выход 27 с выхода элемента 57 задержки поступает сигнал признака окончания моделирования ветви. Начинается этап проверки исполнения узла и подготовка к моделированию исходящих из исполненного узла ветвей.

После окончания моделирования всех ветвей графа на вход 23 многоканального таймера 1 поступает сигнал признака окончания работы. С входа 23 сигнал поступает на первый вход блока 62 элементов И, на второй вход которого с выхода счетчика 58 длины пути поступает код веса пути графа.

С выхода блока 62 элементов И код веса пути графа поступает на выход

18. На этом устройство свою работу заканчивает.

Многоканальный блок 2 ввода-вывода (фиг.3) работает следующим об- разом.

При начальном пуске с входа 17 на первый вход элемента ИЛИ 13, а в процессе моделирования при исполнении любого узла графа, когда исполненный узел не является конечным узлом, с выхода неравенства блока 6 сравнения на второй вход элемента ИЛИ 13 поступает сигнал высокого уровня. Кроме того, при начальном пуске с входа

16 на первый вход блока 11 элементов

ИЛИ поступает код номера начааьного узла графа, а при исполнении узла с выхода регистра 7 на второй вход блока 11 элементов ИЛИ поступает код но" мера этого узла. С выхода блока 11 элементов ИЛИ код номера узла поступает на адресный вхол узла 64 памяти адресов первой выходящей ветви узлов сети. Сигнал с выхода элемента ИЛИ 13 поступает на вход чтения узла 55 памяти, а также на единичный вход триггера 66, устанавливая его в единичное состояние. Считанный из узла 64

1532942

20 памяти код номера первой ветви; исходящей из исполненного (начального) узла графа, через блок 70 элементов.

ИЛИ поступает на информационный вход регистра 65 и записывается в него по

5 приходу с элемента И 68 первого им- " пульса синхросерии ГИ1. С вь|хода регистра 65 код номера ветви графа поступает на адресный вход узла 63 памяти адресов выходящих ветвей узлов сети, а также на выход 28. На выход

29 с выхода элемента И 69 поступает первый тактовый сигнал признака выдачи слова. Начинается процесс подготовки к моделированию первой исходящей ветви. Кроме того, первый импульс с выхода элемента И 69 поступает на вход чтения узла 63 памяти, осуществляя считывание кода номера второй исходящей ветви. Считанный код с выхода узла 63 памяти через блок 70 элементов ИЛИ поступает на информационный вход регистра 65 и записывается в него по приходу второ- 25

ro тактового импульса, поступившего с выхода элемента И 68. С выхода регистра 65 код номера второй исходя.щей ветви опять поступает на адресный вход узла 63 памяти и на вход 28 номера подготавливаемой к моделированию ветви. На выход 29 с выхода элемента И 69 поступает второй импульс синхросерии признака выдачи спова.

Начинается процесс подготовки к моделированию второй исходящей ветви.

Описанный процесс поиска исходящих ветвей продолжается до тех пор, пока из узла 63 памяти адресов выходящих ветвей не будет считан код Х, означающий конец списка исходящих 40 ветвей. Считанный код поступает на вход дешифратора 67 состояния Х, где путем. сравнения вырабатывается признак конца списка исходящих ветвей.

С выхода дешифратора 67 признак кон 45 ца списка поступает на выход 30, а также на нулевой вход триггера 66. Триггер 66 устанавливается в нулевое состояние, запрещая прохождение тактовых сигналов через элемен- 50 ты И 68 и 69.На этом многоканальный блок

2 ввода-вывода прекращает свою работу.

Блок 3 регистрации и сложения массивов (фиг.4) работает следующим образом.

При подготовке каждой ветви графа к моделированию на вход 29 с многоканального блока 2 ввода-вывода по1ступает сигнал признака выдачи слова.

Этот сигнал с входа 29 поступает на информационный вход узла 72 памяти меток моделируемых ветвей и через элемент ИЛИ 14 — на вход записи указанного узла. На адресный вход узла

72 памяти в это время с входа 28 через блоки 12 и 80 элементов ИЛИ поступает код номера подготавливаемой ветви. Происходит запись единичной метки в узел 72 памяти по адресу подготавливаемой ветви.

По окончании моделирования длительности каждой ветви графа на вход

27 с многоканального таймера 1 поступает сигнал признака окончания моделирования ветви. С входа 27 указанный сигнал через элемент ИЛИ 14 поступает на вход записи узла 72 памяти. На адресный вход узла 72 памяти в это время с входа 26 через блоки 12 и 80 элементов ИЛИ поступает код номера йсполненной ветви. Происходит запись нулевой метки в узел 72 памяти по адресу исполненной ветви.

После подготовки всех ветвей, исходящих из исполненного (начального) узла графа, на вход 30, а при анализе исполнения узла при неисполнении любой входящей ветви, на вход 31 поступает сигнал высокого уровня. С выхода элемента ИЛИ 15 этот сигнал поступает на входы сброса счетчика 73 поиска номеров моделируемых ветвей и регистра 75 - накопителя сумматора, устанавливая их в нулевое состояние.

Кроме того, сигнал с выхода элемента

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

И 78. Первый такой сигнал, поступая на счетный вход счетчика 73, устанавливает на его выходе код, равный "1".

Этот код поступает на адресный вход узла 71 памяти величины ресурса ветвей и узла 72 памяти меток моделируемых ветвей. На вход чтения узла 72 памяти с выхода элемента 83 задержки поступает задержанный сигнал первого импульса синхросерии ГИ1. Считанная

1532942 метка с выхода узла 72 памяти поступает на вход элемента И 77. Если считана единичная метка, на выходе элемента И 77 формируется тактовый сиг5 нал. Указанный сигнал поступает на вход чтения узла 71 памяти, чем осуществляется считывание кода величины ресурса ветви с номером "1". Этот код поступает на первый вход сумматора 74 величины ресурса ° На другой вход сумматора 74 поступает код величины накопленного ресурса с выхода регистра 75 (при первом импульсе ГИ2 код "0") . С выхода сумматора 74 код суммы 5 поступает на вход регистра 75 и записывается в него по задержанному сигналу, поступающему с выхода элемента

82 задержки. Если же из узла 72 будет считана нулевая метка (ветвь с номером "1" в рассматриваемый момент не моделируется), сигнал чтения узла

71 памяти не вырабатывается и суммирование не производится. Следующий тактовый импульс установит на выходе 25 счетчика 73 код "2", и процесс определения суммарного ресурса повторяется .

После просмотра всех возможных номеров ветвей графа на выходе переполнения счетчика 73 формируется сигнал высокого ЗО уровня. Этот сигнал поступает на выход

22 признака выдачи величины ресурса, через элемент ИЛИ 81 на нулевой вход триггера 76 и на вход блока 79 элементов И, На другой вход блока 79 элементов И с выхода регистра 75 поступает код величины суммарного ресурса. С выхода блока 79 элементов И код величины суммарного ресурса поступает на выход 21. На этом блок 3 регистрации и сложения массивов работу заканчивает, Блок 4 регистрации и сравнения массивов (фиг.5) работает следующим образом.

После окончания моделирования длительности каждой ветви графа на вход записи узла 85 памяти меток исполнения ветвей с входа 27 поступает сигнал признака окончания моделирования ветви, 50 а на адресный вход узла 85 памяти с входа 26 поступает код номера этой ветви, Производится запись единичной метки исполнения ветви в узел 85 памяти по адресу номера этой ветви.

Далее производится анализ исполне5S ния узла, в который входит исполненная ветвь. При этом в блок 4 регистрации и сравнения массивов с выхода элемента 10 задержки поступает задержанный сигнал признака окончания моделирования ветви, а с выхода регистра 7 — код номера конечного узла этой ветви. Сигнал признака окончания моделирования ветви поступает на единичный вход триггера 90, устанавливая его s единичное состояние, а также на вход чтения узла 87 памяти адресов первой входящей ветви узлов сети. На адресный вход узла 87 памяти с выхода регистра 7 поступает код номера конечного узла исполненной ветви. Считанный из узла 87 памяти код номера первой входящей ветви через блок 94 элементов ИЛИ поступает на информационный вход регистра 88 адреса входящей ветви и записывается в него по первому тактовому импульсу, поступившему на установочный вход регистра 88 с выхода элемента И 91. С выхода регистра 88 код номера первой входящей ветви поступает на адресный вход узла 86 памяти адресов входящих ветвей узлов сети и через блок 93 элементов ИЛИ на адресный вход узла 85 памяти меток исполнения ветвей. Первый импульс с выхода элемента И 92 поступает на вход считывания узлов 85 и 86 памяти. Из узла 86 памяти считывается код номера второй входящей ветви, который через блок 94 элементов ИЛИ поступает на информационный вход регистра 88. Из узла 85 памяти считывается метка исполнения ветви. Если будет считана нулевая метка, что соответствует йеисполнению ветви, сигнал с выхода узла 85 памяти через элемент НЕ 96 поступает на выход 31 признака неравенства массивов, а также через элемент НЕ 96 и элемент ИЛИ 95 на нулевой вход триггера 90, устанавливая его в нулевое сосотояние. На этом блок 4 свою работу заканчивает. Если же из узла 85 памяти будет считана единичная метка исполнения ветви, анализ исполнения узла продолжается дальше. Ilo второму тактовому импульсу B регистр 88 записывается код но-, мера второй входящей ветви. Ilo адресу этой ветви из узла 85 памяти производится считывание метки ее исполнения, а также осуществляется считывание номера третьей входящей ветви из узла 86 памяти. Описанный процесс продолжается до тех пор, пока из узла 85 памяти по какому-либо ад16

1532942

55 ресу не будет считана нулевая метка исполнения ветви (при этом на выход

31 выдается сигнал признака неравен ства массивов}, или же пока из узла

86 памяти не будет считан код Х, означающий конец списка входящих вет" вей. В этом случае код Х с выхода регистра 88 поступает на вход де,. шифратора 89, где методом сравнения

| кодов вырабатывается сигнал призна,ка равенства массивов. С выхода, дешифратора 89 сигнал признака ра венства массивов поступает на выход

32, а также через элемент И 95 на нулевой вход триггера 90. На этом блок 4 работу заканчивает.

:формула изобретения

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

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

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

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

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

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

1532942

1532942

Корректор Э.Лонцакова

Редактор M.Öèòêèíà

Тираж 668

Заказ 8101/54

Подписное

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

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

Производственно-издательский комбинат нПатент", r. Ужгород, ул. Гагарина, 101

С8ьмо иене

ЯЧ

Фиг, ч

Составитель А.Мишин

ТехРед И.Xоданиv