I n d on e s i an   Jo u r n al   o f  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 a  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 d  M a r  18,   20 19   A c c e pt e d  M a y   20 ,   20 1 9       T hi s   w o r k  pr e s e n t s   a   m e t ho d  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 n  m o de r n  v e r y   l a r g e - s c a l e   i n t e g r a t e d  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 n  t o p  of   bl o c ka g e   i s   a   po s s i bl e   s o l u t i o n  bu t   buf f e r s   c a nno t   be   pl a c e d  o v e r   t he   o bs t a c l e .   M o de r n  V L S I   de s i g n  O A R S M T   c o ns t r uc t i o n  ha s   l o n g   w i r e   l e ng t h ,   w h i c h  r e s ul t s   i n  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 d  t o   be   c o ns i de r e d  i n  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 h  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 k  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 h  r o ut i ng   r e s o ur c e s   o v e r he a d  due   t o   buf f e r   i ns e r t i o n  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 k  p r e s e nt s   a n  O bs t a c l e   A w a r e   D e l a y   O pt i m i z e d  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 d  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 d  a p pr o a c h  o v e r   e xi s t i ng   a pp r o a c h  i n  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 d  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 d  v a r i e d  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 n  s uc h  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 r  s t e i n e r   t r e e   S l a c k  a n d  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 d  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 d  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 d  i n   t o   a   s i n gl e   o n   c hi p  (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 d  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 n  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 d  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 d  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 d  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 d  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 d  t o   s o l v e   a n d  c o nn e c t   a   s e t   o f  pi n s   i n   r o ut i n g  s t a ge   a n d  i t   i s   a l s o   us e d  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 g  p a t h ,   o v e r a l l   w i r e   l e n gt h   a n d  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 n  o f   V L S I  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 d  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 h  c h a l l e n ge   i n  V L S I  de s i g n   i n  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 p  o f  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 d  t o   b e   m o r e   c h a l l e n g i n g  Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a n  J   E l e c   E ng  &   Co m p  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 a  G )   641   a n d  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 g  t o   t r a n s m i s s i o n   o f   n e t   i n  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 d  of   V L S I  a ut o m a t i o n .   T h e   m a j o r   go a l   o f  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 g  o v e r   l o gi c a l   de l a y   a n d  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 p  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 d  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 g  t o   b e   n o t e d  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 d  o n   t o p  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 d  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 p  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 d  t o   a ddr e s s   t h i s   i s   t o   b ui l d  a n   a v o i di n g  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 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 d  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 d  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 d  [6]  t h e   p r e s e nt e d  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 g  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 d  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 g  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 n  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 d  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 d  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 g  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 d  i n   l o w e r   m e t a l   l a y e r   a n d  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 n  b e   po s i t i o n e d  o n   t o p  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 d  i n  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 d  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 d  o n   t o p  of  b l o c ka ge s   a n d  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 d  a s   R S M T   w i t h   r e us i n g  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 f  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 k  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 d  o n   t o p  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 g  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 d  s l a c k  c o n s t ra i nt   w i l l   l e a d  t o   de l a y   o pt i m i z a t i o n   e rr o r   a n d  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 d  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 d  t h a t   m a j o r   de s i g n  a r e   de v e l o pe d  ba s e d  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 d  t ha t   t h e   t i m i n g  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 d  r o ut i n g  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 d  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 p  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 h  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 n  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 g  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 n  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 k  p r e s e n t   a   de l a y   o pt i m i z e d  r o ut i n g  o v e r   t h e   o b s t a c l e   b a s e d  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 n  a nd  s l a c k  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 n  a c c u r a t e   de l a y   o pt i m i z a t i o n  i n f o r m a t i o n   a n d  R S T   i s   i t e r a t i v e l y   c o m put e d  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 d  t h e   de l a y   r e s i s t e d  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 d  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 k  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 d  t o   r e duc e   o pt i m i z i n g  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 f  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 d  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 d  r o ut i ng  o n   t o p  o f   ob s t a c l e   b a s e d  R S M T   w h i c h  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 g  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 d  i n  [12 ]   i n  t o   o ur   m o de l .   T h e   p r o po s e d  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 g  o n   t o p  o f   ob s t a c l e   a n d  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 d  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 d  f o r   c r e a t i n g  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 d  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 r  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 d  O b s t a c l e   a w a r e   de l a y   o pt i m i z e d  R S M T   m o de l s   a r e   p r e s e n t e d  i n  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 g  v a r i o us   b e n c hm a rk  a r e   p r e s e nt e d  i n  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 k  i s   d i s c us s e d  i n   t h e   l a s t   s e c t i o n .       2.   LI TTER A TU R E  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 n  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 d  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 d  c l oc k  t r e e   s y n t h e s i s   (CT S )  a do pt i o n  i n   V L S I  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 d  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 n  J   E l e c   E ng  &   Co m p  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 d  a   f a s t   l o o kup  b a s e d  s i m u l a t i o n  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 d  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 d  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 d  t h e   gl o b a l   r o ut i n g  o pt i m i z a t i o n   s pa c e   a n d  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 d  r e duc e   l a t e n c y .   H ow e ve r   t he   m o de l   di d  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 h  a n d  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 g  ob s t a c l e   by   c o n n e c t i n g  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 g  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 d  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 d  di r e c t i o n  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 d  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 d  p r e s e n t e d  a   t r a n s f o r m a t i o n   o f  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 d  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 d  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 d  s pe e d  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 d  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 r  pe r f o r m a nc e   e v a l ua t i o n  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 d  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 d  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 k  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 d  a n   a pp r o a c h   o f   c r e a t i n g  a   l i n e a r   s pa c e   r o ut i n g  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 d  r e s o l ve   i s s ue s   of   e xi s t i n g  h e uri s t i c   r o ut i n g  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 d  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 k  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 d  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 g  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 d  n o t   b e   v i o l a t e d  w h e n   c o n s t r uc t i n g  R S M T   o n   t o p  o f   ob s t a c l e   a n d  t h i s   p r o b l e m   i s   c a l l e d  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 d  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 g  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 o  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 g  c o n ge s t i o n,   pow e r   c o n s um pt i o n   a n d  m i ni m i z e d  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 d  e s pe c i a l l y   c o nn e c t i n g  m u l t i - pi n   n e t s .   I n   [1 5 ]  a do pt e d  l e n g t h - r e s t r i c t e d  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 d  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 d  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 d  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 r  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 o  ph a s e s ,   p r e p r o c e s s i n g  a n d  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 g  p h a s e ,     t h e   r u nni n g  t i m e   a r e   s a v e d  f o r   ge n e r a t i o n   a n d  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 h  di a m e t e r  s m a l l e r  t h a n      a r e   i g n o r e d.   T h e n  i n  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 d  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 d  S t e i n e r   n o de s   a r e   l i m i t e d  i 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 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 d  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 d  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 d  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 d  i n   [1 6],   t h e   m o de l   a do pt e d  [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 d  a s   O A R S M T _S C  (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 d  a n  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 C  b y   e xt e n di n g  H a n a n  g ri d .   T h e y   fo r m u l a t e d  t h a t   O A R S M T _S C  c a n   b e   di v i de d  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 o  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 f  e xt e r na l   a n d  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 n  us i n g   IL P   (I n t e ge r   L i n e a r  P r o gra m m i n g) .   T h e   m o di f i e d  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 d  H a n a n   g ri ds .   E xt e n d i n g  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 d  p r o c e s s i n g  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 h  s u r v e y   c a r ri e d  o ut   s h o w s   t h a t   t h e r e   i s   a   n e e d  t o   de v e l o p  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 d  O A R S M T   w h i c h  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 g  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 d  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 d  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 g  s e w   c o n s t r a i n t   a nd  m i ni m i z i n g  de l a y .   T hi s   w o r k  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 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 r e e   (O A D O R S M T )  Ro ut i n g  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 d  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 d  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 n  J   E l e c   E ng  &   Co m p  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 a  G )   643   3.   P R O P O S ED   O B S TA C LE  A WA R E  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 d  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 g  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 g  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 n  o f   pa t h  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 d  t o po l o g y   i s   ge n e ra t e d  t o   o b t a i n  i n f l ux   t i m e   a n d  de l a y   r e s i s t e d  pa t h   a t   e a c h   n o de .   T h e n   b a s e d  o n   t h e   i n f o r m a t i o n   ob t a i n e d  i n   de l a y   o pt i m i z a t i o n  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 r  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 g  p ha s e ,   r o ut i n g  o n   t o p  o f   ob s t a c l e   i s   c o n s i de r e d  i n   o u r   w o r k  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 g  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 g  o n   t o p  o f  ob s t a c l e   w i l l   l e a d  t o   s l e w   c o n s t ra i nt   e rr o r  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 n  i s   do n e   o n   t h e   r e c o n s t r uc t e d  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 k  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 d  t o po l o g y   s t r uc t u r e   i s   o pt i m i z e d  b a s e d  o n   de l a y   o pt i m i z e d  pa ra m e t e r   a n d  f urt h e r   d e l a y   o pt i m i z a t i o n  i s   do n e   t o   o b t a i n  t h e   b e s t   pa t h  a n d   m i n i m i z e   c o s t .   T a b l e   1  s h o w n   t h e   n o t a t i o n  a n d   s y m bo l   us e d.           F i g u r e   1.   P r o po s e d  O n   t o p  o f   O bs t a c l e   b a s 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 r e e   Co n s t ruc t i o n    w h i c h  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 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 r e e   Co n s t ruc t i o n    w h i c h  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 n  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 f  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  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 r  l a y e r   fo r  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 r  l a y e r   fo r  e d g e             D e l a y   d u e   t o   p r e s e n c e   o f  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 f  p i n                           i f      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 f  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 d  Ro ut i n g  O n   t o p  o f   O b s t a c l e   ba s 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 r e e   C o n s t r uc t i o n   i s   p r e s e nt e d  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 n  J   E l e c   E ng  &   Co m p  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 d  r o ut i n g  o n - t o p  o f   o bs t a c l e   m o de l       L e t   c o n s i de r  a   s e t   o f   pi n s   o f   n e t     {                     }   i n  a   t ra n s m i s s i o n  a r e a   w i t h          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 k  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 k  i n  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 n  t h e   r e gi o n   po s s e s s e d  by     .   T h e   b l o c ka ge       i s   c o n s i de r e d  f o r   l a rge l y   po pul a t e d  a n d   c o m pl e x  c e l l s .     T h e   p r o po s e d  a ppr o a c h   p r o duc e s   a   de l a y   o pt i m i z e d  g r a p h                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 d  t o   b e   i n s i de   t h e   b l o c k  i f       o ve r l a p   w i t h   b l o c k     .   T h e   g r a p h      i s   r e pr e s e nt e d  a s   i n l i n e   g r a p h  a n d   t h e   o ut l i n e   b l o c k  gra p h      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 h                    i s   c o m put e d  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 d  t o   de l a y   o pt i m i z e r   s e l e c t e d  f r o m   d e l a y   o pt i m i z e d  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 r  g ra p h  a nd  pr e s e n c e   o f   de l a y   o pt i m i z e r  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 r  s pl i t   t h e   p a t h  i n  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 k  o p t i m i z e d  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 k  o pt i m i z e d  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 d  by   s um m i ng  up  t h e   de l a y   a t   e a c h  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 d  by   v a r i o us   e xi s t i n g   r e s e a r c h e r  t o   m e a s u r e   de l a y .   T h i s   w o r k  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 g  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 h  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 d  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 g  de l a y   i s   ob t a i n e d  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 g  p a t h   i s   c o m put e d  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 d  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 n  J   E l e c   E ng  &   Co m p  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 a  G )   645                   {       }   (3)     w h e r e       i s   t h e   w o r s t   s l a c k  w h i c h  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 k  o f   n o de         w h i c h  i s   c o m put e d  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 d  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 h  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 p  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 d  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 d  t r e e   c r e a t i o n   i s   s h o w n   b e l ow   i n  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 d  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 n  J   E l e c   E ng  &   Co m p  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 n  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 d  de l a y   o pt i m i z e r  pa ra m   i s   s a v e d  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 d  o n   de l a y   o pt i m i z e d  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 k  i n f o r m a t i o n   (de l a y   o pt i m i z e d  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 d  t r u nk  a nd  s i n k  a r e   r e c o m put e d  us i n g  de l a y   o pt i m i z e d  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 k  i s   r e - po s i t i o n e d  a n d   o t h e r  2 - pi n  n e t s   a r e   r i p pe d  a p a r t   a nd  r o ut i n g   pa t h   i s   c ha n ge d  a pp l y i n g  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 d  de l a y   r e s i s t e d  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 n  of  r e di r e c t i o n   a n d  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 d  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 ,   6  a n d  7  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 n  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 k      t o   r o o t   a s   t h e   r e qu i r e d  i n f l ux   t i m e   o f       i s   v e r y   l e s s .   I n  n e xt   s t e p  t h e   t o po l o g y   c r e a t i o n  m o de l   de c i de s   t o   j o i n      t o   t h e   t r u n k   a s   s h o w n  i n  F i gu r e   6,   s i n c e   i n  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 n  s a t i s fy   t h e   r e qui r e d  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 g  a ddi t i o n  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 k      a n d  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 n  s t a r  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 d  t r e e   c o n s t r uc t i o n  w h i c h  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 n  o f   de l a y   o pt i m i z e d   T r e e   w h i c h  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 d  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 g  o n   To p   o f  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 d  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 d  t h e   t r e e   c o ul d  ov e r l a p  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 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   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 k  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 d  pa t h  a nd  w i r e   l e n gt h  i n   n o n - de l a y   r e s i s t e d  pa t h.   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a n  J   E l e c   E ng  &   Co m p  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 a  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 r  s l a c k  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 d  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 d  t o   b e   a n   o pt i m i z a t i o n  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 h  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 n  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 d  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 n  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 d  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 n  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 d  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 d  p a t h  a n d   w i r e   l e n g t h  o n  n o n - de l a y   r e s i s t e d  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 n  F i g u r e   8 ,   9   a n d  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 n  us i ng  de l a y   o pt i m i z e d  R S T   w i t h  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 n  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 h  m i ni m u m   w i r e   l e n g t h  pe n a l t y   w h i c h  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 n  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 n  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 d  p a t h  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           Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a n  J   E l e c   E ng  &   Co m p  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 d  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   9  r e s e r v e s   t h e   t i m i n g   o f  de l a y   r e s i s t e d  s i n k  by   m ov i n g  t h e   e s c a pi n g  po i n t s   o n   n o n - de l a y   r e s i s t e d  pa t h .   T h e   c o n s t r a i n t   ( 9 )  a n d  ( 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 n          ha s   t o   b e   i n  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 d  l i m i t s   o n l y   o n e   po s i t i o n  s e l e c t e d  f o r   e a c h  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 f  P ath   C o n s tr u c ti o n   C om p u ti n g  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 g  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 d  pa t h  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 d  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 d  de s i g n   w i t h  t w o   de l a y   o pt i m i z e r  a nd   o n e   S t e i n e r  n o de   a s   s h o w n   i n  F i g u re   11.   D e l a y   o pt i m i z e r        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 r  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 d  c a n  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 d  i n            .   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 r  a n  a s s u m pt i o n  t ha t                       a n d  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 n  bo un d  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 n  b e   f ul f i l l e d  by   pl a c i n g  t h e   S t e i n e r   n o de   t ow a r d  t h e   po s i t i o n  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 h  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 2  s h o w s   a s s um pt i o n  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 f                      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 n  o f   de l a y   o pt i m i z e r   c o n s i de ri n g  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 r  a n o t h e r   a s s um p t i o n  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 d  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 n e d  c a n   b e   f ul f i l l e d  by   pl a c i ng  t h e   S t e i n e r  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 h  t h e   n e w   po s i t i o n   of  S t e i n e r  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 r  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 d  t o po l o g y   a f t e r   r e l o c a t i n g  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 d  i n  a c c o r d a n c e   t o           ⁄         due   o   w i r e   l e n g t h  a b o ve         i s   r e duc e d  by           ⁄ .   T h e   de l a y   o pt i m i z e r        i s   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a n  J   E l e c   E ng  &   Co m p  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 a  G )   649   a t t a c h e d  t o               du ri n g  pa t h  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 d  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 d  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 d  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 d  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 d  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 h  c o n s t r uc t i o n   i s   s h o w n   b e l ow   i n  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 n  o f   de l a y   o pt i m i z e r   c o n s i de ri n g  w i t ho ut   n e gl e c t i n g  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 d  pa t h  c o n s t r uc t i o n       T h e   p r o po s e d  a pp r o a c h  pe r f o r m a n c e   s t udy   i s   p r e s e nt e d  i n  n e xt   s e c t i o n.     Evaluation Warning : The document was created with Spire.PDF for Python.