Устройство для анализа параметров графа Советский патент 1989 года по МПК G06F15/173 

1

(21).4155409/24-24

(22) 03.12.86

(46) 30.12.89. Бюл. W 48

(71)Институт проблем моделирования в энергетике АН УССР

(72)А.Г.Додонов, А.А.Котляренко, С.П.Пелехов, В.П.Лриймачук

и А.М.Щетинин

(53)681.333 (088.8)

(56)Авторское свидетельство СССР N° 907552, кл. G Об F 15/20, 1980.

Авторское свидетельство СССР № 1161951, кл. G Об F 15/20, 1983.

(54)УСТРОЙСТВО ДЛЯ АНАЛИЗА ПАРАМЕТРОВ ГРАФА

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

§

(Л

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

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

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

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

схема блока регистрации и сравнения массивов.

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

СП

со

1чЭ

СО 4Ь Ю

графа устройства, вход 19 задания номера конечного узла графа устройства, вход 20 начальной установки устройства, выход 21 величины потребного ресурса устройства, выход 22 признака выдачи величины ресурса устройства и выход 23 признака окончания работы устройства, блок 2k синхронизации, выход 25 времени работы,выход 26 номера канала, выход 27 признака прерывания счета,выход 28 номера подготавливаемой к моделированию ветви, выход 29 признака выдачи слова, выход 30 признака конца списка, выход 31 признака неравенства массивов, выход 32 признака равенства массивов, первый выход 33 синхронизации, второй выход 34 синхронизации.

Многоканальный таймер 1 (фиг.2) содержит п каналов 35 моделирования длительности ветви, узел 36 поиска канала моделирования, узел 37 загрузки канала, канал 38 измерения пути. 8 свою очередь, каждый канал 35 моделирования длительности ветви содержит формирователь 39 временного интервала, триггеры 40, 41, элементы 42...46 И, блок 47 элементов И, элемент ИЛИ 48, элементы 49, 50 задержки. Узел 36 поиска канала моделирования содержит шифратор 51 адреса, элементы ИЛИ 52 и 53. Узел 37 загрузки канала содержит узел 54 памяти длительности ветвей, узел 5$ памяти

10

15

Блок 4 регистрации и сравнения массивов (фиг.5) содержит узел 85 памяти меток исполнения ветвей, уз 86 памяти адресов входящих ветвей лов сети, узел 87 памяти адресов первой входящей ветви узлов сети, регистр 88 адреса входящей ветви, дешифратор 89 состояния X, триггер 90, элементы И 91 и 92, блоки 93 и 94 элементов ИЛИ, элемент ИЛИ 95, элемент НЕ 96.

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

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

20

25

30

40

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

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

Блок 3 регистрации и сложения мас45

сивов (фиг.4) содержит узел 71 памяти величины ресурса ветвей, узел 72 памяти меток моделируемых ветвей, счетчик 73 поиска номеров моделируемых ветвей, сумматор 74 величины ресурса, регистр 75 - накопитель сумматора, триггер 76 определения величины суммарного ресурса, элементы И,77 и 78, блок 79 элементов И, блок 80 элементов ИЛИ, элемент ИЛИ 81, элементы 82-84 задержки.

50

55

вей, входящих в узлы графа, номера которых совпадают с номерами канал блока 4, в блок 5 памяти номеров налов заносят номера конечных узло для ветвей, номера которых совпада с адресами блока Ь, в регистр 8 за носят код номера конечного узла гр фа.

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

10

15

329424

Блок 4 регистрации и сравнения массивов (фиг.5) содержит узел 85 памяти меток исполнения ветвей, узел 86 памяти адресов входящих ветвей узлов сети, узел 87 памяти адресов первой входящей ветви узлов сети, регистр 88 адреса входящей ветви, дешифратор 89 состояния X, триггер 90, элементы И 91 и 92, блоки 93 и 94 элементов ИЛИ, элемент ИЛИ 95, элемент НЕ 96.

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

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

20

25

30

его каналы загружают списками вет-

вей, входящих в узлы графа, номера которых совпадают с номерами каналов блока 4, в блок 5 памяти номеров каналов заносят номера конечных узлов для ветвей, номера которых совпадают с адресами блока Ь, в регистр 8 заносят код номера конечного узла графа.

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

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

0

0

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

В этом случае, если все ветви исполнены, импульсный сигнал уровня логической единицы появляется на выходе 32 признака равенства массивов блока k. Это возможно в том случае, если закончено моделирование всех ветвей, входящих в узел графа. Сигнал на выходе 32 признака равенства мас5 сивов разрешает в блоке 6 сравнение кодов достигнутого и конечного узлов пути. В том случае, есди достигнутый узел не является конечным, на выходе признака неравенства блока 6 появляется импульсный сигнал уровня логической единицы. Этот сигнал через элемент ИЛИ 13 „запускает блок 2 ввода-вывода, и каналы таймера 1, свободные для моделирования ветвей,

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

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

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

На этапе подготовки ветвей графа к временному моделированию после определения каждой исходящей ветви на

, вход 29 с многоканального блока 2 ввода-вывода поступает сигнал признака выдачи слова, а на вход 28 - код номера подготавливаемой ветви. С входа 29 сигнал признака выдачи слова поступает на вход чтения узла 5 памяти длительности ветвей узла 37 загрузки канала и на входы элементов И kk и kS первого канала 35(1) моделирования длительности ветви. Если триггер М первого канала 35 (1) моделирования длительности ветви находится в единичном состоянии (канал занят), сигнал единичного уровня с выхода элемента И kk поступает на

5

0

0

5

входы элементов И 44 и 45 второго канала 35 (2) моделирования длительности ветви. Если триггер 41 и второго канала 35 (2) находится в единичном состоянии, сигнал единичного уровня с выхода элемента И 44 второго канала 35 (2) поступает на входы элементов И 44 и 45 третьего канала 35 (3) моделирования длительности ветви и т.д., до первого свободного канала 35 (k). В первом свободном канале 35 (k) сигнал с выхода элемента И 45 через элемент И 48 поступает на вход шифратора 51 адреса узла 36 поиска канала моделирования. С выхода шифратора 51 адреса код номера свободного канала поступает на адресный вход узла 55 памяти номеров моделируемых ветвей узла 37 загрузки канала. На информационный вход узла 55 памяти поступает код номера подготавливаемой ветви с входа 28, а на вход записи с выхода элемента 56 задержки поступает сигнал признака выдачи слова. Происходит запись кода номера подготавливаемой ветви по адресу номера свободного канала 37 (k) моделирования длительности ветви. Кроме этого, сигнал с выхода элемента И 45 свободного канала 35 (k) моделирования длительности ветви поступает на первый вход блока 47 элементов И, на второй вход которого поступает код длительности подготавливаемой ветви, считанный с узла 5 памяти длительности ветвей узла 37 загрузки канала. Указанный код длительности ветви с выхода блока 47 элементов И поступает на установочный вход формирователя 39 временного интервала и заносится в него в качестве исходной информации. На этом заканчивается подготовка данной ветви к процессу временного моделирования ее длительности. При подготовке следующей ветви на вход 29 таймера 1 опять поступает сигнал признака выдачи слова, а на вход 28- код номера новой ветви. Описанный процесс подготовки ветви повторяется.

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

0

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

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

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

5 Сигнал с выхода элемента И 43 этого канала поступает на нулевой вход триггера 41 этого канала, сбрасывая его в нулевое состояние. Данный канал становится свободным и готов для моо делирования длительности другой ветви. Кроме того, сигнал с выхода элемента И 43 через элемент ИЛИ 48 поступает на вход шифратора 51 адреса узла 36 поиска канала моделирования. С выхода шифратора 51 адреса сформированный код номера данного канала 35 (т) поступает на адресный вход узла 55 памяти номеров моделируемых ветвей узла 37 загрузки канала. На вход чтения узла 55 памяти поступает сигнал с выхода элемента ИЛИ 52 узла 36 поиска канала моделирования. Считанный из узла 55 памяти код номера ветви графа, моделирование / длительности которой окончено (исполнено) , поступает на выход 26.На выход 27 с выхода элемента 57 поступает сигнал признака окончания моделирования ветви. Начинается этап анализа исполнения узла и подготовки к

® моделированию исходящих ветвей.

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

5

0

5

915

пути, а также на вход блока 61 элементов И. На второй вход блока 61 элементов И поступает код отрезка пути с выхода счетчика 58 длины пути. С выхода блока 61 элементов И код отрезка длины пути поступает на выход 25. Единичное состояние триггера 59 разрешает прохождение тактовых импульсов на вход счетчика 58 длины пути. С приходом каждого импульса код счетчика

увеличивается на 1, таким обра зон формируется величина отрезка пути. Кроме

,того, сигнал с выхода элемента И 60 канала 38 измерения пути поступает на входы элементов И 46 всех каналов 35 моделирования длительности ветви. У тех каналов, которые заняты моделированием длительности ветвей, на второй вход элементов И 46 поступает разрешающий потенциал с выхода триггера 41. С выхода элементов И 46 сигналы измерительной серии поступают на счетный вход формирователей 39 временного интервала. Формирователи 39 работают на вычитание, с приходом количества импульсов, равного минимальному коду, занесенному в формирователь, последний обнуляется, и на его выходе формируется сигнал переполнения. Это означает, что данный канал 35 окончил моделирование дли тельности ветви. С выхода формирователя 39 сигнал поступает на единичный вход триггера 40, устанавливая его в единичное состояние, а также на вход элемента ИЛИ 53 узла 36 поиска канала моделирования.С выхода элемен- та ИЛИ 53 сигнал высокого уровня поступает на входы элементов И 42 и 43 первого канала 35 (1) моделирования. Если триггер 40 первого канала 35 (1) находится в нулевом состоянии (канал не окончил моделирования длительности ветви), сигнал с выхода элемента И 42 этого канала поступает на входы элементов И 42 и 43 второго канала 35 (2) моделирования длительности ветви. Если триггер 40 и второго канала 35 (2) моделирования длительности ветви находится в нулевом состоянии, сигнал с выхода элемента И 42 этого канала 35 (2) поступает на входы элементов И 42 и 43 третьего канала 35 (3) и т.д., до первого канала, который окончил моделирование длительности ветви. Сигнал с выхода элемента И 43 этого канала через элемент ИЛИ 52 узла 36 поиска канала модели

10

, Q

5

0

5

0

5

0

5

0

5

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

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

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

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

памяти кол номера первой ветви, исходящей из исполненного (начального) узла графа, через блок 70 элементов ИЛИ поступает на информационный вход регистра 65 и записывается в него по приходу с элемента И 68 первого им- v пульса синхросерии ГИ1. С выхода регистра 65 код номера ветви графа поступает на адресный вход узла 63 памяти адресов выходящих ветвей узлов сети, а также на выход 28. На выход 29 с выхода элемента И 69 поступает первый тактовый сигнал признака выдачи слова. Начинается процесс подготовки к моделированию первой исходящей ветви. Кроме того, первый импульс с выхода элемента И 69 поступает на вход чтения узла 63 памяти, осуществляя считывание кода номера второй исходящей ветви. Считанный код с выхода узла 63 памяти через / блок 70 элементов ИЛИ поступает на информационный вход регистра 65 и записывается в него по приходу второго тактового импульса, поступившего с выхода элемента И 68„ С выхода регистра 65 код номера второй исходящей ветви опять поступает на адресный вход узла 63 памяти и на вход 28 номера подготавливаемой к моделированию ветви. На выход 29 с выхода элемента И 69 поступает второй импульс синхросерии признака выдачи слова. Начинается процесс подготовки к моделированию второй исходящей ветви. Описанный процесс поиска исходящих ветвей продолжается до тех пор, пока из узла 63 памяти адресов выходящих ветвей не будет считан код X, означающий конец списка исходящих ветвей. Считанный код поступает на вход дешифратора 67 состояния X, где путем сравнения вырабатывается признак конца списка исходящих ветаей, С выхода дешифратора 67 признак конца списка поступает на выход 30 а также на нулевой вход триггера 66, Триггер 66 устанавливается в нулевое состояние, запрещая прохождение тактовых сигналов через элементы И 68 ибЭ.На этом многоканальный блок 2 ввода-вывода прекращает свою работу. Блок 3 регистрации и сложения массивов (фиг.4) работает следующим образом.

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

5

0

5

0

5

0

5

0

5

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

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

После подготовки всех ветвей, исходящих из исполненного (начального) узла графа, на вход 30, а при анализе исполнения узла при неисполнении любой входящей ветви, на вход 31 поступает сигнал высокого уровня. С выхода элемента ИЛИ 15 этот сигнал поступает на входы сброса счетчика 73 поиска номеров моделируемых ветвей и регистра 75 - накопителя сумматора, устанавливая их в нулевое состояние. Кроме того, сигнал с выхода элемента ИЛИ 15 поступает на единичный вход триггера 76 определения величины суммарного ресурса, устанавливая его в единичное состояние. Если в рассматриваемый момент нет больше ветвей, моделирование длительности которых окончено, на входе 27 будет присутствовать потенциал низкого уровня и триггер 76 будет находиться в единичном состоянии. Единичное состояние триггера 76 разрешает прохождение сигналов синхросерии ГИ1 через элемент И 78. Первый такой сигнал, поступая на счетный вход счетчика 73, устанавливает на его выходе код, равный 1. Этот код поступает на адресный вход узла 71 памяти величины ресурса ветвей и узла 72 памяти меток моделируемых ветвей. На вход чтения узла 72 памяти с выхода элемента 83 задержки поступает задержанный сигнал первого импульса синхросерии ГИ1. Считанная

метка с выхода узла 72 памяти поступает на вход элемента И 77. Если считана единичная метка, на выходе элемента И 77 формируется тактовый сиг- нал. Указанный сигнал поступает на вход чтения узла /1 памяти, чем осуществляется считывание кода величины ресурса ветви с номером 1. Этот код поступает на первый вход суммато ра 7 величины ресурса. На другой вход сумматора 7 поступает код величины накопленного ресурса с выхода регистра 75 (при первом импульсе ГИ2 код О). С выхода сумматора 7 код сумм поступает на вход регистра 75 и записывается в него по задержанному сигналу, поступающему с выхода элемента 82 задержки. Если же из узла 72 будет считана нулевая метка (ветвь с номе- ром 1 в рассматриваемый момент не моделируется), сигнал чтения узла 71 памяти не вырабатывается и суммирование не производится. Следующий тактовый импульс установит на выходе счетчика 73 код 2, и процесс определения суммарного ресурса повторяется После просмотра всех возможных номеров ветвей графа на выходе переполнения счетчика 73 Формируется сигнал высокого уровня.Этот сигнал поступает на выход 22 признака выдачи величины ресурса, через элемент ИЛИ 8 на нулевой вход триггера 76 и на вход блока 79 элементов И, На другой вход блока 79 элементов И с выхода регистра 75 поступает код величины суммарного ресурса. С выхода блока 79 элементов И код величины суммарного ресурса поступает на выход 21. На этом блок 3 регистрации и сложения массивов работу заканчивает.

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

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

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

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

5- о ы 5 2о 25 . зо 4Q

,

35

45

50

55

элемента 10 задержки поступает задержанный сигнал признака окончания моделирования ветви, а с выхода регистра 7 код номера конечного узла этой ветви. Сигнал признака окончания моделирования ветви поступает на единичный вход триггера 90, устанавливая его в единичное состояние, а также на вход чтения узла 87 памяти адресов первой входящей ветви узлов сети. На адресный вход узла 87 памяти с выхода регистра 7 поступает код номера конечного узла исполненной ветви. Считанный из узла 87 памяти код номера первой входящей ветви через блок 9 элементов ИЛИ поступает на информационный вход регистра 88 адреса входящей ветви и записывается в него по первому тактовому импульсу, поступившему на установочный вход регистра 88 с выхода элемента И 91. С выхода регистра 88 код номера первой входящей ветви поступает на адресный вход узла 86 памяти адресов входящих ветвей узлов сети и через блок 93 элементов ИЛИ на адресный вход узла 85 памяти меток исполнения ветвей. Первый импульс с выхода элемента И 92 поступает на вход считывания узлов 85 и 86 памяти. Из узла 86 памяти считывается код номера второй входящей ветви, который через блок 9 элементов ИЛИ поступает на информационный вход регистра 88. Из узла 85 памяти считывается метка исполнения ветви. Если будет считана нулевая метка, что соответствует Неисполнению ветви, сигнал с выхода узла 85 памяти через элемент НЕ 96 поступает на выход 31 признака неравенства массивов, а также через элемент НЕ 96 и элемент ИЛИ 95 на нулевой вход триггера 90, устанавливая его в нулевое сосотояние. На этом блок k свою работу заканчивает. Если же из узла 85 памяти будет считана единичная метка исполнения ветви, анализ исполнения узла продолжается дальше. По второму тактовому импульсу в регистр 88 записывается код но-, мера второй входящей ветви. По адресу этой ветви из узла 85 памяти производится считывание метки ее исполнения, а также осуществляется считывание номера третьей входящей ветви из узла 86 памяти. Описанный процесс продолжается до тех пор, пока из узла 85 памяти по какому-либо адресу не будет считана нулевая метка исполнения ветви (при этом на выход 31 выдается сигнал признака неравенства массивов), или же пока из узла 86 памяти не будет считан код X, означающий конец списка входящих ветвей. В этом случае код X с выхода регистра 88 поступает на вход дешифратора 89 где методом сравнения кодов вырабатывается сигнал признака равенства массивов, С выхода дешифратора 89 сигнал признака равенства массивов поступает на выход 32, а также через элемент И 95 на нулевой вход триггера 90. На этом блок k работу заканчивает.

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

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

0

5 0 о 5

0

5

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

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

17

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

18

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

у/ тгр ъ3

1625 ™

Jtf

С выхода элемента 7 П

длвментзб

Фиг.2

30