13
445 SIMULATION PAR CALCULATEURS DE RI~,SEAUX LOGIQUES * par Christian KUBIAK et Jean LE SAINTMILON I.N.S.A., Lyon, option 61ectronique ** Licenci6 ~s sciences math6matiques et physiques ** RI~SUM~. - - Une mdthode de simulation de rdseaux logiques, prdsentant des ddfauts, esl exposde ici. La simulation tient compte des dispersions des caracldristiques dynamiques des circuits logiques utilisds. Ceci, en deux temps : la ddtection des uldas est e~ssurde par une simulation quasi statique, c' est-d~-dire, portant non pas sur des niveaux logiques mats sur des lransitions entre niveaux logiques. Une dtude dynamique approfondie est ensuite effectude pour rdsoudre les cas d'aldas ddtectds. La simulation quasi statique est prdsenlde ici de mani~re ddtaillde ainsi que les rdsullats du programme la mettant en oeuvre. Deux mdlhodes diffdrentes d'analyse des aldas sont ensuile exposdes. PLAN. Introduction I : Simulation par propugagion de modificagions II : Principe et ulgorithmes de la simulation quasi statique II.1. Description du rdseau logique ; II.2. Fonctionnement du rdseau logique; II.3. ModUle quasi slatique des transitions rdelles; II.4. Simulation d'un dldment; II.5. Simulation d'un rdseau sans boucle; II.6. Simulation d'un rdseau quelconque. III: Lasimu- lation temporelle III.1. Domaine d'ulilisation; III.2. Mdthode gdndrale, rdseau critique; III.3. La mdthode par analyse statistique ; III.4. La mdlhode par analyse de cas. IV : Presentation des programmes IV.1. Organisation de la simulation de ddfauts ; IV.2. Prdsentation de la simulalion saine ; IV.3. Prdsenta- tion de la simulation de ddfauts. V : Rdsultats obtenas. Conclusion. Annexe. Bibliographie (14 r6f.). I N T B O D U ~ T I O N I1 existe actuellement de nombreux programmes de simulation de r6seaux logiques. Les solutions qu'ils mettent en oeuvre sont varides et sont fonction surtout du domaine d'utilisation pr6vu. Une premiere m6thode consiste h simuler des r6seaux dont les fonctions sont d6crites en termes d'6quations logiques. Outre que des probl~mes se posent pour la prise en compte des d6lais associds aux opdrateurs, et donc des courses critiques dont ils sont la cause, cette m6thode de reprdsentation rend difficile l'6tude des d6fauts. Lorsque le r6seau est d6crit en termes d'op6rateurs et de connexions entre op6rateurs, deux approches sont possibles : -- une simulation dite compiMe [1, 2], off un pro- gramme est construit h partir de la description du r6seau logique et simule les fortctions de celui-ci ; -- une simulation dire interprdtative, plus proche du fonctionnement du r6seau, off un programme, ind~pendant de la representation du r6seau, travaille sur une description interne de celui-ci. La deuxi~me mdthode pr6sente sur la premiere l'avantage de permettre le traitement de ddfauts complexes, modifiant jusqu'h la structure de certaines parties du r~seau. C'est celle qui a ~t~ choisie ici. A ce niveau, un choix reste h faire entre deux techniques diff6rentes : - - u n e simulation temporelle, off l'on associe h chaque opdrateur ses caract6ristiques dynamiques; -- une simulation statique, portant sur des niveaux logiques, off le temps n'entre pas dans les calculs. En [3, 4] est pr6sent~e une technique de simulation temporelle, off chaque caract6ristique dynamique re~oit une valeur prdcise. On y utilise un proc~d6, baptis6 simulation d'activit6, dont nous reparlerons plus loin. En [5] est d6crit un simulateur qui tient compte de la dispersion de ces caract6ristiques, l'int6rieur d'une fourchette donn6e. Le nombre d'op6- rateurs accept6 est cependant tr~s limit~. Une simu- lation h trois 6tats a 6t~ introduite par Eichelberger et mise en oeuvre darts [6], afin de d6tecter les aMas de fonctionnement. Elle manque cependant par trop de pr6cision dans ses r6sultats. Tr~s proche de la m6thode pr6sent6e ici, est celle d6crite en [7], off est prise en compte l'~volution d'un signal entre deux affichages. Le choix de la mdthode h employer dans le pro- gramme de simulation recherch~ a ~t~ guid~ par l'objectif poursuivi : simuler le fonctionnement de r6seaux affect6s de ddfauts, en tenant compte non seulement des caract6ristiques dynamiques nominales, mats aussi de leur dispersion. Nous avons doric choisi une simulation interprd- tative, quasi statique h trois dtats, capable de d6tecter les al~as de fonctionnement. Une analyse temporelle * Etude men6e sous contrat du Comit6 de recherches en informatique, convention n ~ 70023. ** Ing6nieurs contractuels au CNET-Lannion, groupement CA.LCUL ~LECTRONIQUE ET INFORMATIQUE, d6partement CONCEPTION DES SYSTI~MES ELECTRONIQUES. 1/14 A. T~L~C., 28, n ~ 11-12, 1973

Simulation par calculateurs de réseaux logiques

Embed Size (px)

Citation preview

Page 1: Simulation par calculateurs de réseaux logiques

445

SIMULATION P A R C A L C U L A T E U R S DE RI~,SEAUX LOGIQUES *

p a r

Chris t ian K U B I A K et J e a n L E S A I N T M I L O N I.N.S.A., Lyon, option 61ectronique ** Licenci6 ~s sciences math6matiques et physiques **

RI~SUM~. - - Une mdthode de simulation de rdseaux logiques, prdsentant des ddfauts, esl exposde ici. La simulation tient compte des dispersions des caracldristiques dynamiques des circuits logiques utilisds. Ceci, en deux temps : la ddtection des uldas est e~ssurde par une simulation quasi statique, c' est-d~-dire, portant non pas sur des niveaux logiques mats sur des lransitions entre niveaux logiques. Une dtude dynamique approfondie est ensuite effectude pour rdsoudre les cas d'aldas ddtectds. La simulation quasi statique est prdsenlde ici de mani~re ddtaillde ainsi que les rdsullats du programme la mettant en oeuvre. Deux mdlhodes diffdrentes d'analyse des aldas sont ensuile

exposdes.

PLAN. - - Introduction �9 I : S i m u l a t i o n par propugagion de modificagions �9 I I : Principe et ulgorithmes de la simulation quasi statique II .1. Description du rdseau logique ; II.2. Fonctionnement du rdseau logique; II .3. ModUle quasi slatique des transitions rdelles; II.4. Simulat ion d'un dldment; II.5. Simulat ion d'un rdseau sans boucle; II.6. Simulat ion d'un rdseau quelconque. �9 I I I : L a s i m u - la t ion t e m p o r e l l e I I I .1 . Domaine d'ulilisation; I I I .2 . Mdthode gdndrale, rdseau critique; I I I .3 . La mdthode par analyse statistique ; I I I .4 . La mdlhode par analyse de cas. �9 IV : Presentation des programmes IV.1. Organisation de la simulation de ddfauts ; IV.2. Prdsentation de la simulalion saine ; IV.3. Prdsenta- tion de la simulation de ddfauts. �9 V : Rdsultats obtenas. Conclusion. Annexe. Bibliographie

(14 r6f.).

I N T B O D U ~ T I O N

I1 existe a c tue l l emen t de n o m b r e u x p rogrammes de s imula t ion de r6seaux logiques. Les solutions qu'i ls

m e t t e n t en oeuvre sont varides et sont fonct ion sur tout du domaine d 'u t i l i s a t ion pr6vu.

Une premiere m6 thode consis te h s imuler des

r6seaux don t les fonct ions sont d6crites en termes

d '6qua t ions logiques. Ou t re que des probl~mes se posen t pour la prise en c o m p t e des d6lais associds aux

opdrateurs , et donc des courses cr i t iques don t ils sont la cause, ce t te m6 thode de reprdsen ta t ion rend difficile

l ' 6 tude des d6fauts.

Lorsque le r6seau est d6cri t en termes d 'op6rateurs

et de connexions en t re op6rateurs , deux approches sont possibles :

- - une s imula t ion di te compiMe [1, 2], off un pro- g r a m m e est cons t ru i t h p a r t i r de la descr ipt ion du

r6seau logique et s imule les fortctions de celui-ci ;

- - une s imula t ion dire in te rp rd ta t ive , plus proche

du f o n c t i o n n e m e n t du r6seau, off un p rogramme, ind~pendant de la r ep re sen t a t i on du r6seau, t ravai l le

sur une descr ip t ion in te rne de celui-ci.

La deuxi~me md thode pr6sente sur la premiere

l ' a v a n t a g e de p e r m e t t r e le t r a i t e m e n t de ddfauts complexes , m o d i f i a n t j u s q u ' h la s t ruc tu re de certaines

par t ies du r~seau. C 'es t celle qui a ~t~ choisie ici. A

ce n iveau , un choix reste h faire en t re d e u x t echn iques

diff6rentes :

- - u n e s imula t ion t empore l l e , off l ' on associe h c h a q u e opdra teur ses ca rac t6 r i s t iques d y n a m i q u e s ;

- - une s imula t ion s ta t ique , p o r t a n t sur des n i v e a u x

logiques, off le t emps n ' e n t r e pas dans les calculs.

E n [3, 4] est pr6sent~e une t e c h n i q u e de s imula t ion

t empore l l e , off chaque ca rac t6 r i s t ique d y n a m i q u e

re~oit une v a l e u r prdcise. On y ut i l ise un proc~d6,

bapt i s6 s imula t ion d ' ac t iv i t6 , d o n t nous repar le rons plus loin. E n [5] est d6cri t un s im u la t eu r qui t i en t

c o m p t e de la dispersion de ces carac t6r i s t iques ,

l ' i n t6 r i eu r d ' u n e fou rche t t e donn6e. Le n o m b r e d 'op6- r a t eu r s accept6 est c e p e n d a n t tr~s l imit~. U n e s imu-

la t ion h trois 6tats a 6t~ i n t r o d u i t e p a r E iche lbe rge r et mise en oeuvre darts [6], afin de d6 tec te r les aMas

de fonc t ionnemen t . El le m a n q u e c e p e n d a n t pa r t rop

de pr6cision dans ses r6sul tats . Tr~s p roche de la m 6 t h o d e pr6sent6e ici, est celle d6cri te en [7], off est

prise en c o m p t e l '~volu t ion d ' u n s ignal en t re deux affichages.

Le choix de la mdthode h e m p l o y e r dans le pro-

g r a m m e de s imula t ion recherch~ a ~t~ guid~ par l ' ob j ec t i f poursu iv i : s imuler le f o n c t i o n n e m e n t de

r6seaux affect6s de ddfauts, en t e n a n t c o m p t e non

seu l emen t des carac t6r is t iques d y n a m i q u e s nominales ,

mats aussi de leur dispersion. Nous avons doric choisi une s imula t ion in terprd-

t a t i ve , quasi s t a t ique h trois dtats , capab le de d6tec ter les al~as de fonc t ionnemen t . U n e ana lyse t empore l l e

* E t u d e m e n 6 e sous c o n t r a t d u C o m i t 6 d e r e c h e r c h e s e n i n f o r m a t i q u e , c o n v e n t i o n n ~ 70023 . ** I n g 6 n i e u r s c o n t r a c t u e l s a u C N E T - L a n n i o n , g r o u p e m e n t CA.LCUL ~LECTRONIQUE ET INFORMATIQUE, d 6 p a r t e m e n t

CONCEPTION DES SYSTI~MES ELECTRONIQUES.

1/14 A. T~L~C., 28, n ~ 11-12, 1973

Page 2: Simulation par calculateurs de réseaux logiques

446 c . K U B I A K . -- S I M U L A T I O N P A R C A L C U L A T E U R S D E R E S E A U X L O G I Q U E S

a p p r o f o n d i e e n cas d ' a l 6 a p e r m e t de p r d c i s e r le c o m p o r -

t e m e n t d u r 6 s e a u .

L e t a b l e a u I r 6 s u m e les 6 t a p e s q u i o n t j a l o n n 6 le

c h o i x d e l a m 6 t h o d e e t c o m p l e t e sa d e s c r i p t i o n .

- - la d i f f d r e n c e e n t r e l ' 6 t a t l o g i q u e e n u n p o i n t

d u r d s e a u d d f e c t u e u x e t ce lu i ca lcu l6 a u m ~ m e p o i n t

d u r d s e a u s a i n e t a u m ~ m e a f f i chage , d a n s le cas de

la s i m u l a t i o n d u r d s e a u d d f e c t u e u x .

T A B L E A U I

Choix de la technique de simulation

S i m u l a t i o n

par r~seau d 'op~rateurs

In t roduc t ion de d~fauts -+ ] Simulat ion in te rpre ta t ive [ I ]

Simulat ion quasi s tat ique Dispersion des caract~- I avec analyse temporelle I r is t iques dynamiques --~ ! I

Etude Complexit~ de la m~thode --~ d 'un soul d~faut h la fois

i Simulat ion d 'aet ivi t~ Opt imal i sa t ion des eodts--~ baptisfie par propagat ion

de modi l ieat ions

I . S I M U L A T I O N P A B P R O P A G A T I O N D E M O D I F I C A T I O N S

D a r t s u n r d s e a u l o g i q u e , le n i v e a u l o g i q u e en u n

p o i n t n e c h a n g e p a s f o r c 6 m e n t h l a s u i t e d ' u n e m o d i f i -

c a t i o n de l ' a f f i c h a g e a u x e n t r d e s p r i m a i r e s . O n e s t i m e

h q u e l q u e s p o u r c e n t la p r o p o r t i o n d e p o i n t s d o n t

le n i v e a u l o g i q u e c h a n g e e n t r e d e u x a f f i c h a g e s . D 'of i

u n e m 6 t h o d e de s i m u l a t i o n q u i c o n s i s t e h n e c a l c u l e r

q u e les c h a n g e m e n t s d ' 6 t a t l o g i q u e e n c~es p o i n t s .

N o u s a v o n s a d a p t 6 c e t t e t e c h n i q u e a u p r o b l ~ m e

de l a s i m u l a t i o n de d d f a u t s , q u i e s t e f f e c t u 6 e e n d e u x t e m p s .

D ' a b o r d , u n e s i m u l a t i o n d u r d s e a u s a i n , c ' e s t - h - d i r e

e x e m p t d e d d f a u t e s t op6rSe. L es c h a n g e m e n t s d ' 6 t a t

l o g i q u e a u x e n t r 6 e s p r i m a i r e s s o n t r 6 p e r c u t 6 s sur les

6 1 6 m e n t s q u ' e l l e s a t t a q u e n t . I1 e n e s t de m ~ m e p o u r

t o u t e s les m o d i f i c a t i o n s c o n s t a t 6 e s s u r les s o r t i e s des d l 6 m e n t s .

E n s u i t e , le r 6 s e a u d d f e c t u e u x e s t s i m u l 6 . C e t t e fois,

o n c a l c u l e les a l t 6 r a t i o n s e i i g e n d r d e s d a n s le rd seau

p a r c h a q u e d 6 f a u t . Ces m o d i f i c a t i o n s d a n s le c o m p o r -

t e m e n t d u r d s e a u s o n t a lo r s p r o p a g 6 e s s e l o n l a m ~ m e

t e c h n i q u e q u e ce l le u t i l i s6e d a n s la s i m u l a t i o n d u r d s e a u sa in .

D a n s les d e u x cas , la m 6 t h o d e c o n s i s t e h p r o p a g e r des m o d i f i c a t i o n s q u i s o n t :

- - l a d i f f d r e n c e e n t r e l ' 6 t a t l o g i q u e e n u n p o i n t e t

ce lu i c a l c u l 6 a u m ~ m e p o i n t h l ' a f f i c h a g e p r 6 c 6 d e n t

d a n s le cas d u t r a i t e m e n t d u r 6 s e a u s a i n ,

I I . P B I N C I P E S E T A L G O B I T H M E S D E L A S I M U L A T I O N Q U A S I S T A T I Q U E

I I . 1 . D e s c r i p t i o n d u r ~ s e a u l o g i q u e .

Le r d s e a u l o g i q u e p e u t ~ t r e r e p r d s e n t 6 p a r u n

g r a p h e o r i e n t 6 d o n t les n c e u d s s o n t les 616men t s f o n c -

t i o n n e l s e t les a r c s , les l i a i s o n s e n t r e ces 616men t s

f o n c t i o n n e l s .

H . I . 1 . So i t l a r e l a t i o n d ' 6 q u i v a l e n c e E dd f in i e s u r

les 616ments f o n c t i o n n e l s p a r : f i E e 2 si, e t s e u l e m e n t

si, il e x i s t e u n c h e m i n de e I h e 2 e t u n c h e m i n de e 2

h f t . C e t t e r e l a t i o n p e r m e t de par tager le rdseau en

blocs, c h a q u e b l o c 6 t a n t u n e c l a s se d ' 6 q u i v a l e n c e de

la r e l a t i o n ~ . O n d i s t i n g u e d e u x t y p e s de b locs �9

- - c e u x q u i n e c o n t i e n n e n t q u ' u n seu l 616men t

f o n c t i o n n e l ,

- - c e u x q u i e n c o n t i e n n e n t p l u s i e u r s .

U n r6seau s a n s boucle n e c o n t i e n t q u e des b locs

d u p r e m i e r t y p e .

U n e boucle e s t l a p a t t i e d u r 6 s e a u c o n s t i t u ~ ~ p a r t i r

de t o u s l e s 6 1 6 m e n t s d ' u n b loc d u d e u x i ~ m e t y p e e t

des l i a i sons e n t r e ces 6 l ~ m e n t s .

H . 1 . 2 . N o u s p o u v o n s m a i n t e n a n t d d f i n i r su r les

b locs la r e l a t i o n d ' o r d r e s u i v a n t e : B l a B 2 si, e t

s e u l e m e n t si, il e x i s t e u n c h e m i n de B 1 h B 2. N o u s

d i r o n s q u e B 1 e s t a n t d r i e u r h B 2 (ou en a m o n t de B2). C e t t e r e l a t i o n p e r m e t d ' a f f e c t e r u n n u m d r o d ' o r d r e

a u x blocs . O n r e s p e c t e r a l a r e l a t i o n B l A B 2 ~ n u m d r o

de B 1 ~ n u m 6 r o de B 2 .

L ' o r d r e d 6 f i n i p a r l a r e l a t i o n A n ' e s t p a s t o t a l . I1

p e u t d o n e e x i s t e r p l u s i e u r s n u m 6 r o t a t i o n s d i f f d r e n t e s

p o u r u n m ~ m e rd seau . O n v e r r a p lu s l o in q u e ceci

n ' e s t p a s s a n s i m p o r t a n c e .

H . 1 . 3 . N o u s a l l o n s p o s e r m a i n t e n a n t q u e l q u e s

d 6 f i n i t i o n s c o n c e r n a n t les bouc l e s .

On a p p e l l e ensemb le de c o u p u r e s d ' u n e b o u c l e ,~

u n e n s e m b l e de l i a i s o n s q u ' i l su f f i r a i t de c o u p e r p o u r q u e

la p a r t i e d u r 6 s e a u d 6 d u i t e de 3~ d e v i e n n e s a n s bouc l e .

U n e l i a i son de r d i n j e c t i o n e s t u n e l i a i son q u i a p p a r t i e n t

h l ' e n s e m b l e d e c o u p u r e . U n e entrde ex terne e s t u n e

l i a i s o n n ' a p p a r t e n a n t p a s h l a b o u c l e e t a r r i v a n t su r

u n 616merit de l a b o u c l e . D e m ~ m e , u n e sort ie ex terne

e s t u n e l i a i s o n q u i n ' a p p a r t i e n t p a s h l a b o u c l e e t

q u i p a r t d ' u n 6 1 ~ m e n t de la b o u c l e . U n e sort ie in terne

es t la p a r t i e d ' u n e l i a i s o n de r 6 i n j e c t i o n v i r t u e l l e m e n t

A. TELEC., 28, n os 11-12, 1973 2 / 1 4

Page 3: Simulation par calculateurs de réseaux logiques

C. K U B I A K . -- S I M U L A T I O N P A R C A L C U L A T E U R S D E R I : : S E A U X L O G I Q U E S 447

coupde, qu i p a r t d ' u n 616ment de la bouc le . U n e entrde interne est ce l le qu i a r r i v e h u n 616ment de la boucle .

L a f igure 1 r d s u m e t o u t e s ees ddf in i t ions .

l ' 6 v o l u t i o n du r6seau au cour s d ' u n i n t e r v e l l e d ' a n a -

lyse r e n d r a c o m p t e du c o m p o r t e m e n t r@l du r6seau

h l ' a f f i chage c o r r e s p o n d a n t .

entr6es externes

sorties externes

~ entr6es internes

~ , ensemble de eoupure

coupure fmtlve

sorties internes

F I G . 1, - - R e p r 6 s e n t a t i o n d ' u n e b o u c l e .

La c o u p u r e v i r t u e l l e 6 t a n t op6r6e, on p e u t m a i n -

t e n a n t n u m d r o t e r les 61dments f o n c t i o n n e l s a p p a r - t e n a n t h la bouc le .

Remarque,

U n e b o u c l e a d m e t p lu s i eu r s e n s e m b l e s de coupure . Les a l g o r i t h m e s ut i l isds darts la s i m u l a t i o n s o n t ind6-

p e n d a n t s de l ' e n s e m b l e choisi .

I I . 2 . Fonctionnement du r6seau l o g i q u e .

I1.2.1. E t a t logique en un po in t .

L ' ~ t a t l o g i q u e en un p o i n t es t d~fini a r b i t r a i r e m e n t

p a r la v a l e u r d ' u n e g r a n d e u r de rdf6rence p a r r a p p o r t h des seuils p r 6 - d d t e r m i n d s . Ains i , en l o g i q u e pos i t i ve

d e u x 6 ta t s d d t e r m i n 6 s , l ' 6 t a t l o g i q u e v a u t O si la

v a l e u r de la g r a n d e u r de rdfdrence es t in fdr ieure h

tin seuil go ; il v a u t 1 si el le es t supd r i eu re h u n seuil g~.

On a b ien stir gz > go" L ' 6 t a t l o g i q u e sera n o t e i, p o u r i n t e r m 6 d i a i r e , d a n s les a u t r e s cas. L ' d t a t l og ique au p o i n t 1R h l ' i n s t a n t t se ra no t6 (g, t )R .

11.2.2. In terva l l e d 'ana lyse e t t rans i t ion rdelle.

Cons id~rons l ' e x p 6 r i e n c e s u i v a n t e : u n e s6quence ,

c o m p o r t a n t k a f f iehages es t a p p l i q u d e a u x en t r6es du r6seau. S o i t t~ un t e m p s p r 6 c 6 d a n t la p r e m i e r e t r a n s i t i o n du i e af f ichage. La i s sons i n c h a n g 6 l ' d [ a t

des en t reds apr6s ce t a f f ichage et o b s e r v o n s l ' 6 t a t de

t o u s l e s po in t s . A u b o u t d ' u n t e m p s s u f f i s a m m e n t long, la p l u p a r t d ' e n t r e e u x o n t a t t e i n t un d t a t s t ab le ;

les au t r e s son~ le si6ge d ' o s c i l l a t i o n s ou o n t un 6 ta t i o g i q u e rea l ddfini . L ' i n t e r v a l l e de t e m p s [t~, + cx~[

es t appe ld i n t e r v a l l e d ' a n a l y s e de l ' a f f i chage i. L ' d v o - l u t i o n du p o i n t R au cou r s de l ' i n t e r v a l l e d ' a n a l y s e

est appe l6e : t r a n s i t i o n r6el le au p o i n t R h l ' a f f i chage i.

E l le es t n o t 6 e (g, T g R . C ' e s t une f o n c t i o n du t e m p s sur l ' e n s e m b l e {0, 1, i}.

D a n s t o u t ce q u i su i t , nous cons idd re rons que

c h a q u e a f f i chage est m a i n t e n u s u f f i s a m m e n t l o n g t e m p s

p o u r q u e t o u s les p o i n t s qu i d o i v e n t a t t e i n d r e un 6 ta t

s t ab l e l ' a t t e i g n e n t . Si c e t t e c o n d i t i o n es t r empl ie ,

11.2.3. E t a t f inal , ~tat init ial d 'une t rans i t ion rdelle.

L ' 6 t a t f inal d ' u n e t r a n s i t i o n rdelle (g, Ti)n es t O

si, e t s e u l e m e n t si,

: I t I : V t > t I : :> ( g , t ) = ( 0 , I ) R .

On d6f in i t de la m ~ m e m a n i ~ r e l ' 6 t a t f inal 1. D a n s

t o u s les a u t r e s cas, off l ' o n ne p e u t affirmer q u e l ' 6 t a t f inal es t 0 ou 1, il se ra no t6 I p o u r i n d d t e r m i n 6 ou

i nconnu .

L ' 6 t a t i n i t i a l d ' u n e t r a n s i t i o n r6el le (g, Ti)R es t l ' 6 t a t f inal de la t r a n s i t i o n r6elle (g, T i I )R .

U n e t r a n s i t i o n rdel le e n t r e d e u x 6 ta t s l o g i q u e s

d d t e r m i n d s es t d i t e franche si

(1) 3l I : VI < t 1 ~ (g, t)R : d t a t i n i t i a l de (g, Ti)l : ,

(2) Vt 1 > t 1 ~- a t ~> (g, t)R 6 t a t f inal de (g, T i ) R ,

oh at es t un i n t e r v a l l e de t e m p s p e t i t , d 6 p e n d a n t de

la t e c h n o l o g i e ut i l i s6e . I1 es t de l ' o r d r e de g r a n d e u r

des t e m p s de m o n t 6 e e t de d e s c e n t e des 616merits.

U n e transition rdelle constanle es t la t r a n s i t i o n r~el le en un p o i n t d o n t l ' d t a t l o g i q u e es t c o n s t a n t p o u r

t ~ [ t ~ , + ~ [ .

D e u x t r a n s i t i o n s r6el les (gx, 7u)1 ~ e t (g2, Ti)R sont dgales jusqu '~ t o (on n o t e (g l , Ti)R = (92, T i )R) , si, e t s e u l e m e n t si, to

(3) V t < t o ~> ( g x , I ) R = ( 9 2 , / ) R �9

Propridtd d'dgalitd jusqu 'd des transitions rdelles.

Quel q u e so i t l ' 616ment p h y s i q u e , les v a r i a t i o n s de la g r a n d e u r de r6 f6 rence h la so r t i e s o n t en r e t a r d

d ' u n i n t e r v a l l e de t e m p s n o n nu l su r les v a r i a t i o n s

de la g r a n d e u r de rd f6 rence h l ' e n t r 6 e q u i les p r o v o -

q u e n t . Cela se t r a d u i t p a r :

si (g, Tf)e d~s igne les t r a n s i t i o n s rdelies h l ' e n t r d e d e

l ' 616ment , §

(g, Ti)s dds igne les t r a n s i t i o n s r6elles h la so r t i e de l '~16ment ,

(4) (gl, T i i e : (g2, T~ie ~ 3 ~ > 0 : (gI, Tiis = (g2, Ti)s �9 t o t0TE

I I . 3 . M o d U l e quasi statique des transitions r 6 e l l e s .

11.3.1. Les t rans i t i ons g loba les .

L a n o t i o n de t r a n s i t i o n r6elle es t u n e n o t i o n t e m p o -

re l le d i f f i c i l e m e n t u t i l i s a b l e p a r le p r o g r a m m e . Celu i -c i

t r a v a i l l e su r des e n s e m b l e s de t r a n s i t i o n s r6el les ,

appe ldes t r a n s i t i o n s g loba les . U n e t r a n s i t i o n g l o b a l e t r a d u i t les i n f o r m a t i o n s s u i v a n t e s :

3 /14 A. T~LI~C., 28, n o8 11-12, 1973

Page 4: Simulation par calculateurs de réseaux logiques

448 c . K U B I A K . -- S I M U L A T I O N P A R C A L C U L A T E U R S D E R I ~ S E A U X L O G I Q U E S

- - l ' d t a t i n i t i a l e t l ' d t a t f inal des t r a n s i t i o n s r6elles

qu i lui a p p a r t i e n n e n t ,

- - un f a c t e u r de q u a l i t d n o t d p si les t r a n s i t i o n s

rdelles c o n t e n u e s s o n t f r a n c h e s on e o n s t a n t e s , p s i

non. U n e t r a n s i t i o n g l o b a l e an p o i n t R e t h l ' a f f i chage i

sera no t6 T G i ~ = cs ,

Y = { P , P } = {0, 1, I}, se lon la v a l e u r de l ' ~ t a t in i t i a l ,

= {0, 1, I}, se lon la v a l e u r de l ' 6 t a t f inal.

11.3.2. Lisle des transi t ions globales.

I I p : e n s e m b l e de t o u t e s les t r a n s i t i o n s r6elles

poss ib les .

OIp ( l i p ) : e n s e m b l e de t o u t e s les t r a n s i t i o n s r6elles

d ' d t a t i n i t i a l 0, (1).

lOp ( I l p ) : e n s e m b l e de t o u t e s les t r a n s i t i o n s r6elles

d ' 6 t a t f inal , 0, (1).

00p ( l l p ) : e n s e m b l e de t o u t e s les t r a n s i t i o n s rdelles

d ' 6 t a t i n i t i a l , 0, (1) e t d ' 6 t a t f inal , 0, (1).

00p ( l l p ) : e n s e m b l e de t o u t e s les t r a n s i t i o n s r6elles

e o n s t a n t e s , d ' d t a t 0.

01p (10p) : e n s e m b l e de r o u t e s les t r a n s i t i o n s rdelles

d ' d t a t i n i t i a l 0, (1) e t d ' 6 t a t f inal 1, (0).

01~ (10~) : e n s e m b l e de t o u t e s les t r a n s i t i o n s f r anehes

d ' 6 t a t i n i t i a l 0, (1) e t d ' 6 t a t f inal 1, (0).

Les t r a n s i t i o n s g l o b a l e s s o n t d i tes f r a n e h e s ou

c o n s t a n t e s si y = ~6 au m ~ m e t i t r e q u e les t r a n s i t i o n s

rdelles. T o u j o u r s c o n ] m e p o u r les t r a n s i t i o n s r6elles,

on p a r l e r a d ' d t a t i n i t i a l e t d ' 6 t a t f inal d ' u n e t r ans i - t i on g loba le . D a n s t o u t ce q u i su i t , nous e m p l o i e r o n s

pa r fo i s les a p p e l l a t i o n s c, c ' ou c p o u r d6s igner les

6 ta t s l og iques 0 on 1 p a r o p p o s i t i o n h 1.

H.3.3. Propridtds des transi t ions globales.

Inc lus ion : u n e t r a n s i t i o n g l o b a l e T G z est inc luse

dans u n e t r a n s i t i o n g l o b a l e T G 2 si, e t s e u l e m e n t si,

t o u t e s les t r a n s i t i o n s r6el les q u i a p p a r t i e n n e n t h T G 1 a p p a r t i e n n e n t auss i h T G 2 . C e t t e r e l a t i o n ddf in i t

un o r d r e p a r t i e l su r l ' e n s e m b l e des t r a n s i t i o n s glo-

ba les q u e l ' o n p e u t r e p d r s e n t e r p a r un g r a p h e (Fig. 2).

T G1--> T G e s i g n i f i a n t : T G 1 = T G 2 .

00p-

01

lO~

11~

01p l O p

l i p lOO ,1o 9 11p _ l i p

FIG. '2. - - Ordre dans l 'ensemble des transitions globales.

Perle d ' in format ion associde (1 la reprdsenlation des transi t ions rdelles par des t rans i t ions globales. P r e n o n s

l ' e x e m p l e s u i v a n t . So i t la t r a n s i t i o n r6elle (g, T~)a

d6finie p a r

Vt < t ~ + At (g, t)R = (0, l ) n ,

VI > l~ + At + 3l (g, t)a = (1, t ) R ,

8t es t l ' i n t e r v a l l e de t e m p s i n t r o d u i t p a r a g r a p h e

I I .2 .3 . Ce t t e t r a n s i t i o n rdel le a p p a r t i e n t a u x t ro is

t r a n s i t i o n s g loba les s u i v a n t e s : 01p, 01p, OIp. Si l ' on

cho i s i t la p r e m i e r e t r a n s i t i o n g l o b a l e p o u r la reprd-

sen te r , on p e r d la e o n n a i s s a n c e du At. Le eho ix de

la s econde e n t r a i n e la p e r t e de l ' i n f o r m a t i o n coneer - n a n t la qua l i t 6 de la t r a n s i t i o n . Q u a n t h la t ro i s i~me

t r a n s i t i o n g loba le , e l le ne m e n t i o n n e m ~ m e plus l ' d t a t

f inal . De ce qu i prdc~de, on p o u r r a done eonc lu re :

s i une lransi t ion rdelle appar t i en t d~ p lus ieurs lransi-

l ions globales, la p lus petite d'enlre elles est celle qui

permel une perle d ' i n formal ion m i n i m a l e .

T-appar tenance . U n e t r a n s i t i o n r6elle a p p a r t i e n t

j u s q u ' h t o h u n e t r a n s i t i o n g l o b a l e TG~R (on n o t e :

E TG~R), si, e t s e u l e m e n t si, il ex i s t e une (g, Ti)[l to

t r a n s i t i o n r6elle a p p a r t e n a n t h TG~jr et 6gale jus -

q u ' h l 0 h (g, T~)n .

C e t t e r e l a t i o n est t r6s i m p o r t a n t e . E l l e a les p ro-

pr idtds s u i v a n t e s .

1. S i , quel que soil t o , une transi t ion r~elle appar- l ienl jusqu'gl t o h une t rans i t ion globaIe constanle, alors

elle esl eonstanle.

2. S i quel que soil t o , une lransi l ion rdelle appar-

l ient jusqu'(~ l o d~ une l rans i l ion globale franche, alors

elle esl franche ou eonstanle.

T - inc lus ion . U n e t r a n s i t i o n g l o b a l e T G 1 est t - inc luse

dans u n e t r a n s i t i o n g loba l e T G 2 , et l ' o n n o t e r a :

TG~ ~ T G 2 si, e t s e u l e m e n t si, t

(5) (g, T I E TG1 =~ (g, T i) E T G 2. to to

C e t t e r e l a t i o n d6f in i t un p r 6 - o r d r e q u e l ' o n p e u t

r e p r 6 s e n t e r p a r le g r a p h e de la f igure 3.

00~ ~ 01 ~ ~ ~ ,,_ ,

I O p , . .

j % [ lp ( ' ) (3 Q)

FIG. 3. - - Graphe de la t-inclusion dans l 'ensemble des tran- sitions globales.

I I . 4 . S i m u l a t i o n d ' u n 6 1 6 m e n t .

N o u s d i rons q u e 00p es t p l u s p e t i t e q u e 00p, et q u e Les a l g o r i t h m e s de s i m u l a t i o n d o i v e n t ~tre te ls

I I p es t la p lus g r a n d e des t r a n s i t i o n s g lobales , q u e les r6 su l t a t s ca lculus su r le m o d u l e t r a d u i s e n t le

A. T~LI~C., 28, n o8 i 1 - 1 2 , 1973 4 / 1 4

Page 5: Simulation par calculateurs de réseaux logiques

C. K U B I A K . -- S I M U L A T I O N P A R C A L C U L A T E U R S D E R E S E A U X L O G I Q U E S 449

plus f i d~ l emen t p o s s i b l e le c o m p o r t e m e n t du c i r cu i t

p h y s i q u e (( mod61is6 )) (le m o d u l e 6 t a n t r6alisd h p a r t i r du c i r cu i t r6el).

II.4.1. S i m u l a t i o n d ' u n ~l~ment c o m b i n a t o i r e .

Les a l g o r i t h m e s d e v r o n t a v o i r les propr i~ t6s sui-

v a n t e s 6nonc6es sous f o r m e de r~gles.

Rdgle d'appartenance. Si les t r a n s i t i o n s r6elles a u x

ent r6es d ' u n 61dment c o m b i n a t o i r e a p p a r t i e n n e n t a u x

t r a n s i t i o n s g loba le s h ces m ~ m e s ent r6es du module ,

les t r a n s i t i o n s r6el les a u x s o r t i e s a p p a r t i e n n e n t a u x t r a n s i t i o n s g loba l e s ca lcu l6es p a r l ' a l g o r i t h m e .

Rdgle de minimalitd. Si, h une sor t ie , p lus ieurs t r a n s i t i o n s g loba l e s s a t i s f o n t h la r~gle d ' a p p a r t e -

nance , cel le chois ie p a r l ' a l g o r i t h m e es t la p lus pe t i t e .

Les t h 6 o r ~ m e s q u i en d 6 c o u l e n t s e ron t donn6s p a r a g r a p h e I I .4 .3 .

~1 "~""'"~" ~ 4

F~a. 4. - - Exemple d'ordre dans l 'ensemble des ~tats internes.

II.4.2. S i m u l a t i o n d ' u n ~l~ment s~quent ie l .

Soi t E l le v e c t e u r des 6 t a t s l og iques i n i t i a u x a u x en t r6es h l ' a f f i c h a g e n ~ i,

S ~ le v e c t e u r des 6 t a t s log iques i n i t i a u x a u x sor t ies h l ' a f f i c h a g e n ~ i.

Le f o n c t i o n n e m e n t de l '616ment s6quen t i e l est

d6cr i t p a r les r e l a t i o n s s u i v a n t e s :

dpi+l = g(dp~, E l + l )

( 6 ) S I + l = f ( ( I ) l + l ) ,

off f et g s o n t c a r a c t 6 r i s t i q u e s de l '616ment e t off

(I)~ e t qb~+l a p p a r t i e n n e n t h l ' e n s e m b l e des d ta t s i n t e rnes {(:I) g }.

Cet e n s e m b l e es t p a r t i e l l e m e n t o rdonn6 se lon un

g r a p h e a n a l o g u e h ce lu i de la f igure 4, off (I) o es t le

p lus g r a n d des 6 t a t s i n t e r n e s . Voi r en a n n e x e une d6f in i t ion pr6c ise de l a r e l a t i o n d 'o rd re . P o u r la c la r t6

de l ' expos6 , n o u s d i r o n s q u e l ' d t a t i n t e r n e A est p lus p e t i t que l ' 6 t a t i n t e r n e B si la d6f in i t ion de B c o n t i e n t

celle de A, q u i es t la p l u s pr6cise des deux .

Les r~gles 6dic t6es p o u r les 61~ments c o m b i n a t o i r e s se t r a n s f o r m e n t a ins i .

Rkgle d'appartenance. Si les t r a n s i t i o n s r6elles a u x en t r6es a p p a r t i e n n e n t a u x t r a n s i t i o n s g loba les h ces

m S m e s ent r~es , si l ' 6 t a t i n t e r n e in i t i a l es t p lus p e t i t ou 6gal h l ' 6 t a t i n t e r n e s e r v a n t de base au ca lcul ,

alors l ' 6 t a t i n t e r n e f ina l es t p lus p e t i t ou 6gal h l ' 6 t a t i n t e r n e f o u r n i p a r l ' a l g o r i t h m e e t les t r a n s i t i o n s

g loba l e s ca lcu l6es c o n t i e n n e n t les t r a n s i t i o n s r6el les

en so r t i e de l ' d l 6men t .

R~gle de minimalitd. Si p l u s i e u r s 6 t a t s i n t e r n e s s a t i s f o n t h la r~gle d ' a p p a r t e n a n c e , l ' a l g o r i t h m e

f o u r n i t le p lus pe t i t . Si p l u s i e u r s t r a n s i t i o n s g loba le s

s a t i s f o n t h c e t t e m ~ m e r~gle, u n e fois l ' ~ t a t i n t e r n e

c a l c u l i , l ' a l g o r i t h m e f o u r n i t l a p l u s pe t i t e .

II .4 .3 . C o n s e q u e n c e s .

N o u s a l lons d o n n e r ici d e u x t h 6 o r ~ m e s ; l eu r ~cri-

t u r e es t i d e n t i q u e p o u r les d e u x t y p e s d '616ments , si l ' o n cons id~re q u ' u n 616ment c o m b i n a t o i r e es t un

616ment s 6 q u e n t i e l q u i n ' a q u ' u n seul 6 t a t i n t e r n e

poss ib le . N o u s n o t e r o n s TGZe les t r a n s i t i o n s g loba les +

a u x en t r6es d ' u n 616ment, TG~s a u x sort ies . Si l ' 6 t a t i n t e r n e i n i t i a l e s t p l u s p e t i t ou 6gal h

l ' 6 t a t i n t e r n e s e r v a n t de b a s e au ca lcu l , alors :

(7) a) (g, Ti)e ~ TGle ~ 3 r > 0 : (g, T*)st~r - t o

(8) b) (TGe) 1 c =>

II .4 .4 . M i s e en oeuvre d e s a l g o r i t h m e s .

P o u r les p o r t e s c o m b i n a t o i r e s , les t r a n s i t i o n s glo- ba l e s en sor t i e s o n t donn6es p o u r des t a b l e s h a d r e s s a g e

d i r ec t . L ' a l g o r i t h m e de s i m u l a t i o n d '61dments sdquen t i e l s

e f f ec tue la c o r r e s p o n d a n c e de la f igure 5.

Etat interne initial ~ i

Transitions globales aux entr~=s (*)

6tat initial des entr6es

6tat f inal �9 ~tat interne final ~ i + i =_ des sorties

�9 existence ou non d'un al6a en sortie

FIG. 5. - - Simulation d'un ~l~ment exponentiel. (*) La partie : 6tat initial des entr6es, n'est pas prise en compte (voir annexe).

5/14 A. TI~Lt~C., 28, n ~ 11-12, 1973

Page 6: Simulation par calculateurs de réseaux logiques

4 5 0 C. K U B I A K . -- S I M U L A T I O N P A R C A L C U L A T E U R S D E R I ~ S E A U X L O G I Q U E S

D u p o i n t d e v u e des t r a n s i t i o n s g l o b a l e s , o n a : §

(9) (I) ~+z = qo ((I) i, TG~ +z) ,

II.5. Simulation d'un r6seau sans boucle.

L e r d s e a u s a n s b o u c l e a 6td o r d o n n 6 (w I I -1) .

C h a q u e 6 1 6 m e n t n ' e s t s i m u l 6 q u ' a p r 6 s q u e t o u s les

616ments de n u m 6 r o i n f d r i e u r F o n t fit& O n e s t a i n s i

st ir q u e c h a q u e 6 1 6 m e n t d u r d s e a u n e s e r a s i m u l 6

q u ' u n e fois a u c o u r s d ' u n a f l i chage . P o u r u n r 6 s e a u

s ans b o u c l e , les r e l a t i o n s (7) e t (8), dd f in i e s a u p a r a -

g r a p h e I I . 4 .3 , s o n t v6r i f ides a i n s i q u e l a r6gle

d ' a p p a r t e n a n c e .

II.6. Simulation d'une boucle. Principe et mise en oeuvre.

H . 6 . 1 . C o m m e n o u s l ' a v o n s v u a u p a r a g r a p h e

I I .1 .3 , u n e b o u c l e p e u t ~ t re c o n s i d 6 r d e c o m m e l ' a s s o -

c i a t i o n d ' u n r d s e a u s a n s b o u c l e e t d ' u n e n s e m b l e de

l i a i sons de r d i n j e c t i o n . L a m a t 6 r i a l i s a t i o n de l a c o u p u r e

e s t a s s u r 6 e p a r u n 616m en t b a p t i s 6 tdte de boucle ou

T B e t q u i a s s u r e d e u x f o n c t i o n s :

-- f o n e t i o n TB~ o u i n i t i a l i s a t i o n d u t r a i t e m e n t de

la b o u c l e ,

-- f o n c t i o n T B ~ ou t r a i t e m e n t des t r a n s i t i o n s glo-

b a l e s s u r les r d i n j e c t i o n s .

I1 p o s s ~ d e d e u x n u m d r o s d ' o r d r e c o r r e s p o n d a n t :

ses d e u x f o n c t i o n s . Ce lu i c o n c e r n a n t l a f o n c t i o n T B z

es t le p l u s p e t i t des n u m d r o s d ' o r d r e de l a bouc l e .

Celu i de l a f o n c t i o n T B 2 e s t s u p 6 r i e u r h t o u s l e s

n u m d r o s des 6 1 6 m e n t s de la bouc l e . L a f igure 6

m o n t r e l ' i m p l a n t a t i o n de la t S t e de b o u c l e T B .

H . 6 . 2 . Le p r o b l 6 m e q u e d o i t r 6 s o u d r e t o u t a lgo-

r i t h m e es t ce lu i des c o u r s e s c r i t i q u e s e n t r e les r d i n j e c -

t i o n s e t e n t r e les r 6 i n j e c t i o n s e t les en t r6es . Celu i q u e

n o u s u t i l i s o n s c o m p o r t e d e u x p h a s e s , c h a c u n e d ' e l l e s

d t a n t i t 6 r a t i v e .

Premidre phase . D 6 t e r m i n a t i o n des r 6 i n j e c t i o n s ou

la t r a n s i t i o n g l o b a l e r 6 s u l t a n t e s e r a so i t c o n s t a n t e ,

so i t f r a n c h e . A la f in d e l a p r e m i 6 r e p h a s e , les t r a n s i -

t i o n s g l o b a l e s a u x r 6 i n j e c t i o n s s e r o n t de d e u x t y p e s :

- - ecp ou e-cp p o u r le p r e m i e r ,

- - . t r a n s i t i o n s p a r a s i t 6 e s p o u r le second�9

D e u x i ~ m e phase�9 C a l c u l p l u s p r6c i s des t r a n s i t i o n s

g loba les .

I I . 6 . 3 . N o u s a l l o n s d d t a i l l e r ici l ' a l g o r i t h m e en

i n d i q u a n t les t h d o r ~ m e s q u i p e r m e t t e n t de le j u s t i f i e r .

C h a q u e p h a s e c o m p r e n d u n c e r t a i n n o m b r e de

s i m u l a t i o n s d u r d s e a u s a n s b o u c l e associ6e. A v a n t

c h a q u e s i m u l a t i o n , o n c a l c u l e s e lon des r~gles p r6 -

cises, les t r a n s i t i o n s g l o b a l e s h a f f i che r a u x r 6 i n j e c t i o n s .

P r e m i e r e phase . L e s t r a n s i t i o n s g l o b a l e s h la p a s s e k

a u x e n t r d e s i n t e r n e s s o n t t e l l e s q u ' e l l e s t - i n c l u e n t les

t r a n s i t i o n s g l o b a l e s a u x s o r t i e s i n t e r n e s h la p a s s e

k - - 1 ; de p lus , l a t r a n s i t i o n g l o b a l e h u n e m ~ m e e n t r 6 e

i n t e r n e d o i t 6 v o l u e r s e l o n le g r a p h e de la f igu re 7.

Ce q u e n o u s p o u v o n s r d s u m e r p a r le t a b l e a u I I .

~-Cp -~ ecp - - ~ ccp

FIG. 7. - - Evolut ion possible d 'une t rans i t ion globale h une entr6e interne au eours de la prerni6re phase de t r a i t emen t

des boucles.

T A B L E A U I I

Rdgles de caleul des transi t ions gtobales & derire aux entr~es internes

all cours de la premidre phase de traitement des boucles

*%• entr~es

entrfes externes ~ ~

�9 ~r f " - - - - - - / sorties internes sorties externes " ~ f

Fro. 6. - - Repr6sen ta t ion~d 'une boucle avec soil 616ment t~te de boucle.

Passe k

TG h l ' e n t r 6 e i

i n t e r n e

c@

T G h la sortie i in te rne

cep ccp

aut re

Passe k - 1

T G ~_ l 'entr6e interne

ccb c c p

c~p

c@ c@ c@ aut re c~p

l i p - - l i p

c@ - - c~p

Le T B z j o u e le r61e d ' u n d r a p e a u ( f l a g ) q u i i n d i q u e

q u ' u n e b o u c l e e s t a t t a q u d e p a r u n s i g n a l , c o r r e s -

p o n d a n t h u n e t r a n s i t i o n n o n c o n s t a n t e .

E n c o n s d q u e n c e , n o u s s o m m e s st ir q u e la p r e m i e r e

p h a s e c o n v e r g e � 9

E x a m i n o n s m a i n t e n a n t les t r a n s i t i o n s g l o b a l e s a u x

e n t r 6 e s i n t e r n e s . L a f o n c t i o n d u T B 1 e s t d ' i n i t i a l i s e r

A�9 T~kkC. , 28, n ~ 11-12, 1973 6 / 1 4

Page 7: Simulation par calculateurs de réseaux logiques

C. K U B I A K . -- S I M U L A T I O N P AR C A L C U L A T E U R S DE RI~SEAUX L O G I Q U E S 451

le t r a i t e m e n t , c ' e s t - h - d i r e q u ' i l e s t dc r i t ccp ou l i p

h c h a q u e e n t r 6 e i n t e r n e , s e l o n la t r a n s i t i o n g loba l e

h l ' a f f i c h a g e p r 6 c 6 d e n t . O n p e u t d o n c a p p l i q u e r a u

r 6 s e a u s a n s b o u c l e associd , l a r e l a t i o n (7) q u e l ' o n

r a p p e l l e ici :

( g , Vl)' e ~ T~-~e:::> ~E ~> 0 : (g, Ti;s E T~G~. t o t0A-E

C e t t e r e l a t i o n e s t v r a i e a u x e n t r 6 e s i n t e r n e s j u s q u ' h

u n t e m p s t o a u m o i n s , off l ' o n a t o u j o u r s des t r a n s i t i o n s

c o n s t a n t e s ou d u t y p e l i p h l ' e n t r d e . E l l e e s t d o n c

v r a i e j u s q u ' ~ t o + z a u x s o r t i e s i n t e r n e s , d o n c a u x

e n t r 6 e s i n t e r n e s , v u l a f a ~ o n d o n t les t r a n s i t i o n s

g l o b a l e s s o n t m o d i f i d e s . L o r s q u e les t r a n s i t i o n s glo-

b a l e s a u x e n t r 6 e s i n t e r n e s n e s o n t p l u s mo~lifi6es, la

p r e m i 6 r e p h a s e e s t t e r m i n 6 e e t o n a :

Vto, (g,

e t l a m 0 m e c h o s e h la so r t i e .

L ' e x p l o i t a t i o n des p r o p r i d t d s de la / - a p p a r t e n a n c e

p e r m e t d ' d c r i r e a u x e n t r d e s e t s o r t i e s i n t e r n e s :

si la t r a n s i t i o n ca l cu lde e s t cc[9, la t r a n s i t i o n rdel le

e s t c o n s t a n t e ; si elle e s t ccp, l a t r a n s i t i o n rdel le es t

f r a n c h e o u e o n s t a n t e . O n p e u t m a i n t e n a n t p r o c d d e r

la d e u x i ~ m e p h a s e .

Deux idme phase. N o u s u t i l i s o n s c e t t e lois la r6gle

d ' a p p a r t e n a n c e . O n r e f a i t u n e d e u x i ~ m e s6rie d ' i t d -

r a t i o n s e n r e s p e c t a n t les r~gles s u i v a n t e s .

P r e m i e r e p a s s e : t o u t e s les t r a n s i t i o n s g loba le s

d i f f d r e n t e s de ccp d e v i e n n e n t c l p ( s a u l b i e n e n t e n d u

l i p ) .

A u d 6 b u t de la (k + 1) e p a s s e , les t r a n s i t i o n s glo-

b a l e s a u x e n t r 6 e s i n t e r n e s s o n t d o n n 6 e s p a r le

t a b l e a u I I I .

II .7 . S i m u l a t i o n d 'un r 6 s e a u q u e l c o n q u e .

U n r d s e a u q u e l c o n q u e e s t u n e n s e m b l e o r d o n n 6 de

b l o c s q u i s o n t des 616men t s ou des b o u c l e s . C h a q u e

b loc e s t s i m u l 6 s e lon son t y p e e t e n t e n a n t c o m p t e

de son o r d r e clans le rdseau .

III . L A S I M U L A T I O N T E M P O R E L L E

III .1 . D o m a i n e d 'ut i l i sa t ion .

L a s i m u l a t i o n p a r t r a n s i t i o n s g l o b a l e s en n e l eu r ,

d o n n a n t a u c u n e v a l e u r , s u p p o s e q u e les c a r a c t 6 r i s -

t i q u e s t e m p o r e l l e s des 616men t s p e u v e n t ~ t r e t o u t h

f a i t q u e l c o n q u e s . E n c o n s 6 q u e n c e , c h a q u e fois q n ' u n e

i n d d t e r m i n a t i o n p e u t s u r v e n i r e n u n p o i n t q u e l c o n q u e

d u r 6 s e a u , d u f a i t de p r o p r i 6 t 6 s t e m p o r e l l e s des

s i g n a u x ou des 616ments , c e t t e i n d 6 t e r m i n a t i o n e s t

a u s s i t S t d 6 t e c t 6 e . N o u s en d o n n o n s u n e x e m p l e su r

la f i g u r e 8 e n i n d i q u a n t les t r a n s i t i o n s g l o b a l e s .

10~

01~

01~ OOp

1 . V" i Ofp

10~

01~"

TABLEAU I I I

Evolution des transitions globales aux entrdes et sorties internes des tdtes de boucle

FIB. 8. - - E x e m p l e d ' a l 6 a n 6 c e s s i t a n t u n e a n a l y s e t e m p o r e l l e .

F in 1 ~'e p h a s e

e n t r S e i n t e r n e

k e passe

e n t r 6 e so r t i e i n t e r n e i n t e r n e

(k -- 1) e passe

e n t r 6 e i n t e r n e

c@ c@

ccp ccp - - ccp ccp - - c@

autre cc ' p cc'~ autre cIp elp

c~p T G a T G a

L a b a s c u l e D, d o n t la s o r t i e Q 6 t a i t i n i t i a l e m e n t h 1,

p r e n d u n 6 t a t i n c o n n u p a r s u i t e de la p o s s i b i l i t 6 d ' a p p a -

r i t i o n d ' u n e i m p u l s i o n p a r a s i t e s u r l ' e n t r 6 e D lo r s d u

f r o n t m o n t a n t s u r H . U n e a n a l y s e d d t a i l l 6 e des t e m p s

de c o m m u t a t i o n p e u t p e r m e t t r e de r 6 s o u d r e l ' i n d 6 t e r - m i n a t i o n .

E n r~gle gdndrale : u n e a n a l y s e t e m p o r e l l e s e r a

e f f e c t u d e c h a q u e fois q u ' a u c o u r s de la s i m u l a t i o n

q u a s i s t a t i q u e u n 616men t s d q u e n t i e l p a s s e r a d a n s u n

6 t a t ddgdndr6 , e t q u e c e t t e i n d d t e r m i n a t i o n a des

c h a n c e s d ' e t r e r d d u i t e p a r l ' a n a l y s e .

L o r s q u e les t r a n s i t i o n s g l o b a l e s s u r les e n t r d e s

i n t e r n e s n e s o n t p l u s m o d i f i d e s , l a d e u x i 6 m e p h a s e

e s t t e r m i n d e .

L a c o n v e r g e n c e de c e t t e p h a s e e s t 6 v i d e n t e . De

m ~ m e , on e s t a s s u r d h la f in d u c a l c u l q u e les t r a n s i -

t i o n s rde l les a p p a r t i e n n e n t a u x t r a n s i t i o n s g loba l e s

en t o u t p o i n t .

Remarques .

1. Si u n e a n a l y s e t e m p o r e l l e p e r m e t de c o n c l u r e h

l ' e x i s t e n c e d ' u n a l~a, ce lu i -c i n e s e r a p a s r e m i s e n

q u e s t i o n u l t d r i e u r e m e n t . A u e u n e a n a l y s e n e s e r a

f a i t e p o u r l e v e r u n e i n d d t e r m i n a t i o n q u i a u r a dt6

p r o v o q u d e p a r c e t a lda . Ce s o n t les t a b l e s d ' d t a t q u i

p e r m e t t r o n t d e s a v o i r si u n e t e l l e a n a l y s e e s t n d e e s s a i r e .

7/14 A. T~L~C., 28, n o~ 11-12, 1973

Page 8: Simulation par calculateurs de réseaux logiques

~ 5 2 C. K U B I A K . -- S I M U L A T I O N P A R C A L C U L A T E U R S D E R E S E A U X L O G I Q U E S

2. Dans le cas d 'une ana lyse t empore l l e concernant

un 61~ment a p p a r t e n a n t h une boucle , celle-ci nc sera

opdrde qu 'apr~s la s imula t ion non t empore l l e com- plete de la boucle.

I I I . 2 . lYI6thode g 6 n ~ r a l e , r 6 s e a u c r i t i q u e .

Le rdseau cr i t ique associ6 h un bloc est un sous-

graphe par t ie l du rdseau comple t d6fini ainsi :

il comprend d 'une pa r t l ' en semble des 616ments tels

qu ' i l exis te un chemin de ces 616ments au bloc consi-

d6r6 et que ce chemin t r a n s m e t des t rans i t ions glo- bales aut res que cop ou l i p ;

il c o m p r e n d d ' au t r e p a r t l ' en semb le des arcs for- m a n t les chemins ddfinis ici.

La figure 9 donne un exemple de rdseau cri t ique.

rdsul ta t con t i end ra les N r6sul ta ts obtenus. Chaque

r6seau sera choisi en t i r a n t au sort la va leur des para-

m~tres d y n a m i q u e s des 6ldments. On pose les hypo- theses s impl i f ica t ives su ivantes :

- - chaque domaine de va r i a t ion des caract6r is t iques

est discr6tisd. Le choix d ' un pas suff i samment fin,

selon la technologie , p e r m e t une observa t ion assez pr6cise des p h 6 n o m ~ n e s ;

- - l e s carac t6r is t iques tempore l les des divers 616-

ments sont des var iab les al6atoires i n d d p e n d a n t e s ;

- - h l ' in t~r ieur de son domaine de va r i a t ion , une

donnde t empore l l e ddpend d ' une mani~re complexe

de la t emp6ra tu re , du mode d 'u t i l i sa t iou de l'616ment,

de l ' u t i l i sa t ion pass6e de cet 616ment, etc. F a u t e de

pouvoi r poser d 'hypoth~ses plus pr6cises, nous consi-

d6rerons que routes les va leurs a p p a r t e n a n t au domaine

sont 6quiprobables .

111.3.2. M i s e en veuvre de la mdthode .

E1 00~ E2 10~

E3 10~

10 6

FIG. 9. - - Exemple de r~seau critique.

OIp

l i p

Le rdseau cr i t ique est compos~ des por tes 4, 2, 6,

des entrdes E 2, E 3, E 5 et E 6 et des arcs en t rai ts forts.

Une analyse t empore l l e n6cessit6e pour pr6ciser

l ' 6 t a t d ' u n ou plusieurs 61dments ne po r t e que sur le r~seau cr i t iqu6e associ6 h cet ou ces 616ments.

Lorsque le r6seau est d6termin6, on effectue N simu-

lat ions tempore l les des r6seaux choisis. Si au bou t

de n (n < N) rdseaux simul6s, le rdsul ta t ob tenu est

iden t ique h celui de la s imula t ion quasi s ta t ique , le

calcul est arrSt6 : l ' i nd6 t e rmina t i on existe. Sinon, le calcul est poursu iv i j u squ '~ son te rme.

111.3.3. Codt de la md thode .

L 'ana lyse t empore l l e s 'effectue sur un rdseau de

pe t i te d imension, mais un grand nombre de fois pour

ce r6seau. Le cofit sera donc assez 61ev~. Si l ' ana lyse

t empore l l e est un compl~men t indispensable h la

s imula t ion quasi s t a t ique , elle ne doi t ~tre utilisde que ra rement .

III .4 . La m 6 t h o d e par a n a l y s e de cas .

I I I . 3 . L a m ~ t h o d e par a n a l y s e s tat i s t ique .

III.3.1.

Elle est ddrivde des mdthodes d ' e s t ima t i on dites

de Monte-Carlo. Les carac t6r i s t iques temporc l les des 61~ments ne sont pas connues de mani~re pr6cise,

mais p e u v e n t p rendre leur va l eu r h l ' in tdr ieur d 'un

domaine d~fini g6n6ra lement pa r une fourchet te . De plus, les c o m m u t a t i o n s h l ' en t r6e du rdseau ne sont

pas s imultan6es, mais se p rodu i sen t dans un inter-

val le de t emps d6termin5 et connu. D e u x r6scaux de m~me s t ruc ture , mais don t les 6Mments n ' o n t pas les

m~mes caract6r is t iques tempore l lcs , p c u v e n t se corn- po r t e r d i f f6remmcnt sous une m~me action.

La m6thode consiste h op6rer une s imula t ion t em- porel le de N r~seaux diff6rents, mais de m~me struc-

ture. Du po in t de r u e des t r ans i t ions globales, le

C'est une m 6 thode alg6brique, qui prdsente sur la prdc6dente l ' a v a n t a g e su ivan t : lorsqu 'e l le abou t i t h

un r6sul ta t plus pr6cis que celui fourni pa r la s imu-

la t ion quasi s t a t ique , celui-ci n ' e s t entach6 d ' aucune

incer t i tude . El le pa ra i t c e p e n d a n t plus l imit6e, son domaine d ' app l i c a t i on privildgi6 6taut les r6seaux

cr i t iques de faible dimension.

III.4.1. Nous al lons la p r d s e n t e r s u r un e x e m p l e .

Nous avons fa i t f igurer sur le sch6ma de la figure 10

les t rans i t ions logiques qui sont pour chaque op6ra teur

le cas le plus d6favorable .

A la sortie de l ' op6 ra t eu r n ~ 5 est reprdsent6 ce qu 'on p e u t appe ler le pire cas pour cet op6rateur .

Donnons h chaque 6v6nement ( changemen t d 'd ta t ) un n o m qui est celui de la connexion oil il appara i t ,

suivi d ' u n num6ro croissant dans l 'o rdre d 'occur rence .

A. T~L~C., 28, n os 11-12, 1973 8/14

Page 9: Simulation par calculateurs de réseaux logiques

C. K U B I A K . -- S I M U L A T I O N PAIR C A L C U L A T E U R S D E R ] ~ S E A U X L O G I Q U E S 4 5 3

_r- i b - - k

I b I , t I~ T~-'I !

C t

�9 I f t

FIG. 13. - - Diagramme de temps des 6vUnements de la figure 12.

F~G. 10. - - Exemple de rUseau prUsentant des alUas.

I1 ex i s t e des r e l a t i o n s e n t r e les 6 v d n e m e n t s , q u e n o u s

r e p r 6 s e n t e r o n s p a r le g r a p h e o r i e n t 6 de l a f igu re 11,

dl [3

" : - x 2,

FIG. 11. - - Graphe des 6vUnements du r6seau de la figure 10.

d o n t les s o m m e t s s o n t les 6 v d n e m e n t s . Ces r e l a t i o n s s o n t de d e u x s o r t e s :

- - des r e l a t i o n s d ' a n t d r i o r i t ~ , ma tUr i a l i sdes p a r u n a r c v e r t i c a l ,

- - des r e l a t i o n s d e causa l i tU , ma td r i a l i sUes p a r u n a r c h o r i z o n t a l o u o b l i q u e .

U n s o m m e t s o u r c e a d t6 i n t r o d u i t d a n s la f i gu re 11

p o u r r e n d r e c o m p t e des t e m p s d i f fUrents de c o m m u -

t a t i o n s a u x e n t r d e s p r i m a i r e s .

Exemple de relations ddfinies par ce graphe.

E x a m i n o n s le c o m p o r t e m e n t de la p o r t e 3 prUsentUe s u r la f igu re 12.

C

FIG. 12. - - E t u d e d 'une t rans i t ion en sortie d 'une porte.

m u m . O n p e u t 6 t r i t e les d e u x r e l a t i o n s s u i v a n t e s :

I Tm ~< TI ~< ~ M ,

Te < S M -

Ou b i e n sous u n e a u t r e f o r m e :

i 1 , T2 ~< "~M, T1 ~ ~m �9

E n g d n d r a l i s a n t p o u r u n e p o r t e h p lu s de d e u x

ent rUes , o n p e u t e n c o r e 6c r i r e ces r e l a t i o n s a i n s i :

l Tj ~< f f M , Vj : (1, n ) , (lO)

L a d e u x i ~ m e de ces r e l a t i o n s s ign i f i e :

T 1 ou T 2 ou T 3 ... ou Tn >1 "vm.

O n t r a n s f o r m e le p r o b l ~ m e d ' e x i s t e n c e des d v d n e -

m e n t s h ~ , h 2 , h 3 de l a f i gu re 11 en u n p r o b l ~ m e

l inUaire . L a d i f f i cu l t6 rUside d a n s la n o n - c o n v e x i t d

d u d o m a i n e ddf in i p a r les c o n t r a i n t e s (10). S e l o n q u e

c h a q u e p r o b l ~ m e a d m e t o u n o n des s o l u t i o n s , o n

c o n c l u e h l ' e x i s t e n c e des 6 v d n e m e n t s associUs. L a

p r d s e n c e de b o u e l e s , t e n d h c o m p l i q u e r e n c o r e les

p r o b l ~ m e s posUs.

IV. P B E S E N T A T I O N D E S P R O G B A M M E S

L e p r o g r a m m e de s i m u l a t i o n e s t u n s o u s - e n s e r n b l e

d u s y s t ~ m e PASTIS de c o n c e p t i o n a s s i s t de p a r o r d i -

n a t e u r . II e s t 6 c r i t e n FORTRAN IV se lon la n o r m e

AFNOR. Ceci a f i n d ' a s s u r e r a u m a x i m u m l ' i n d U p e n -

d a n c e d u p r o g r a m m e e n v e r s le c a l c u l a t e u r . L a l e c t u r e

e t l ' i n t e r p r U t a t i o n des d o n n d e s c o n c e r n a n t le s c h U m a

e s t assurUe p a r des p r o g r a m m e s a p p a r t e n a n t h PASTIS

e t c o m m u n s h t o u s les t r a v a u x exdcutUs p a r ce lu i -c i .

L e d i a g r a m m e de t e m p s de ces d v U n e m e n t s l o g i q u e s

p e u t 8 t r e p a r e x e m p l e ce lu i de la f igure 13.

P o s o n s T 1 = T off v e s t le t e m p s de p r o p a g a t i o n

h t r a v e r s l a p o r t e 3 d ' u n s i g n a l t e l q u e ce lu i q u i e s t

p r d s e n t en b. S o i t ~m le m i n i m u m p o u r ce t y p e de

p o r t e des v a l e u r s q u e p e u t p r e n d r e z, e t r le m a x i -

9 / 1 4

I V . 1 . O r g a n i s a t i o n de la s i m u l a t i o n de dUfauts .

L ' o r g a n i g r a m m e d e l a f i g u r e 14 dUcri t le dUrou-

l e m e n t d u t r a v a i l e t les c o m m u n i c a t i o n s e n t r e les p r o g r a m m e s .

A. T~LI~C., 28, n ~ II-12, 1973

Page 10: Simulation par calculateurs de réseaux logiques

454 C. KUBIAK. -- SIMULATION PAn CALCULATEI_TRS DE 1RI~SEAUX LOGIQUES

I V . 2 . P r 6 s e n t a t i o n d e l a s i m u l a t i o n s a i n e .

F I �84 Cr- E--]

~- DEBUT : lecture du type de travail. Ici Simulation

:Dr Lecture du schdma et interprdtation ) L_P

~._ Lecture de donndes ({ technologiques ))

p rdparation des donndes ~-- pour la simulation :

-a ffichages, cont~61es, 6 d i t i o n ~ ( ~

Simulation saine Traitements des affichages Contrdles divers - Editions

R,sultats int~rmddiaires ~ ( ~ l

Simulation de ddfauts ContrSles divers . . ( ~

Editions z.

Editions des rdsultats

L..I F~6. 14. - - Organ i sa t ion g~n~rale de la s imulat ion.

Le p r o g r a m m e ne s imule que les al tdrations du schdma h l 'aff ichage n ~ i pa r r appor t h l 'aff ichage

n ~ i - 1. Le fichier des points d ' a t t a q u e mdmorise,

selon leur num6ro d 'o rd re , la l iste des 616ments h simuler. La f g u r e 15 donne l ' o r g a n i g r a m m e gdndral

de la s imulat ion saine pour un affichage.

Pour chaque 616ment simul6, don t la sortie est

modifide, il y a inscr ip t ion d ' u n ou de plusieurs did-

merits dans le fichier des points d ' a t t aque . Ce fichier

doi t ~tre explor6 afin d ' insdrer h sa place chaque

6ldment, selon son num6ro d 'ordre .

On vo l t ici l ' i m p o r t a n c e de la num6ro ta t ion qui

pen t pe rme t t r e d ' a l longe r ou de raccourcir l ' explo-

ra t ion du fichier. I1 semble q u ' u n e num6ro ta t ion des

616ments, telle que les ~l~ments d ' u n arbre du r6seau

aient des numdros vois ins , op t imal i se la gestion du fichier des points d ' a t t a q u e .

IV.3. Pr6sentation de la s imulat ion de d6fauts.

Le p r o g r a m m e de s imu la t i on de d6fauts est cons t ru i t selon le m~me pr inc ipe que le p r o g r a m m e de simu-

Traitement de oui I'affichage suivant

Examen des entrdes du rdseau /

Pour les entrdes Jodifides insertion des 616ments attaquds dans le fichier des points d'attaque

I_

Fichier des points d'attaque vide

non Prendre le lerdldment

du fichier

Aiguillage selon son type

1 imulation de I'~l~ment I.

I

Pour chaque sortie

Transition globale diffdrente de celle I'affichage prdcddent

~ 1

Recherche des 616ments attaquds et inscription dans le fichier

des Points d'attaque

I

Effacer 1'616ment simul6 du fichier

des points d'attaque

non

FIG. 15. - - Organ ig ramme de la s imulat ion saine.

La lec ture des donn6es se fai t sur cartes, sauf les donn6es de t y p e technologique , mais elles p e u v e n t

cependan t aussi 6tre lues sur cartes. Les fichiers s6quentiels sont soit des bandes magn6t iques , soit des fichiers sdquent ie ls sur disque.

la t ion saine. Ici, c ependan t , une a l t6rat ion est une

diff6rence, au m 6 m e affichage, entre la t rans i t ion

globale d 'un po in t du rdseau ddfectueux et celle de ce m~mc point du r6seau sain. Les al t6rat ions sont pro-

pag6es de la m~me mani~re que dans la s imula t ion saine.

A. T~L~C., 28, n os lt-12, 1973 10/14

Page 11: Simulation par calculateurs de réseaux logiques

C. KUBIAK. -- SIMULATION PAR CALCULATEURS DE RESEAUX LOGIQUES 4 5 5

L a f igure 16 d 6 c r i t l ' o r g a n i g r a m m e de la s i m u l a - m 6 m o i r e , les d d f a u t s s o n t r a s s e m b l 6 s e n g r o u p e s , d o n t

t i o n de d 6 f a u t s . P o u r u n e u t i l i s a t i o n o p t i m a l e de la l a t a i l l e e s t p o u r l ' i n s t a n t f ix6e h 50 d d f a u t s .

affichage suivant

d~faut suivant

oui

oui

Lecture du fichier des d~fauts

Former un groupe de n d~fauts

- t 1 er affichage

Lire les r~Mrences saines

1 er ddfaut

Simulation du schema cet affichage

pour ce~d~faut

Mr les alterations constat~es

D (ffaut t6teet~ sur une sortie

oui l

Supprimer ce d~faut de la liste et effacer les

alterations qu'il a cr~es

Existe-t-il d'autres d(~fauts dans le groupe

non

Existe-t-il d'autres affichages

I non

Sortir les d~fauts non d~tect~s de la liste des

d~fauts b traiter

xiste-t-il d'autres d(~ auts

oui I Former un autre groupe de d6fauts

I

non

FIG. 16. - - S i m u l a t i o n d u c i rcui t d6 fec tueux .

V . R ~ S U L T A T S O B T E N U S

L e p r o g r a m m e de s i m u l a t i o n q u a s i s t a t i q u e a dt6

e s s a y 6 s u r c a l c u l a t e u r (*), t r a v a i l l a n t e n t r a i t e m e n t

p a r l o t s sous m o n i t e u r B P M .

N o u s a l l o n s d o n n e r sous f o r m e de t a b l e a u I V les

r 6 s u l t a t s o b t e n u s p o u r c i n q c i r c u i t s l o g i q u e s , cho i s i s

p a r m i c e u x q u i s o n t en s e r v i c e d a n s le s y s t 6 m e PLATON.

L a t a i l l e d u c i r c u i t c o r r e s p o n d h u n e c a r t e de c i r c u i t

i m p r i m 6 e n u s a g e d a n s ce s y s t 6 m e . Les a f f i c h a g e s

o n t 6 t6 f o u r n i s p a r le p r o g r a m m e LOGITEST, de t e s t

d e c i r c u i t s l o g i q u e s [8]. N o u s a l l o n s d ' a b o r d d 6 f i n i r

d e u x t e r m e s :

- - l ' a c t i v i t d e n pour cent e s t le r a p p o r t d u n o m b r e

d ' 6 1 6 m e n t s s imu l6s , c ' e s t - h - d i r e a y a n t 6 td a c t i v 6 s , a u

h o m b r e t o t a l d ' 6 1 d m e n t s h s i m u l e r , c ' e s t - h - d i r e le

p r o d u i t : n o m b r e d ' 6 1 6 m e n t s x n o m b r e d ' a f f i c h a g e s ;

- - l ' a c t i v i t d c o m p e n s d e se c a l c u l e c o m m e l ' a c t i v i t 6

m a i s e n t e n a n t c o m p t e d u n o m b r e de p a s s e s d a n s les

b o u c l e s p o u r c a l c u l e r le n o m b r e d ' 6 1 6 m e n t s h s i m u l e r .

1 Fin

C O N C L U S I O N

Les e x e m p l e s p r 6 s e n t d s ici p e r m e t t e n t de d6 f in i r

le d o m a i n e d ' a p p l i e a t i o n d u p r o g r a m m e . L ' o b t e n t i o n

TABLE~kU IV Rdsultals du programme

Descr ip t ion du s c h 6 m a

~o

- o

m Z -o Z

202 0 39

(1)

137 2 108

(9) (27)

151 3 159

(12) (7,3)

102 2 277

(11) (8)

83 4 136

(19) (36)

S imula t ion sa ine

Z ~

450 69

421 49

i ( 4 5 )

31 394

I r 45

320 l :1(40)

i 93 322 ,

i ( 4 9 , 5 ) I

. <

Z

28

38

205

(289)

S i m u l a t i o n de d6 fau t s

:~-~ ~ v

T e m p s to ta l . R e m a r q u e s

12 I 1

(3) j 65 i 7,5

( 9 , 4 ) !

40 r 2,65

(5,45) i

49 5 , 7 5 i

(3,9) I (5)

43 i 4O)

(4,1) (24,7)

100

58,5

76

37

(4,5)

6 72 m i n u t e s . R 6 s e a u p r e s q u e e n t i ~ r e m e n t c o m b i n a t o i r e et s an s boucle�9

366 14 532 mn . Fa ib l e t a u x de d6- Jfauts d6tec t6s . P lu s d u q u a r t des

(1,5) 616ments a p p a r t i e n t h u n e boucle .

215 9 865 m n .

(1,8)

72

47,5

3O5

(1,4)

1 093

(0,96)

11 882 m n .

24 155 ran. Ci rcu i t par t icu l i~re- m e n t difficile h t r a i t e r .

1 1 / 1 4

(*) C I I 10070.

A. TI~Lg:C., 28, n ~ 11-12, 1973

Page 12: Simulation par calculateurs de réseaux logiques

456 c. K U B I A K . -- S IMULATION PAR C A L C U L A T E U R S DE R]~SEAUX LOGIQUES

des p r o g r a m m e s d 'essai n ' a pas 6t6 a u t o m a t i q u e , ce qui exp l ique le grand n o m b r e d 'appe ls h l ' ana lyse

te~mporelle. E n effet, un op6ra teur est capable de

ten i r c o m p t e de donn6es tempore l les s imples afin de

faei l i ter l '61aborat ion de ces p r o g r a m m e s d ' e s sa i ; c 'es t ce qui fur fai t ici. I1 va de sol que t o u t ce qui

est dfi au j u g e m e n t de l ' op6ra teu r est du ressort de

l ' ana lyse tempore l le . Le p r o g r a m m e de s imula t ion

quasi s t a t ique se con ten te dans ces cas-lh de signaler

ur~ a l 6 a possible.

L ' u t i l i s a t eu r du p r o g r a m m e de s imula t ion quasi

s t a t ique doi t respec te r les r~gles su ivan tes :

1) l ' ana lyse t empore l l e est un out i l pr6cis, mais

d ' u n emploi cofi teux. El le doi t donc 6tre uti l is6e pour

r6soudre des eas d61ieats de f o n e t i o n n e m e n t et non

pour 6tudier l ' inf luence et l ' ex i s t enee d 'a ldas qui

n ' a p p a r a i s s e n t pas lors d ' une u t i l i sa t ion normale du

c i rcui t logique simul6 ;

2) l '61aborat ion des afflchages ne dol t 6tre f a r e

que darts le, cas d ' un f o n c t i o n n e m e n t en s t a t ique du

circuit .

Ces re la t ions sont c e p e n d a n t insuffisantes pour

rendre c o m p t e du c o m p o r t e m e n t r6el de l '616ment

s6quentiel, lorsque, pa r exemple , plusieurs entr6es

changent d ' 6 t a t quasi s imul tan6ment .

Afin de pouvo i r t r a i t e r ces changement s mul t ip les d '6 ta t des entr6es, nous avons ainsi d6fini l ' 6 t a t

interne. L ' e n s e m b l e des conf igura t ions des var iables

internes et des entr6es d6finit l ' ensemble des 6tats

internes de l '616ment s6quentiel .

Son f o n c t i o n n e m e n t est alors d~crit pa r le sys-

t~me (A-3) :

! ap~+l : g (q)~, E~+I), (A-3) ( 3 i4-1 : f ((I)14-1),

off (I)~ d~signe l ' 6 t a t i n t e rne au temps t~. Le syst~me

((A-3) a m~me forme que le syst~me (A-2). I1 est

donc repr6senta t i f d ' u n module de Moore de l'616ment.

Exemple. On t r o u v e r a figure A-1 des exemples d 'd ta t s

internes d6finis pour une bascule de t y p e D, pour

laquelle on a ddfini t rois var iab les internes.

2

3

1 8

9

Yl Y2 Y3 H U Z D

-- 1 1

0 1 1

1 0 -

1

1 1 1 -

0 1 1 1

0 1 1 0

0 1 1 -

O QB

1 0

1 0

1 0

FIG. A-1. - - Etats internes.

A N N E X E

E t a t i n t e r n e d ' u n 6 1 6 m e n t s 6 q u e n t i e l .

Nous allons d6finir ici les not ions d '~ t a t interne, de d6g6n6rescence d ' 6 t a t i n t e rne et d ' o rd re dans

l ' ensemble des 6tats internes.

I. E ta t in terne d'un d ldment s~quent ie l .

Le c o m p o r t e m e n t d ' u n 616ment s6quent ie l d~pend de l ' 6vo lu t ion de l ' 6 ta t de ses entrdes, mais aussi de

celle de l ' 6 t a t de points in ternes appelds var iables

in ternes .

Si 71 d6signe le vec t eu r des 6tats logiques des var iab les in te rnes au t emps t i ,

E l e t Sl d6signent r e s p e c t i v e m e n t ceux des entr6es

et des sorties au m6me temps ,

alors le c o m p o r t e m e n t de l '616ment s6quent ie l peut

~tre dgcri t pa r l ' un des

I yi+l : (A- l ) Si4-1 :

l yl+l : (A-2)

t S~+~ =

deux syst~mes :

g l ( y I , E i + l ) ,

f l ( yi~l, Ei4-1) ,

g~ ( yi, El+l),

f2 (y~+l).

H. Ddgdn~rescence d'un dtat interne.

Dd finitions.

- - Un ~tat in t e rne est non ddgdndrd si l ' 6 t a t des

entr6es et des var iab les in ternes lui co r respondan t ,

et par cons6quen t celui des sorties, est en t i~ rement d6termind. C 'es t le cas de l ' 6 ta t in terne n ~ 3 de la

figure A-1.

- - Un dta t in t e rne est ddgdndrd si l ' 6 t a t d ' une an

moins des sort ies lui co r r e spondan t est d6termin6in.

- - Dans les au t res cas, l ' 6 ta t in terne sera partiel- lement ddgdndrd si le c o m p o r t e m e n t de l ' d ldment s6quentiel est modif id h la sui te de la lev6e de l ' ind6ter -

mina t ion sur une entrde ou une var iab le interne. I1

est non d6g6n6r6 dans le cas contraire . Dans l ' e x e m p l e de la figure A - l , l ' d t a t n ~ 2 est non d6gdndr6. Par contre ,

il est 6v ident que la levde de l ' i nd6 te rmina t ion sur

l 'entr6e D mod i f i e ra le c o m p o r t e m e n t de l '61dment,

si on appl ique par exemple une mont6e d 'hor loge lorsqu ' i l se t r o u v e dans l ' d t a t in terne n ~ 9.

III. Mise en o r d r e de l 'ensernble des ~tats internes .

Construisons un g raphe don t les sommets sont les

6tats in ternes et don t les arcs jo ignen t deux 6tats

A. T~L~C., 28, n ~ 11-12, 1973 12/14

Page 13: Simulation par calculateurs de réseaux logiques

C. KUBIAK. -- SIMULATION PAR CALCULATEURS DE RESEAUX LOGIQUES 457

in ternes s'il existe une commande qui fait passer l '61dment de F u n des dtats in ternes h l ' au t re . Par eommande , il f au t en tendre un e h a n g e m e n t d'fi tat logique d ' une ou plusieurs entr6es. Deux commandes diff6rent d6s q u ' u n c h a n g e m e n t d '6 ta t des entrdes est affectd de paras i tes sur l ' une et pas sur l ' au t re .

Nous appel lerons ensemble image d ' u n 6tat in terne qbk, que nous no tons ['{qbk} l ' ensemble des 6tats in ternes h l ' ex t rdmi td d ' u n are dont l 'or igine est qb~.

Pa r ddfini t ion :

Le graphe de eet te re la t ion peu t fitre eelui de la figure 4. On m o n t r e fae i lement qu ' i l existe un 6tat in te rne qui est le plus g rand de tous. I1 est not6 @o et il correspond h une indd te rmina t ion eompl6te de l 'd ta t des entrdes et des var iables internes .

Manuscr i t re~u le 2 mars 1973.

Manuscr i l revisd recu le 24 aodt 1973.

BIBLIOGRAPHIE

[1] HARDIE (F. H.), SUHOCK1 (R. J.). Design and u~e of fault simulation for Saturn computer design (Conception du calculateur Saturne : 6rude et emploi d'une simulation des ddfauts). I .E.E.E. , Trans., EC, U. S. A. (aofit 1967), 16, n ~ 6, pp. g12-429.

[2] YETTER (I. H.). High speed fault simulation for UNIVAC 1107 Computer system (Simulation rapicle des ddfauts pour ordinateur UNIVAC 1107 Proc. 2:~ ra Nat. Conf@ence ACM Brandon systems Presse Preuceton (1968), pp. 265-277.

[3] ULRICU (E. G.). Serial parallel event scheduling for the simulation of large systems (Programmation des 6vdnements en sdrie et parall61e pour la simu- lation de grands syst6mes). Proc. 23 ra Nat. Confdrence ACM Brandon systems Press Princeton (1968), pp. 279-28q~

[4] ULRICH (E. G.). Exclusive simulation of activity in digital networks (Simulation exclusive de l'acti- tivit6 de~. rdseaux numdriques). Communication ACM, U. S, A. (fdv. 1969), 12, n ~ 21, pp. 102-110.

[5] CnAPPEL (S. G.), YAU (S. S.). Simulat ion of large asynchronous logic circuits using an ambiguous gate (Simulation de grands circuits logiques asyn- chromes utilisant une porLe ambigue). Fall joint Computer Confdrence A F I P S Press, Montuale N. J. (16-18 nov. 1971), 39, pp. 651-661.

[6] JEPHSON (J. S.), n c QUARRIE (R. P.), VOGELSBERG (R. E.). Three value computer design verification system (Syst6me de vdrification de la conception d 'un calculateur /~ trois valeurs). I B M J. Develop., U. S. A. (1969), 8, n ~ 3, pp. 78-88.

[7] LEWIS (D. W.). Hasard detection by a quinary simu- lation of logic devices with bounded propagation delay (Ddtection d'aldas par simulation quinaire de dispositifs logiques h temps de propagation bornd). Proc. o/ the I . E . E . E . - A C M (Design automation Workshop. Dallas, Texas June 26-28 (1972), pp. 157- pp. 607-614.

[8] MEURIC (J. N.), PIGNAL (P.}, VINCENT-CAEREFOUR (J.). Un programme d'aide au contrgle des r6seaux logiques. Ann. Tdl~communic. Fr., (juillet-aofit 1971), 26, nos 7-8, pp. 259-277.

[9] SALLE (P.), VIGNOLE (J.). Etude de la simulation et du ddcoupage logique. Bey. Jr. Automat. In/ormat. Bech. operat. (sept. 1972), 6, n ~ B-3, pp. 39, 59.

[10] ***. Etude de l 'influence des aldas de fonctionnement d'une carte logique sur une sdquence de test. Rapport final de la Convention CRI 70023. (1972).

[11] TRAEEY (J. H.). Intersal state assignment for asynchronous sequential machines (Assignements des 6tats internes dans les machines sequentielles asynchrones). I .E .E.E. , Trans. EC, U. S. A. (RoOt 1966), 15, no 4, pp. 551-560.

[12] UNGER (S. H.). Asynchronous sequential circuit with unrestricted imput change (Circuits de com- mutation sdquentielle asynchrones ~ transitions d'entrde quelconques). I .E.E.E. , Trans., C, U. S. A. (ddc. 1971), 20, n ~ 12, pp. 1 ~ 3 7 - 1 ~ .

[13] CARRIER (C.), PIGNAL (P.), *V-INCENT-CARREFOUR (J.). Un syst6me d'aide ~ la conception des ensembles logiques, le programme PASTIS. Commut. et Elec- tron. Fr. (avril 1970), n ~ 29, pp. 29-37.

[t~] BREUEn (M. A.). A note, on the three valued logic simulation (Note sur la simulation logique ~ trois valeurs). I .E .E.E. , Trans. C (avril 1972), 21, n ~ 4, pp. 401-~02.

A. T~:L~C., 28, n ~ 11-12, 1973 14/14