Вероятностное устройство для анализа сетей Советский патент 1982 года по МПК G06F15/173 G06F7/70 

Изобретение относится к вычислительной технике и предназначено для решения задач анализа сетей, представленных вероятностными графами, в частности, для определения надежности связи между вхо ными и любыми из выходных элементов рассматриваемой вероятностной сети. Известны устройства для моделирования вероятностных графов, содержащие генератор тактовых импульсов, запоминающие триггеры, схему сравнения , запоминающее устройство и другие яы Cl . t2 . Наиболее близкой по технической сущности к предлагаемой является вероятностная машина, содержащая генератор тактовых импульсов, датчик случайных чисел, схему сравнения чисел, запоминакшее устройство, регистр сдвига, диодные вентили, потенциальные триггеры в качестве промежуточной памяти, импульо ные вентили, коммутационное поле, выходные счетчики и регулируемый счетчик циклов 3 j . Основным недостатком известного устройства является низкое быстродейст вие машины вследствие последсйвательного принципа работы. Это обстоятельство препятствует получению с помощью указанной машины достоверных статистических аналоговых искомых характеристик вероятностных графов и приемлемое машинное время, что обусловлено известной сходимостью метода Монте-Карло l/VFip , где N о - число циклов моделирования. Кроме того, недостатком является тот факт, -что все ранее заявляемые устройства для анализа стохастических сетей, как показали экспериментальные провер-i ют, позволяют исследовать лишь струк туры, в которых отсутствуют обратные связи между элементами. Цель изобретения - повышеш:е быстродействия. Поставленная цель достигается тем, что вероятностное устройство для анализа сетей, содержащее генератор тактовых импульсов, блок выходных счетчиков. счетчик 1ШКЛОВ, дополнительно содержт блок наборного поля, блок И (1,2...) преобразователей код - вероятность по числу максимального количества вероятностных элементов исследуемых сетей, формирователь двоичного кода, триггер, первый, второй, третий и четвертый формирователи импульсов, и элемент И, rtepвый вход которого соединен с выходом генератора тактовых шипульсоВ; второй вход - с единичным выходом триггера; а выход - с входом третьего формирователя импульсов, счетным входом счетчика циклов и первым входом блока наборНО1Ч) поля, выход третьего формирователя импульсов соединен с группой сдвиговых входов блока преобразователей код вероятность и входом четвертого формирователя импульсов, выход которого соединен с вторым входом блока наборного поля и блока выходных счетчиков, группа выходов блока наборного поля соединена с группой входов блока выходных счетчиков, нулевой и единичный входы формирователя двоичного кода являются нулевым и е циничным вхоцами устройства, а группа выходов -соединена с группой установочных входов счетчика циклов и 2 гх группами установочных входов блока преобразователей код - вероятность, группа выходов которого соед нена с группой входов блока наборного п ля, вход первого формирователя импульсо является входом запуска устройства, а выход соединен с входом сброса блока выходных счетчиков и с единичным входом триггера, нулевой вход которого сое динен с выходом счетчика циклов, вход второго формирователя импульсов является входом записи числа циклов устройст ва, а выход соединен с управляющим входом счетчика числа циклов. На чертеже представлена блок-схема предлагаемого устрбйства. Устройство содержит генератор 1 так товых импульсов (ГТИ), первый формирователь 2 импульоов, триггер 3, элемент И 4, третий формирователь 5 импульсов, четвертый фо13мирователь 6 импульсов, второй формирователь 7 импуль сов, счетчик 8 циклов, блок 9 наборного поля, формирователь Ю двоичного кода, блок 11 выходных счетчиков, блок преоб разователей 12 код - вероятность. Выход первого форгАнрователя 2 им пульсов соединен с входом сфоса блока выходных счетчиков 11 и единичным входом триггера 3, единичный выход коп торого соединен с первым входом алемента И 4. Второй вход элемента И 4 соединен с выходом ГТИ 1, а выход соединен с первым входом блока 9 набор ного поля, счетным входом счетчика 8 циклов и входом третьего форммиррвателя 5 импульсов, выход которого соединен с группой сдвиговых входов блока преобразователей 12 код-вероятность и входом чет вертого формирователя 6 импульсов. Выход четвертого формирователя 6 импульсов соединен с управляющим входом блока 11 выходных счетчиков и вторым входом блока 9 наборного поля, группа выходов которого соединена с группой входов Giioка 11 выходных счетчиков. Выход второго формирователя 7 импульсов соединен с управляющим входом счетчика 8 цик лов, выхоа которого соединен с кулевым вкоцом триггера 3. Группа выходов формирователя 10 двоичного кода соединена -с группой установочных входов счетчика 8 циклов и с группами установочных входов блока преобразователей 12 код - вероятность, группа выходов которого соединена с группой входов блока 9 наборного поля. Блок 9 наборного поля состоит из (1,2...) импульсных вентилей по числу максима/1Ьного количества вероятностных элементов исследуемых сетей и шнурового коммутатора, с помощью которого из импульсных вентилей реализуется физическая модель графа исследуемой вероятностной сети. Модель реализуется как соответствующими соединениями между задействованными на данное испытание импульсными вентилями (элементами сети), так и коммутацией входов и выходов этих вентилей на соответствующие выходы и входы блока 9 наборного поля. Блок 12 преобразователей код - вероятность состоит из и одиночных преобразователей, каждый из которых в свою очередь состоит из датчика псевдослучайных чисел (ДПСЧ), регистра числа и цифрового компаратора. Каждый задействованный на конкретное испытание преобразователь предназначен для разыгрывания случайного состояния соответствующего элемента исследуемой вероятностной сети, Ш1Я чего выкои цифрового компаратора этого преобразователя соединяется с соответствующим входом указанного элемента (импульсного вентиля в блоке 9 наборного поля). Формирователь 10 двоичного кода представляет собой группу переключателей, коммутирующих сигналы уровней О И I в соответствии с установпеьным адресом и заданным кодом на раэрядные входы либо счетчика 8 циклов, либо соответствующего ДПСЧ или соответствующего регистра числа в соответстВующем преобразователе 12 код - вероятность. Устройство работает следующим о&разом. I, ,.. На блоке 9 наборного поля посредст вом шнуровой коммутации реализуется граф исследуемой вероятностной сети,при чем выходные звенья сети подключаются к выходным счетчикам блока 11, а . вкоцные звенья соединяются с выходом элемента И 4, Импульсы, поступающие с этого выхода, нспо/шзуйэтся в качестве сигнада прозвонкй сети. Затем с помощью формирователя Ю двоичного кода по соответствующим адресам в блок преобразователей 12 код - вероятность заносятся начальные случайные комбинации двоичных чисел для ДПСЧ, а также двоичные коды вероятностей состояния элементов сети для регистров числа. Далее посредством формирователя 10 двоич ного кода и формирователя 7 импульсов в счетчик 8 циклов заносится необходимое число циклов моделирования, по команде Запуск сбрасываюггся выходные счетчики блока 11 и триггер 3, затем происходит моделирование иссле/ емой сети методом Монте-Карло. Каждый элементарный цикл моделирования проходит следующим образом. По переднему фронт каждого импульса ГТИ 1, прошедшего на выход элемента И 4 и далее в счетчик 8 циклов и блок 9 наборного поля, посредством формирователя 6 импульсов сначала формируется короткий импульс, для одновременного обновления содержим го всех ДПСЧ блока преофазователей 12 код - вероятность, которое с помощь цифровых компараторов сравнивается с соцержимым регистров числа и далее на выходах компараторов появлякугся сигналы, разрещающие или не разрешающие прохождение импульса через соответству щий импульсный вентиль, причем сигнал сохраняется в течение всего элементарного цикла моделирования. Затем с помо щью формирователя 6 имщльсов формируется стробирующий импульс, отпираю щий одновременно все импульсные вентили блока 9 наборного поля н обеспечива ющий прохождение импульса прозвонки только в период действия стробирукщего импульса. В противном случае в структурах, содержащих обратные связи, воэниКают участки сети, которые остаются в устойчивом состоянии (триггерный эффект) и препятствуют нормальному прохождению импульса прозвонки по этим участкам во втором, третьем и других последующих тактах. С формированием каждого импульса ГТИ одновременно происходит вычитание содержимого счетчика 8 циклов. Затем описанный процесс повторяется. Число элементарных циклов, описанных выше, занесено в счётчик 8 циклов, и в момент, когда содержимое этого счетчика становится равным нулю, происходит переключение триггера 3, который формирует сигнал, запрещающий прохождение импульсов ГТИ на выход элемента И 4 до момента подачи очередного сигнала Захгуск на вход формирователя 2 импульсов. Предлагаемое устройство позволяет довести скорость моделирования вероятностных графов до десяти миллионов элементарных циклов моделирования в секунду. Предлагаемая блок-схема выгодно от личает предлагаемое устройство от прототипа зна штельно более высоким быст роде{Ьгтвием и расширенными возможностями по типам исследуемых структур вероятностных сетей, а также возмохшость исследования произвольных структур без каких-либо ограничений. Высокое быстродействие за счет , параллельного принципа работы, универсальность функциональных блоков, байтовая организация стохастической машины и программо-схемная совместимость ее с ЭВМ делают описанное устройство мощным инструментом, предназначенным для моделирования сложных технических систем, представленных вероятностными графами. Формула изобретения Вероятностное устройство рля анализа сетей, содержащее генератор тактовых импульсов, блок выходных счетчиков, счетчик циклов, отличающееся тем, что, с целью повышения быстродействия, онс содержит блок наборного поля, блок и (1. 2...) преобразователей код -. вероятность по числу максимального количества вероятностных элементов исследуемых сетей, формирователь двонч79401

ного кода, тризгтрр, первый, второй, третий и четвертый формирователи импульсов и элемент И, первый вход которого соединен с выходом генератора тактовых импульсов, второй вход - с единичным вы- 5 ходом триггера, а выход - с входом третьего формирователя импульсов счет ным входом счетчика циклов и первым входом блока наборного поля, выход третьего формирователя импульсов соеди- 10 нен с группой сдвиговых входов блока преобразователей код -вероятность и входом четвертого формирователя импульсов, выход которого соединен с вто рым ьходом блока наборного поля иis

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

75/8

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

Источники информации, принятые во внимание при экспертизе

1.Авторское свидетельство СССР № 191908, кл. GO6 G 7/48, 1965.

2.Авторское свидетельство СССР № 222754, кл. G06 G 7/48, 1967.

3.Авторское свидетельство СССР № 193158, кл. GO6G 7/15, 1966 (прототип).

л.