I n d on e s i an   Jo u r n al   o El e c t r i c al   En gi n e e r i n g   an d   C o m p u te r   S c i e n c e   V o l .   16 ,   N o .   2 N o v e m b e r   201 9 ,   pp.   6 4 0 ~6 5 2   IS S N :   2502 - 4752 ,   D O I :   10. 1 1591 / i j e e c s . v 1 6 .i 2 . pp6 4 0 - 6 5 2             640       Jou r n al   h o m e pa ge ht t p: / / i ae s c or e . c om / j our na l s / i nde x . php/ i j e e c s   Ob st a c l e   a w a r e   d e l a y   o p t i m i z e d   r e c t i l i n e a r   s t e i n e r   m i n i m u m   t ree  r o u t i n g       S h yam al G ,   G .   R .   P r as ad   B   M   S   C o l l e g e   o f   E ng i ne e r i ng ,   B a ng a l o r e ,   I ndi a       A r ti c l e   I n fo     A B S TR A C T     Ar t i c l e   h i s t or y :   R e c e i v e d   J a n   1 5 ,   2 019   R e v i s e M a 18,   20 19   A c c e pt e M a y   20 ,   20 1 9       T hi s   w o r pr e s e n t s   a   m e t ho t o   s o l v e   t he   pr o bl e m   o f   c o ns t r uc t i ng   R e c t i l i n e a r   S t e i ne r   M i ni m um   T r e e   ( R S M T )   f o r   a   g r o up  o f   pi ns   i n   t h e   pr e s e nc e   o f   o bs t a c l e s .   I m o de r v e r y   l a r g e - s c a l e   i n t e g r a t e c i r c ui t   ( V L S I )   de s i g ns ,     t he   o bs t a c l e s ,   g e ne r a l l y   bl o c ks   t h e   m e t a l   a nd  t he   de v i c e   l a y e r .   T he r e f o r e   r o ut i ng   o t o of   bl o c ka g e   i s   a   po s s i bl e   s o l u t i o bu t   buf f e r s   c a nno t   be   pl a c e o v e r   t he   o bs t a c l e .   M o de r V L S I   de s i g O A R S M T   c o ns t r uc t i o ha s   l o n g   w i r e   l e ng t h ,   w h i c r e s ul t s   i s i g na l   v i o l a t i o n .   T o   a ddr e s s   t h i s   i s s u e   a   s l e w   c o ns t r a i nt   i n t e r c o nne c t   ne e t o   be   c o ns i de r e i r o ut i ng   o v e r   o bs t a c l e .   T h i s   i s   c a l l e d   t h e   O bs t a c l e - A v o i di ng   R e c t i l i ne a r   S t e i ne r   m i ni m um   t r e e s   ( O A R S M T )   pr o bl e m   w i t s l e w   c o ns t r a i nt s   o v e r   o bs t a c l e s .   T he   dr a w ba c o f   t r a d i t i o na l   O A R S M T   i s   t h a t   t h e y   o nl y   c o ns i de r   s l e w   c o ns t r a i nt ,   a nd   de l a y   c o ns t r a i n t s   a r e   n e g l e c t e d.   I t   i nduc e s   hi g r o ut i ng   r e s o ur c e s   o v e r he a due   t o   buf f e r   i ns e r t i o a nd  do e s   no t   s o l v e   g l o ba l   r o ut i ng   s o l ut i o n.   T hi s   w o r p r e s e nt s   a O bs t a c l e   A w a r e   D e l a y   O pt i m i z e R e c t i l i ne a r   S t e i ne r   M i ni m um   T r e e   ( O A D O R S M T )   R o ut i ng   t o   a ddr e s s   t he   de l a y ,   s l e w   c o ns t r a i n t   a nd   r e duc e   t he   r o ut i ng   r e s o ur c e s .   E x pe r i m e n t s   a r e   c o nduc e t o   e v a l u a t e   t h e   p e r f o r m a nc e   o f   pr o po s e a p pr o a c o v e r   e xi s t i ng   a pp r o a c i t e r m   o f   w i r e   l e ng t h   a nd  w o r s t   ne g a t i v e   s l a c k.   T he   e xp e r i m e n t s   a r e   c o nduc t e f o r   s m a l l   a nd  l a r g e   ne t s   c o ns i de r i ng   f i xe d   a n v a r i e o bs t a c l e s   a nd   o ut c o m e   s ho w s   t he   pr o po s e d   e f f i c i e nc y   o v e r   e xi s t i ng   a pp r o a c he s .   T he   O A D O R S M T   i s   de s i g ne d   i s uc a   w a y   w he r e   i t   c a n   be   pa r a l l e l i z e d   t o   o bt a i n   b e t t e r   e f f i c i e nc y .   Ke y w or d s :   O b s t a c l e - a vo i di ng   R e c t i l i n e a s t e i n e r   t r e e   S l a c a n s l e w   c o n s t r a i n t   V L S I   C opy r i gh t   ©   201 9   I n s t i t ut e   o f   A dv anc e E ng i ne e r i ng   and   S c i e nc e .     A l l   r i gh t s   r e s e r v e d .   Cor r e s pon di n g   Au t h or :   S h y a m a l a   G ,     B   M   S   Co l l e ge   o f   E ngi n e e ri n g ,     B a n g a l o r e ,   I n d i a .   E m a i l :   s h y a m a l a . c s e @ b m s c e . a c . i n       1.   I N TR O D U C TI O N     T h e   w i de   gr o w t h   o f   s e m i c o n duc t o r   i ndus t r i e s   ha s   l e t o   t h e   e vo l ut i o n a r y   gr o w t h   o f   i t s   de s i gn.   Cu rr e nt   de s i g n   a l l o w s   m i l l i o n   t o   b i l l i o n s   o f   t r a n s i s t o r   t o   b e   e m be dde i n   t o   a   s i n gl e   o n   c hi (S O C) .     T h e   e vo l ut i o na r y   gr o w t h   o f   t h i s   ha s   l e t o   m a n y   r o ut i n g   c ha l l e n ge s   s uc h   a s   po w e r ,   p r o pa ga t i o de l a y ,   b uffe r   i n s e r t i o n   a nd  t i m i ng  c o n s t ra i nt .   T h e   r e c t i l i n e a r   S t e i n e r   m i n i m a l   t r e e   (R S M T pr o b l e m   h a s   b e e n   a do pt e b y   v a r i o us   r e s e a r c h e r s   a n d   h a s   b e e n   a do pt e t o   s o l v e   t h e   f un da m e nt a l   p r o b l e m s   i n   t h e   f i e l ds   o f   V L S I     (v e r y   l a r ge - s c a l e   i n t e g ra t e c i r c ui t de s i g n.   T h e   R S M T   pl a y   a   s i g n i f i c a n t   r o l e   i n   de s i g n i ng  v e r y   l a rge - s c a l e   i n t e g r a t e c i r c ui t .     T h e   r e c t i l i n e a r   S t e i n e r   m i n i m a l   t r e e   ha s   b e e n   us e t o   s o l v e   a n c o nn e c t   a   s e t   o pi n s   i n   r o ut i n s t a ge   a n i t   i s   a l s o   us e fo r   c o m p ut i ng  t h e   de l a y   i n   t h e   r o ut i n p a t h ,   o v e r a l l   w i r e   l e n gt h   a n t i m e   c o n s t ra i nt   i n   t h e   pl a c e m e nt   s t a ge .   H ow e ve r   t h e   R S M T   c o n s t r uc t i o n   i s   s a i d   t o   a n   N P - c o m pl e t e   de t e r m i n i s t i c   pr o b l e m   [1].   Co n s i de r i n g   t h e   p r e s e nt   de s i g o f   V L S t h e r e   e xi s t   m a n y   ob s t a c l e s   s uc h   a s   IP   b l o c ks ,   M a c r o - c e l l s   a nd  p r e - r o ut e n e t s .   S o   t h e r e   e xi s t s   a   ha r de r   r e s e a r c c h a l l e n ge   i V L S de s i g n   i p r e s e n c e   o f   o bs t a c l e .     T h e r e f o r e   t r a n s m i t t i ng  o v e r   t h e   b l o c ka ge   i s   a   p r o b a b l e   s o l ut i o n   b ut   po s i t i o n i n g   t h e   b uf fe r   o n   t o o ob s t a c l e   i s   n o t   po s s i b l e .   In   t h e   p r e s e n c e   o f   b l o c ka ge   t h e   R S M T   p r o b l e m   i s   c o n s i de r e t o   b e   m o r e   c h a l l e n g i n Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       O bs t ac l e   aw ar e   de l a y   o pt i m i z e d   r e c t i l i ne ar   s t e i ne r   m i n i m um   t r e e   r out i ng   ( Shy am al G )   641   a n p r o b l e m a t i c a l .   T h e   i s s ue   pe r t a i ni n t o   t r a n s m i s s i o n   o f   n e t   i p r e s e n c e   o f   o bs t a c l e   ha s   b e e n   w i de   a n   a ppl i c a t i o n   de s i g n   c ha l l e n ge s   i n   f i e l of   V L S a ut o m a t i o n .   T h e   m a j o r   go a l   o t h e s e   de s i gn s   i s   t o   r e duc e   t h e   r o ut i ng  l e ngt h   a nd  r e s o ur c e s   t o   c o nn e c t   n e t s .   T h e   i nt e r c o nn e c t i o n   de l a y   i s   pr e v a i l i n o v e r   l o gi c a l   de l a y   a n t r a n s i s t o r   de l a y   due   t o   t h e   gr o w t h   o f   de e s u b m i c r o n   t e c hn o l o gi e s   [2].   T h e   s i g n a l   i n t e g r i t y   m a y   de gr a de   due   t o   h i g h   i nt e r c o nn e c t e r e s i s t a n c e   w h e n   c o n s i de r i ng  l o n ge r   c o nn e c t i o n .   T o   s o l v e   t h e   s i g n a l   i nt e g r i t y   pr o b l e m   t h e   b u ff e r   c a n   b e   pl a c e d,   w h i c h   b r e a ks   a   w i r e   i n   t o   s m a l l e r   c h u nks .   A n   i m po r t a n t   t hi n t o   b e   n o t e i s   t h a t   t h e   b u f fe r s   c a nn o t   b e   po s i t i o n e o n   t o of   ob s t a c l e .   T h o ugh   t ra n s m i s s i o n   o v e r   t h e   b l o c ka ge   i s   po s s i b l e ,   t h e   de s i gn   s h o ul b e   a w a r e   of   s i gn a l   i nt e gri t y   i s s ue   fo r   l o n ge r   w i r e s   o n   t o b l o c ka ge   t h a t   m a y   be   pr o b l e m a t i c   i n   po s t   t r a n s m i s s i o n   e l e c t r i c a l   f i xups .   T h e   o n e   po s s i b l e   m e t h o t o   a ddr e s s   t h i s   i s   t o   b ui l a n   a v o i di n r e c t i l i n e a r   S t e i n e m i n i m u m   t r e e   (O A R S M T ).     R S M T   c o n s t r uc t i o n   a v o i di ng  t h e   o bs t a c l e s   i s   s a i t o   be   O A - R S M T   (O bs t a c l e   A vo i da n c e - R S M T pr o b l e m .   T h e   O A - R S M T   h a s   b e e n   w i de l y   a do pt e by   v a r i o u s   e xi s t i ng  r e s e a r c h e r   i n   r e c e n t   t i m e s   [3 - 6].   I n   [5]  a n [6]  t h e   p r e s e nt e a   m o de l   t h a t   a dd r e s s   t h e   i s s ue   pe r t a i ni n t o   r e c t a n gu l a r   o b s t a c l e s .   T o   ove r c o m e   i n   [4]  pr e s e nt e a   t e c hni que   t o   a dd r e s s   o b s t a c l e s   w i t h o ut   di v i d i n r e c t i l i n e a r   o b s t a c l e s   i n t o   r e c t a n gl e   na t u r e .     T h e   O A - R S M T   [7 ,   8]   a p p r o a c h   c a p r o v i de   a   f e a s i b l e   s t r a t e g y   t ha t   po s s e s s   b u ff e r   a n w i r e s   a m o n g   a dj a c e nt   b l oc ks .   H ow e v e r ,   i t   i n duc e s   ove rh e a d,   s i n c e   i t   c o n s i de r   I P   b l o c ks   a s   r o ut i ng  o bs t a c l e s   a n c o n s i de ra b l y   de gr a de s   r o ut i n g   r e s o ur c e s   of   t h e s e   IP   b l o c ks   a n d   a l s o   i n duc e s   de l a y   i n   r o ut i n g   pa t h.   In   r e a l i t y   t h e r e   e xi s t   m ul t i p l e   r o ut i n l a y e r   a nd  t h e   ob s t a c l e s   a r e   m o s t l y   pr e s e n t e i n   l o w e r   m e t a l   l a y e r   a n de v i c e   l a y e r   a s   a   r e s ul t   t h e   w i r e   c a b e   po s i t i o n e o n   t o o f   ob s t a c l e .   T h e   b uf fe r s   a r e   i n s e r t e i t o   S t e i n e r   t r e e   t o   f ur t h e r   s pl i t   i n   t o   s ub t r e e   i n   o r de r   t o   s o l v e   t i m e   a n s l e w   c o n s t r a i n t .   S i n c e   t h e   b u f fe r s   c a nn o t   be   pl a c e o n   t o of  b l o c ka ge s   a n t o   ut i l i z e   r o ut i ng  r e s o ur c e s   ove r   ob s t a c l e ,   R S M T   m us t   b e   b ui l t   o n   t o   of  b l oc ka ge s   w i t h o ut   v i o l a t i ng  t h e   s l e w   c o n s t ra i nt .   T hi s   p r o b l e m   i s   c a l l e a s   R S M T   w i t h   r e us i n r o ut i ng  r e s o ur c e s   o ve r   o b s t a c l e s   (R S M T - R E RR ).   T h e   m a i n   o b j e c t i ve   of   o ur   r e s e a r c h   i s   t o   s o l ve   t h e   R S M T - R E RR   pr o b l e m   i n   t h e   p r e s e n c e   o ob s t a c l e .   T o   i m p r o v e   t h e   o v e r a l l   c i r c ui t   pe r f o r m a n c e   w e   c o n s i de r   s l e w ,   s l a c a nd  de l a y   c o n s t ra i nt   o n   i nt e r c o nn e c t s   t h a t   a r e   t r a n s m i t t e o n   t o o f   ob s t a c l e .   T h e   s l e w   pa r a m e t e r   i s   a   c r uc i a l   f a c t o r   i n   i m p r o v i n o v e r a l l   pe r f o r m a n c e ,   s i n c e   v i o l a t i o n   o f   s l e w   a n s l a c c o n s t ra i nt   w i l l   l e a t o   de l a y   o pt i m i z a t i o n   e rr o r   a n r e s ul t   i n   de g r a d i n g   pe r f o r m a n c e .   T h e   e xi s t i n g   m o de l   ha s   c o n s i de r e s o l v i ng  s l e w   c o n s t ra i nt   i s   m o r e   i m po rt a nt   t ha n   t i m i n g   c o n s t ra i nt .   I n   [ 9]  s h o w e t h a t   m a j o r   de s i g a r e   de v e l o pe ba s e s l e w   o n   c o n s t ra i nt   a nd  t h e y   c o n s i de r e t ha t   t h e   t i m i n c o n s t r a i nt   [10 c a n   b e   s o l v e d   i f   s l e w   c o n s t r a i nt   i s   s a t i s f i e d.   T h e r e fo r e   t h e   hi g h l i g ht   of   t h e i r   t e c hn i q ue   i s   t o   a vo i r o ut i n o ve r   t h e   ob s t a c l e   t o   s o l v e   s l e w   c o n s t r a i n t .   T hi s   p r o b l e m   c a n   b e   r e pr e s e nt e a s   O A R S M T   pr o b l e m   w i t h   s l e w   c o n s t r a i n t   o n   t o of   b l oc ka ge .   H ow e v e r   t h e   s l e w   c o n s t r a i nt   de pe n ds   o n   l e n gt of   w i r e s   a n d   de l a y   a s   a   r e s ul t   t h e   t r a d i t i o na l   O A R S M T   c a nno t   b e   a ppl i c a b l e   fo r   gl o b a l   r o ut i n g   s o l ut i o s i n c e   i t   do e s   n o t   c o n s i de r   t h e   de l a y   pa ra m e t e r   a nd  r o ut i n o v e r   t h e   o bs t a c l e   c a nn o t   a s s u r e   s l e w   v i o l a t i o n   a n d   i n t e r c o nn e c t   pe r f o r m a n c e .   T h e   s o l ut i o t o   t hi s   p r o b l e m   i s   t o   r e duc e   t h e   r o ut i n g   r e s o ur c e   ov e r h e a d .     T h i s   w o r p r e s e n t   a   de l a y   o pt i m i z e r o ut i n o v e r   t h e   o b s t a c l e   b a s e R S M T   i n   o r de r   t o   a dd r e s s   t h e   r o ut i ng  r e s o ur c e   m i n i m i z a t i o a nd  s l a c c o n s t ra i nt .   T hi s   m o de l   f i r s t l y   pr e s e n t   a a c c u r a t e   de l a y   o pt i m i z a t i o i n f o r m a t i o n   a n R S T   i s   i t e r a t i v e l y   c o m put e u n t i l   a   c o n v e r ge n c e   i s   m e t   a nd  de l a y   o pt i m i z a t i o n   i s   do n e   t o   f i n t h e   de l a y   r e s i s t e pa t h .   S e c o n dl y   m o de l   s o l v e s   t h e   s l e w   a n de l a y   o pt i m i z e r   f a i l u r e   t o   i m p r o v e   t h e   s l a c pe r f o r m a n c e .   L a s t l y   t h e   de l a y   o pt i m i z e r   po s i t i o n   o f   S t e i n e r   po i n t s   i s   o pt i m i z e t o   r e duc e   o pt i m i z i n c o s t   a n d   w i r e   l e n gt h.       1. 1 .   Th e   C o n tr i b u ti o n   o Wo r k   C an   b e   C l as s i f i e d   A s   F o l l o w s   T h e   p r o po s e m e t h o do l o g y   pr e s e n t   a   de l a y   o pt i m i z e r o ut i ng  o n   t o o f   ob s t a c l e   b a s e R S M T   w h i c s o l ve s   t h e   gl o b a l   r o ut i ng  p r o b l e m   [11 a n d   r e duc e s   r o ut i ng  r e s o ur c e s .   T h e   e xi t i n E l m o r e   m o de l   i n duc e s   hi g h e r   e rr o r   f o r   s l e w   c a l c ul a t i o n .   T o   o v e r c o m e   t hi s   m o de l   i n c o r po ra t e s   s l e w   c a l c ul a t i o n   p r e s e n t e i [12 ]   i t o   o ur   m o de l .   T h e   p r o po s e m o de l   a ddr e s s e s   t h e   s l e w   c o n s t ra i nt   f o r   r o ut i n o n   t o o f   ob s t a c l e   a n i m p r o v e s   pe r f o r m a n c e   i n   t e rm   o f   w o r s t   n e g a t i v e   s l a c k.   T h e   p r o po s e a pp r o a c h   r e duc e s   t h e   n u m b e r   o f   l o gi c   ga t e s   r e qui r e f o r   c r e a t i n e f f i c i e n t   R S M T   i n   o r de r   t o   r e duc e   de l a y   a n a l s o   r e duc e s   t h e   w i r e   l e n gt h.   T h e   pa pe o r ga ni z a t i o n   i s   a s   f o l l ow s :   T h e   pr o po s e O b s t a c l e   a w a r e   de l a y   o pt i m i z e R S M T   m o de l s   a r e   p r e s e n t e i S e c t i o n   t w o .   T h e   e xpe ri m e n t a l   s t udy   c o n s i de ri n v a r i o us   b e n c hm a rk  a r e   p r e s e nt e i pe nul t i m a t e   s e c t i o n.   T h e   c o n c l udi ng  r e m a r k   a nd  f ut u r e   w o r i s   d i s c us s e i n   t h e   l a s t   s e c t i o n .       2.   LI TTER A TU R S U R V E Y   In  t h e   p a s t   s e v e r a l   a t t e m pt s   ha v e   b e e n   m a de   t o   s o l ve   R S M T - R E R R   pr o b l e m   i t h e   p r e s e n c e   of  ob s t a c l e .   I n   [1 3 p r e s e nt e a   m o de l   f o r   h i g h   pe r f o r m a n c e   s y n c h r o n o us   c h i p   de s i g n .   T h e   b uf f e r e c l oc t r e e   s y n t h e s i s   (CT S a do pt i o i n   V L S de s i g n   i s   a   c ruc i a l   f a c t o r   t o   a c hi e v e   h i g h   pe r f o r m a n c e .   T h e   m o de l   a dd r e s s e t h e   s i g n a l   po l a ri t y   c o r r e c t i o n   a nd  s l e w   c o n s t r a i n t   i n   o b s t a c l e   a w a r e   t o po l o g y   ge n e r a t i o n   (O B B ).   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   16 ,   N o .   2 N o v e m be r   2 019   :     6 4 0 - 6 5 2   642   T h e y   pr e s e nt e a   f a s t   l o o kup  b a s e s i m u l a t i o m o de l   na m e l y   N G S P ICE .   T h e   N G S P IC E   a c hi e v e s   a c c ur a t e   s l e w   a n b uffe r   de l a y   by   a do pt i ng  O B B   a l go r i t hm .   T h e   O BB   a l go r i t hm   p r o v i de s   f a s t   h e uri s t i c   b uff e r   i n s e r t i o n   a n b a l a n c e s   t h e   i n s e rt i o n   o f   b uffe r   pl a c e m e n t .   T he   m o de l   e xpl o r e t h e   gl o b a l   r o ut i n o pt i m i z a t i o n   s pa c e   a n o v e r c o m e s   t h e   n e ga t i v e   i m pa c t   o n   s ke w   due   t o   ob s t a c l e s .   T h e   o ut c o m e   s h ow s   t h e r e   m o de l   i m p r o v e s   s ke w   p e r f o r m a n c e   a n r e duc e   l a t e n c y .   H ow e ve r   t he   m o de l   di n o t   c o n s i de r   m i n i m i z i n g   w i r e   l e n gt a n p r o c e s s   v a r i a t i o n.   T h e   O A R S M T   m i n i m i z e   w i r e   l e n g t h   w i t h o ut   i nt e r s e c t i n ob s t a c l e   by   c o n n e c t i n a l l   pi n - v e rt i c e s   t hr o ugh   S t e i n e r   n o de s   us i n h o r i z o n t a l   a nd  v e r t i c a l   n o de s .   T o   de a l   w i t h   pr o c e s s   v a r i a t i o n   a n m u l t i pl e   r o ut i ng  l a y e r s ,   [1 4 c o n s i de r   O A P D - S T   (o b s t a c l e   a vo i da n c e   pr e f e r r e di r e c t i o S t e i n e r   t r e e p r o b l e m   a n d   m ul t i l a y e r   O A RS M T   pr o b l e m .   F i r s t l y   t h e y   pr e s e n t e a   m ul t i l a y e r   t h e o r e t i c a l   m o de l   f r o m   2D   a n p r e s e n t e a   t r a n s f o r m a t i o n   o m ul t i l a y e r   i n s t a n c e   t o   3D   i n s t a n c e .   T h e y   a do pt e c o m put a t i o na l   ge o m e t ri c   t e c hn i que   t o   pr e s e nt   a n   e f f i c i e n t   t e c hn i que   us i n g   e xi s t i ng  h e u r i s t i c   a l go ri t hm   t o   s o l ve   M L - O A R S M T .   T o   f urt h e r   i m p r o v e   pe r f o r m a n c e   a   n e w   S t e i n e r   n o de   s e l e c t i o n   m e t h o i s   p re s e n t e d,   w h i c h   a v o i ds   i n f e r i o r   S t e i n e r   n o de s .     T h e   o ve r a l l   o ut c o m e s   s h o w   t h e   m o de l   a c h i e v e s   g o o s pe e up.   H ow e ve r   t h e   o pt i m a l i t y   gua r a nt e e   i s   n o t   pr e s e nt e f o r   hi g h e r   p i n   n e t s   a nd  di d   n o t   c o n s i de pe r f o r m a nc e   e v a l ua t i o f o r   di f f e r e n t   u ni t   w i r e   c o s t .   In   [8 p r e s e n t e a   m o de l   t o   s o l ve   O A R S M T   pr o b l e m .   T he y   pr e s e n t e a   m o de l   fo r   S t e i n e r   n o de   s e l e c t i o n   t ha t   s o l v e s   t h e   b o t t l e n e c of  e xi s t i ng  h e u ri s t i c   a l go ri t hm .   T h e y   pr e s e n t e a n   a pp r o a c h   o f   c r e a t i n a   l i n e a r   s pa c e   r o ut i n g ra p h,   S t e i n e r   n o de   po s i t i o n i ng  w i t h   s a t i s f a c t o r y   S t e i n e r   n o de   c a n d i da t e s   a n r e s o l ve   i s s ue s   of   e xi s t i n h e uri s t i c   r o ut i n g r a p h .   T h e   m o de l   a c hi e v e s   g o o d   qua l i t y   a n s pe e dup  pe r f o r m a n c e .     T h e   m o de l   a l s o   s h ow s   i t   w o r w e l l   fo r   O A P D - S T   pr o b l e m .   H ow e v e r   t h e i r   m o de l s   di n o t   a dd r e s s   R S M T - R E RR   pr o b l e m   i n   t h e   p r e s e n c e   o f   ob s t a c l e .   A s   a   r e s ul t   t h e   r o ut i n r e s o ur c e s   a r e   w a s t e d.   T o   m a xi m i z e   t h e   r o ut i ng  r e s o ur c e   ov e r   t h e   ob s t a c l e ,   t h e   s l e w   c o n s t r a i n t   s h o ul n o t   b e   v i o l a t e w h e n   c o n s t r uc t i n R S M T   o n   t o o f   ob s t a c l e   a n t h i s   p r o b l e m   i s   c a l l e a s   R S M T - R E RR .   M a n y   a pp r o a c h e s   h a v e   b e e n   p r e s e n t e t o   s o l ve   R SMT R E RR   [1 5 ,   16 ].   T h e   R S M T - R E RR   c a n   t a ke   f ul l   b e n e f i t   o f   r o ut i n r e s o ur c e   o v e r   b l oc ka ge ,   b uff e r   r e s o ur c e s   a n d   a l s s a v e s   r o ut i ng  r e s o ur c e s   o ut s i de   t h e   b l o c ka ge .   M o r e   i m po rt a nt l y   i t   r e duc e s   t h e   de l a y ,   r o ut i n c o n ge s t i o n,   pow e r   c o n s um pt i o n   a n m i ni m i z e w i r e   l e ngt h.   A t   t h e   s a m e   n e w   c o n s t r a i n t   w i l l   f u r t h e r   i n c r e a s e s   c o m pl e xi t y   a n e s pe c i a l l y   c o nn e c t i n m u l t i - pi n   n e t s .   I n   [1 5 a do pt e l e n g t h - r e s t r i c t e S t e i n e r   m i ni m um   t r e e   (L R S M T ).   T h e   m o de l   de s i gn   i s   b a s e o n   r e a c h   a w a r e   v i s i b i l i t y   gr a p h .   T h e   v i s i b i l i t y   gr a p h   s h o ul a t   l e a s t   c o n t a i n   o n e   s h o rt e s t   p r o b a b l e   pa t h   w h i c h   i s   l e n g t h   r e s t ri c t e a m o n g   a n y   v e r t i c e s   pa i r   (o b s t a c l e   c o r n e r   po i n t s   o t e rm i na l s ) .   T h e   m o de l   c o n s i s t s   of   t w ph a s e s ,   p r e p r o c e s s i n a n po s t   pr o c e s s i n g.   I n   p r e p r o c e s s i n p h a s e ,     t h e   r u nni n t i m e   a r e   s a v e f o r   ge n e r a t i o n   a n r e duc i ng  t h e   s i z e   o f   v i s i b i l i t y   gr a p h .   H e r e   s m a l l   o b s t a c l e   w i t di a m e t e s m a l l e t h a     a r e   i g n o r e d.   T h e i po s t   p r o c e s s i n g   pha s e ,   o b s t a c l e - una w a r e   S t e i n e r   t r e e   a l go ri t hm s   [1 7 a r e   a do pt e t o   r e c o n n e c t   pi n s   t o   i m p r o v e   qua l i t y .   I n   [1 5 t h e   b l o c k e S t e i n e r   n o de s   a r e   l i m i t e i n   r e a c a w a r e   v i s i b i l i t y   gr a p t o   a s s u r e   f e a s i b l e   o ut c o m e   f o r   a l l   s o l ut i o n.   T h e   o ut c o m e   of   c o n n e c t e e l e m e nt   t h a t   a r e   c o i n c i de s   by   t h e   b l oc ka ge s   of   t h e   o ut c o m e s   a r e   a l l   pa t h s   ra t h e r   t ha n   S t e i n e r   g r a p h s   w h i c h   c o n s i s t s   of  n u m e r o us   S t e i n e r   n o de s .   H ow e ve r   t h e   s i m p l i f i e L R S M T   pr o b l e m   i n c r e a s e s   t h e   w i r e   l e n g t h   a n de g r a de s   w i r i n g   pe r f o r m a n c e .     A n   e f f i c i e n t   m o de l   t o   s o l v e   R S M T - R E RR   i s   pr e s e n t e i n   [1 6],   t h e   m o de l   a do pt e [1 8 f o r   s l e w   r a t e   c a l c ul a t i o n.   T hi s   m o de l   i s   c a l l e a s   O A R S M T _S (O A R S M T   p r o b l e m   w i t h   s l e w   c o n s t ra i nt s   o ve r   o b s t a c l e s ).   In  [16]   p r e s e nt e a o pt i m a l   s o l ut i o n   t o   de t e rm i n e   O A R S M T _S b y   e xt e n di n H a n a g ri d .   T h e y   fo r m u l a t e t h a t   O A R S M T _S c a n   b e   di v i de i n t o   a   s e t   e xt e r na l   a nd  i n t e rna l   t r e e s .   T h e   m o de l   de s i gn   i s   c o m po s e d   of  t w s t a ge s .   I n   f i r s t   s t a ge ,   t h e   m o de l   c o m put e s   a   c a n di d a t e   s e t   o e xt e r na l   a n i nt e rna l   t r e e s .   In   s t a ge   t w o ,     i t   c h o o s e s   a n d   c o m b i n e s   a   s ub s e t   o f   t h e s e   t r e e s   t o   c o n s t ruc t   a n   i de a l   s o l ut i o us i n g   IL P   (I n t e ge r   L i n e a P r o gra m m i n g) .   T h e   m o di f i e H a n a n   g r i ds   c o n s i s t   o f   e s c a pi ng  gra p h   a n H a n a n   g ri ds .   E xt e n d i n H a n a n   g ri d   m a y   n o t   s o l ve   L R S M T   pr ob l e m .   T h e r e f o r e   t h e i r   m o de l   i s   n o t   s ui t a b l e   fo r   ra pi p r o c e s s i n i n   p h y s i c a l   de s i gn   b e c a us e   of   t h e   c o n s i de ra b l e   IL P   p r o b l e m .   E xt e n s i v e   r e s e a r c s u r v e y   c a r ri e o ut   s h o w s   t h a t   t h e r e   i s   a   n e e t o   de v e l o a   m o de l   t ha t   m i n i m i z e   w i r e   l e n gt h   a nd  r e duc e   s l e w   ov e r h e a d .   It   i s   s e e n   t ha t   m o s t   of   t h e   a ppr o a c h e s   h a v e   a do pt e O A R S M T   w h i c i n duc e s   w a s t a ge s   of   r o ut i ng  r e s o ur c e .   Ro ut i n o v e r   t h e   b l oc ka ge   i s   a n   e f f i c i e n t   m e t h o t o   ut i l i z e   r e s o ur c e   e ff i c i e n t l y .   H ow e ve r   t h e   e xi s t i ng  m o de l   pr e s e n t e s o   f a r   i s   n o t   e ff i c i e n t   i n   a dd r e s s i n s e w   c o n s t r a i n t   a nd  m i ni m i z i n de l a y .   T hi s   w o r o ve r c o m e   t h e s e   c h a l l e n ge s   a n d   p r e s e n t s   a n   e f f i c i e n t   m o de l   n a m e l y   O b s t a c l e   A w a r e   D e l a y   O pt i m i z e R e c t i l i n e a r   S t e i n e r   M i n i m u m   T r e e   (O A D O R S M T Ro ut i n t o   a dd r e s s   t h e   de l a y ,   s l e w   c o n s t ra i nt   a n r e duc e   t h e   r o ut i ng  r e s o ur c e s .   In   n e xt   s e c t i o n   t h e   pr o po s e O A D O RS M T   m o de l   i s   pr e s e nt e d.           Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       O bs t ac l e   aw ar e   de l a y   o pt i m i z e d   r e c t i l i ne ar   s t e i ne r   m i n i m um   t r e e   r out i ng   ( Shy am al G )   643   3.   P R O P O S ED   O B S TA C LE  A WA R D E LA Y   O P TI M I ZE D   R S M T   M O D EL   H e r e   w e   pr e s e n t   o b s t a c l e   a w a r e   de l a y   o pt i m i z e r e c t i l i n e a r   s e i n e r   t r e e   c o n s t r uc t i o n   a n d   r o ut i n g .     T h e   m o de l   c o n s i s t s   o f   fo l l ow i n p ha s e s ,   D e l a y   O pt i m i z a t i o n   p h a s e ,   R o ut i n O pt i m i z a t i o n   p ha s e   a nd  M i n i m i z a t i o o f   pa t c o n s t r uc t i o n   c o m put i n g   c o s t   pha s e .     F i r s t l y   w e   m o de l   de l a y   o pt i m i z a t i o n ,   h e r e   a   de l a y   o pt i m i z e t o po l o g y   i s   ge n e ra t e t o   o b t a i i n f l ux   t i m e   a n de l a y   r e s i s t e pa t h   a t   e a c h   n o de .   T h e n   b a s e o n   t h e   i n f o r m a t i o n   ob t a i n e i n   de l a y   o pt i m i z a t i o pha s e ,   a   de l a y   o pt i m i z e d   r e c t i l i n e a S t e i n e r   t r e e   i s   c o n s t r uc t e d.     In   r o ut i n p ha s e ,   r o ut i n o n   t o o f   ob s t a c l e   i s   c o n s i de r e i n   o u r   w o r a s   s h o w n   i n   F i gu r e   1   r a t h e r   t h a n   r o ut i ng  a v o i di n o b s t a c l e   a s   s h ow n   i n   F i gu r e   2 .   T he   r o ut i n o n   t o o ob s t a c l e   w i l l   l e a t o   s l e w   c o n s t ra i nt   e rr o due   t o   de l a y   o pt i m i z e r   f a i l u r e   c o n s t r a i nt .   T h e n   de l a y   o pt i m i z a t i o i s   do n e   o n   t h e   r e c o n s t r uc t e t o po l o g y ,   i n   o r de r   t o   a dd r e s s   t h e   s l e w   c o n s t ra i nt   a nd  i m p r o v e   s l a c pe r f o rm a n c e .   L a s t l y   t h e   de l a y   o pt i m i z e t o po l o g y   s t r uc t u r e   i s   o pt i m i z e b a s e o n   de l a y   o pt i m i z e pa ra m e t e r   a n f urt h e r   d e l a y   o pt i m i z a t i o i s   do n e   t o   o b t a i t h e   b e s t   pa t a n d   m i n i m i z e   c o s t .   T a b l e   s h o w n   t h e   n o t a t i o a n d   s y m bo l   us e d.           F i g u r e   1.   P r o po s e O n   t o o f   O bs t a c l e   b a s e R e c t i l i n e a S t e i n e r   M i n i m u m   T r e e   Co n s t ruc t i o   w h i c c o n s i s t   o f   t w o   s i n k       a n d       a n d   o n e   r o o t   s i n k       F i g u r e   2.   E xi s t i n g   O b s t a c l e   A v o i da n c e   b a s e R e c t i l i n e a S t e i n e r   M i n i m u m   T r e e   Co n s t ruc t i o   w h i c c o n s i s t   o f   t w o   s i n k       a n d       a n d   o n e   r o o t   s i n k       T a b l e   1 .   N o t a t i o a nd  S y m bo l   us e d   S y m b o l   U s e d   A b b r e v i a t i o n       S e t   o f   p i n s   i n   a   t ra n s m i s s i o n   a r e a       S e t   o f   g ra p h       A   s e t   o n o n - i n t e r s e c t i n g   r e c t i l i n e a a r e a       N o n - i n t e r s e c t i n g   r e c t i l i n e a r   b l o c k       T ra n s m i s s i o n   a r e a       Co l l e c t i o n   o f   s i n k       S e t   o f   h o r i z o n t a l   a n d   v e r t i c a l   e d g e       S e t   o f   n o d e s       D i s t i n c t i v e   ro u t e       S t e i n e r   n o d e s       N o d e       W i r e   c a p a c i t a n c e   s i z e   o n   a   p a rt i c u l a r   l a y e r         E d g e   s i z e   o f             W i r e   s i z e   o f   c a p a c i t a n c e   u n i t   o n   a   p a rt i c u l a l a y e r   fo e d g e             W i r e   s i z e   o f   r e s i s t a n c e   u n i t   o n   a   p a rt i c u l a l a y e r   fo e d g e             D e l a y   d u e   t o   p r e s e n c e   o b u ffe r s         S e l e c t e d   d e v i c e   re s i s t a n c e   o u t c o m e             S t e i n e r   p o i n t   o p i n                           i     i s   a   ro o t   o r   d e l a y   o p t i m i z e d   n o d e   e l s e       if       i s   a   n o t   a   ro o t   o r   d e l a y   o p t i m i z e d   n o d e         S e l e c t e d   d e v i c e   c a p a c i t a n c e   o u t c o m e               o v e ra l l   c a p a c i t a n c e   o t h e   s u b - t r e e   t ra n s m i t t e d   a t   p i n   t o   t h e   c l o s e s t   s i n k   w h i c h   i n c l u d e s   d e l a y   o p t i m i z e d   i n p u t   c a p a c i t a n c e                 P ro p a g a t i o n   t i m e   f r o m   p i n       t o           T h e   o ve r a l l   f l ow   of   pr o pos e Ro ut i n O n   t o o f   O b s t a c l e   ba s e R e c t i l i n e a r   S t e i n e r   M i n i m u m   T r e e   C o n s t r uc t i o n   i s   p r e s e nt e i n   F i gu r e   3 .     Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   16 ,   N o .   2 N o v e m be r   2 019   :     6 4 0 - 6 5 2   644       F i g u r e   3 .   D e l a y   o pt i m i z e r o ut i n o n - t o o f   o bs t a c l e   m o de l       L e t   c o n s i de a   s e t   o f   pi n s   o f   n e t     {                     }   i a   t ra n s m i s s i o a r e a   w i t         pi n s ,     w h e r e       t h e   di s t i n c t i v e   r o o t   i s   a nd  o t h e r s   a r e   t h e   s i n n o de s .   L e t   c o n s i de r   a   c o l l e c t i o n   o f       {                     }   n o n - i nt e r s e c t i n g   r e c t i l i n e a r   b l o c i a   t ra n s m i s s i o n   a r e a     .   L e t   fo r   a l l               i s   n o t   i t h e   r e gi o n   po s s e s s e by     .   T h e   b l o c ka ge       i s   c o n s i de r e f o r   l a rge l y   po pul a t e a n d   c o m pl e c e l l s .     T h e   p r o po s e a ppr o a c h   p r o duc e s   a   de l a y   o pt i m i z e g r a p               t o   a s s oc i a t e   a l l   pi n s   i n       w h e r e       c o l l e c t i o n   o f   ve r t i c a l   a n d   h o r i z o n t a l   e dge s   a n d       i s   t h e   c o l l e c t i o n   o f   s i n ks .   T h e   s e t   o f   gra p h       {                         }   i s   c o n s i de r e t o   b e   i n s i de   t h e   b l o c i f       o ve r l a p   w i t h   b l o c k     .   T h e   g r a p     i s   r e pr e s e nt e a s   i n l i n e   g r a p a n d   t h e   o ut l i n e   b l o c gra p     i s   de f i n e d   a s     .   T h e   de l a y   o pt i m i z e d   g ra p                   i s   c o m put e us i ng      o n c e   t h e   i n s e r t i o n   o f   n o de s       t h a t   a r e   r e l a t e t o   de l a y   o pt i m i z e r   s e l e c t e f r o m   d e l a y   o pt i m i z e t a b l e   a n d             .   T h e r e   e xi s t   a   d i s t i n c t i v e   r o ut e     (           )   f r o m         t o         i n   S t e i n e g ra p a nd  pr e s e n c e   o f   de l a y   o pt i m i z e a l o n g   t h e   t r a n s m i s s i o n   r o o t   w i l l   f urt h e s pl i t   t h e   p a t i t o   s ub   l e ve l   g r a p h.     E a c h   s pl i t   c o n s i s t   o f   S t e i n e r   n o de s ,   a   c o l l e c t i o n   o f   s l a c o p t i m i z e s i nks   a nd  a l s o   e dge s   c o n n e c t i n g   S t e i n e r   n o de s   a n d   s l a c o pt i m i z e s i n ks .     T h e   c um ul a t i v e   de l a y   of   t h e   p r o pa ga t i ng  pa t h   c a n   b e   c o m p ut e by   s um m i ng  up  t h e   de l a y   a t   e a c l e v e l .   T h e   E l m o r e   t e c hni que   i s   b e e n   a do pt e by   v a r i o us   e xi s t i n g   r e s e a r c h e t o   m e a s u r e   de l a y .   T h i s   w o r a l s o   a do pt s   t h e   E l m o r e   m o de l   t o   c o m put e   de l a y   f o r   w i r e s   a n d   fo r   de l a y   o pt i m i z e r   (a dd i n ga t e s w e   a do pt   a   s w i t c h   l e v e l   de l a y   e s t i m a t i o n   m o de l .   T h e   t o t a l   de l a y   a t   e a c l e v e l   of   t h e   p r o pa ga t i n g   r o ut e   i s   f o r m u l a t e a s   fo l l ow s .                                   (                         )                                             (         )         (1)     T h e   c um ul a t i v e   pr o pa ga t i n de l a y   i s   ob t a i n e by   s um m i ng  e a c h   s ub l e v e l   of  pr o pa ga t i n p a t h   i s   c o m put e a s   f o l l ow s       (           )                                 (           )   (2)     T h e   w o r s t   n e ga t i v e   s l a c k     i s   c o m put e a s   f o l l o w s   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       O bs t ac l e   aw ar e   de l a y   o pt i m i z e d   r e c t i l i ne ar   s t e i ne r   m i n i m um   t r e e   r out i ng   ( Shy am al G )   645                   {       }   (3)     w h e r e       i s   t h e   w o r s t   s l a c w h i c i s   c o m put e d   a s   f o l l ow s               {           (     ) }                          (4)     w h e r e             (     )   i s   t h e   s l a c o f   n o de         w h i c i s   c o m put e a s   f o l l ow s               (     )     (     )     (           )   (5)     w h e r e       i s   t h e   de l a y   o pt i m i z e i n f l ux  t i m e .   T h e   s l e w   r a t e   i s   c o m put e d   us i n g   [18 w hi c i s   a s   f o l l ow s                 (                                              )   (6)     w h e r e                 i s   t h e   s l e w   a t   a n y   n o de                        i s   t h e   o ut put   s l e w   a t   n o de            a nd                               i s   t h e   s t e s l e w   f r o m          t o          .   T h e   s t e p   s l e w   i s   c o m put e a s   f o l l ow s                                                                        (7)     3. 1 .   D e l ay   O p t i m i z e d   T r e e   C r e at i o n :   T h e   t r e e   c r e a t i o n   o f   R S T   m i g ht   r e qu i r e   r e qui r e d   i n f l ux   t i m e   o n   i n t e rna l   n o de s   duri n g   p h a s e   o f   t r e e   c r e a t i o n   a nd  r e qu i r e s   e s t i m a t i o n   o f   i n f l ux  t i m e   o n   e a c h   s i n k .   T h e   f l ow   di a g r a m   o f   d e l a y   o pt i m i z e t r e e   c r e a t i o n   i s   s h o w n   b e l ow   i F i g u r e   4.           F i g u r e   4 .   F l o w   di a g ra m   o f   de l a y   o pt i m i z e t r e e   c r e a t i o n   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   16 ,   N o .   2 N o v e m be r   2 019   :     6 4 0 - 6 5 2   646   F i r s t   c r e a t e   a n   i n i t i a l   t r e e   us i n g   de l a y   o pt i m i z e d   R S T   m o de l .   T h e n   i de l a y   o pt i m i z a t i o n   p ha s e ,   a n a l y s e   t i m i ng  a nd  de l a y   o pt i m i z e   t h e   R S T .   T h e n   t h e   t o po l o g y   a n de l a y   o pt i m i z e pa ra m   i s   s a v e i f   i t   i s   i de a l   s o   f a r .   W e   f ur t h e r   c o m put e   t h e   a c t u a l   i n f l ux  t i m e   b a s e o n   de l a y   o pt i m i z e t r e e .   T hi s   i s   do n e   t o   ob t a i n   f e e d b a c i n f o r m a t i o n   (de l a y   o pt i m i z e t i m e f o r   t o po l o g y   ge n e ra t i o n   m e t h o do l o g y .   In   n e xt   s t e p,   a l l   a c t ua l   de l a y   r e s i s t e t r u nk  a nd  s i n a r e   r e c o m put e us i n de l a y   o pt i m i z e pa ra m .   I n   R S T   m o de l   de l a y   r e s i s t e d   t r u n i s   r e - po s i t i o n e a n d   o t h e 2 - pi n e t s   a r e   r i p pe a p a r t   a nd  r o ut i n g   pa t h   i s   c ha n ge a pp l y i n m a z e   r o ut i n g   a f t e r   de l a y   o pt i m i z e de l a y   r e s i s t e t r u n k   g r o w t h .   L a s t l y   i t   p r o duc e s   a n o t h e r   R S T   a f t e r   a ppl i c a t i o of  r e di r e c t i o n   a n r e c t i l i n e a ri z a t i o n.   T h e   p r o c e s s   i s   c o n t i n ue d   u n t i l   t i m e   l i m i t   i s   r e a c h e o r   t h e   t r e e   t o po l o g y   c o n v e r ge s .   In   F i gu r e   5 ,   a n s h o w s   t h a t   t h e   t i m i n g   a n d   t o po l o g y   c on v e r ge s   du r i ng  e a c h   s t e ps .   I F i gu r e   5 ,   in i t i a l   s t r uc t u r e   d i r e c t l y   c o nn e c t s   S i n     t o   r o o t   a s   t h e   r e qu i r e i n f l ux   t i m e   o f       i s   v e r y   l e s s .   I n e xt   s t e t h e   t o po l o g y   c r e a t i o m o de l   de c i de s   t o   j o i     t o   t h e   t r u n k   a s   s h o w i F i gu r e   6,   s i n c e   i F i g u r e   5   t h e   de l a y   t o       i s   v e r y   l e s s ,   w h i c h   c a s a t i s fy   t h e   r e qui r e i n f l ux   t i m e .   A s   a   r e s ul t   l a t e   b ra n c h   c a n   b e   pe rm i t t e d.     A l l o w i n a ddi t i o o f   l a t e   b r a n c h   w i l l   i n c u r   m o r e   de l a y   o n   s i n     a n l e a ds   t o   t o po l o g y   c o n v e r ge n c e   a n d   r e s ul t   i s t a l i ke   R S M T   s t r uc t u r e .           F i g u r e   5 .   I ni t i a l   de l a y   r e s i s t e t r e e   c o n s t r uc t i o w h i c c o n s i s t   o f   fo ur   s i n k           a n d       a n d   o n e   r o o t           F i g u r e   6 R e c o n s t r uc t i o o f   de l a y   o pt i m i z e d   T r e e   w h i c c o n s i s t   o f   fo ur   s i n k           a n d       a n d   o n e   r o o t               F i g u r e   7 .   T h e   de l a y   o pt i m i z e t o po l o g y   c o n v e r ge n c e s   w h i c h   c o n s i s t   o f   fo ur   s i n k     ,             a n d     a nd  o n e   r o o t           3. 2 .   D e l ay   O p t i m i z e r   A w ar e   R o u ti n o n   To p   o O b s tac l e   F i r s t l y ,   t h e   i n i t i a l   t r e e   i s   c r e a t e w i t h o ut   c o n s i de r i ng  a n y   bl o c ka ge s .   T h e   i ni t i a l   t r e e   m i g h t   i nduc e   s l e w   c o n s t r a i n t   e v e n   a f t e r   i n s e r t i o n   o f   de l a y   o pt i m i z e r   a n t h e   t r e e   c o ul ov e r l a o v e r   t h e   b l o c ka ge .   T h e r e f o r e   t o   a ddr e s s   i t   r o ut i n o v e r   t h e   b l o c ka ge   i n s i de   t h e   t r e e   i s   c o n s i de r e d .   T h e   o bj e c t i v e   of   o ur   m o de l   i s   t o   r e duc e   de l a y   a n d   w i r e   l e n g t h .   T h e r e f o r e   o ur   o b j e c t i v e   f un c t i o n   i n t e g ra t e s   s l a c a n d   c ri t i c a l i t y .     T h e   o b j e c t i ve   f un c t i o n   m i ni m i z e s   de l a y   of   de l a y   r e s i s t e pa t a nd  w i r e   l e n gt i n   n o n - de l a y   r e s i s t e pa t h.   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       O bs t ac l e   aw ar e   de l a y   o pt i m i z e d   r e c t i l i ne ar   s t e i ne r   m i n i m um   t r e e   r out i ng   ( Shy am al G )   647   F o r   r o ut i n g   o v e r   t h e   b l o c ka ge   i n s i de   t h e   t r e e   c o n s t r uc t i o n   u n de s l a c a n d   s l e w   c o n s t ra i nt ,                 w e   f i r s t   n e e t o   i de nt i f y   t h e   pr o b a b l e   po i n t .   T h e   s e l e c t i o n   of   po i n t   i s   c o n s i de r e t o   b e   a n   o pt i m i z a t i o pr o b l e m   a s   f o l l ow s                    (     (       )         ) |       |       |     |         (8)     S uc h   t h a t   (                           |       |       |     |       )     (                           |       |       |     |       )                          (9)                              {                 |     | } |       |         (10)     w h e r e             (       )   i s   t h e   p r o duc t   o f   t o t a l   do w n s t r e a m   c a p a c i t a n c e   a n d   r e s i s t a n c e ,   w hi c c o m pu t e s   c um ul a t i v e   de l a y   of   a l l   s i n k   i do w n s t r e a m   f r o m                  i s   t h e   c um ul a t i v e   a b s o l ut e   pa ra m   o f   n e ga t i v e   s l a c ks   of   s i n ks   do w n s t r e a m   f r o m               |                   |       i s   t h e   de l a y   r e s i s t e pa t h s   w e i ght s   b e l ow         .   T h e   w e i ght       i de n t i f i e s   t h e   s o l ut i o w i t h   l e a s t   c o m put e d   w i r e   l e n g t h   pe n a l t y   o n   n o n - de l a y   r e s i s t e p a t h.   T o   e l ude   a f fe c t i n g   de l a y   r e s i s t e d   p a t h,   t h e       i s   s e t   v e r y   l ow   w i t h   re s pe c t   t o       (       )     .   T h e   o bj e c t i v e   f un c t i o m i ni m i z e   c h a nge s   o n   de l a y   r e s i s t e p a t h,   t h us   s a t i s fy   s l e w   c o n s t ra i nt .   O u r   m o de l   c o n s i de r s   de l a y   o n   de l a y   r e s i s t e p a t a n d   w i r e   l e n g t o n o n - de l a y   r e s i s t e p a t h.   T h e   e xa m pl e   o f   t h i s   i s   s h o w n   i F i g u r e   8 ,   9   a n 10.             F i g u r e   8 .   I ni t i a l   t r e e   c r e a t i o us i ng  de l a y   o pt i m i z e R S T   w i t s l e w   v i o l a t i o n   w hi c h   c o n s i s t   o f   t hr e e   s i nk         a n d       a n d   o n e   r o o t           F i g u r e   9 .   T r e e   c r e a t i o us i ng  de l a y   o pt i m i z e d   R S T   t h a t   f i xe s   s l e w   v i o l a t i o n   w i t m i ni m u m   w i r e   l e n g t pe n a l t y   w h i c c o n s i s t   o f   t hr e e   s i n k         a n d       a n d   o n e   r o o t               F i g u r e   10 .   T r e e   c r e a t i o us i ng  de l a y   o pt i m i z e d   R S T   t ha t   f i xe s   s l e w   v i o l a t i o a n d   o pt i m i z e   de l a y   o n   de l a y   r e s i s t e p a t w hi c c o n s i s t   o f   t hr e e   s i nk         a n d       a n d   o n e   r o o t           Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   16 ,   N o .   2 N o v e m be r   2 019   :     6 4 0 - 6 5 2   648   F i g u r e   10  i s   p r e f e rr e t ha n   F i g u r e   9,   s i n c e   t o   s a t i s fy   s l e w   c on s t ra i nt ,   F i g u r e   r e s e r v e s   t h e   t i m i n g   o de l a y   r e s i s t e s i n by   m ov i n t h e   e s c a pi n po i n t s   o n   n o n - de l a y   r e s i s t e pa t h .   T h e   c o n s t r a i n t   ( 9 a n ( 10 ),   l i m i t s   t h e   c um u l a t i v e   s l e w   r e duc t i o n   o         ha s   t o   b e   i po s i t i o n   t o   pul l                 do w n   b e l ow   n e c e s s i t i e s   a n l i m i t s   o n l y   o n e   po s i t i o s e l e c t e f o r   e a c e s c a pi n g   po i nt   r e s p e c t i v e l y .     3. 3 .   M i n i m i z ati o n   o P ath   C o n s tr u c ti o n   C om p u ti n C o s t   O ur   m o de l   de s i gn   pe rm i t s   o pt i m i z i n t o po l o g y   t o   r e duc e   d e l a y   o n   de l a y   r e s i s t e pa t by   e xt e n di ng   w i r e   w i t h   s l e w   b o un ds .   A s   t h e   s l e w   bo un o c c ur s   b e l ow   S t e i n e r   n o de ,   w e   e xt r a c t   t h e   n o r m a l i z e de s i g n   w i t t w o   de l a y   o pt i m i z e a nd   o n e   S t e i n e n o de   a s   s h o w n   i F i g u re   11.   D e l a y   o pt i m i z e       a n d       s t a y   ri g ht   b e l o w   fo r   s hi e l di n g   a n d   a b o ve   t h e   S t e i n e n o de s   r e s pe c t i v e l y .   W e   no t e   t ha t   t h e   p ha s e   d ri v e n   by         as             ,   p h a s e   dri v e n   b y         a s               a nd   t ha t   a b o ve         as             .   T h e   e l o n ga t i o n   a m o un t   o f       t o   us e   s l e w   bo un c a b e   c o m put e d,   due   t o   a v a i l a b i l i t y   o f   s l e w   bo un i           .   T h e   di s t a n c e   a m o n g         a n d       i s   de n o t e d   as                           F i g u r e   11 .   S h o w s   t h e   pa t t e rn   o f   s l e w   m a r gi n       L e t   c o n s i de a a s s u m pt i o t ha t                       a n i n pu t   c a pa c i t a n c e   o f   de l a y   o pt i m i z e r   i s   w i t hi bo un o f   w i r e   c a pa c i t a n c e ,   a l l   s l e w   c o n s t r a i nt   c a b e   f ul f i l l e by   pl a c i n t h e   S t e i n e r   n o de   t ow a r t h e   po s i t i o of         a n d         up  t o   t h e   po s i o t i o n   r i g h t   b e n e a t t h e   n e w   po s i t i o n   o f   S t e i n e r   n o de .   T h e   F i g u r e   1 s h o w s   a s s um pt i o o f   n e gl i gi b l e   i nput   c a p a c i t a n c e   o f   de l a y   o pt i m i z e r.   T h e   s l e w   of               i s   w i t hi n   b o un d   o                     a n d   t h e   l o a d   a n d   s l e w   o f               a r e   n o t   c ha n ge d .           F i g u r e   12 .   O p t i m i z a t i o o f   de l a y   o pt i m i z e r   c o n s i de ri n i n pu t   c a pa c i t a n c e   o f   de l a y   o pt i m i z e r   n e gl i gi b l e       L e t   c o n s i de a n o t h e r   a s s um p t i o t ha t                                 a nd  i n pu t   c a p a c i t a n c e   o f   de l a y   o pt i m i z e r   i s   n o t   w i t h i n   b o un o w i r e   c a pa c i t a n c e ,   a l l   s l e w   c o n s t r a i n e c a n   b e   f ul f i l l e by   pl a c i ng  t h e   S t e i n e n o de   t o             a b ov e         a n d   m o v i n g   de l a y   o pt i m i z e r         up   t o   t h e   po s i t i o n   r i g h t   b e n e a t t h e   n e w   po s i t i o n   of  S t e i n e po i n t   (w h e r e         i s   t h e   w i r e   s e gm e nt   a b o ve         i n i t   c a p a c i t a n c e   a n d         i s   t h e   de l a y   o pt i m i z e i n pu t   c a pa c i t a n c e ).   T h e   F i gu r e   13   s h o w s   t h e   de l a y   o pt i m i z e t o po l o g y   a f t e r   r e l o c a t i n t h e   S t e i n e r   n o de s       t o             a b ov e         a nd  de l a y   o pt i m i z e r   r e l o c a t i o n .   T h e   do w n s t r e a m   c a pa c i t a n c e   f o r               i s   r e duc e i a c c o r d a n c e   t o                   due   o   w i r e   l e n g t a b o ve         i s   r e duc e by           .   T h e   de l a y   o pt i m i z e       i s   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       O bs t ac l e   aw ar e   de l a y   o pt i m i z e d   r e c t i l i ne ar   s t e i ne r   m i n i m um   t r e e   r out i ng   ( Shy am al G )   649   a t t a c h e t o               du ri n pa t c o n s t r uc t i o n   o pt i m i z a t i o n ,   t ha t   i n c l u de s         i n t o   do w n s t r e a m   c a pa c i t a n c e .   A s   a   r e s ul t   t h e   c u m ul a t e do w n s t r e a m   c a p a c i t a n c e   r e m a i n s   s a m e   f o r               a nd  t h e   qua nt i t y   of   d ow n s t r e a m   c a pa c i t a n c e   o f               s u r ge s   b y                   a s   w i r e              i s   a dde b e n e a t h     .   T h e   i n put   c a pa c i t a n c e   of        i s   de t a c h e f r o m               w h e r e   do w n s t r e a m   c a pa c i t a n c e   i s   r e de e m e by     T h e r e f o r e   t h e   o ve r a l l   dow n s t r e a m   c a pa c i t a n c e   b e n e a t h         r e m a i n s   u n c ha n ge a nd  s l e w   of               s a t i s fy   s l e w   c o n s t r a i n t .   T h e   f l o w   di a g ra m   o f   pa t c o n s t r uc t i o n   i s   s h o w n   b e l ow   i F i g u r e   14 .           F i g u r e   13 .   O p t i m i z a t i o o f   de l a y   o pt i m i z e r   c o n s i de ri n w i t ho ut   n e gl e c t i n i n pu t     c a pa c i t a n c e   o f   de l a y   o pt i m i z e r           F i g u r e   14 .   F l o w   di a g r a m   o f   p r o po s e pa t c o n s t r uc t i o n       T h e   p r o po s e a pp r o a c pe r f o r m a n c e   s t udy   i s   p r e s e nt e i n e xt   s e c t i o n.     Evaluation Warning : The document was created with Spire.PDF for Python.