Iccad 95 Tut.ps

8/13/2019 Iccad 95 Tut.ps

1/219

T u t o r i a l

T h e S y s t e m a t i c D e s i g n o f A s y n c h r o n o u s C i r c u i t s

M i c h a e l K i s h i n e v s k y

T h e U n i v e r s i t y o f A i z u ,

J a p a n

L u c i a n o L a v a g n o

P o l i t e c n i c o d i T o r i n o ,

I t a l y

C a d e n c e B e r k e l e y L a b s ,

U S A

P e t e r V a n b e k b e r g e n

S y n o p s y s , I n c , U S A

I C C A D ' 9 5 t u t o r i a l T h e S y s t e m a t i c D e s i g n o f A s y n c h r o n o u s C i r c u i t s 1


2/219

O u t l i n e

I n t r o d u c t i o n a n d b a s i c s

W h a t i s a s y n c h r o n o u s , a d v a n t a g e s a n d d i s a d v a n t a g e s , d e s i g n s t y l e s ,

h a z a r d s a n d r a c e s , c o n t r o l / d a t a d i c h o t o m y

S p e c i c a t i o n a n d s y n t h e s i s m e t h o d o l o g i e s

E v e n t b a s e d m o d e l s , c o n c u r r e n t l a n g u a g e s , F S M s

S y n t h e s i s f r o m S i g n a l T r a n s i t i o n G r a p h s

S y n t h e s i s o w , s t a t e a s s i g n m e n t , l o g i c s y n t h e s i s , d e s i g n - f o r - t e s t a b i l i t y ,

c o m p a r i s o n w i t h s y n c h r o n o u s

V e r i c a t i o n a n d v a l i d a t i o n o f a s y n c h r o n o u s d e s i g n s

F o r m a l v e r i c a t i o n , c h e c k i n g p r o p e r t i e s , v a l i d a t i o n i n V H D L e n v i r o n m e n t

P r a c t i c a l a p p l i c a t i o n s

I n t e r f a c e d e s i g n , a s y n c h r o n o u s p r o c e s s o r s , D S P c i r c u i t s , C A D t o o l s



3/219

M o t i v a t i o n

R e l i a b l e d e s i g n m e t h o d o l o g y f o r a s y n c h r o n o u s i s c o m i n g

A s y n c h r o n o u s d e s i g n s o m e t i m e s u n a v o i d a b l e

( a s y n c h r o n o u s i n t e r f a c e s , a r b i t e r s , e t c )

A s y n c h r o n o u s i s g e t t i n g m o r e i m p o r t a n t :

" I n t h e m i c r o p r o c e s s o r o f t h e y e a r 2 0 0 0 ] w e w i l l s e e p e r h a p s e v e n

a s y n c h r o n o u s d e s i g n "

" L o o k i n g a t t h e f u t u r e "

A n a n t A g r a w a l , V i c e P r e s i d e n t ,

E n g i n e e r i n g S u n M i c r o s y s t e m s

S P A R C T e c h n o l o g y B u s i n e s s



4/219

W h a t i s a s y n c h r o n o u s ?

A s y n c h r o n o u s = n o t s y n c h r o n o u s )

S y n c h r o n o u s : u s e a n e x t e r n a l g l o b a l c l o c k f o r

o b s e r v i n g s y s t e m s t a t e s

A s y n c h r o n o u s : u s e i n t e r n a l a n d e x t e r n a l e v e n t s f o r

o b s e r v i n g s y s t e m s t a t e s

A s y n c h r o n o u s a r e a l s o c a l l e d s e l f - t i m e d



5/219

S y n c h r o n o u s c o m m u n i c a t i o n

Register

Sender Receiver

Register

Clock

Logic

Data input

Clock

Tsetup Thold

T i m i n g c o n s t r a i n t : i n p u t d a t a m u s t s t a y u n c h a n g e d w i t h i n a s e t u p / h o l d

w i n d o w a r o u n d a c l o c k e v e n t



6/219

A s y n c h r o n o u s c o m m u n i c a t i o n

Register

Sender Receiver

Register

Logic

Ack

Req

Data

A s i g n a l h a n d s h a k e i s u s e d i n s t e a d o f a g l o b a l c l o c k

H a n d s h a k e c a n b e i m p l e m e n t e d u s i n g

d e l a y p a d d i n g o r / a n d c o m p l e t i o n d e t e c t i o n



7/219

C o m p l e t i o n d e t e c t i o n

Register

Sender Receiver

Register

Logic

Ack

Data

detector

Req

S p e c i a l r e d u n d a n t d a t a e n c o d i n g ) a r e a o v e r h e a d

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

C o m p l e t i o n d e t e c t i o n c a n b e d o n e i n s i d e a r e c e i v e r

T o l e r a t e s d a t a s k e w



8/219

D e l a y p a d d i n g

Register

Sender Receiver

Register

Logic

Ack

Req

Data

d

S i m i l a r t o s y n c h r o n o u s

M e a s u r e o r e s t i m a t e m a x i m u m l o g i c d e l a y

P a d e x t r a d e l a y ( i f R e q s e t s b e f o r e L o g i c s t a b i l i z e s )

f o r m i m i c k i n g c o m p l e t i o n d e t e c t i o n

T i m e r e d u n d a n c y { t i m i n g m a r g i n s a r e r e q u i r e d



9/219

P o t e n t i a l a d v a n t a g e s

T o p t e n l i s t s a t A s y n c 9 4 f r o m A l D a v i s

N o c l o c k d i s t r i b u t i o n

A v e r a g e c a s e p e r f o r m a n c e

L o w p o w e r c o n s u m p t i o n

R o b u s t n e s s t o p a r a m e t e r v a r i a t i o n s

M o d u l a r c o m p o s i t i o n

M e t a s t a b i l i t y

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

G l o b a l s y n c h r o n y d o e s n o t e x i s t a n y w a y

( h a r d w a r e / s o f t w a r e c o d e s i g n )



10/219

R o b u s t n e s s

1 2 3 4 5 6 7 8 9 10

1

5

20

15

10

MOperations/sec

Voltage, V

77K

300K

5 op/s

A l a i n M a r t i n 1 9 8 9

C h r i s t i a n N i e l s e n 1 9 9 4

O p e r a t i n g r a n g e :

5 o p / s u n d e r 0 5 V a n d 3 0 0 K $ 1 9 M o p / s u n d e r 1 1 V a n d 7 7 K

I C C A D ' 9 5 t u t o r i a l T h e S y s t e m a t i c D e s i g n o f A s y n c h r o n o u s C i r c u i t s 1 0


11/219

P r o b l e m s

H a v e y o u e v e r s e e n a s y n c h r o n o u s c i r c u i t s ?

A r e a o v e r h e a d

T e s t a b i l i t y ?

H o w t o d e s i g n t h e m ?

A s y s t e m a t i c d e s i g n m e t h o d o l o g y i s n e e d e d



12/219

P a r t 1 : B a s i c s

E x a m p l e : C - e l e m e n t d e s i g n


D e s i g n s t y l e s

{ d e l a y m o d e l s

{ s i g n a l l i n g m e t h o d s

{ m o d e l s o f e n v i r o n m e n t

H a z a r d s a n d r a c e s : r e v i e w

A s y n c h r o n o u s d a t a p a t h



13/219

S y n c h r o n i z a t i o n o f p a r a l l e l p r o c e s s e s

?coci

bo

aoai

biB

A

C

A f t e r A a n d B d o C

B o t h r i s i n g a n d f a l l i n g t r a n s i t i o n s

h a v e t o b e s y n c h r o n i z e d :

i f a = b = 1 t h e n c : = 1

i f a = b = 0 t h e n c : = 0

o t h e r w i s e c : = c

A N D - g a t e s y n c h r o n i z e s o n l y

r i s i n g t r a n s i t i o n s

S y n c h r o n i z a t i o n c a n b e d o n e w i t h a C - e l e m e n t



14/219

C - e l e m e n t o n b a s i c g a t e s

cab

0 0

0

0

1 1 1

1

1

42

3

a

bc

I s t h i s i m p l e m e n t a t i o n c o r r e c t ?



15/219

D e l a y a s s u m p t i o n s

1

42

3

a

bcn1

n2

n3

n4

Environment

delay1

delay2

01 01

0101

0

0

0

010

0

D e l a y 1 i s a p r o p a g a t i o n

d e l a y f r o m n o d e 1 v i a

e n v i r o n m e n t t o n o d e 3

D e l a y 2 i s a p r o p a g a t i o n

d e l a y f r o m n o d e 1 v i a

i n t e r n a l f e e d b a c k

t o n o d e 3

D e l a y 1 m u s t b e g r e a t e r

t h a n D e l a y 2

D e l a y a s s u m p t i o n s i n u e n c e c o r r e c t n e s s o f a s y n c h r o n o u s d e s i g n



16/219

C M O S i m p l e m e n t a t i o n o f a C - e l e m e n t

b

ac

a

a

a

b

b

b

weak

b

a

a

b

a

a

b

bc

c

c

S t a t i c D y n a m i c Q u a s i - s t a t i c

A r e t h e s e i m p l e m e n t a t i o n s c o r r e c t ?

C a r e f u l d e s i g n i s r e q u i r e d ( l a y o u t , t r a n s i s t o r s i z i n g , c h a r g e s h a r i n g )



17/219

R S - l a t c h w i t h c o m p l e t i o n d e t e c t i o n

R

S

Completion

Q

Q

R

S

Completion

Q

Q

C o m p l e t i o n = 0 , < S R > = < Q Q

0

>

G i l l i e s , S w a r t w o u t ' 6 1 ( i n M i l l e r ' 6 5 ) , M a r t i n , v a n B e r k e l 8 0 ' s ]



18/219

D u a l - r a i l f o u r - p h a s e e n c o d i n g

1

2

3

4Data

Ack

Send Reset

Cycle

Valid Empty

X X t X f

T r u e 1 0

F a l s e 0 1

E m p t y 0 0

V a l i d = f T r u e , F a l s e g



19/219


Cn C2

. . .

x1.t

x1.f

xn.t

xn.f

X. . .

. . .

x1.t

x1.f

xn.t

xn.f

X

. . .completion(X) completion(X)

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

A r m s t r o n g e t a l 6 9 ] V a r s h a v s k y 7 5 ]



20/219

C o m p l e t i o n d e t e c t i o n v s d e l a y p a d d i n g


{ C o m p l e t i o n d e t e c t i o n i s w e l l d e v e l o p e d

{ R e q u i r e s a n a r e a o v e r h e a d a n d a n e x t r a - d e l a y

N o t p r a c t i c a l f o r w i d e d a t a p a t h s

B u n d l e d d a t a

{ P a d d i n g d e l a y a l l o w s t o m i m i c t h e c o m p l e t i o n d e t e c t i o n

{ D a t a p a t h i s s y n c h r o n o u s

{ R e q u i r e s t i m i n g r e d u n d a n c y f o r s a f e d e s i g n



21/219

W h a t i n u e n c e s t h e d e s i g n m e t h o d o l o g y

D e l a y m o d e l

S i g n a l l i n g m o d e l

E n v i r o n m e n t m o d e l

S p e c i c a t i o n l a n g u a g e



22/219

D e l a y m o d e l s

P l a c e : g a t e s , w i r e s , g a t e s + w i r e s

T i m i n g p r o p e r t i e s : b o u n d e d a n d u n b o u n d e d

B o u n d e d = l o w e r a n d u p p e r b o u n d s f o r c i r c u i t c o m p o n e n t s a r e k n o w n

U n b o u n d e d = d e l a y s a r e u n k n o w n b u t n i t e

M e m o r y p r o p e r t i e s : i n e r t i a l a n d p u r e

A p p l y a t r a i n o f s h o r t p u l s e s t o t h e i n p u t o f a d e l a y e l e m e n t

b e f o r e t h e o u t p u t o f a d e l a y h a s c h a n g e d i t s v a l u e

I n e r t i a l = a l l p u l s e s a r e l t e r e d o u t

P u r e = n o p u l s e s a r e l t e r e d o u t

I n t e r m e d i a t e m o d e l s a r e p o s s i b l e



23/219

G a t e v s w i r e d e l a y m o d e l s

G a t e d e l a y m o d e l = d e l a y s a r e i n g a t e s , n o d e l a y s i n w i r e s

M o r e r e a l i s t i c v e r s i o n : g a t e s m a y h a v e a r b i t r a r y d e l a y s , w i r e s

a f t e r f o r k m a y h a v e d e l a y s l e s s t h a n o n e g a t e d e l a y

W i r e d e l a y m o d e l = g a t e + w i r e d e l a y m o d e l :

w i r e s ( a n d g a t e s ) m a y h a v e a r b i t r a r y d e l a y s



24/219

D e l a y m o d e l s a n d c o r r e c t n e s s

c

b

a

b

a

a

b

a

a

b

bc

c

Transistor view Logic view

a

b

c

d2

d1

d4

d3 d5

T h i s d e s i g n i s c o r r e c t f o r u n b o u n d e d g a t e d e l a y m o d e l

T h i s d e s i g n i s i n c o r r e c t f o r u n b o u n d e d w i r e d e l a y m o d e l

I f d 1 > d 3 + d 5 o r d 2 > d 3 + d 4 t h e n t h e i m p l e m e n t a t i o n

d o e s n o t s a t i s f y t h e s p e c i c a t i o n

C o r r e c t n e s s o f t h i s d e s i g n u n d e r t h e b o u n d e d d e l a y m o d e l

d e p e n d s o n d e l a y c o n s t r a i n t s



25/219

D e s i g n s t y l e s f o r a s y n c h r o n o u s c o n t r o l l o g i c

B o u n d e d d e l a y s : r e a l i s t i c d e l a y m o d e l f o r g a t e s a n d w i r e s

T e c h n o l o g y m a p p i n g i s e a s y

V e r i c a t i o n i s d i c u l t s i n c e t i m e m u s t b e i n c l u d e d i n t h e m o d e l

S p e e d - i n d e p e n d e n t : p e s s i m i s t i c d e l a y m o d e l f o r g a t e s

( u n b o u n d e d ) a n d o f t e n a c c e p t a b l e d e l a y m o d e l f o r w i r e s

( d e l a y s a f t e r f o r k a r e l e s s t h a n o n e g a t e d e l a y )

T e c h n o l o g y m a p p i n g i s m o r e d i c u l t

V e r i c a t i o n i s e a s y s i n c e t i m e i s e x c l u d e d f r o m t h e m o d e l

D e l a y - i n s e n s i t i v e : p e s s i m i s t i c d e l a y m o d e l f o r g a t e s a n d w i r e s

( b o t h a r e u n b o u n d e d )

T h e c l a s s o f s u c h c i r c u i t s ( b u i l t o u t o f b a s i c g a t e s ) i s a l m o s t e m p t y

Q u a s i - d e l a y i n s e n s i t i v e = d e l a y - i n s e n s i t i v e e x c e p t c r i t i c a l w i r e f o r k s ,

c a l l e d i s o c h r o n i c f o r k s

I n p r a c t i c e t h i s i s t h e s a m e a s s p e e d - i n d e p e n d e n t



26/219

S i g n a l l i n g m e t h o d s

T w o - p h a s e :

r i s i n g a n d f a l l i n g s i g n a l t r a n s i t i o n s a r e e q u i v a l e n t

F o u r - p h a s e :

r i s i n g a n d f a l l i n g s i g n a l t r a n s i t i o n s a r e n o t e q u i v a l e n t



27/219

T w o - p h a s e s i g n a l l i n g

Cycle Cycle

Data

Req

Ack1

3

2Register

Sender Receiver

Register

Logic

Ack

Req

Data

T w o t r a n s i t i o n s a t t h e c o n t r o l l i n e s d u r i n g o n e c y c l e

a c k n o w l e d g e ) d a t a c h a n g e ) r e q u e s t



28/219

F o u r - p h a s e s i g n a l l i n g

Register

Sender Receiver

Register

Logic

Ack

Req

Data

Cycle

ResetSend

1

2

3

4

Data

Ack

Req

F o u r t r a n s i t i o n s a t t h e c o n t r o l l i n e s d u r i n g o n e c y c l e

C o n t r o l i s s i m p l e r

R e s e t p h a s e : c h a n g e d a t a a n d r e s e t c o n t r o l



29/219

M o d e l s o f t h e e n v i r o n m e n t

A s y n c h r o n o u s c i r c u i t s o p e r a t e i n t h e e n v i r o n m e n t

S l o w e n o u g h e n v i r o n m e n t = F u n d a m e n t a l m o d e :

i n p u t s c a n c h a n g e a f t e r t h e a s y n c h r o n o u s s y s t e m h a s s e t t l e d i n t o a s t a b l e

s t a t e

R e a c t i v e e n v i r o n m e n t = I n p u t / o u t p u t m o d e :

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

t h e p r e v i o u s i n p u t c h a n g e

C o n s t r a i n t s o n i n p u t c h a n g e s f o r f u n d a m e n t a l m o d e a n d I / O - m o d e :

{ S i n g l e i n p u t c h a n g e ( S I C ) - t o o s l o w

{ M u l t i p l e i n p u t c h a n g e ( M I C ) - d i c u l t t o d e s i g n u s i n g c l a s s i c a l a s y n -

c h r o n o u s F S M t e c h n i q u e

{ U n r e s t r i c t e d i n p u t c h a n g e ( U I C ) - v e r y d i c u l t t o d e s i g n u s i n g c l a s s i c a l

a s y n c h r o n o u s F S M t e c h n i q u e

F u n d a m e n t a l m o d e c o n s t r a i n t s a r e s i m i l a r t o s e t u p a n d h o l d r e s t r i c t i o n s i n

s y n c h r o n o u s d e s i g n F u n d a m e n t a l m o d e i s o f t e n t o o r e s t r i c t i v e

E x a m p l e : a n y p i p e l i n e o p e r a t e s i n I / O - m o d e



30/219

E n v i r o n m e n t a n d c o r r e c t n e s s

1

42

3

a

bcn1

n2

n3

n4

Environment

delay1

delay2

0101

0101

0

0

0

010

0

F o r f u n d a m e n t a l m o d e

t h i s d e s i g n i s c o r r e c t ( n e c -

e s s a r y d e l a y c o n s t r a i n t s

h o l d b y d e n i t i o n )

F o r I / O - m o d e t h i s d e s i g n

m a y b e i n c o r r e c t u n l e s s

" D e l a y 1 > D e l a y 2 " t y p e

c o n s t r a i n t s h o l d

A s s u m p t i o n s o n t h e e n v i r o n m e n t i n u e n c e t h e c o r r e c t n e s s o f

a s y n c h r o n o u s d e s i g n



31/219

G o a l s o f t u t o r i a l

W i l l p r e s e n t d e s i g n m e t h o d o l o g y f o r

{ I / O - m o d e ( m o s t g e n e r a l )

{ B o u n d e d a n d u n b o u n d e d d e l a y m o d e l s

( e a c h o f t h e m m a y b e u s e f u l f o r c e r t a i n d e s i g n s )

{ F o u r - p h a s e s i g n a l l i n g ( m o r e e c i e n t a n d f a s t c o n t r o l )

T w o - p h a s e s i g n a l l i n g c a n b e a l s o h a n d l e d

W i l l n o t p r e s e n t

{ S p e c i c m e t h o d s f o r F u n d a m e n t a l m o d e

{ S p e c i c m e t h o d s f o r t w o - p h a s e s i g n a l l i n g

{ A l l t h e m e t h o d s t h a t h a v e b e e n d e v i s e d i n h i s t o r y : : :



32/219

H a z a r d s

0

01

1

ab

1 -> 0

0 -> 1

1 -> 0

0 -> 1

1 -> 0 -> 1

slow

2

1

transition cube

H a z a r d e x a m p l e :

f u n c t i o n s t a t i c 1 - h a z a r d

f o r c = a x o r b

H a z a r d : s i g n a l t r a n s i t i o n n o t s p e c i e d b y t h e d e s i g n e r

H a z a r d s m a k e a s y n c h r o n o u s d e s i g n d i c u l t

T h e o r y o f h a z a r d s : U n g e r , K u n g , N o w i c k ]



33/219

H a z a r d s a n d d e l a y m o d e l

5 10

10

205

5

I n e r t i a l g a t e d e l a y m o d e l

) n o h a z a r d s

W i r e d e l a y m o d e l

) h a z a r d s

H a z a r d a n a l y s i s d e p e n d s o n t h e d e l a y m o d e l



34/219

T a x o n o m y o f h a z a r d s

0

1

0

1 1

0

1

0

Dynamic hazards

0 0

1 1 1

0

Static hazards

S i g n a l b e h a v i o r :

s t a t i c ( n o t r a n s i t i o n i s r e q u i r e d )

o r d y n a m i c ( m o n o t o n o u s t r a n s i t i o n i s r e q u i r e d )

C i r c u i t t y p e :

c o m b i n a t i o n a l ( c i r c u i t s w i t h o u t f e e d b a c k s ) o r

s e q u e n t i a l ( c i r c u i t s w i t h f e e d b a c k s )

D u e t o s p e c i c a t i o n o r d u e t o i m p l e m e n t a t i o n :

f u n c t i o n o r l o g i c e s s e n t i a l o r n o t e s s e n t i a l

D u e t o t h e I / O m o d e o f o p e r a t i o n : d e l a y h a z a r d s o c c u r s w h e n t w o

i n p u t t r a n s i t i o n s a r e t o o c l o s e t o g e t h e r



35/219


36/219

S t a t i c l o g i c h a z a r d e l i m i n a t i o n

cab

c

0 1 1 0

1 1 0 0

a

c

b1

1

0

1

1

0

1

0

20 1

1

0 1

1

c

01

abc

0 1 1 0

1 1 0 0a

c

b1

1

0

1

120 1

a

b

1

1 1

1 01

S t a t i c h a z a r d : a s i g n a l w h i c h s h o u l d r e m a i n c o n s t a n t c h a n g e s

S t a t i c l o g i c 1 - h a z a r d e l i m i n a t i o n c o n d i t i o n :

e a c h t r a n s i t i o n c u b e i s c o n t a i n e d i n s i d e a c u b e o f t h e c o v e r

S t a t i c l o g i c 0 - h a z a r d s n e v e r o c c u r i n a t w o - l e v e l S u m - o f - p r o d u c t s

i m p l e m e n t a t i o n



37/219

D y n a m i c f u n c t i o n h a z a r d s

abcd 00 01 11 10

10

11

01

00 1

1

00

1 1

001 1

1

000 1

1

transition cube

Non-monotonous change

D y n a m i c h a z a r d : a s i g n a l w h i c h s h o u l d c h a n g e o n c e c h a n g e s m u l t i p l e t i m e s

D y n a m i c f u n c t i o n h a z a r d :

n o n - m o n o t o n o u s c h a n g e o f t h e f u n c t i o n i n s i d e t h e t r a n s i t i o n c u b e



38/219

D y n a m i c l o g i c h a z a r d e l i m i n a t i o n

abcd 00 01 11 10

10

11

01

00 1 00

1 1

00 1

1

000 1

1

0

0

abcd 00 01 11 10

10

11

01

00 1 00

1 1

00 1

1

000 1

1

0

0

a

b

cd

01

1

01

1

10

0

10

1010 10

a

b

c

d

slow1010

01

1

01

1

10

010

0

10

10

very slow

D y n a m i c l o g i c 1 t o 0 - h a z a r d e l i m i n a t i o n c o n d i t i o n :

i f t r a n s i t i o n c u b e i n t e r s e c t s c u b e c o f t h e c o v e r ,

t h e n c c o n t a i n s t h e s t a r t p o i n t o f t h e t r a n s i t i o n c u b e

0 t o 1 - h a z a r d s a r e s y m m e t r i c a l ( t h e s a m e f o r t h e e n d p o i n t )



39/219

S e q u e n t i a l h a z a r d s

S e q u e n t i a l c i r c u i t s c i r c u i t s w i t h f e e d b a c k s

S e q u e n t i a l h a z a r d s o c c u r b e c a u s e f e e d b a c k s p r o p a g a t e n e w v a l u e s

b e f o r e t h e i n p u t n e t c o m p l e t e s s i g n a l p r o p a g a t i o n t o a l l i n p u t s o f

t h e n e x t s t a t e l o g i c

E s s e n t i a l h a z a r d : i n h e r e n t i n t h e F S M s p e c i c a t i o n

c a n n o t b e e l i m i n a t e d b y a n o t h e r s t a t e e n c o d i n g )

c a n n o t b e e l i m i n a t e d f o r u n b o u n d e d d e l a y s

c a n b e m a s k e d o u t b y c o n t r o l l i n g t h e d e l a y s

N o n - e s s e n t i a l h a z a r d s ( r a c e s ) :

c a n b e e l i m i n a t e d b y a p r o p e r s t a t e e n c o d i n g



40/219

N o n - c r i t i c a l r a c e s

0010

011 000

010

001

10

10

1010

10

transient states

s1 s2

a b b

011 000

1000

Encoding

R a c e : m o r e t h a n o n e s t a t e s i g n a l c h a n g e s

N o n - c r i t i c a l r a c e :

a l l t r a n s i e n t s t a t e s d r i v e t h e F S M i n t o t h e s a m e n a l s t a t e



41/219

C r i t i c a l r a c e s

10

b b

s3 s4

010 110

011

1000

s1 s2

a b b

000

0010

011

010

001

10

10

10

10

10

110

000

10

C r i t i c a l r a c e :

d i e r e n t t r a n s i e n t s t a t e s d r i v e t h e F S M i n t o d i e r e n t n a l s t a t e s

F i n a l s t a t e d e p e n d s o n t h e r a c e w i n n e r



42/219

R a c e - f r e e e n c o d i n g

0010

011

001

10

10

10

10

000

10

10

01010

110 100

T r a c e y e n c o d i n g :

T w o s t a t e t r a n s i t i o n s u n d e r

t h e s a m e i n p u t

s 1

b

! s 2 a n d s 3

b

! s 4

m u s t b e d i s t i n g u i s h e d b y a

s t a b l e s t a t e s i g n a l :

0 1 1

1 0

! 0 0 0 a n d 1 1 0

1 0

! 1 0 0



43/219

T y p e s o f r a c e - f r e e e n c o d i n g

S i n g l e b i t c h a n g e e n c o d i n g : s i m p l e , b a d t h r o u g h p u t

a d j a c e n t s t a t e s d i e r b y e x a c t l y o n e b i t

m a y r e q u i r e a f e w F S M c y c l e s t o r e a c h a s t a b l e s t a t e

S i n g l e t r a n s i t i o n t i m e e n c o d i n g :

b e t t e r t h r o u g h p u t , m o r e c o m p l e x

a d j a c e n t s t a t e s m a y d i e r b y m u l t i p l e b i t s

r e q u i r e s e x a c t l y o n e F S M c y c l e t o r e a c h a s t a b l e s t a t e

E x a m p l e : T r a c e y e n c o d i n g

R a c e - f r e e F S M s m a y s t i l l h a v e e s s e n t i a l h a z a r d s



44/219

M o d - 2 c o u n t e r : e s s e n t i a l h a z a r d s

D

D

very slow

010

010

01

01

010

01

01

10

010

xy1

y1

010

y2

z

1...001

00

11

0/01/0

1/0

0/0

0/01/11/1

0/0

transition1

transition3

transition2

01

10

U n g e r ' s c o n d i t i o n f o r e s s e n t i a l h a z a r d s :

s t a t e a f t e r t h r e e t r a n s i t i o n s o f a n i n p u t s i g n a l 6=

s t a t e a f t e r o n e t r a n s i t i o n s o f t h e s a m e i n p u t s i g n a l



45/219

W h y e s s e n t i a l h a z a r d s o c c u r

Next state

logic State

Input net

delay_feedback

delay_next

delay1

delay2

N o e s s e n t i a l h a z a r d s i f a n d o n l y i f

j d e l a y 1 ; d e l a y 2 j < m i n d e l a y

n e x t

+ m i n d e l a y

f e e d b a c k

E s s e n t i a l h a z a r d s c a n b e r e m o v e d b y c o n t r o l l i n g t h e d e l a y s



46/219

D e l a y h a z a r d s

1

42

3

a

bcn1

n2

n3

n4

Environment

slow0

010

010

01

010

010

I / O - m o d e :

i n p u t b c h a n g e s

a f t e r o u t p u t c , b u t

b e f o r e t h e o u t p u t o f g a t e

3 h a s s e t t l e d

T h i s i s a d e l a y h a z a r d

D e l a y h a z a r d s m a y o c c u r u n d e r I / O - m o d e e v e n i n d e s i g n s f r e e

f r o m e s s e n t i a l h a z a r d s



47/219

H a z a r d e l i m i n a t i o n m e t h o d s

C h a n g i n g d e l a y s ( d e l a y p a d d i n g )

W o r k s o n l y f o r b o u n d e d d e l a y m o d e l

L o g i c t r a n s f o r m a t i o n s ( c i r c u i t r e d u n d a n c y )

W o r k s b o t h f o r b o u n d e d a n d u n b o u n d e d d e l a y m o d e l s

E n c o d i n g o f i n p u t s a n d o u t p u t s ( c o d e r e d u n d a n c y )

a n d / o r c h a n g i n g a l l o w e d i n p u t t r a n s i t i o n s

W o r k s b o t h f o r b o u n d e d a n d u n b o u n d e d d e l a y m o d e l s

F i g h t i n g w i t h h a z a r d s a l w a y s r e q u i r e s s o m e a r e a a n d t i m e o v e r h e a d



48/219

M a s k i n g h a z a r d s b y d e l a y p a d d i n g ( 1 )

10

205

5

205

20

C o n t r o l l i n g d e l a y s c a n e l i m i n a t e h a z a r d s



49/219

M a s k i n g h a z a r d s b y d e l a y p a d d i n g ( 2 )

0

01

1

0

01

1

0 -> 11

1 -> 02

0 -> 1

1a b

1

b

b

a

a

fast

slow

0 -> 1

slow

ab

1 -> 0

0 -> 1

1 -> 0

1

fast

2

1 -> 0

C o n t r a d i c t o r y d e l a y

c o n s t r a i n t s )

c o n t r o l l i n g d e l a y s c a n n o t

e l i m i n a t e h a z a r d s i n

g e n e r a l



50/219

H a z a r d e l i m i n a t i o n b y r e d u n d a n t e n c o d i n g

0

01

1

ab 1 -> 0

0 -> 1

1 -> 0

0 -> 1

1 -> 0 -> 1

slow

2

1

b.t b.f01 11 1000

00

01

11

10

c.t

0 *

1

1

*

*

*

* * *

0

00

0 0

0

a.t a.fc.t

c.f

a.f

b.t

b.f

a.t

D u a l - r a i l f o u r - p h a s e X O R - g a t e

F u n c t i o n h a z a r d s c a n n o t b e

e l i m i n a t e d b y c h a n g i n g t h e l o g i c

) c h a n g e t h e s p e c i c a t i o n

H a z a r d s d e p e n d o n t h e a l l o w e d

i n p u t t r a n s i t i o n s : X O R - g a t e i s

h a z a r d - f r e e u n d e r u n i q u e

i n p u t c h a n g e s i n t h e

f u n d a m e n t a l m o d e

R e d u n d a n t e n c o d i n g o f i n p u t

a n d o u t p u t s i g n a l s a n d f o u r

p h a s e s i g n a l l i n g p r o t o c o l a l l o w s

t o e l i m i n a t e e v e n f u n c t i o n a l

h a z a r d s



51/219

M o d e r n v i e w o n h a z a r d s a n d r a c e s

C l a s s i c a l h a z a r d / r a c e t a x o n o m y i s c o m p l e x f o r s e q u e n t i a l c i r c u i t s

e v e n i n F u n d a m e n t a l M o d e

I t i s m u c h m o r e c o m p l e x f o r t h e I / O - m o d e :

H a z a r d s m a y b e v i e w e d a s s i g n a l t r a n s i t i o n d i s a b l i n g

C r i t i c a l r a c e s m a y b e v i e w e d a s i n c o m p l e t e ( a m b i g u o u s )

s p e c i c a t i o n s

H a z a r d a v o i d a n c e :

d e s i g n a c i r c u i t i n w h i c h t r a n s i t i o n d i s a b l i n g c a n n o t o c c u r

C r i t i c a l r a c e a v o i d a n c e :

m a k e t h e s p e c i c a t i o n c o m p l e t e a n d u n a m b i g u o u s



52/219

S p e e d - i n d e p e n d e n t d e s i g n

0

1

0

0

1

0

1

1 1

time

1

01

Switching Disabling

Enabling

Stable

Enabled (0*)

Stable

Output changes Input changes

F o r u n b o u n d e d g a t e d e l a y m o d e l :

D i s a b l i n g c a n n o t o c c u r ) n o h a z a r d s

N o n e e d f o r a c o m p l e x t h e o r y o f h a z a r d s f o r t h i s d e l a y m o d e l



53/219

C r i t i c a l r a c e s a s i n c o m p l e t e s t a t e c o d i n g

0010

011

001

10

10

10

10

000

10

10

010

10

010 110

y2 must change

y2 must stay unchanged

Conflict

F S M s p e c i s

a m b i g u o u s , i e i n c o m p l e t e

S t a t e a s s i g n m e n t c o n i c t :

< y 1 y 2 y 3 > n e x t s t a t e y 2

0

0 1 0 0

0 1 0 1



54/219

C o m p l e t e s t a t e c o d i n g

0010

10

10

10

10

10

10

10

11010101

0110

0010

0100

0000S o l v i n g s t a t e a s s i g n m e n t

c o n i c t s :

A d d n e w s t a t e s i g n a l s o r

R e m o v e o n e o f t h e s t a t e s

( b y r e - e n c o d i n g , r e d u c i n g

c o n c u r r e n c y )



55/219

D a t a p a t h d e s i g n

T w o w a y s t o d e s i g n d a t a p a t h :

S y n c h r o n o u s d a t a p a t h - b u n d l e d d a t a

A s y n c h r o n o u s d a t a p a t h

( s p e e d - i n d e p e n d e n t = q u a s i d e l a y - i n s e n s i t i v e )

A s y n c h r o n o u s d a t a p a t h i s u s e f u l i f p e r f o r m a n c e i s d a t a d e p e n d e n t

a n d t h e a v e r a g e c a s e c o m p u t a t i o n d e l a y i s m u c h l e s s t h a n t h e w o r s t

c a s e d e l a y

T w o e c i e n t m e t h o d s f o r a s y n c h r o n o u s d a t a p a t h : r e d u c e d d i r e c t

l o g i c ( R D L ) a n d d i e r e n t i a l c a s c o d e v o l t a g e s w i t c h l o g i c ( D C V S L )



56/219

I n d i c a t i o n

a

b

c

b

a

cC

a

b

c

a

b

c

O R - g a t e : o u t p u t i n d i c a t e s

f a l l i n g i n p u t t r a n s i t i o n s

C - e l e m e n t : o u t p u t i n d i c a t e s

f a l l i n g a n d r i s i n g i n p u t t r a n s i -

t i o n s

I n d i c a t i o n : A T a u b i n ( 1 9 8 0 )

T r a n s i t i o n c i n d i c a t e s t r a n s i t i o n a

i f a n d o n l y i f :

c c a n n o t o c c u r w i t h o u t a

c i s a " c o m p l e t i o n d e t e c t o r " f o r

a

D e s i g n i d e a :

A l l i n p u t a n d i n t e r n a l t r a n s i t i o n s

m u s t b e i n d i c a t e d b y s o m e o u t -

p u t t r a n s i t i o n s

C h o o s e i n d i c a t i n g o u t p u t s t o o p -

t i m i z e p e r f o r m a n c e / a r e a



57/219

D i e r e n t i a l C a s c o d e V o l t a g e S w i t c h L o g i c

network

N transistor

Req

Req

Inputs

Output.t Output.f

I n p u t s a r e ( t y p i c a l l y ) d u a l - r a i l

A d d i t i o n a l r e q u e s t s i g n a l i s

u s e d f o r p r e c h a r g i n g

O u t p u t s a r e d u a l - r a i l f o u r -

p h a s e ( v a l i d - e m p t y p r o t o c o l )

S t a t i c i z e r s ( c r o s s - c o u p l e d i n -

v e r t e r s ) m a y b e n e e d e d f o r

o u t p u t s i g n a l s

T w o c r o s s - c o u p l e d p u l l - u p

t r a n s i s t o r s m a y i m p r o v e p e r -

f o r m a n c e



58/219

R e d u c e d d i r e c t l o g i c

network

N transistor

Input1.f

Input1.t

Input1.f Input1.t

Inputs

Output.t Output.f

I n p u t s a n d o u t p u t s a r e f o u r -

p h a s e d u a l - r a i l

N o a d d i t i o n a l r e q u e s t s i g n a l

F u l l c u s t o m d e s i g n o n l y

D e s i g n i d e a :

A d d a p a i r o f p - t r a n s i s t o r s f o r

e a c h o u t p u t a n d a p a i r o f n -

t r a n s i s t o r s f o r e a c h d u a l r a i l

i n p u t

O p t i m i z e n - t r a n s i s t o r l o g i c

D i s t r i b u t e i n d i c a t i o n o f t h e

i n p u t s a m o n g t h e o u t p u t s



59/219


60/219

C r i t i c a l d e l a y i n a s y n c h r o n o u s a d d e r

1 0 1 1

0 0 0 1

1 1 0 0

Indication in

Indication in

0 0 1 11 001

0

Critical delay

valid phase

empty phase

C r i t i c a l d e l a y i s p r o p o r t i o n a l t o l o g

2

N ( N = n u m b e r o f b i t s )

I t i s d e t e r m i n e d b y t h e m a x i m a l n u m b e r o f c o n t i g u o u s d i e r e n t b i t s

3 2 - b i t a d d e r d e l a y ( 1 6 M O S I S C M O S ) :

a s y n c h r o n o u s : 1 1 n s e c s y n c h r o n o u s : 4 0 n s e c



61/219

P a r t 2 : S p e c i c a t i o n a n d s y n t h e s i s

S p e c i c a t i o n o f c o n t r o l

{ C S P

{ F S M

{ S i g n a l T r a n s i t i o n G r a p h s ( S T G )

S T G i n d e t a i l s : b a s i c s , l i m i t a t i o n a n d e x t e n s i o n s , t i m i n g

S y n t h e s i s o v e r v i e w

S i m u l a t i o n e n g i n e

C o m p l e t e s t a t e c o d i n g = r a c e e l i m i n a t i o n



62/219

C S P

C S P = c o m m u n i c a t i n g s e q u e n t i a l p r o c e s s e s

C o n c u r r e n t p r o c e s s e s c o m m u n i c a t i n g b y i n p u t a n d o u t p u t c o m -

m a n d s o n c h a n n e l s

S e m a n t i c s a r e b a s e d o n t r a c e t h e o r y U d d i n g , v a n d e S n e p -

s c h e u t , R e m ]

I n g e n e r a l , t e c h n i q u e s t r y t o c o m e u p w i t h q u a s i - d e l a y - i n s e n s i t i v e

i m p l e m e n t a t i o n s

T w o m a i n a p p r o a c h e s : P r o d u c t i o n r u l e b a s e d M a r t i n , ] a n d

S y n t a x - d i r e c t e d d e c o m p o s i t i o n E b e r g e n , B e r k e l ]


C S P P R O G R A M


63/219

l

i

] r

o

" r

i

] r

o

# : r

i

] l

o

" : l

i

] l

o

# ]

\ " = s e q u e n c i n g

r

0

" = r

0

g o e s h i g h , r

0

# r

0

g o e s l o w

l

i

] = w a i t u n t i l l

i

i s h i g h , : l

i

] w a i t u n t i l l

i

i s l o w

P r o g r a m m e a n i n g : l

i

h a s t o b e h i g h b e f o r e r

0

g o e s h i g h T h e

c i r c u i t w i l l w a i t u n t i l r

i

g o e s h i g h , b e f o r e r

0

w i l l g o l o w a g a i n

a n d s o o n


P R O D U C T I O N R U L E S


64/219

l

i

7! r

o

"

r

i

7! r

o

#

: r

i

7! l

o

"

: l

i

7! l

o

#

p r o d u c t i o n r u l e = b o o l e a n c o n d i t i o n 7! t r a n s i t i o n

l

i

7! r

o

" : w h e n l

i

i s h i g h , r

o

w i l l g o h i g h

: r

i

7! l

o

" : w h e n r

i

i s l o w , l

o

w i l l g o h i g h

c o n i c t : r

o

" a n d r

o

# a r e n o t m u t u a l l y e x c l u s i v e


P R O D U C T I O N R U L E S ( 2 )


65/219

A d d a s t a t e s i g n a l t o s o l v e c o n i c t :

l

i

] r

o

" r

i

] x " x ] r

o

# : r

i

] l

o

" : l

i

] x # : x ] l

o

# ]

T h e n e w p r o d u c t i o n r u l e s :

: x l

i

7! r

o

"

r

i

7! x "

x 7! r

o

#

x : r

i

7! l

o

"

: l

i

7! x #

: x 7! l

o

#


I M P L E M E N T A T I O N


66/219

li

lori

ff

ro

x x

T h e p r o d u c t i o n r u l e s c a n n o w b e i d e n t i e d w i t h o p e r a t i o n s

r

0

m a p s t o a n a n d - g a t e ( r

0

= x l

i

)

: x l

i

7! r

o

"

x 7! r

o

#


F S M


67/219

s1

s2

s3

xC/o

xC/o

y1y2

00

10

11

xC+xC/o

C+xC/o

xC/o

xC/o


F S M ( 2 )


68/219

N o d e s = s t a t e s , a r c s = s t a t e t r a n s i t i o n

E a c h a r c i s l a b e l e d w i t h a p a i r o f i n p u t = o u t p u t s y m b o l s

i n p u t = c o n d i t i o n f o r s t a t e t r a n s i t i o n t o t a k e p l a c e

o u t p u t = v a l u e s f o r o u t p u t s i g n a l s a f t e r t h e s t a t e t r a n s i t i o n

M o s t l y l i m i t e d t o f u n d a m e n t a l m o d e U n g e r ]


B U R S T M O D E F S M


69/219

s1

s2

s3

s4

a+/y+

b+/y-b-/y+

b+/x+y-

a-b-/x-


B U R S T M O D E F S M


70/219

b a s e d o n s i g n a l t r a n s i t i o n s r a t h e r t h a n s i g n a l l e v e l s N o w i c k ,

Y u n ]

F i r s t a s e t o f i n p u t t r a n s i t i o n s r e s

S e c o n d a s e t o f o u t p u t t r a n s i t i o n s r e s

F i n a l l y s t a t e v a r i a b l e s c h a n g e a n d t a k e t h e s y s t e m t o a n o t h e r

s t a t e

M o s t l y l i m i t e d t o f u n d a m e n t a l m o d e U n g e r ]


S I G N A L T R A N S I T I O N G R A P H


71/219

a+ b+

c+

a- b-

c-

STG

a

c

b

input

output

input

TIMING DIAGRAM


S I G N A L T R A N S I T I O N G R A P H ( 2 )


72/219

V e r t i c e s r e p r e s e n t s i g n a l t r a n s i t i o n s

A r c s r e p r e s e n t c a u s a l r e l a t i o n s b e t w e e n t r a n s i t i o n s

I n t r o d u c e d b y M o l n a r 8 5 ] C h u 8 7 ] R o s e n b l u m 8 5 ]


S I G N A L T R A N S I T I O N G R A P H ( 3 )


73/219

a+ b+

c+

a- b-

c-

PETRI NET

p3 p4

p5 p6

p7 p8

p1 p2

a+ b+

c+

a- b-

c-

STG

S T G i s a n i n t e r p r e t e d P e t r i n e t


C O N S I S T E N C Y


74/219

A+ A+

A-

A- A-

A+

x+

Two subsequent up-transitions

without a down-transition in between

Two subsequent down-transitions

without an up-transition in between

Parallel transitions of the same signal

INCONSISTENT

A+ A-

Two up-transitions with a down-transition

in between (and vice versa)

CONSISTENT

A+


M O D E L I N G P O W E R


75/219

CONCURRENCY

CHOICE

c+

a- b-

a- b-

a- concurrent with b-

choice made by environment

EITHER a- firesOR b- fires

but not both

EITHER a- fires before b-OR b- fires before a-

OR a- and b- fire simultaneously


F I R I N G S E M A N T I C S


76/219

c+ fires

c+

= TOKEN

= PLACE

= TRANSITION

c+

p3 p4

p5 p6

c+ = enabled c+ has fired

c+

p3 p4

p5 p6


S Y N T H E S I S


77/219

Petri Net

Signal Transition Graph

Reachability Graph

State Graph

Karnaugh Map

Logic equations

Translation

Token flow simulation

Encoding

Logic synthesis

direct

method


R E A C H A B I L I T Y G R A P H


78/219

V e r t i c e s r e p r e s e n t s t a t e s t h e c i r c u i t c a n b e i n

A r c s r e p r e s e n t t r a n s i t i o n f r o m o n e s t a t e t o a n o t h e r

C a n b e d e r i v e d f r o m t h e P e t r i n e t b y s i m u l a t i n g t h e t o k e n o w

E a s i e s t r e p r e s e n t a t i o n t o d o a n a l y s i s o n

S i z e m a y b e e x p o n e n t i a l i n t h e n u m b e r o f t r a n s i t i o n s

S i m i l a r t o t r a c e s t r u c t u r e s D i l l ] , t r a n s i t i o n d i a g r a m s M u l l e r ]


R E A C H A B I L I T Y G R A P H ( 2 )


79/219

a+ b+

c+

p3 p4

p1 p2

a+ b+

c+

p3 p4

p1 p2

a+ b+

c+

p3 p4

p1 p2

a+ b+

c+

p3 p4

p1 p2

Fire a+ Fire b+

Fire a+Fire b+

STATE {p1,p2}

STATE {p1,p3}

STATE {p3,p4}

STATE {p1,p4}


S T A T E G R A P H


80/219

000

100 010

110

a+ b+

a+b+

111

011 101

001

a- b-

a-b-

c+

c-

STATE GRAPH

{p1,p2}

{p2,p3} {p1,p4}

{p3,p4}

a+ b+

a+b+

{p5,p6}

{p6,p7} {p5,p8}

{p7,p8}

a- b-

a-b-

c+

c-

REACHABILITY GRAPH

ENCODING


E N C O D I N G


81/219

000

100 010

a+ b+

signal a signal b

signal a and b low

signal a high,signal b low

signal a low,signal b high

E v e r y s t a t e i s a s s i g n e d a c o d e

T h i s c o d e i s d e t e r m i n e d b y s i g n a l s i n t h e P e t r i n e t

B a s e d o n t h i s c o d e , l o g i c a l e q u a t i o n s c a n b e d e r i v e d


E Q U A T I O N S


82/219

000

100 010

110

a+ b+

a+b+

111

011 101

001

a- b-

a-b-

c+

c-

STATE GRAPH

00 01 11 10

0

1

ab

c

c

0

1 1

1

1

0

0

0

K-MAP

LOGIC EQUATIONS

c = ab + ac + bc


E Q U A T I O N S ( 2 )


83/219

000

100 010

110

a+ b+

a+b+

c+

00 01 11 10

0

1

ab

c

c

0 10 0K-MAP

S t a t e 0 0 0 : c i s a s s i g n e d 0 b e c a u s e c s t a y s l o w i n t h i s s t a t e

S t a t e 0 1 1 : c i s a s s i g n e d 1 b e c a u s e c g o e s h i g h i n t h i s s t a t e

( c

+

i s e n a b l e d )



84/219

L E V E L S A N D T R A N S I T I O N S


85/219

CK

SDA

CK

SDA

CK

SDA

CK

SDA

0 bit 1 bit

stop command start command

P r o t o c o l d i s t i n g u i s h i n g d i e r e n t s i t u a t i o n s


S T G W I T H E X T E N S I O N S


86/219

SDA+

SDA

SDA

a b1 0

#

s

CK+

SDASDA

.....

CK-

CK-

CONDITION

SIGNAL LEVEL

CONDITION

TRANSITION

b

b

SDA

SIGNAL LEVEL

DONT CARE

e x t e n s i o n s p r o p o s e d b y M o o n e t a l ]


O R P R E C E D E N C E


87/219

c goes high after a and b

have gone high

a+ b+

c+

c goes high after a OR b

have gone high

a+ b+

c+

NO CHOICE!!

T h i s b e h a v i o r i s h a r d t o m o d e l w i t h c l a s s i c a l P e t r i n e t s



88/219


89/219

B O O L E A N G U A R D S


90/219

X

1

, X

2

a r e B o o l e a n c h a r a c t e r i s t i c f u n c t i o n s

F u n c t i o n s d e t e r m i n e ( t o g e t h e r w i t h t o k e n s ) w h i c h t r a n s i t i o n i s

e n a b l e d

t1 t2

1 2 = 0 = 1

t

1

i s e n a b l e d i f p c o n t a i n s a t o k e n A N D s i g n a l i = 0

t

2

i s e n a b l e d i f p c o n t a i n s a t o k e n A N D s i g n a l i = 1


T R A N S L A T I O N T O S T A T E G R A P H


91/219

+

is

m

m

m(i)=0

m(i)=1

+

is #

is

m

m

m(i)=?

m(i)=-

#

is

1

is

m

m

m(i)=?

m(i)=1

1

is

m

m

m(i)=-

m(i)=0

s

is

0

is

m

1

is

m(i)=1

t1 t2

i=0 i=1

mif m(i) == 0 then t1 is enabled

if m(i) == 1 then t2 is enabled


T I M I N G : S P E C I F I C A T I O N


92/219

A

B

UP >30

[20-40]A

BUP

E n v i r o n m e n t : i f A g o e s h i g h , B w i l l g o h i g h 2 0 t o 4 0 n s l a t e r

C i r c u i t : i f A g o e s h i g h U P n e e d s t o g o h i g h b e f o r e B a n d

n e e d s t o s t a y h i g h a t l e a s t 3 0 n s


T I M I N G : S P E C I F I C A T I O N ( 2 )


93/219

A

B

UP >30

[20-40]

Tolerance

Delay

relation

Specification

relation


T I M I N G : S P E C I F I C A T I O N ( 3 )


94/219

S p e c i c a t i o n r e l a t i o n s i n d i c a t e h o w t h e c i r c u i t s h o u l d r e a c t ,

i f s y n t h e s i z e d c o r r e c t l y

D e l a y r e l a t i o n s i n d i c a t e h o w a n e x i s t i n g c i r c u i t

( o r e n v i r o n m e n t ) r e a c t s

T o l e r a n c e : d e l a y s a r e n o t x e d n u m b e r s , b u t i n t e r v a l s

( e v e n m o r e c o m p l e x s y m b o l i c r e p r e s e n t a t i o n i s p o s s i b l e )


T I M I N G C O N S T R A I N T S


95/219

A n a l y s i s o f t i m i n g c o n s t r a i n t s R o k i c k i , H u l g a a r d , B u r n s , D i l l ,

B e r t h o m i e u , A m o n , W a l k u p ]

T a k e i n t o a c c o u n t a n a l y s i s r e s u l t s M y e r s ]

A c t i v e s y n t h e s i s t o s a t i s f y t i m i n g c o n s t r a i n t s B o r r i e l l o , V a n -

b e k b e r g e n ]

S t i l l a l o t o f r e s e a r c h n e e d e d i n t h i s a r e a


T I M I N G : A N A L Y S I S


96/219

t1

t2

t3

t4

t5[135-inf]

[50-80]

[0-inf]

[50-80]

[0-20]

[30-40]

MAX(t4-t5)?

H a r d p r o b l e m i n i t s f u l l g e n e r a l i t y B e r t h o m i e u ]

E c i e n t s o l u t i o n b y R o c k i k i ( b u t m i g h t s t i l l b e e x p o n e n t i a l )

P o l y n o m i a l s o l u t i o n s w i t h v a r i o u s r e s t r i c t i o n s D i l l , A m o n ]


T I M I N G : S Y N T H E S I S


97/219

A

30 ns

set

reset

out UPHCK

UP

20ns

20ns

A

B

UP >30

[20-40]Trigger to

clock edges Add delay line

S o l u t i o n s w i t h v a r y i n g r e s t r i c t i o n s B o r r i e l l o , V a n b e k b e r g e n ]


S Y N T H E S I S : O V E R V I E W

AFSM STG VHDLSIMULATION


98/219

AFSM STG VHDLS U O

RESULTS

STATE GRAPH

TECH INDEPENDENTEQUATIONS

LIBRARY

TECH. DEPENDENT

EQUATIONS

CORRECTION PHASE

LAYOUT

HAZARD-LIST

VHDLSIMULATION

RESULTS

TOLERANCE


S Y N T H E S I S : O V E R V I E W ( 2 )


99/219

S i m u l a t i o n a t h i g h l e v e l ( s p e c i c a t i o n ) a n d l o w l e v e l ( c i r c u i t )

S t a r t f r o m A F S M o r S T G

R a c e - e l i m i n a t i o n b y s t a t e g r a p h t r a n s f o r m a t i o n

F i r s t s t e p h a z a r d - e l i m i n a t i o n ( t e c h n o l o g y i n d e p e n d e n t )

S e c o n d s t e p h a z a r d - e l i m i n a t i o n ( t e c h n o l o g y d e p e n d e n t )



100/219

W H Y V H D L ?


101/219

T h e n e e d f o r a c o n s i s t e n t l a n g u a g e f o r a l l d i g i t a l a p p l i c a t i o n s

( s y n c h r o n o u s a n d a s y n c h r o n o u s )

T o o l s ( s i m u l a t o r s ) f o r f r e e

T h e c o m p l e t e d e s i g n c a n b e v a l i d a t e d a t d i e r e n t l e v e l s o f

a b s t r a c t i o n

U s e f u l f o r d e b u g g i n g s o f t w a r e p r o t o t y p e s

I C C A D ' 9 5 t u t o r i a l T h e S y s t e m a t i c D e s i g n o f A s y n c h r o n o u s C i r c u i t s 1 0 1

S I M U L A T I O N E N V I R O N M E N T

SYSTEM USERSTG


102/219

SYSTEM USER

VHDL

SIMULATION

TESTBENCHVHDL

ASSERTIONVHDL

BEHAVIORALVHDL

GATE-LEVELVHDL

STG

RESULTSASSERTIONVIOLATIONS

OR

OR


A R C H I T E C T U R E


103/219

BEHAVIORALVHDL ORGATE-LEVELVHDL

ASSERTIONVHDL

TESTBENCH

inputsoutputs

statesignals

Errormessages


V H D L M O D E L


104/219

s+

p1 p2

p3 p3

S t a t e = s e t o f t o k e n s i n p l a c e s

A v e c t o r o f B o o l e a n s : p l a c e s

{ p l a c e s ( 1 ) = 1 i f p l a c e p

1

c o n t a i n s a t o k e n

{ p l a c e s ( 1 ) = 0 i f p l a c e p

1

d o e s n o t c o n t a i n a t o k e n


V H D L M O D E L ( 2 )

BLOCK (places(1) = 1 AND places(2) = 1)


105/219

s+

p1 p2

p3 p3

BLOCK (places(1) 1 AND places(2) 1 )

BEGIN

places(1)


106/219

BLOCK (places(1) = 1 AND pcond = 0 )

BEGIN

places(1)


107/219

A l l b l o c k s a r e p o s s i b l y c o n c u r r e n t

I n V H D L a r e s o l u t i o n f u n c t i o n i s n e e d e d

S T G i s o n l y c o r r e c t i f n o t w o t r a n s i t i o n s o f t h e s a m e s i g n a l a r e

e n a b l e d a t t h e s a m e t i m e

A s s e r t i o n i n t h e r e s o l u t i o n f u n c t i o n t h a t t h e r e a r e n o t w o

s i m u l t a n e o u s a s s i g n m e n t s t o t h e s a m e s i g n a l


A S S E R T I O N ( 2 )

p1


108/219

ASSERT (sSTABLE = TRUE OR places(1) = 1 OR ....)

s+

p1

G i v e s i n f o a b o u t

{ w h e r e ?

{ w h i c h s i g n a l ?

{ w h i c h t y p e o f v i o l a t i o n ?

D e b u g g i n g c i r c u i t A N D e n v i r o n m e n t


T E S T B E N C H


109/219

T e s t b e n c h = b e h a v i o r a l V H D L o f \ i n v e r s e " S T G ( i n p u t s a n d

o u t p u t s s w i t c h e d )

U s e o f s a m e p r o c e d u r e a s t h e o n e g e n e r a t i n g b e h a v i o r a l V H D L

( n o t w r i t t e n b y d e s i g n e r )

A s s u m e s t h a t t h e e n v i r o n m e n t i s t h e f a s t e s t p o s s i b l e

N o t c o m p l e t e ( l i k e v e r i c a t i o n ) , b u t m a n y e r r o r s f o u n d t h i s

w a y


R A C E : M O D E L I N G


110/219

R a c e s a r e m o s t e a s i l y d e t e c t e d a t s t a t e g r a p h l e v e l

N o r a c e i f t h e l o g i c e q u a t i o n s c a n b e d e r i v e d u n a m b i g u o u s l y

S u c i e n t c o n d i t i o n :

A l l s t a t e s a r e a s s i g n e d a u n i q u e c o d e

U n i q u e S t a t e C o d i n g ( U S C )

A l e s s t i g h t s u c i e n t c o n d i t i o n :

C o m p l e t e S t a t e C o d i n g ( C S C )


C O M P L E T E S T A T E C O D I N G

CSC-violation no CSC-violation


111/219

abc

000a+

abc

000a+ c+

abc

000c+

abc

000a+ c+

00 01 11 10

0

1

ab

c

c

0/1

00 01 11 10

0

1

ab

c

c

1


R A C E E L I M I N A T I O N


112/219

R a c e - e l i m i n a t i o n i s e n f o r c i n g C S C ( o r U S C )

W h i c h r o u t e t o t a k e ?

INITIAL STG FINAL STG

FINAL STATE GRAPHINITIAL STATE GRAPH

11

2

IMPLEMENTATION

2

2


R A C E E L I M I N A T I O N ( 2 )

1 S T G - L E V E L K o n d r a t y e v , Y a k o v l e v , L i n , P a s t o r ]


113/219

A v o i d s t h e s t a t e g r a p h l e v e l ( r u n - t i m e e c i e n c y )

C i r c u i t s n o t a l w a y s e c i e n t K o n d r a t y e v ] o r r e s t r i c t i o n s o n

t y p e o f s p e c i c a t i o n h a n d l e d Y a k o v l e v , L i n , P a s t o r ]

2 S T A T E G R A P H L E V E L L a v a g n o , Y k m a n , P u r i , V a n b e k b e r -

g e n ]

C a n b e v e r y c o m p u t a t i o n i n t e n s i v e

V e r y g e n e r a l t e c h n i q u e w h i c h c a n h a n d l e m o r e g e n e r a l

s p e c i c a t i o n s t h a n ( 1 )



114/219

S T G - L E V E L M E T H O D

W o r k s d i r e c t l y a t S T G - l e v e l a n d t h u s a v o i d s s t a t e - e x p l o s i o n


115/219

R e s t r i c t i o n s :

{ N o c h o i c e s

{ E v e r y s i g n a l h a s o n e u p - a n d d o w n - t r a n s i t i o n Y a k o v l e v ]

E x t e n s i o n s :

{ C h o i c e L i n , P a s t o r ]

{ S i g n a l m a y h a v e m o r e t h a n o n e u p - a n d d o w n - t r a n s i t i o n

L i n , Y k m a n , P a s t o r ]



116/219

S T G - L E V E L M E T H O D ( 3 )

ADD SIGNAL


117/219

A+ B+

A-

B-

STG

00

10 01

11

01

A+ B+

A+B+

A-

B-

STATE GRAPH

A+ B+

A-

B-

NEW STG

C+

C-

NEW STATE GRAPH

010

110

A+

C+

000

100

B+

B+

A+

001

101

C-

C-

A+

A-

111

011


L O C K R E L A T I O N


118/219

T h e m a i n p r o b l e m : w e w a n t t o t r a n s f o r m t h e S T G t o s a t i s f y

a p r o p e r t y w h i c h i s d e n e d a t s t a t e g r a p h l e v e l

A t h e o r y i s n e e d e d t h a t t r a n s f o r m s t h e C S C o r U S C p r o p e r t y

t o t h e S T G - l e v e l

A+

B+

A-

B-

Two signals A and B are locked

iffthe transitions of the two signals resideon a simple cycle in an alternating way

Corresponds to handshake protocol


L O C K G R A P H

The vertices correspond to the signals A B C


119/219

p g

There is an arc between two vertices if the

corresponding signals in the STG are locked.

A B C

D

Lock Graph = connected

STG satisfies USC


L O C K T H E O R E M

OLD STG lock graph NOT connected


120/219

NEW STG lock graph connected

TRANSFORM

A d d i n g a r c s

A d d i n g n e w s i g n a l s ( a n d t r a n s i t i o n s )

I f n e c e s s a r y , t a k i n g i n t o a c c o u n t t i m i n g c o n s t r a i n t s


I N T U I T I O N

A c o m p l e m e n t a r y s e t i s a s e t o f t r a n s i t i o n s s u c h t h a t i f a

+

i s


121/219

i n t h e s e t t h e n a l s o a

;

a n d v i c e v e r s a

F i r i n g a c o m p l e m e n t a r y s e t l e a d s t o s t a t e s w i t h t h e s a m e c o d e

( f o r i n s t a n c e f A

+

1

R

;

1

A

;

1

R

+

1

g i n t h e n e x t e x a m p l e ( a ) )

T h e o n l y a l l o w e d c o m p l e m e n t a r y s e t t h a t y o u c a n r e i s t h e

s e t c o n t a i n i n g a l l t r a n s i t i o n s

L o c k i n g m a k e s s u r e t h a t n o c o m p l e m e n t a r y s u b s e t o f t r a n s i -

t i o n s i s r e a b l e


L O C K E X A M P L E

R1- R2+ R1- R2+ R1- R2+


122/219

A1-

R1+

A1+

A2+

R2-

A2-

R1 R2

A1 A2

A1-

R1+

A1+

A2+

R2-

A2-

R1 R2

A1 A2

A1-

R1+

A1+

A2+

R2-

A2-

R1 R2

A1 A2

X+

X-

X


S T A T E G R A P H L E V E L M E T H O D

T r a n s f o r m s t h e p r o b l e m i n t o a s a t i s a b i l i t y p r o b l e m


123/219

V e r y c o m p u t a t i o n i n t e n s i v e

V e r y f e w r e s t r i c t i o n s :

{ G e n e r a l P e t r i n e t s ( w i t h a l l e x t e n s i o n s )

{ G e n e r a l t r a n s f o r m a t i o n s ( c o n c u r r e n t t r a n s i t i o n s )

P a r t i t i o n i n g P u r i ] a n d H e u r i s t i c s L a v a g n o , Y k m a n ] t o i m p r o v e

e c i e n c y o f c i r c u i t a n d c o m p u t a t i o n t i m e

C o n c u r r e n c y r e d u c t i o n Y k m a n ]


S T A T E A S S I G N M E N T

\ E x p a n d " a s t a t e g r a p h i n t o a n e w s t a t e g r a p h t h a t s a t i s e s

C S C


124/219

4 - v a l u e a s s i g n m e n t s e t : f 0 1 U P D O W N g

M e a n i n g o f a s s i g n i n g a v a l u e t o a s t a t e P f o r s i g n a l S

{ P i s a s s i g n e d 0 : S i s l o w i n P

{ P i s a s s i g n e d 1 : S i s h i g h i n P

{ P i s a s s i g n e d U P : P w i l l b e e x p a n d e d i n t w o s t a t e s w i t h S

+

c o n n e c t i n g b o t h s t a t e s

{ P i s a s s i g n e d D O W N : P w i l l b e e x p a n d e d i n t w o s t a t e s w i t h

S

;

c o n n e c t i n g b o t h s t a t e s



125/219

S T A T E A S S I G N M E N T ( 3 )

STATE GRAPHNEW STATE GRAPH


126/219

00

10 01

11

01

A+ B+

A+B+

A-

B-

010

110

A+

C+

B-

000

100

B+

B+

A+

001

101n2

C-

C-

A+

A-111 011

DOWN

DOWN 0

UP

1


D E C O M P O S I T I O N M E T H O D

a+ d+ a1+ d+ a2+

original STG(a,b,c)projection

(d,e,f)projection

(a,f)projection


127/219

b-

c+

a-

b+

c-

e-

f+

d-

e+

f-

b-

c+

a1-

b+

c-

e-

f1+

d-

e+

f1-

f2+

a2-

f2-

a1

b

c

d

e

f1

a2

f2

PROJECTION

IMPLEMENT

a1

b

c

a2

f2

d

e

f1

C

Cf

COMPOSE


P a r t 3 : H a z a r d - f r e e s y n t h e s i s a n d t e s t a b i l i t y

H a z a r d - f r e e s y n t h e s i s b a s e d o n l o g i c t r a n s f o r m a t i o n s


128/219

U n b o u n d e d g a t e d e l a y s

H a z a r d - f r e e s y n t h e s i s b a s e d o n c h a n g i n g d e l a y s

B o u n d e d w i r e d e l a y s

S y n t h e s i s o f n o n - d e t e r m i n i s t i c a s y n c h r o n o u s c i r c u i t s

M e t a - s t a b i l i t y p r o b l e m

T e s t i n g


H a z a r d - f r e e s y n t h e s i s

I n p u t : S T G ( o r S G ) w i t h C S C


129/219

O u t p u t : l o g i c c i r c u i t i m p l e m e n t i n g t h e S T G

{ c o r r e c t l y ( n o h a z a r d s , n o r a c e s )

{ w i t h m i n i m a l c o s t ( a r e a / d e l a y / p o w e r / t e s t a b i l i t y )

D i r e c t m e t h o d s ( s y n t a x - d r i v e n f r o m S T G ) : f a s t b u t p o t e n t i a l l y

s u b o p t i m a l

S y n t h e s i s - b a s e d m e t h o d s


S T G - b a s e d s y n t h e s i s

A b s e n c e o f r a c e s g u a r a n t e e d b y c o n s t r u c t i o n ( o n l y S T G s i g n a l s

c a n b e f e d b a c k )


130/219

A b s e n c e o f h a z a r d s c a n b e a c h i e v e d :

{ b y a c k n o w l e d g m e n t / i n d i c a t i o n ( e a c h g a t e h a s s o m e o t h e r

g a t e t h a t \ c h e c k s " w h e n i t s t r a n s i t i o n i s c o m p l e t e d , t o

a v o i d h a z a r d s )

{ b y i n s e r t i o n o f a p p r o p r i a t e d e l a y s

M i n i m a l i t y i s a c h i e v e d b y l o g i c s y n t h e s i s ( s p e c i a l m e t h o d s f o r

t w o - l e v e l a n d m u l t i - l e v e l i m p l e m e n t a t i o n s )


S y n t h e s i s w i t h u n b o u n d e d g a t e d e l a y s

M u l l e r ( 5 9 ) : f o r m a l a n a l y s i s m e t h o d , b u t o n l y d e s i g n h i n t s


131/219

M a r t i n ( 8 6 , : : : ) : s y n t a x - d i r e c t e d t r a n s l a t i o n , t h e n Q D I - p r e s e r v i n g

o p t i m i z a t i o n

V a r s h a v s k y ( 9 0 ) : s y n t a x - d i r e c t e d t r a n s l a t i o n f r o m S T G

B e e r e l ( 9 2 ) : i m p r o v e s w i t h h e u r i s t i c S G - l e v e l t e c h n i q u e b a s e d

o n \ m o n o t o n o u s s w i t c h i n g " o f c u b e s

K o n d r a t y e v ( 9 3 , : : : ) : n e c e s s a r y a n d s u c i e n t c o n d i t i o n s f o r

m o n o t o n o u s s w i t c h i n g , S T G - a n d S G - l e v e l s y n t h e s i s t e c h n i q u e s


D r i v i n g a n d s u p p o r t i n g g a t e s

z+ x-

STG

1->0->1 21 4 driving

Complex gate - no hazards Simple gates - hazards


132/219

z-x+

y+

y-

0 01-> ->x = zy + zx

x

zyz

x

y

0->10

0

z

z

1 >0 >10->1

2

3

supporting

4 5

A l l i n t e r n a l s i g n a l t r a n s i t i o n s m u s t p r o p a g a t e t o t h e o u t p u t

( a c k n o w l e d g e m e n t p r i n c i p l e a p p l i e d t o i n d i v i d u a l g a t e s )

D r i v i n g g a t e s : \ g o o d " , s u p p o r t i n g g a t e s : \ b a d "


I m p l e m e n t a t i o n s t r u c t u r e s

Set function

Signal implementation

Ca

C-latch

R

S

E a c h s i g n a l t r a n s i t i o n

p r o d u c e s a n A N D g a t e


133/219

Latch

Reset function

R

S=0, R=1

S=1, R=0 a+

a-

a + s e t s t h e l a t c h

a ; r e s e t s t h e l a t c h

...

...

...

...

a-

a+1

a+n

1

Sa

Ra

a~

ad~

e

c~

b

BASIC ARCHITECTURES

a-n

cb

de a-

a+1

a+n

1

a-n

Sa

Ra

Ca

RS flip-flop


R e g i o n s o f t h e s t a t e g r a p h

S y n t h e s i s i d e a : S e t o f c o n c u r r e n t t r a n s i t i o n s ) c o v e r c u b e

i n R o r S f u n c t i o n ) d r i v i n g g a t e


134/219

0*0*1

10*1* 0*11

000*

111*10*0

01*0

1*10

region +zExcitation

Cube x

(Sz = x)

region +z

Quiescent

zyx

E x c i t a t i o n r e g i o n ( E R ) m u s t

b e c o v e r e d b y o n e c u b e

Q u i e s c e n t r e g i o n ( Q R ) i s a

d o n ' t c a r e s e t f o r a c o v e r

c u b e


M o n o t o n o u s c o v e r c o n d i t i o n s

b+

a-

0*10*0

00*00

1*000abcd

C o v e r c u b e C i s a m o n o t o n o u s c o v e r


135/219

a+ c+

a-

b-

a+

d-

d+

c-

0*10*0

110*0 0*110

1110*

1*111

01*11

0*01*1

101*11001*

0*001

cube ac

cube abc

ER

QR

ER(d-)

(d+)

(d+)

f o r E R ( a ) i :

1 C c o v e r s a l l s t a t e s E R ( a )

2 C c o v e r s n o s t a t e s o u t s i d e

E R ( a ) Q R ( a )

3 C c h a n g e s o n l y o n c e i n s i d e Q R ( a )

M o n o t o n o u s c o v e r ) S I - i m p l e m e n t a t i o n

R e s t r i c t e d ( b u t u s e f u l a n d r e a l i s t i c ) a r c h i t e c t u r e


R e d u c t i o n t o m o n o t o n o u s c o v e r f o r m

b+

x+

d-ab

cd00 10 11 01

00 00 - -

C u b e s f b d , c g f o r m a c o r r e c t

n o n - m o n o t o n o u s c o v e r o f

E R ( a + ) :


136/219

a+

d+

x-

c-

a-

b-

b+

b-

00

01

11

10

1 1 1

1 1 1

1 1

0

0

- -

ER(a+)

cube bd

cube c

c+{ n o n e c o v e r s a l l s t a t e s o f

E R ( a + )

{ d u e t o n o n - p e r s i s t e n c y o f c d

w r t a +

A f t e r i n s e r t i o n o f x :

c u b e b x i s a m o n o t o n o u s c o v e r

E x t e r n a l l y o b s e r v a b l e b e h a v i o r i s p r e s e r v e d

S u c i e n t c o n d i t i o n : a n y M C v i o l a t i o n c a n b e e l i m i n a t e d w i t h

a t m o s t t w o a d d e d s i g n a l s


E x t e n s i o n s o f m o n o t o n o u s c o v e r t h e o r y


137/219

E x a c t S G - b a s e d p r o c e d u r e b a s e d o n s t a t e l a b e l i n g

( s i m i l a r t o s t a t e e n c o d i n g )

T h e o r y c a n b e e x t e n d e d t o h a n d l e c o m p l e x g a t e s :

{ m o n o t o n i c i t y c o n d i t i o n s m u s t h o l d f o r a s e t o f c u b e s

{ e a c h t r a n s i t i o n i n E R m u s t b e c o v e r e d b y a t l e a s t o n e c u b e

o f t h e g a t e


S y n t h e s i s w i t h b o u n d e d w i r e d e l a y s

U n g e r ( 6 9 ) : s u m m a r y o f c l a s s i c a l t e c h n i q u e s f o r a s y n c h r o n o u s


138/219

F S M s

L

Documents

Iccad 95 Tut.ps