R e s e a r c h o n C o m b i n e d
A p p r o a c h e s o f G r a p h T h e o r y a n d M a t h e m a t i c a l P r o g r a m m i n g f o r
H i g h - L e v e l a n d P h y s i c a l S y n t h e s i s o f V L S I
Cong HAO
2017 4
2
A l o n g w it h e x p l o s i v e V L S I ap p li c a t i o ns i n m o d e r n t e c h n ol o g i es , V L S I d e s i g n us i n g s of t w a r e t o o ls be c om e s of t h e u t m os t i m p or t a nc e, w h i c h is r e f er r ed t o as e l ec t r o n ic d e s i g n a u t o m a t io n ( ED A ) . ED A d e s i gn f low, a l s o c a l l ed I C d es i g n f l ow, is a p r oc es s w h i c h c o ns i s t s o f s e v e r a l a u t om a t e d s t ep s t o ac c om p l i s h t h e d es i g n o f a n I C . Si n c e E D A t o o ls p l a y a n im p o r t an t r o l e i n d e v e l op i n g I C s w i t h hi g h p er f o r m a n c e, l ow c os t a nd f a s t t i m e- t o - m a r k et , t h e d e v e l op m en t o f h i g h ef f ic i e nc y a l g or i t h m s us ed i n ED A d e s i g n f l ow f or v ar i o us op t i m i z at i o n o b j ec t i v es a r e at t r a c t i n g m o r e a nd m o r e r e s ea r c h i n t er es t s . T h e g en e r al ED A d e s i g n f l ow c o nt a i n s s e v e r a l r ep r es e nt a t i v e s t e p s i nc l u d i n g h i g h l e ve l s y n t h e s i s ( H LS ) , l o g i c s y n t h es is , a n d p h y s ic a l s y n t h es i s , et c . , t o m e e t v ar i o us d e s i g n r e q u i r e m e n t s s u c h a s p o w e r, c h i p a r e a, c l oc k f r e q uen c y a nd s i g n a l d e l a y.
Si n c e m id - 1 9 7 0s , t h e i n ve s t i g a t io n s o f E D A d es i g n m e t ho d ol o g i es h a v e b e e n c a r r i ed o n f or d e c ad es , a n d s i g n i f i c a nc e ac h i e v em e nt s h a v e be e n m a d e f or a u t o m at ed d es i g ns i ns t e a d o f m a n u al d es i g ns . A lo n g w i t h t h e d e v e l op m e n t o f c o m m er c ial ED A t o o ls , E D A c om p a n i e s ar e a ls o g r ow i n g f a s t a n d c on t i n uo us l y. B es id es t h e ac h i e v em e nt s , t h e r e ar e s t i l l u ns o l v ed p r o b le m s , e it h er b ec a us e of t h e c o m p le x i t y of t h e p r o b l em s o r of t he r a p id l y g r o w i n g p r o bl e m s i z e. F or e x am p le i n H LS , t h e s ol u t i on q u a li t y i s s t il l l ow e r t h a n m a n u al d es i g ns , w h i c h ha s a l ar g e r oo m f or i m p r o ve m e n t ; f o r i nt e r c o n n ec t io n op t im i z at i o n, s om e im p or t a nt p r o bl e m s s u c h as t h e p o r t as s i g nm e nt p r o b l em , a r e i g n or ed a nd n ot b ei n g f u l l y i n v es t i g at e d . T h er e f o r e, a l g or it hm s w it h h i g h op t im a l it y a r e s t i l l e x p e c t e d , w h i c h e q u a l or e ve n e xc e l m a n u a l d e s i g n s . I n a d d i t io n , i n p h ys i c al s y nt h es i s , t o g et h er w i t h t h e g r ow i n g d es i g n a n d c i r c u i t s i z e, s o m e p r o bl em s b e c o m e e x t r em el y h u g e, w hi c h m a k e s i t d if f i c u lt t o b e s o l v ed u s i n g e x is t i n g al g o r it h m s . T h er e f o r e, a l g or i t hm s w i t h hi g h ef f ic i e nc y ar e e x p ec t ed t o h a nd l e l a r g e s c a le d p r o b l em s in p h ys i c al s y n t he s i s .
M o t i v at ed b y t h e e x is t i n g is s u es , i n t h is r es e ar c h, t w o t op i c s a r e t o b e s t ud i ed . O n e i s t h e l ow p ow er H L S t ec h n o lo g y, i n c l u d in g s c h ed u l i n g, r e s o u r c e al l o c a t i o n, bi n d i n g, a n d i n t e r c o n n ec t i on op t i m i z a t i o n. A n ot h e r is t h e p h ys i c a l s y nt h es is f o r 3D I C t ec h n ol o g y, w he r e t h e TS V i n s e r t i o n f o r 3D - I C is s t ud i ed . T h e y ar e s o l v ed b y c o m m o n t e c h n ol o g i es , i n c l ud i n g g r ap h t h e or y, m at h em a t i c a l p r o g r am m i n g a nd it e r a t i v e m et h o d s , w i t h t h e p r i nc i p le of im p r o v i n g t h e al g o r it h m op t i m al i t y a nd ef f ic i e nc y. T hi s t h es i s is o r g a n i ze d a s t h e f ol l ow s .
C h ap t er 1 , [ I n t r o d u c t i o n ] , f i r s t g i v es a br i ef i n t r o d u c t io n t o ED A d e s i g n f l ow. T he n s o m e e x i s t i n g p r o b le m s i n c u r r e n t ED A d e s i g n f l ow a r e
3
ad d r e s s ed . M o t i v a t e d b y t he e x is t i n g p r ob l em s , t h e p r in c ip l es of t h i s r e s e a r c h ar e g i v e n , w h ic h i s t o i m p r o v e a l g or i t hm o p t i m a l it y f o r s m al l a nd m e d i u m s i z ed p r o b le m s , a nd t o im p r o v e a l g or i t h m e f f ic i e nc y f or la r g e s i z ed p r o bl e m s . T h e n, t h e t hr e e t o p i c s of t h is r es e a r c h ar e i n t r o d u c e d, f o l lo w e d b y t he i r c o m m o n t ec h n o lo g i es. B es id es , n e c e s s ar y p r e li m in a r i e s ar e b r ie f l y g i v e n, i nc l u d i n g t h e b ac k g r o u n d k n ow l ed ge of H LS , 3D I C a n d T S V i ns e r t i o n p r o b l em . F in a l l y, t h e o r ga ni z a t io n o f t hi s t h es is i s g i v e n.
C h ap t er 2, [ A U n i f i ed S c h ed u l in g A p p r o ac h w it h M u l t i p l e Vd d or / a nd Vt h i n H L S] , d i s c us s es t h e d y n am ic a nd l e ak a g e p ow er m i n im i z at i o n p r o b le m us i n g m u l t i p le Vd d an d Vt h t ec h n o lo g y i n op er a t i o n s c h ed u l i n g, a s w e l l a s t h e c om b i n ed s c h ed u l i n g an d b i n d i n g m e t h od . A lt h o u g h t h is i s a m e d i u m s c a le d p r o b le m , t h e op t im a li t y of e x is t i n g a l g o r i t hm s ar e s t i l l n ot h i g h e n ou g h , s a y e q u al t o o r ev e n e x c e l m a n u a l d e s i g ns .
T h er e f o r e, i n t h is c h ap t e r, a hi g h l y o p t im i z e d u n if i e d s c h ed u l i n g ap p r o a c h w h i c h is ap p l ic a b le t o v a r i o us op t i m i z at i o n p r o bl e m s i s p r o p o s e d , i nc l u d i n g : ( 1 ) d y n am i c p ow e r a nd r es o ur c e us a g e c o - op t i m i za t i o n; ( 2) l ea k a ge p ow e r op t i m i za t i on ; a n d ( 3 ) d y n a m i c p ow er a nd l e ak a g e p ow e r c o - op t i m i za t i o n. To d ea l w it h d if f e r e n t o b j ec t i v es w i t h h i g h f l e x i b i li t y, t h r e e p r o b l em s a r e d i v i d e d i nt o t w o c om m o n s u b - p r o bl e m s, i nc l u d i n g d e la y as s i g n m en t a nd r es o ur c e d e ns it y v ar i a n c e m i n i m i z a t i on . T he n a v er t e x p o t e nt i a l b a s e d m o b i li t y a ll o c at i o n m od e l is p r op os ed t o s ol v e t w o s u b - p r o b l em s s im u lt a n e o us l y. O n t h e m o b i lit y g r a p h , t h e ne t w o r k s i m p l e x m e t ho d is ap p li e d , w h ic h op t im i z e s b ot h d y n am ic p ow er a n d r es o ur c e us a g e b y ad j u s t i n g t h e v e r t e x p o t e n t i a ls . T h e m o b i li t y g r a p h is it e r a t i v el y s o l v ed b y lo c a l s e ar c h u n t il t he a l g or i t h m m ee t s s t op c r i t e r i a. T h e c o m bi n e d s c h e d u l i n g an d bi n d i n g f o r p ow er m i n im i z at i o n i s a l s o i n v es t i g a t e t o f u r t h er r e d u c e o v er a l l p o w er c o ns um p t i o n .
E x p er im e n t a l r es u lt s s h ow t h a t , f o r d y nam i c p ow er a nd r e s o u r c e c o - op t i m i za t i o n, t h e p r op os e d s c he d u l i n g a p p r o a c h p r od u c es op t im u m s o l ut i o ns f o r a l l 6 b e nc h m a r k s w it h 1 5 g r o u p s of d a t a ; f o r l ea k a ge p ow er op t im i z at i o n it a ls o g r ea t l y e x c e ls t he l a t es t e x i s t i n g w o r k , b y 2 0 % l ea k a ge p ow e r r e d u c t i o n a nd 52 t i m e s s p e e d up .
C h ap t er 3, [ I nt e r c o n n e c t i o n A l lo c at ion be t w e e n F u nc t i o n a l U ni t s a nd R e g is t er s i n H L S] , d is c us s e s t h e i nt e r c o n n ec t i o n op t im i z at i o n t e c h n iq u es i n H LS , w hi c h h as n ot b e e n f u l l y i n ves t i g a t ed . A lt h o u g h it is a m e d i u m s c a le d p r o bl e m , i t s op t im a l it y h as a l a r ge i m p a c t o n c h i p p ow e r, ar e a a n d s i g n a l d e l a y. T h e r e f or e h i g h o p t im a l it y a l go r i t h m s ar e e x p e c t e d .
4
I n t h is c h a p t e r, t h e p o r t as s i g nm e nt p r o b le m f o r i n t e r c o n n ec t i on c o m p l e x it y r ed u c t i o n is d i s c us s ed . Fir s t , t h e p o r t a s s i g nm e n t p r o bl em i s f o r m u l at e d o n a c o ns t r a i nt g r ap h , a nd a p r ac t ic a l m e t h o d i s p r o p os ed t o f i n d a v a li d a nd i n it i a l s o l ut i o n. F o r s o l ut i o n op t im i z at i on , a n el e m e n t ar y s p a n ni n g t r ee t r a n s f or m a t i on b as ed l oc al s e a r c h al g o r it hm i s p r o p o s e d . To im p r o v e t h e ef f ic i e nc y o f o p t i m i z a t i o n, a m a t r i x f or m u l at i o n i s p r op os e d , a nd t h e n e t w or k s i m p l e x m e t h od i s a d op t e d w i t h p i v ot i n g o p er a t i o ns t o p e r f o r m o p t im i z a t i on . T h e t w o- s t ep s u c c e s s i v e p i v o t in g i s a ls o d i s c u s s e d t o f u r t h e r im p r o v e a l g o ri t hm e f f i c i e n c y a nd op t i m a li t y.
E x p er im e n t a l r es u lt s s h ow t h at o n t he r a nd o m l y g e ne r at e d t e s t c a s es , t h e m a t r i x b as ed al g o r it h m s h ow s h i g hes t s o l u t i o n o p t im a l it y a n d is f i v e t im es f as t e r t h an t h e el em e n t a r y t r a ns f o r m a t io n m et h od . O n t he r e a l h i g h - l e v e l s y nt h e s i s b e nc h m a r k s , t h e m a t r i x b a s e d m e t ho d r ed u c ed 1 4% i n t e r c o n n e c t i o ns , w h i l e t h e p r e v i o us a l g o r i t hm r e d u c e d 8% .
C h ap t er 4 , [ A M u l t i - L e ve l A l g o r it hm f o r 3D - I C T S V As s i g n m e n t i n P h ys i c a l S y nt h es i s ] , d is c us s e s t he p r o b le m of T hr o u g h S i li c on Vi a ( T S V ) i ns er t i on o n 3D - I Cs i n p h y s ic a l s y nt h e s i s . T h is is a h u g e s c a l e p r o bl em w h i c h r e q u ir es h i g h ef f ic i e nc y a l go r i t h m s w h il e t h e s o l ut i o n o p t im a l it y is n ot s ac r if i c e d .
T h r o u g h- s i li c o n v i a ( TS V ) as s i g nm e nt p r o bl em is o n e of t h e k e y d e s i g n c h a ll e n g es of 3- D I C w h i c h i s c r u c ia l t o t h e w ir e le n g t h a nd s i g n a l d e l a y. I n t h is c h a p t er t h e 3- D I C T S V as s i g n m en t i s f or m ul a t ed as a n I n t e g e r M i n im um C os t M ul t i C o m m od it y ( IM C M C ) p r o b le m , a nd a m u l t i - le v e l a l g or i t hm i s p r op os e d . I t c o a r s ens t he I M C M C ne t w o r k l e ve l b y l e v e l, a p p l i es a r o u g h f l ow a s s i g n m en t o n e ac h l e v e l o f c o a r s e n ed g r a p h, a nd g e ne r a t e s o n l y p r o m is i n g ed g es t o r ed u c e t he I M C M C n et w o r k s i z e. To im p r o v e t h e T S V a s s i g n m e nt q ua l i t y, a m i x e d s i n g l e a n d m u l t i- c o m m od i t y f l ow m e t h od is p r o p o s e d . B e s i d es , a n e x t e n d e d l a y er b y l a y er a l g or i t hm i s p r op o s e d t o op t im i z e t he TS V as s i g n m e n t .
E x p er im e n t a l r e s u lt s s h ow t h a t t h e p r op os e d m u lt i- l e v e l p r o p os a l ac h i e v es 3 7 t i m e s s p ee d up c om p ar ed t o t h e p r e v i o us w or k , a n d m e a nw hi l e r e d uc e s t h e t o t a l w i r e l e n gt h by 7. 0% . T h e e x t e nd ed la y e r b y la y e r op t im i z at i o n f u r t h er r e d uc es 0. 6% t o t a l w ir e l e n g t h .
C h ap t er 5 , [ C o n c l us i o ns ] , c o n c l ud es t hi s t h es is a n d d is c us s es s om e op e n is s ue s of t h is r es e ar c h, f o ll ow e d b y f u t ur e w o r k s .
