Устройство для решения задач на графах Советский патент 1992 года по МПК G06F15/419 

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

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

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

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

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

О

ел

00 4 О

В сош емснпъ х радио-к .г-ктчюнмыу ус г рОЙСШЛ/. i: -.- Vv:-; и rn,. iV r;n i enЫih-x сил:

1 о ,-,,) Y . :: .;,- . г i ;- , j ;, n . M. : p P : : I

i.v i-f. i i .-; гч-Ч г....: I .r.i .r..ii.i oro ro

p -.-.:;..:.,.... ( .- (..УЧ, 1 ; J , 1 ; . Г, 1 f. i Ч М Г: 11 f

; :- r. ii.i/. ;r .; -f-: пг.ч -,-i-1i; i ч,.--: г .won .,.;; , ; : ;::. -И 1 : ;. i i , , ,:;.:,,- .- -,.-: I .: -.:.-. .

; V ..,,-,.:,. . : ..,.. i i;i - .. : -:.- . ,: , v; .,.. .;,;.. . -.; r ;; n ;.., ), ., : ; - ;..-. ...

... .. --: ; ..-.ч ..::: : :,

i ;. -..-ч : i..:.. :.-..... i- ; . -.: .,-,. ,::.:...

..-. : .... Jl : ; .. . I:- -

.: . ; .,- -i

........I ;. -. - . I I I-,.: .. , i 1

. .: ,,.. -,.-i ,. ., .. .. -., .П , j. V i r-.(- : . ;.. , v- :.-„ . У1 -;: ;: ; ..I. : : , ... I ... - : ,r- ., ... : Г

. . :; . : .. f,

- - -.. -..;.-:,, -.; ,.:,. - ,-, , i

; i. . -. .. ; i .; I...; ;: .

. :.- .;. ; .1 . ;.- .. ; : (,;-:

...;...- , ... , . f- , i - M, .-

...-:v .. ;. ..f .

, i , . ::;-: - . .;-. , ,

. . - H - ,;.. i-.--i

:

. :

: - :

: ( J

: : . , i : .;: ..i : ;. 1 I I -.ltd: iv

..;- i /, . - . .. I Л Л К 1 Я

/ : . i о .. v. I I.M , HO ,;(.. - MI;: ГУ

.. .-.r, ,n-., .. :;, ,.-;;-.. a ;, (. I :/ :

.,: .- Mil- .f.1}-; . - ПЛ hi i :H

:.-. ,:. i ; :: -., . ;: . . ... .-,. .млн, .; r ;; . , i i

Г- : . ,- . С :. ,..:,; .. -i... -41 . I . I,; :|:l V . ;.

; -, . ; ;..;. i.:; ,. .-;.,:. ,...;,-. ; . : ;:

. . ; .. , . -.. ..-. ... : ;: .f. ; . i ,.

; ;.. .:: - ,i- ;i / r. Чг);1

.i ,;.i .,;.t-; . : f. . .. f .r.;1 : : глт1.

. : . :... : : ; f :.. i i ;

:r -,. -: ; ;: n i .,. , , ;

...- : ..i - .., i ... ;,... : -.,- , , .,,. . ,- . /и ri.i ii-...-i ;.

. iHt .- .. .: ..-): Ml,. . .;, :/-Ц i, i -,. :. .,

:L UJ:- ЧИ1Н L,/.;-, L l i:-v i ,. ,.-,:.f . . ., i;,(,

f. . Г-.Т- ( ..; .-I .г-л1 i r , ; ,

., : . у - . . , .. : ...

1 i,1 : . .i. i.-;.-:-.... Pi :i .. : . , . : ,: j... , :;

.-. ;-.: :../ : . ..- ;. -... ; ..,-/.; г..

) - .v-,- i ; ;... : f ,r.- . . : ; . Г.РС/

- :/. ;. f . . ;-.. .-).. . . i: :.; ; f ::-.,- i-

-, -. . C;, ...; -f.. .v /ij . :- ; i

iVI; . i.,. . : : : : . ,./.; -I -Ч: J . I

h- .- ;i.; /V V i. . - fl1.

; . :i i л . ::. .., . . .-: -..- v i ,:

Ц :i; . -Ohi: : .. -... ,. :: ., % - .- ч -:u .

1 ; ) - i . ,,.,. i .- ; . .1.

.

нем с выходом 10 признака наличия отказа системы устройства.

Усфпистно раГютлеп с.ледуюи|им обрз10 М

,a начапом раПгпы каналы ГС.С 2 н,к; т, ма заданные законы распреде- . -;нчз г.луччйных .чтии и конкретные зна --i-:ii-- ...-iMOipnP . | (i.e. ЗУД- ЮТ

-ч:(..;осп1 cyuier.r orjf-ния нершин и /;yi rp;i.. К ром о того, на 7 9 ПО/ЛЧРГСП

,-,:.(|;:М;ЦЦ1Ч. КОГОО. Я 3;1 1МОЫНЧе 10 В СООГ М Т. i i.yK:M.P-ie ОЛОКИ ИР ВХОД 6 ПуОГ ПОДЛЮГ

..i.i;V.:b. у |;. арл...-н11я . Г1)и:чом ЬГ, i форVa i-yO1 И -.: ГЛЮИ.Х Г.: 40, i Г у. 1 И / ПГ С ШДОВ;:

тс j i.i: .o г,, ии ;-ч .. in, еду; мл р о иную

.;--:( ..н.-,й .-(:-эЧ J IM Р О p. j: ;oi-..i. Сигнал

. -; ..«..ТОМГЯ 1 :П -.:1С НГ.р.ОМ ЯХ ,1С П ц.Гу- :-.,;- -.-.) | Лл М..Г.||.П Н,-.(У (ТЧ . .MOM l CV

. j 1..7ьТ -.aCfVj iX i(L,.-;. -.;i,-jv Н.-)Г,О1 nr-T.jH- ,и -Г. :ц ,.;ip:iRnt1l-i|.r; ( Я/; i; ч-« с -.. ; :; ч.ч:.1Гр:-.-. --- и :) 1 г у f. -- :, n. i.tv) п ро:.м i ii;м.:-). Н:-.. ..VIM.-: l на i.:,.,i:-4 i C.C - i - i M: lua-iM нь:я i ;у . . ,- ;,,:-pV faUf 1Г-л ; r;r-iOio iin:. ;-; п;;г.1е :. i; ; ;м; т оыходог Ы i .5 ;ia LOOI «e ir. г-зую

.. -. П/ОДЫ bOl. 4 КОТорЬЧ О f |) СП. С Л Н е 1

, --ииныи п: С р.|Ф:3 и гы,;лс . rt. значение :.« |.г;чо; : MM.-linpM.-inHi-iiiHi, - ,...::i; па i..-p- t4 -i tiM-J -.pi. :iii..-.iOH;n-.-|. н,:,. опока ) ,,л;ч 0 . г/ ;:,- ,- в рс-м ; j i, О ; I f : -1 Д л Я

,1,;;:с, у к п 1 Я-, I.V {ii 1 Ни ОС О ; :,, j;a) : .уо- с,. ---i-j/lчл снм.-г.-, -;0j; -i l-.-if,1 . 1 -Ю1Ц| Й П.Э Р-;ОД О г:; :(-,,.- 1 Г;ЛОКа 5 CpDf;- i. ,-K UV I 1()И 3TOM .O . 5 r.;;P Ut -:ll iiJ иравнм;;.;. r информап.. умичлую на ого

:(фирМ,Ч111-1 :( НлОДМ :.СЛИ ТНачОН 1. ВО. -. мы иог.ту нчн ):--: i1 nept :i ( ;-JDM, МНЫП . . ЧН i L1,4 :.-., МП,

. -, - . irv.i Hf. Ь ..1 МНф ..ч;Г, .)| ;:;, f- : : .11.;

-О.-. 0 H-; НЫХОД:; rppi-KMV- Krt -.Oi..: j,:; f;;|.;

ср,шн :нигн- C Ot;f-iHpy :- .я . 1 no

;|.;-. 0 .-IIJ/C. I r :- i Чг.ч.; :i (.ЧЛПЧИЯ : .) Oil. -.ЧЫ ,-. if iji V- . R npOTHF.HOM

1 о ;.- H. . ...охраняет уровень

: . i .;....,:.- op;.: :,.- ,; :.: :Hi,iuci

; -:.-; о;н)т„ уг -рпйстпа закан ива: . : г.

. ДОНГ1/.-; .-, :;:,1ЬНЫХ уЗЛОВ И СВЯ

:: ff:U -i -:, iM -ДО . L j ч. :. Ь СИСТем.

, ,;/.. -: .;;. представить гра- f, ом .о i р-:ы;пим ,-;.., чония требуемой

.-I о . но...- / -г .,( --ния заданного .;. ;. .-,i,c к, uii-ii..,- i . . гемы.

f; i1 1 у - з i : i е т е н и я .. rpiv,i, м-.,-., i; . ,. пня задач пч ipa

i . ;--- .v;j iu; - .,.. i-.. - ...«хронизации. мно- г,:..:-,1;;,.-н-n,i. i ;F-i:t di n , лучайных событий

i.1,..-: ..rvinblit .и ..:. пймлги, причем

i : д. н, yi юойс . - :.дключен к

пуска блока синхронизации, К-й выход первой группы и (К,М)-й выход второй группы многоканального генератора случайных событий (,,..,В; М 1.....В. где В - количе- с(ло вершин в графе) подключены к входам опроса К-ro канала первой группы и (К,М)-го канала второй группы многоканального бло- кя памяти соответственно, отличающе е с я 1вм что, с целью расширения функциональных возможностей устройства путем определения состояния отказа системы, описываемой графом, по критерию обеспечения требуемой вероятности восстановления заданного уровня эффективности системы, в него введены блок сложения и блок сравнения, причем входы задания веса К-й вершины устройства и (К,М)-й дуги устройства подключены к. установочным входам первой и второй групп многоканального блока памяти соответственно, информационные выходы К-го канала первой группы и (К,М)-го канала второй группы которого подключены к входам К-ro слагаемого первой группы и (К,М)-го слагаемого второй группы блока сложения, выход которого подключен к первому информационному входу блока сравнения, второй информационный вход

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

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

Изобретение относится к вычислительной технике и может быть использовано для исследования надежности и живучести систем, структуру которых можно представить графами и сетями. Цель изобретения - расширение функциональных возможностей устройства за счет определения состояния отказа системы, описываемой графом по критерию обеспечения требуемой вероятности восстановления заданного уровня эффективности. Устройство содержит блок 1 синхронизации, многоканальный генератор 2 случайных событий многоканальный блок 3 памяти, блок 4 сложения, блок 5 сравне ния. вход 6 пуска устройства, вход 7 задания веса вершин графа, вход 8 задания веса дуг графа, вход 9 задания минимально допустимого суммарного веса графа и выход 1П отказа системы устройства. Каждому элементу графа ставится в соответствие вес, характеризующий затраты, необходимые для его восстановления после отказа. Минимально допустимое (порсгорое) значение суммарного веса графа отражает состояние системы, еще предполагающее возможность восстановления заданного уровня эф- фективнести системы с требуемой вероятностью. 1 ил. fe

7 д