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

 

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

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

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

РЕСПУБЛИК

lsi)s G 06 F 15/фЖ. - «, и р.„, ГОСУДАРСТВЕННЫЙ КОМИТЕТ

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4897418/24 (22) 27.12.90 (46) 15.11,92. Бюл. ¹ 42 (71) Московский институт инженеров гражданской авиации (72) С,Ж.Кишенский, Н.С.Вдовиченко, А.Л.Кузьмин и О,Ю.Христенко (56) Авторское свидетельство СССР № 1265815, кл. G 06 G 7/52, 1985.

Авторское свидетельство СССР № 1273959, кл. G 06 G 7/52, 1985. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ВЕРОЯТНОСТНОГО ГРАФА

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

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

НЕ, причем выход первого генератора случайных сигналов соединен с информационным входом ключа, выход которого соединен со счетным входом счетчика, выход которого подключен к первым входам элементов запрета и к входу первого элемента ИЛИ, выход которого соединен с входом сброса первого триггера, выходы второго и третьего генераторов случайных сигналов соединены соответственно с установочным входом второго триггера и с вхо„,5Ц „„1775725 А1 (57) Изобретение относится к вычислительной технике и может быть использовано при моделировании процессов функционирования сложных систем. Цель изобретения— повышение точности и расширение функциональных возможностей за счет обеспечения моделирования систем с множеством узлов обработки. Цель достигается за счет того, что дополнительно введена группа последовательно соединенных блоков моделей ребер графа, в состав каждого из которых введены пороговый элемент, пятый элемент ИЛИ, четвертый элемент И, формирователь импульсов. 1 з.п.ф-лы, 2 ил. дом второго элемента ИЛИ, выход которого соединен с входом сброса второго триггера, прямой и инверсный выходы которого соединены соответственно с вторыми входами первого и второго элементов запрета, выходы которых соединены соответственно с объединенными входами первого и второго элементов И и третьего элемента ИЛИ, выходы первого элемента И и третьего элемента ИЛИ соединены соответственно с информационными входами первого и второго блоков индикации, выход генератора импульсов с регулируемыми частотой и скважностью соединен с входом первого элемента И и через первый элемент HE — с входом второго элемента И, вход сброса устройства соединен с входами сброса блоков индикации и с входами первого, второго и четвертого элементов ИЛИ, Недостатками известного устройства являются низкая точность моделирования из — за отсутствия учета при моделиров ании процессов технического обслуживания сис1775725 системы, где ребра графа моделируют вероятности успешной обработки некоторого задания определенным узлов системы, а вершины — передачу обработанного задания другому отрабатывающему узлу системы, Целью изобретения является повышение точности моделирования и расширение функциональных возможностей эа счет обеспечения моделирования систем с множеством узлов обработки.

10

На фиг.1 приведена структурная схема устройства для моделирования вероятностного графа; на фиг.2 — структурная схема блока модели ребра графа, Устройство для моделирования вероятностного графа (фиг.1) содержит генератор входных импульсов 1 и последовательно соединенные К блоков моделей ребер графа 2, 20 выход генератора импульсов соединен с информационным входом первого блока модели ребра графа, вход 3 запуска устройства соединен с входом запуска генератора 1 и с входами сброса всех блоков 2.

Первый блок 2 содержит (фиг,2) RSтриггер 4, ключ 5, генератор 6 случайных импульсов, счетчик 7, элементы ИЛИ 8 — 12, 25 элемент ИЛИ, генератор 13 случайных сигты НЕ 17, 18, элементы И 19 — 22, первый 23 и второй 24 блоки индикации, формирователь 25 импульсов. Выход триггера 4 и генератора 6 случайных импульсов соединены соответственно с управляющим и информационным входами ключа 5, выход которого подключен к счетному входу счетчика 7, выход переполнения которого соединен с входами элементов И 19 и 20 и ИЛИ 8, выход которого подключен к входу сброса триггера

4, к установочному входу которого подклю40 чен информационный вход блока 2, и вход элемента И 21. Вход сброса блока соединен с входами элементов ИЛИ 8 и 9 и с входами сброса блоков индикации 23 и 24. Выход элемента ИЛИ 9 соединен с входом сброса счетчика 7. Выход элемента ИЛИ 10 соединен с входом элемента И 22 (и с входом элемента И 26), Выход элемента ИЛИ 11 соединен с информационным входом блока индикации 24. Выход элемента ИЛИ 12 сое45

50 динен с входом элемента И 20. Выход генератора случайного сигнала 13 соединен через пороговый элемент 16 с входом элемента НЕ 17 и с входом элемента И 12.

Выход генератора импульсов 14 соединен с входами элемента НЕ 18 и элемента ИЛИ

12. Выход генератора импульсов 15 соединен с входами элемента И 21, формировате55 является истинным вероятностным графом ля 25, элемента ИЛИ 9. Выходы элементов темы; узкие функциональные возможности и область применения за счет отсутствия возможности моделирования более одного ребра вероятностного графа системы одновременно; отсутствие учета всех ситуаций, возникающих в моделирующем устройстве для точной индикации его вероятностных характеристик.

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

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

Недостатками этого устройства являются невысокая точность моделирования:вопервых, в прототипе генераторы отказов и восстановлений независимы, что принципиально не позволяет достичь произвольной требуемой точности моделирования надежности системы, так как в реальной системе и ринципиально не позволяет достичь произвольной требуемой точности моделирования надежности системы, так как в реальной системе принципиально не возникают ситуации "двойного" отказа без восстановления по первоначальному отказу, а потоки отказов и восстановления зависимы — вернее, поток восстановлений связан (хотя бы статистически) с потоком отказов; во вторых, в прототипе в силу его структуры имеет место ограничение на закон формирования входных импульсов (моделирующих количество работ): импульс инициализации очередной работы.(с генератора 18 — в нумерации прототипа) может сформироваться лишь после окончания моделирования выполнения предыдущей работы, иначе он будет потерян, а результаты моделирования искажены; в-третьих, начало процесса технического обслуживания (TO) системы, совпавшее с процессом выполнения работы, также искажает результаты измерения, так как не фиксируется в блоках индикации; узкие функциональные возможности, не позволяющие моделировать системы с множеством узлов обработки (что, собственно; и налов, первый 14 и второй 15 генераторы

30 импульсов, пороговый элемент 16, элемен1775725

10

И 17 и 18 соединены с входами элемента И

19, выход которого подключен к информационному входу блока индикации 23 и является выходом блока 2. Выходы элементов И

20, 21, 22 (и 26) соединены с входами элемента ИЛИ 11. Выход формирователя 25 соединен с входом элемента И 22. (Остальные блоки — блоки 2 -2, могут иметь ту же конструкцию, однако, в целях упрощения их., из их состава могут быть исключены узлы М 11, 12, 20, 21, 22, 24, 25 и 26, так как показатели, фиксируемые в блоках индикации 24 второго и последующих блоков 2, могут быть простым образом вычислены из остальных зафиксированных в блоках индикации блоков 2 параметров систем ы).

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

На вход 3 запуска устройства подается импульс запуска (возможно, от одновибратора, как в прототипе, или от любого устройства, например, от ЭВМ), По этому сигналу в блоках 2 устанавливаются в нулевое состояние блоки индикации 23 и 24, через элемент ИЛИ 8 — триггер 4, через элемент ИЛИ

9 — счетчик 7; запускается генератор- импульсов 1. Генератор 1 может быть выполнен, например, так же, как и в прототипе, в виде генератора пачки импульсов, определяющей объем выборки моделируемых "работ"; генератор 1 начинает вырабатывать импульсы (по требованию пользователя при соответствующей реализации генератора 1— либо со случайным интервалом следования, либо с регуляторной частотой), поступающие в первый блок 2>, Все блоки 2> — 2к работают аналогично; выходные импульсы одного блока 2 являются входными для последующего блока 2; поэтому рассмотрим функционирование блока 2ъ Входной импульс (информационный) устанавливает триггер 4 в единичное состояние, при этом открывается ключ 5, через который импульсы со случайным интервалом следования от генератора 6 начинают поступать на счетный вход счетчика 7, который для каждого импульса с генератора 1 ("работы) моделирует случайное время выполнения данной работы. Через случайный интервал времени счетчик 7 выдает импульс на выходе переполнения; этот импульс поступает на входы элементов И 19 и 20, и на вход элемента

ИЛИ 8, с выхода которого сбрасывает триггер 4 в нулевое состояние; фиксируя окончание выполнения работы (по данному импульсу от генератора 1).

Первый генератор импульсов 14 (генераторы импульсов 14 и 15 выполнены аналогично генераторам 10 и 21 прототипа — по нумерации прототипа — и представляют собой генераторы импульсов с регулируемой частотой следования и скважностью) моделирует факт выполнения соответствующей

"работы" или ее невыполнения, например, при загрузке данного ребра графа — узла обработки, включенного в совокупность последовательно включенных узлов обработки — обработкой других "заданий", и т.д.— при абсолютной надежности данного узла (его безотказной работе). При длительности импульсов (они могут также иметь случайную длительность и период следования, или быть регулярными) — средней — т, и среднем периоде Т, вероятность выполнения работы составит Р = (Т -r )/Т, а вероятность невыполнения — соответственно О = х/Т.

Положительный потенциал на выходе генератора 14 соответствует интервалу времени, в котором работы, задаваемые генератором 1, не выполняются, при нулевом потенциале возможно выполнение работ (например, это означает, что данный узел обработки не занят другими работами), Аналогично, генератор случайных сигналов 13 (вырабатывающий аналоговый сигнал, амплитуда которого изменяется по случайному закону) выдает сигнал на пороговый элемент, который при превышении амплитудой сигнала с генератора 13 порогового уровня выдает положительный потенциал, а при снижении уровня входного сигнала ниже второго порогового уравняв нулевой потенциал, моделируя интервалы отказа узла обработки (при положительном потенциале) и восстановления (нормальной работы) — при нулевом потенциале. Узел 16 может быть выполнен в виде двухпорогового амплитудного детектора (входные пороговые уровни опорного напряжения не показаны на чертеже).

Таким образом, при безотказном интервале работы узла и его незанятости, на выходах элементов НЕ 17 и 18 — положительные потенциалы, и сигнал переполнения со счетчика 7 проходит через открытый элемент И 19 на вход блока индикации 23 (подсчитывающего успешно выполненные работы), Блок индикации аналогично прототипу может быть выполнен в виде последовательно соединенных счетчиков и цифровых индикаторов (как для блока 23, так и для блока 34) (не показано на чертежах).

В том случае, когда llpvi появлении сигнала переполнения счетчика 7 хотя бы один из сигналов с выходов генераторов 13 и 14 имеет положительное значение (соответственно — занятость или отказ узла), элемент

1775725

40

50

И 19 закрыт, и импульс со счетчика 7 не поступает в блок индикации 23, но на выходе элемента ИЛИ 12 — положительный потенциал, и элемент И 20 закрыт, через него импульс переполнения счетчика 7 поступает на вход элемента ИЛИ 11 и с него - на вход счета блока индикации 24, фиксируя невыполнение данной работы.

Генератор 15 — также генерирующий импульсы с регулируемыми частотой следования и скважностью — моделирует процес. сы технического обслуживания узла обработки 2, Аналогично, положительный потенциал на его выходе свидетельствует о процессе технического обслуживания (TO), а нулевой — о работе узла, Период импульсов определяет периодичность ТО. а длительность — продолжительность ТО. При появлении импульса (положительного потенциала) ТО на выходе генератора 15 устанавливает счетчик 7 в нулевое состояние (независимо от его предыдущего состояния) через элемент ИЛИ 9 и удерживает его, в этом состоянии в течение длительности импульса ТО. При этом импульсы с генератора

1, поступающие в данный узел 2>, через открытый элемент И 21 поступают на элемент ИЛИ 11 и на счет блоком 24, моделируя невыполнение рабо1 в течение интервала

ТО.

Важным моментом, отличающим описанное устройство от прототипа и повышающим точность работы, является следующая особенность конструкции устройства: при появлении сигнала Т0 в интервале времени счета счетчика 7. что фактически означает прерывание выполняемой работы и ее невыполнение в конечном счете, этот факт фиксируется заявляемым устройством (и не фиксируется (!) прототипом, снижая точность результатов моделирования), Это осуществляется следующим образом: в интервале счета счетчика 7 хотя бы на одном из его разрядных выходов— положительный потенциал, что вызывает появление на выходе элемента ИЛИ 10 положительного потенциала, открывающего элемент И 22. Появление в этом интервале времени сигнала о начале ТО, положительный фронт этого сигнала вызывает .формирование блоком 25 короткого положительного импульса, который через элементы И 22 и ИЛИ 11 поступает на вход счетчика блока индикации 24, Как указано выше. моделирование процессов отказов узла осуществляется в описанном устройстве блоками 13 и 16, что приближает процесс к реальным процессам отказов в системах обработки, где процессы восстановления работоспособности узлов связаны статистически с процессами их отказов, Такая реализация процессов отказов и восстановлений в моделирующем описанном устройстве повышает точность моделирования, так как используемые прототипом два независимых генератора для имитации отказов и восстановлений не позволяют принципиально реализовать требуемую статистическую зависимость.

Другой особенностью устройства является обеспечение точности результатов моделирования при произвольных законе распределения времен выполнения работ и интенсивности требований к их выполнению. В прототипе, если в процессе моделирования выполнения некоторой работы поступает требование на выполнение следующей, происходит потеря этой новой работы (в результатах моделирования), Выполнение же условия, при котором максимальное время выполнения работ (случайное, что затрудняет выполнение этого условия) меньше, чем минимальное время между требованиями выполнения очередных работ, значительно сужает область применения прототипа и круг систем, моделируемых им. В описанном устройстве данное условие (ограничение) снимается; в том случае, когда узел отрабатывает выполнение некоторой работы (счетчик 7 — в режиме счета), поступающее требование новой работы на информационном входе проходит через открытый элемент И 26 (положительным потенциалом с выхода элемента

ИЛИ 10) и также фиксируется счетчиком блока 24, как невыполненная работа, то есть— отказ в обслуживании.

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

И 19 — соответствующий потоку выполненных предыдущим узлом работ (с соответствующими моментами появления).

Совокупность показаний блоков 23 и 24 всех блоков 2 позволяет определить статистику выполнения работ в совокупности последовательных обрабатывающих узлов сложной системы, долю работ, которая "отвергается" каждым конкретным узлом этой совокупности, Следует отметить, что при произвольной выборке в узлах 22-"24 нет необходимости в совокупности блоков, перечисленных ранее, и организующих счет соответствующего блока 24, так как совокупность "отвергнутых" данным узлом работ легко вычисляется, как разность выполненных работ предыдущим узлом и числа работ, выполненных узлом 2. Таким образом, до1775725

5

30

45

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

Счетчик 7,.выдав сигнал переполнения, должен быть вновь установлен в исходное (нулевое) состояние. Если в реализации счетчика нет соответствующих цепей, это можно осуществить подключением его выхода переполнения через элемент задержки к соответствующему (третьему) входу элемента ИЛИ 9 — (не показано на фиг,2). При этом интервал задержки выбирается таким, чтобы обеспечить срабатывание от импульса переполнения последующих блоков узла

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

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

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

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

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

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

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

ИЛИ и к S-входу RS-триггера.

1775725

Составитель С,Кишенский

Техред М.Моргентал Корректор Е.Папп

Редактор

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

Заказ 4034 Тираж Подписное

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

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