I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute r  E ng in ee ring   ( I J E CE )   Vo l.   8 ,   No .   5 ,  Octo b e r   2 0 1 8 ,   p p .   3 3 6 8 ~ 3 3 7 3   I SS N:  2088 - 8708 ,  DOI : 1 0 . 1 1 5 9 1 / i j ec e . v 8 i 5 . pp 3 3 6 8 - 3373           3368       J o ur na l  ho m ep a g e :  h ttp : //ia e s co r e . co m/ jo u r n a ls /in d ex . p h p / I JE C E   Perf o r m a nce  Ana ly sis  of Mesh - ba s ed NoC’s  on Ro ut ing   Alg o rith m s       Ana la   M .   R . ,   Am it   N .   Su bra h m a ny a ,   Allbrig ht  D’ So uza   De p a rtme n t  o f   Co m p u ter S c ien c e   a n d   E n g in e e rin g ,   R  V   C o ll e g e   o f   En g in e e rin g ,   I n d ia       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   No v   30 ,   2 0 1 7   R ev i s ed   J an   19 ,   2 0 1 8   A cc ep ted   Feb   7 ,   2 0 1 8     T h e   a d v e n t  o f  S y ste m - on - Ch ip   ( S o Cs),  h a s  b ro u g h t  a b o u t  a   n e e d   to   in c re a se   th e   sc a le  o f   m u lt i - c o re   c h ip   n e tw o rk s.  Bu s   Ba se d   c o m m u n ica t io n s  h a v e   p ro v e d   to   b e   li m it e d   in   term s  o f   p e r f o r m a n c e   a n d   e a s e   o f   s c a la b il it y ,   th e   so lu ti o n   t o   b o th   b u s  –   b a se d   a n d   P o in t - to - P o in t  ( P 2 P )  c o m m u n ica ti o n   s y ste m s  is  to   u se   a   c o m m u n ica t io n   in f ra stru c tu re   c a ll e d   Ne tw o rk - on - Ch i p   (No C).   P e rf o rm a n c e   o f   No C  d e p e n d s  o n   v a rio u s  f a c to rs  su c h   a s  n e tw o rk   to p o lo g y ,   ro u ti n g   stra teg y   a n d   sw it c h in g   tec h n iq u e   a n d   traf f ic   p a tt e rn s.  In   th is  p a p e r,   w e   h a v e   ta k e n   th e   in it iativ e   to   c o m p il e   to g e th e r  a   c o m p a ra ti v e   a n a ly sis  o f  d iff e r e n t  Ne t w o rk   o n   Ch i p   in f ra stru c tu re s  b a se d   o n   t h e   c las si f ica ti o n   o f   ro u ti n g   a lg o rit h m ,   s w it c h in g   tec h n iq u e ,   a n d   traf fic  p a tt e rn s.   T h e   g o a l  is  to   sh o w   h o w   v a ried   c o m b in a ti o n s  o f   th e   th re e   f a c to rs  p e rf o r m   d if fe re n tl y   b a se d   o n   th e   siz e   o f   t h e   m e sh   n e tw o rk ,   u sin g   NO X IM ,   a n   o p e n   so u rc e   S y ste m C  S i m u lat o r  o f   m e sh - b a se d   No C.   T h e   a n a ly sis  h a s  sh o w n   ten a b le ev id e n c e   h ig h li g h ti n g   t h e   n o v e lt y   o f   X Y ro u ti n g   a lg o rit h m .   K ey w o r d :   Net w o r k - on - c h ip   P er f o r m a n ce   R o u ti n g   alg o r it h m   S w itc h in g   tec h n iq u e   T r af f ic  p atter n   Co p y rig h t  ©   2 0 1 8   In stit u te o f  A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e .    Al l  rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   An ala  M .   R . ,    Dep ar te m en t o f   C o m p u ter   Sci en ce   an d   E n g i n ee r in g ,   R   V  C o lle g e  o f   E n g i n ee r in g ,   R   V  Vid y a n i k eth a n   P o s t,  M y s o r e  R o ad ,   B en g al u r u   -   5 6 0   0 5 9 ,   I n d ia .   E m ail:  a n ala m r 2 0 0 4 @ g m ai l.c o m       1.   I NT RO D UCT I O N     Net w o r k - on - C h ip   is   an   e s s e n t ial  co m m u n icatio n   s u b s y s te m   f o r   S y s te m - on - C h ip   ( So C )   ar ch itect u r es   as  it   h a s   t h e  ca p ab ilit y   to   m ee t   t h e  r eq u ir e m e n ts   o f   s ca lab ilit y ,   ea s e  o f   f ab r icatio n   a n d   ad v a n ci n g   tech n o lo g ies.   A   Mu l tip r o ce s s o r   S y s te m - on - C h ip   ( MP So C )   is   t h e   a g g lo m er atio n   o f   m icr o p r o ce s s o r s ,   m icr o co n tr o ller s ,   m e m o r y   b lo ck s ,   a n d   m o r e  s u ch   an a lo g   a n d   d ig ital  in ter f ac es,  co u n ter s ,   p o w er   m a n a g e m en t   cir cu its ,   etc.   T h e  s y s te m   is   b u ilt  to   m a k e  u s e  o f   a  lar g e  n u m b er   o f   I n tellect u al  P r o p er t y   ( I P )   co r es  f o r   h ig h   p r o ce s s in g   p o w er .   B u s es  a n d   p o in t - to - p o in t  ( P 2 P )   lin k s   w er e  u s ed   as  co m m u n icatio n   i n f r astru ct u r e  f o r   So C   at  its   i n ce p tio n ,   b u t  i t  f ai led   to   f u l f ill  f u t u r e  co m m u n icatio n   r eq u ir e m e n t s   s u ch   a s   h ig h e r   s ca lab ilit y ,   s tab le   p er f o r m a n ce   a n d   ac ce p tab le  p o w er   co n s u m p tio n   [ 1 ] ,   [ 1 0 ] .   Hen ce ,   th er e  w as  a  n ee d   t o   v ee r   a w a y   f r o m   co m p u tatio n   ce n tr ic  m o d els   to   co m m u n icatio n   ce n tr ic  m o d e ls   [ 3 ] .   T h ese  p r o b lem s   w er e  s o lv ed   Net w o r k - on - C h ip   ( No C )   m o d els.  C o u p led   w it h   m i n i m al  co m p lex i t y   a n d   h ig h   s ca lab ilit y ,   it  p r o v id es  h i g h   v er s at ilit y   alo n g   w it h   q u al it y   p er f o r m an ce .   T h e  p ith   o f   th e  No C   ap p r o a ch   is   to   u s e  a  m ac r o s co p ic  co n ce p t  s u ch   as  p ac k et - s w it ch in g   an d   in f r astru ct u r al   I P s   w h ich   allo w s   ac ce s s   to   i n d iv id u al  f u n ct io n al - I P   b lo ck .   T h e   m o s t  i m p o r tan t  f ea tu r e s   t h at   d is tin g u is h   No C   ar ch itect u r es   ar e  n et w o r k   to p o lo g y ,   r o u tin g ,   an d   p ac k et  p r io r ity .   Ho w e v er ,   p ar am eter s   s u c h   as  b u f f er   s ize,   p o w er   co n s u m p tio n ,   an d   ar ea   o v er h ea d   s h o u ld   also   b e  co n s id er ed   w h i le  d ea lin g   w i th   n et w o r k   p er f o r m a n ce .   T h e  No C   ar c h it ec tu r e  is   co m p r is ed   o f   th r ee   p ar ts   -   R eso u r ce s ,   R o u ter s   a n d   R eso u r ce   Ne t w o r k   I n ter f ac e  [ 2 ] .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2088 - 8708       P erfo r ma n ce   A n a lysi s   o f Mes h - b a s ed   N o C ’ s   o n   R o u tin g   A lg o r ith ms   ( A n a la   M.  R . )   3369   a.   R eso u r ce s :  T h e y   ar e  t h e  p r o ce s s i n g   ele m en ts   th at   ar e  s e l ec ted   b ased   o n   f u n ct io n alit y ,   s ize  a n d   s p ee d   r eq u ir e m en ts   o f   a   n e t w o r k .   E . g .   Mic r o p r o ce s s o r s ,   Mic r o co n tr o ller s ,   A DC s ,   D AC s ,   FP G As,  Au d io   Vid eo   co n tr o ller s   o r   Me m o r y   B lo ck   co n tr o ller s .   b.   R eso u r ce   to   Net w o r k   in ter f ac e:  T h ey   p r o v id e  t h e  i n ter f ac e  f o r   th e  co m m u n icatio n   b et w e en   t h e  r eso u r c e   an d   th e  r o u ter s .   T h e y   ar e  in v o lv ed   w it h   th e  co n v er s io n   o f   p ac k ets  o f   d ata  i n to   a  s u itab le  f o r m   f o r   tr an s p o r tati o n   ( f l its   o r   p h its )   a n d   its   co n v er s io n   b ac k   to   th e  o r ig in a l p ac k et  o f   d ata.   c.   R o u ter :  I t   is   r esp o n s ib le  f o r   t h e  tr a n s f er   o f   d ata  f r o m   t h e  s o u r ce   I P   to   d esti n a tio n   I P   th r o u g h   r o u ter s   i n   ac co r d an ce   w it h   th e  r o u t in g   al g o r ith m .   T h e  t w o   m ain   r eso u r ce s   alo n g   w ith   t h e  I P   th at  ch ar ac ter izes  No C s   ar e  b u f f er s   an d   ch an n el s .   T o   in cr ea s e  t h e  r eso u r ce s   al lo ca tio n   f o r   ea c h   p ac k et,   a   p h y s ical   ch a n n el   is   m u ltip le x ed   i n to   a   n u m b er   o f   v ir tu a l   ch an n el s .   I t  is   v ia  t h ese  c h an n els  th a t  th e  p ac k ets  ar e  tr a n s f er r ed   f r o m   t h e  s o u r ce   I P   to   th e  d esti n atio n   I P   b y   d ef er r in g   to   th e  r o u ti n g   alg o r ith m   a s   p r escr ib ed .   E ac h   ch an n el  i s   co m p o s ed   o f   b u f f er s   th at  allo w   t h e  f r ee   m o v e m e n t o f   p ac k et s   in   a  m o r e  d is cr ete  f as h io n .   As  g i v e n   i n   t h e  liter at u r e  s u r v e y   b elo w ,   th e  r esear c h   s o   f ar   h as  b ee n   f o cu s e d   o n   g r ad in g   th e   p er f o r m a n ce   o f   r o u ti n g   alg o r it h m s   b ased   o n   laten c y   an d   p ac k et  in j ec tio n   r ate.   Ho w e v er ,   th er e  h as  b ee n   a  lac k   o f   f o c u s   o n   s ize  o f   th e  m e s h ,   w h ic h   cr ea tes  a  d r a m a tic  ch a n g e  in   t h e  p er f o r m an ce   o f   t h e   r o u tin g   al g o r ith m .   Hen ce ,   th is   e x p er i m e n t  is   f o c u s ed   o n   e m p h as izin g   t h e  ef f e ct  o f   s ize  o n   p er f o r m a n ce   t h r o u g h   t h e  s i m u latio n s   ca r r ied   o u t o n   NOXI M.     1 . 1 .   P er f o r m a nce  d epe nd encie s   As  p r ev io u s l y   m en tio n ed ,   an   N o C   is   d is tin g u is h ed   b ased   o n   v ar iab les  s u ch   as   n etwo r k   to p o lo g y ,   r o u tin g   alg o r ith m ,   s witc h in g - tech n iq u e ,   an d   tr af f ic  p atter n .   No C   s y n th etic  tr af f ic  p atter n s   ar e  ess en tial  to o ls   f o r   No C   p er f o r m an ce  ass ess m en t  an d   d ev is in g   n ew  ar ch itectu r es.   Per f o r m an ce  o f   th e  No C   with   r esp ect  to   th e  s ize  o f   t h e  n etwo r k   is   d r am aticall y   d ep en d en t  o n   t h ese  f acto r s ,   th e   m ain   m etr ics  u s ed   f o r   th e   ev alu atio n   o f   p er f o r m an ce  ar e  th r o u g h p u t  an d   av er ag e p ac k et  d ela y ,   b u t  o u r   f o cu s   in   t h is   p a p e r   is   o n   Gl o b al  A v er ag e Dela y   ( la ten c y ) .       1 . 1 . 1 .   T o po lo g y   Net w o r k   to p o lo g y   is   a  s p atia l   ar r an g e m e n t  o f   n o d es  co n n e cted   to   f o r m   a  n et w o r k .   A  d is tin g u i s h ed   ar r ay   o f   to p o lo g ies  s u c h   as   M esh ,   T o r u s ,   R i C o B it  an d   B FT   etc.   h as  b ee n   d esi g n ed   to   s u i t  d if f er en t  s y s te m s   an d   th eir   n ic h e  ap p licatio n s .   Ho w e v er ,   f o r   all  g e n er al  p u r p o s e  s i m u lat io n   a n d   m o s t  r ea l - w o r ld   ap p licatio n s ,   Me s h   to p o lo g y   i s   u s e d   d u e  to   its   s i m p licit y   in   co n s tr u ctio n   a n d   d esig n i n g   r o u ti n g   alg o r it h m s .   M esh   T o po lo g y :   I t  is   th e  ea s i est  to   f ab r icate   o f   all   th e   ar r an g e m e n t s   as   all  n o d es  ar e  ar r an g ed   in   th e   o r d er   o f   an   m   x   n   m atr i x .   T h e  m atr ix   f o r m   f ac to r   allo w s   th e  n et w o r k   to   b e  f lat  an d   v er y   t h i n .     1 . 1 . 2 .   Ro uting   R o u ti n g   al g o r ith m s   d eter m i n e   th e   p ath   s elec ted   b y   a  p ac k e t  to   r ea ch   its   d esti n atio n .   R o u ter s   h a v e  b ee n   d e - s i g n ed   s u ch   th at   at  ea ch   i n ter m ed iar y   r o u ter ,   a  d ec i s io n   i s   m ad e  to   tr an s f er   t h e  p ac k et  i n   a  p ar ticu lar   d ir ec tio n   i.e .   n o r th ,   s o u t h ,   e ast,  w est   o r   lo ca l  ( to   I P ) .   R o u ti n g   al g o r ith m s   h a v e  t wo   b asic  ap p r o ac h es    1 )   Dete r m in i s tic  a n d   2 )   A d ap tiv e  [ 2 ] ,  [ 6 ] .   T h e  d eter m i n i s ti c  alg o r ith m   n ee d s   n o   in f o r m a tio n   o th er   t h an   th e   s o u r ce   ad d r ess   an d   th e  d esti n atio n   ad d r ess   to   d eter m i n e  a  p ar tic u lar   r o u te  f o r   th e  p ac k et.   T h e  ad ap tiv e   alg o r ith m   h as  n o   p r ed ef in ed   r o u te  an d   i s   d eter m i n ed   d y n a m icall y   at  ea c h   r o u ter   b ased   o n   th e  n et w o r k   lo ad   an d   tr af f ic  co n d itio n s .   T h e  d eter m i n is tic  al g o r ith m s   ar e  p r o v en   to   b e  d ea d lo ck   an d   liv elo ck   f r ee   s i n ce   ea ch   p ac k et  w ill  ev e n t u all y   r ea ch   its   d esti n atio n .   Ho w e v er ,   p ac k et  late n c y   i n   s u ch   a n   alg o r i th m   w ill  i n cr ea s e  d r asti ca ll y   i f   m u ltip le  p ac k e t s   n ee d   to   tr a v el  ac r o s s   t h e  s a m e  c h an n el  [ 6 ] .   On   t h e  o t h er   h an d ,   ad ap tiv e  alg o r ith m s   ar e  p r o n e  to   d ea d lo ck   an d   liv elo c k ,   b e - ca u s e  t h e y   ar e  d ep en d en t  o n   th e  tr a f f i c  d en s it y   a n d   m a k e  d ec is io n s   b ased   o n   its   a v aila b ilit y .   T o   av o id   d ea d lo ck s   an d   liv elo c k s   ca u s ed   b y   p ac k ets  c y cli n g   ar o u n d ,   ce r tain   t u r n s   n ee d   to   b e  eli m i n ated   [ 6 ] .   Du e  to   co m p u tatio n   d ep en d en c y ,   it  is   le s s   e f f ici en t  to   u s e  ad ap ti v e   r o u tin g   at  lo w er   p ac k et  in j ec ti o n   r ate.   T h e  m o s t c o m m o n   r o u ti n g   al g o r ith m s   ar e  as  f o llo ws:   a.   XY  r o u ti n g :  T h is   i s   a  d eter m i n is t ic  r o u ti n g   al g o r ith m   i n   w h ich   t h e  p ac k et  f ir s t   tr av er s e s   a cr o s s   th e   X  a x i s   u n t il  t h e  s o u r ce   a n d   d esti n at io n   ar e  ali g n e d   in   th e   s a m e  co lu m n ,   a n d   t h en   it  tr a v er s e s   i n   t h e  Y - a x i s   d ir ec tio n   till   t h e  d esti n a tio n   i s   r ea ch ed .   An   alter n ate  d esi g n   to   th i s   w o u ld   b e  th e  Y X  r o u ti n g ,   w h ic h   h a s   th e  p ac k et  m o v e  alo n g   t h e  Y - a x is   f ir s t  f o llo w ed   b y   th o s e  i n   t h e  X - a x i s .   b.   W est  f ir s t:  T h is   is   a n   ad ap tiv e   alg o r ith m   in   w h ic h   p ac k ets  m u s t  f ir s t  tr av el  i n   th e  w e s t war d   d ir ec tio n   an d   th en   m o v e  to w ar d s   t h e  d esti n a tio n   w it h o u t  m ak in g   an y   m o v e m en ts   w e s t [ 7 ] .   c.   No r th   last :   A n a lo g o u s   to   t h e   p r ev io u s ,   t h is   is   a n   ad ap tiv e  alg o r ith m   m a k es  ad ap ti v e  d ec is io n s   i n   t h e   b eg in n i n g   a n d   th e n   f in al l y   allo w s   th e  p ac k e t to   tr av el  n o r t h war d s   to   its   d esti n atio n   if   n ee d e d   [ 7 ] .   d.   Neg ati v e  Firs t:  I n   t h is   ad ap t iv e  al g o r ith m ,   th e  p ac k et  m u s t  ad ap tiv e l y   m a k e  all  n e g ativ e  d ir ec tio n a l   m o v e m e n t  in   t h e  b eg i n n i n g   an d   th en ,   all  t h e  p o s iti v e  m o v e m en ts .   Neg a tiv e  m o v e m e n ts   h er e  ar e  d ef in ed   as  w e s t a n d   s o u t h   w h i le  p o s iti v e  m o v e m e n t s   ar e  n o r th   a n d   ea s t [ 7 ] .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  8 ,   No .   5 ,  Octo b er   2 0 1 8   :   3 3 6 8   –   3 3 7 3   3370   e.   Od d - E v e n :  T h is   ad ap ti v e  r o u t in g   p r o h ib its   ea s t  to   n o r th   t u r n s   a n d   ea s t   to   s o u th   tu r n s   at   an y   n o d e  i n   an   ev en   co lu m n .   I t  a ls o   d is a llo ws  n o r th   to   w est   t u r n s   a n d   s o u t h   to   w est   tu r n s   at  a n y   n o d e  in   an   o d d   co lu m n   [ 8 ] .   f.   D y A D:  D y n a m icall y   s w i tch i n g   b et w ee n   A d ap tiv e  a n d   D eter m i n is tic  r o u tin g   i s   th e  c u l m i n atio n   o f   t h e   ad v an ta g es  o f   b o th   d eter m i n is t ic  an d   ad ap tiv e  al g o r ith m s .   I t  co u ld   b e  a  co m b i n at i o n   o f   a n y   t w o   alg o r ith m s ,   s u ch   th at   it  co n ti n u o u s - l y   m o n ito r s   it s   lo ca l  n et w o r k   lo ad   an d   m ak e s   d ec is io n s   b ased   o n   t h is   in f o r m atio n   [ 6 ] .     1 . 1 . 4 .   Sy nthet ic  t ra f f ic  pa t t er ns   T h ese  ar e  s p ec u lat iv e   m o d els   o f   tr a f f ic  to   d e m o n s tr ate  h o w   th e   s i m u latio n   w o u ld   p r o g r e s s .   T h e y   d if f er   f r o m   r ea lis tic   m o d el s   t h at  ar e  b ased   o n   ce r tai n   b en ch m ar k   p r o g r a m s .   T r af f ic   p at ter n s   p r ed ef i n e  t h e   d esti n atio n   n o d e  f o r   a  p ar ticu l ar   s o u r ce   n o d e.   I n   o u r   s i m u lati o n s ,   w e  u s ed   th e  f o llo w i n g   [ 3 ] :   a.   R an d o m   p atter n :  E ac h   s o u r c e  n o d e  d is p atch es  p ac k et  to   an o th er   r an d o m   n o d e  at  th e  s p ec if ied   p ac k e t   in j ec tio n   r ate.   b.   T r an s p o s e  1 :  I t  is   a  m atr i x - t r an s p o s e  p atter n   in   w h ich   e ac h   P E   p r esen t  in   a  ch ip   at  lo ca tio n   ( I ,   J )   d is p atch es a   m ess a g e  to   th e  P E   at  ( n   –   1  –   I ,   n   –   1 –   J )   f o r   an   ( n   x   n )   s ize  N OC .     c.   T r an s p o s e  2 :  T h e  P E   p r esen t a t c h ip   ( I ,   J )   co m m u n icate s   o n l y   w it h   th e  n o d e  ( J ,   I )   in   th e  n e t w o r k .     1 . 2 .   L it er a t ure  s urv ey   No C s   h a v e  b ec o m e   th e   m o s t  s o u g h t - a f ter   ar ch itect u r e  d u e  t o   its   o v er w h el m i n g   ad v a n ta g e s   o v er   t h e   p r im iti v e  So C   m o d el.   T h e  a b ilit y   to   p r o v id e   h i g h er   s ca la b ilit y   a n d   r e - u s ab ilit y   g iv e s   i t  an   ed g e  o v er   it s   co m p eti to r s .   E x ten s i v e  r esear ch   h as  b ee n   d o n e  i n   d ev elo p in g   n e w   to p o lo g ies  an d   r o u tin g   alg o r it h m s .   L e s s   co n v e n tio n al  to p o lo g ies  li k e   th e  R i C o B it  h a v e  b ee n   e x p lain ed   w ith   f le s h ed   o u t  in f o r m at io n   a n d   also   p er f o r m a n ce   e v al u atio n s   i n   m an y   p ap er s   [ 9 ] .   T h e  r atio   o f   a v er ag e  t h r o u g h p u t  a n d   av e r ag e  p ac k et  d ela y   is   co m p u ted   to   co m p ar e  d if f er e n t  s i m u latio n s .   I t  is   s h o w n   t h at  Od d - E v e n   r o u ti n g   is   s u p er io r   to   XY  r o u ti n g   w it h   a  r atio   o f   2 . 5 3 5 8   as  co m p ar ed   to   2 . 1 1 2 6   r esp ec tiv el y   [ 1 0 ] .   T h e  p er f o r m a n ce   o f   XY  r o u tin g   i s   p r ef er ab le  at  u n i f o r m   tr a f f ic  p atter n s .   Fo r   n o n - u n i f o r m   tr a f f ic,   th e  lo ad   at  th e  ce n ter   o f   t h e  n et w o r k   is   h i g h er   t h an   t h e   av er ag e  n et w o r k   lo ad   lead in g   to   a  t r af f ic  h o t s p o t  [ 1 1 ] .   A n o th er   d is ad v an tag e   is   t h at  if   a  n o d e  is   f au lt y ,   th a t   p ac k et  w il l  r e m ain   b lo ck ed   o n   t h at   p ath   [ 1 2 ] .   Ho w ev er ,   X Y  r o u ti n g   is   s i m p le   an d   h as   v er y   lo w   h ar d - w ar e  o v er h ea d   as  co m p ar ed   to   ad ap tiv e  r o u ti n g   [ 1 3 ] .   Un d er   d is tr i b u ted   tr af f ic  p atter n s ,   XY  r o u t in g   a n d   Od d - E v e n   r o u tin g   w o r k   b etter .   Ho w ev er ,   in   d ir ec ted   tr af f ic  f o r   m o s t  p r ac tical  cir cu m s tan ce s ,   D y AD   r o u tin g   w o r k s   b et - ter   th an   m o s t  o f   t h e  o th er   r o u tin g   al g o r ith m s   [ 1 4 ] .   I n v es tig ati n g   th e  d esi g n   o f   a  No C   b y   ev al u ati n g   its   p er f o r m a n ce   r eq u ir es  t h e   av ai lab ilit y   o f   f a s t  a n d   ac c u r a te  s i m u latio n   to o ls .   No x i m   i s   a  S y s te m C   b a s ed   o p e n   s o u r ce ,   c y cle  ac c u r ate  p latf o r m   f o r   t h e  s i m u latio n   o f   b o th   co n v en t io n al  w ir e - b ased   N o C s   an d   e m er g i n g   W iNo C   ar ch itectu r es.  Se v er a l  d o cu m en t s   ar e  av ailab le  f o r   g ettin g   s tar ted   o n   th e  s i m u lato r .   T h e  r o u tin g   a lg o r ith m s   u s ed   i n   t h is   p ap er   h av e   b ee n   d e v elo p ed   w it h   ad eq u ate  d o cu m e n tat io n .   An   elab o r ate  ar ticle   d escr ib in g   t h e  g e n er al  s y s te m   s tr u ctu r e  o f   t h e  No C   i s   av ailab le  to   p r o v id e  th e  n ec es s ar y   k n o w led g e  f o r   f u r t h er   s t u d y   [ 1 ] .       2.   RE S E ARCH   M E T H O D     W e  ev alu ate   th e   p er f o r m a n ce   o f   m e s h   n et w o r k s   o f   s ize s   v ar y in g   ( f r o m   4 x 4   to   1 0 x 1 0 )   b ased   o n   th e   af o r e - m en tio n ed   d ep en d en cie s   s u c h   as  tr af f ic  p atter n s ,   r o u t - i n g   al g o r ith m s   a n d   s w itc h i n g   s ch e m e s .   T r af f ic  p atter n s   co n s id er ed   ar e  r an d o m ,   tr an s p o s e  1   an d   tr a n s p o s e  2   [ 3 ] .   T h e  r o u tin g   al g o r ith m s   co n s id er ed   ar e  XY,   w e s t  f ir s t,  n o r th   last ,   n e g ati v e  f ir s t,  o d d   ev e n   &   D y AD  [ 6 ] - [ 9 ] .   S w itc h i n g   s c h e m es  u s ed   ar e  n ei g h b o r s   o n   p at h   ( NOP )   an d   b u f f er   le v el  s tr ate g y .   A ll t h e  test s   w er e  co n d u cte d   o n   NOXI M,   an   o p en   s o u r ce   S y s te m C   Si m u lato r   o f   m es h - b ased   No C   [ 1 ] .   T h e  r esu l ts   h a v e  b ee n   o b tain ed   w it h   r e - s p ec t  to   g lo b al  a v er ag e  d ela y   at   d if f er en t   p ac k et  in j ec tio n   r ates ( P I R )   o r   th r o u g h p u t f o r   th e  f o llo w in g   T ab le  1   co n f ig u r atio n s :       T ab le  1 .   Sim u latio n   S etti n g s   S e t t i n g   V a l u e   B u f f e r   D e p t h   4   S i z e   o f   F l i t s( i n   b i t s)   32   D y a d   T h r e sh o l d   0 . 6   S i mu l a t i o n   T i me ( i n   c y c l e s )   1 0 0 0 0   P a c k e t   S i z e ( i n   f l i t s)   8   P a c k e t   I n j e c t i o n   R a t e   0 . 0 0 8   t o   0 . 0 2 0   S e l e c t i o n   S t r a t e g y   B u f f e r   L e v e l ,   N O P     Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2088 - 8708       P erfo r ma n ce   A n a lysi s   o f Mes h - b a s ed   N o C ’ s   o n   R o u tin g   A lg o r ith ms   ( A n a la   M.  R . )   3371   3.   RE SU L T S  A ND  AN AL Y SI S   T h e  p er f o r m a n ce   o f   No C s   i s   e v alu a ted   b ased   o n   t w o   d if f er e n t  tr a f f ic   p atter n s   ( r a n d o m ,   tr a n s p o s e  2 )   an d   s w itc h i n g   s ch e m e s   ( Neig h b o r s   o n   P ath ,   b u f f er   le v el)   h av e  b ee n   m ad e  ac r o s s   f o u r   d i f f er en t  I n j ec tio n   r ate,   g iv in g   r i s e  to   a  d escr ip ti v e  l is ti n g   o f   F ig u r e   1   a n d   Fi g u r e  2   th at  i llu s tr ate  h o w   ea c h   r o u tin g   al g o r ith m   p er f o r m s .   I n t u iti v el y ,   w e  ca n   r elate   th e  s ize  o f   t h e  m es h   w i th   t h e  d ela y   a s   d ir ec tl y   p r o p o r tio n al,   s i n ce   lar g er   ti m e  w o u ld   b e  r eq u ir ed   to   tr an s f er   th e   p ac k ets   ac r o s s   lar g er   n et w o r k s .   B u t,  r o u t in g   al g o r ith m s   h a v e  b ee n   d esig n ed   d if f er e n tl y   to   h a n d le   lig h t  a n d   h ea v y   lo ad s .   Mo r e  o f ten   t h an   n o t,  T r af f ic  p atter n s   m a y   f a v o r   ce r tain   p ath s   m o r e  t h an   o th er s   d u e  t o   co m m o n   d esti n atio n   n o d es   th is   ca n   b e  b etter   s h o w n   b y   th e  f o llo w i n g   t w o   tr af f ic  p atter n s .               ( a)       ( b )     ( c )           ( d )       ( e )     ( f )         ( g )     ( h )     Fig u r e  1 .  ( a)   P I R   =  0 . 0 0 8 ,   T r a f f ic  P atter n : Ra n d o m   o n   s w itc h in g   s c h e m es:  NOP ,  ( b )   P I R   =   0 . 0 1 2 ,   T r af f ic  P atter n : Ran d o m   o n   s w itc h i n g   s ch e m es: N OP ,  ( c)   P I R   =  0 . 0 1 6 ,   T r af f ic  P atter n : Ran d o m   o n   s w itc h i n g   s ch e m es:  NOP ,  ( d )   P I R   =  0 . 0 2 ,   T r af f ic  P atter n : Ra n d o m   o n   s w itc h i n g   s c h e m e s : N OP ,  ( e)   PIR =   0 . 0 0 8 ,   T r af f ic  P atter n : Ran d o m   o n   s w itc h i n g   s c h e m e s : B u f f er   L e v el ,  ( f )   P I R   =  0 . 0 1 2 ,   T r af f ic  P atter n : Ra n d o m   o n   s w itc h in g   s c h e m es: B u f f er   L e v el ,  ( g )   P I R   =  0 . 0 1 6 ,   T r af f ic  P atter n : Ra n d o m   o n   s w itc h i n g   s ch e m e s : B u f f er   L e v el ,  ( h )   P I R   =  0 . 0 2 ,   T r af f ic  P atter n : Ran d o m   o n   s w itc h i n g   s ch e m es: B u f f er   L e v el       Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  8 ,   No .   5 ,  Octo b er   2 0 1 8   :   3 3 6 8   –   3 3 7 3   3372           ( a)     ( b )       ( c)           ( d )     ( e)     ( f )             ( g )     ( h )       Fig u r e  2 .   ( a )   P I R   =  0 . 0 0 8 ,   T r a f f ic  P atter n : T r an s p o s e  2  o n  s w itc h i n g   s c h e m e s : N OP ,  ( b )   PIR =   0 . 0 1 2 ,   T r af f ic  P atter n : T r an s p o s e  2   o n   s w itc h in g   s c h e m es:  NOP ,  ( c )   P I R   =  0 . 0 1 6 ,   T r af f ic  P atter n : T r an s p o s e  2   o n   s w i tch i n g   sc h e m es:  NOP ,  ( d )   P I R   =  0 . 0 2 ,   T r af f ic  P atter n : T r an s p o s e  2  o n   s w itc h i n g   s ch e m es : N OP ,  ( e)   P I R   =  0 . 0 0 8 ,  T r af f ic  P atter n : T r an s p o s e  2   o n   s w itc h i n g   s c h e m e s : B u f f er   L ev el , ( f )   P I R   =  0 . 0 1 2 ,   T r af f ic  P atter n : T r an s p o s e  2   o n   s w i tch i n g   s c h e m e s : B u f f er   L ev el , ( g )   P I R   =   0 . 0 1 6 ,   T r a f f ic  P atter n : T r an s p o s e  2   o n   s w itc h i n g   s c h e m e s :  B u f f er   L e v el , ( h )   P I R   =  0 . 0 2 ,   T r af f ic  P atter n : T r an s p o s e  2   o n   s w itc h i n g   s c h e m e s : B u f f er   L ev el       I n   T r af f ic   p atter n :   R a n d o m ,   w h ic h   tr a n s f er s   p ac k ets   h ap h az ar d ly   to   a n y   d esti n atio n   n o d e,   in   b o t h   b u f f er   lev el  an d   NOP   s elec ti n g   s ch e m e,   XY  r o u ti n g   i s   s ee n   to   o u tp er f o r m   t h e  r est.  As  th e  o v er all  d is tr ib u tio n   o f   r eq u es ts   is   co n s id er ed ,   n o   tr af f ic  h o ts p o ts   e x i s t.  T h is   m ak es   th e   tr af f ic   d is tr ib u tio n   s ee m   m o r e  u n i f o r m .   Du e  to   th is ,   XY  r o u t in g   d o es n ' t  s p e n d   th e  ti m e  tr y in g   to   d eter m i n e  an d   s elec t  f r ee   p ath s   lik e  t h e  ad ap tiv e   alg o r ith m s .   T h is   b eh a v io r   o f   XY  r o u tin g   h o ld s   g o o d   ev en   at  h ig h   P I R   an d   lar g e  m es h   s i ze s   as  illu s tr ated   in   Fig u r e   1 ( d ) ,   Fig u r e  1 ( e) ,   Fi g u r e  1 ( i)   an d   Fi g u r e   1 ( j ) .   Ma k in g   it   m o r e   r eliab le  t h a n   e v en   D y AD   w h ich   s h o w s   co n s is ten tl y   h i g h er   d ela y   t h an   XY  as  s h o w n   in   Fig u r e   1 ( a)   an d   Fig u r e   1 ( b ) .   Ho w e v er ,   XY  r o u ti n g   d em o n s tr ate s   b etter   d elay   t h a n   th e  o th er   ad ap tiv e  al g o r ith m s   as  s h o w n   in   Fi g u r e   1 ( c)   a n d   Fig u r e   1 d ) .   T h is   m a y   b e  ac co u n ted   d u e  to   th e  f ac t  th at  it  h a s   to   d eter m i n e  w h ich   ap p r o ac h   to   p r o ce ed   w it h   an d   its   co m p lex it y   o f   h ar d w ar e.   D y AD  al s o   b eh a v es  a s   e x p ec ted   it  h a s   a  h i g h er   d ela y   at  lo w   P I R   in   b o t h   t h e  s elec tio n   s tr ateg ie s .   Ho w e v er ,   its   laten c y   r ed u ce s   w it h   an   i n cr ea s e  i n   P I R   as  it  b ec o m e s   m o r e  s tab le.   I t  h as  a  v er y   h i g h   d ela y   in   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2088 - 8708       P erfo r ma n ce   A n a lysi s   o f Mes h - b a s ed   N o C ’ s   o n   R o u tin g   A lg o r ith ms   ( A n a la   M.  R . )   3373   co m p ar is o n   to   o th er   alg o r ith m s   as  s ee n   in   F ig u r e   1 ( a)   to   Fig u r e   1 ( e) .   T h is   p atter n   is   v is ib le  o n l y   i n   NOP .   Ho w e v er ,   it  s h o w s   i m p r o v e m en t  in   late n c y   w it h   an   i n cr ea s e  in   P I R   u n d er   B u f f er   L e v el.   T h e  r em ai n i n g   ad ap tiv e  alg o r ith m s   h a v e  d elay s   r an g i n g   f r o m   m ed iu m   to   h i g h   v al u es.   I n   T r af f ic  p atter n :  T r an s p o s e  2 ,   XY  r o u tin g   h a s   h i g h er   d ela y   th a n   it s   ad ap tiv e  co u n ter p ar ts   at  lo w   P I R   s u ch   as  0 . 0 0 8   an d   0 . 0 1 2   as  s h o w n   i n   Fi g u r e  2 ( a) ,   Fig u r e   2 ( b ) ,   Fig u r e   2 ( f ) ,   Fig u r e   2 ( g ) ,   b u t  w i th   a n   in cr ea s e  i n   P I R   at  s izes  lar g er   th an   8 x 8 ,   it  g en er all y   p er f o r m s   b etter   th a n   t h e  ad ap tiv e   co u n ter p ar ts   D y A D  a n d   odd - ev en   as  i n d icate d   in   Fig u r e  2 ( c) .   C o m p ar ed   to   th e  r e m ai n in g   ad ap tiv e  alg o r it h m s ,   Neg ativ e  F ir s t,  as   s h o w n   in   Fig u r e  2 ( g ) ,   Fig u r e   ( 2 h )   s h o w s   h ig h   p er f o r m a n c e  at  m ed iu m   to   h i g h er   P I R .   T h is   is   b ec au s e  it  i s   b etter   s u ited   f o r   s en d in g   p ac k ets  to   o p p o s ite  en d s   as  it  ad ap tiv el y   a llo w s   in itial  n e g ati v e  m o v e m e n ts   an d   t h en   ad ap tiv el y   p o s iti v e  m o v e m e n t s ,   m ak i n g   t h e   d ela y s   s h o r ter ,   th o u g h   it s   la ten c y   in cr ea s e s   at   s m aller   m e s h   d u e   to   ex tr a  ti m e  s p e n t  in   m a k in g   m o r e  ad ap tiv e  d ec is io n s .     No r th   l ast  s h o w s   lo w   to   m ed iu m   d ela y   ac r o s s   all   f i g u r es  a n d   th is   m a y   b e  b ec au s e  n o r th   last   is   ad ap tiv e  i n   th e  b eg in n in g   an d   d eter m i n is tic   in   th e  en d   w ith   it s   ap p r o ac h .   Sin ce   alo n g   t h e  p r i n cip al  d iag o n al  i s   w h er e  m o s t  tr af f ic  w i ll  b e  co n ce n tr ated ,   th e  ad ap tiv e   f ir s t   n atu r e   o f   n o r th   last   m a k e s   it  f aster   th a n   th e   r est  at   lo w   to   m ed iu m   P I R   an d   lo w   to   m ed iu m   s ize.   W est  f ir s t  i s   s h o w s   s i m i lar ,   if   n o t  s li g h t l y   w o r s e  p er f o r m a n ce   in   co m p ar is o n   to   No r th   L ast.  D y AD  is   m o r e  s tab le  at  lo w   P I R   v alu e  0 . 0 0 8   as  s h o w n   i n   Fig u r e  2 ( a)   an d   Fig u r e  2 ( f ) .   I t s   p er f o r m a n ce   w o r s en s   w it h   a n   i n cr ea s e  i n   b o th   th e  P I R   an d   th e  m es h   s ize.       4.   CO NCLU SI O N     I n   th i s   p ap er ,   w e  h a v e  ai m ed   at  d er iv in g   an d   p o r tr ay in g   t h e  ef f ec t  o f   v ar io u s   f ac to r s   o n   p er f o r m an c e   w it h   r esp ec t  to   t h e  s ize  o f   a n   No C .   I t  ca n   b e  co r r o b o r ated   u s i n g   t h e  g r ap h s   t h at  t h e  d eter m i n is tic  r o u ti n g   alg o r ith m   -   XY  i s   n o t   s tab le  d u e  to   its   f lu ct u ati n g   b eh a v io r   f o r   d if f er en t   co m b i n atio n s   o f   tr af f ic  a n d   m es h   s izes  ( i.e .   at  lo w   P I R   an d   s m a ll  m es h   s ize) .   A d ap tiv e  al g o r i th m s   li k e  W est  Fir s t,  No r th   L ast,  Neg ati v e  Fir s t  an d   Od d - E v e n   s h o w   th a t  th e s e  alg o r ith m s   ar e  q u ite  r eliab le  in   d ea lin g   w it h   ce r tai n   tr af f ic   p atter n s   b u t  s u f f er   f r o m   lar g er   d ela y   ac r o s s   lar g e r ,   less   co n g e s ted   m es h   s tr u ct u r es  d u e  to   in cr ea s ed   p ac k et  lat en c y   ca u s ed   b y   it s   m o r e  co m p le x   h a r d w ar e.   Fo r   lar g e  No C s   at  h ig h er   P I R s ,   X Y  is   u n d o u b ted l y   a  m o r e  attr a ctiv e  al g o r ith m   f o r   m o s t  tr a f f ic  p atter n s   d u e  to   i ts   lack   o f   d ep en d en ce   o n   n et w o r k   lo ad .   Si n ce   t h e  p ath   o f   tr an s ac tio n   n e v er   ch an g es,  i t  is   i n d ep en d en t  o f   t h e  p ath   ta k e n   b y   alie n   p ac k et s   as  lo n g   as  it s   o w n   p at h   is   f r ee .   A s   lar g er   m e s h es  lack   i n   t h e  n u m b er   o f   co m m o n   p ath s ,   XY  i s   d ef i n itel y   a  b et ter   ch o ice  f o r   a  r o u ti n g   alg o r it h m .   Mo r eo v er ,   XY   r o u tin g   h as  a   s i m p le  i m p le m en tatio n   t h u s   h av in g   a  s m all  o v er h ea d   d u r i n g   p ac k et  tr an s it.  A s   s ee n   b y   th e   o b s er v atio n s   t h u s   f ar ,   th e   r es u lts   o b s er v ed   g o   h a n d   i n   h a n d   w it h   t h e  i n tr o d u ctio n ,   s h o w ca s in g   t h e  o v er all   ef f ec tiv e n e s s   o f   XY  r o u tin g   al g o r ith m   o v er   th e  o t h er   alg o r it h m s .       RE F E R E NC E S    [1 ]   V in c e n z o   Ca tan ia,   e t  a l . ,   “ Cy c l e - A c c u ra te  Ne t w o r k   o n   Ch ip   S im u l a ti o n   w it h   No x im ” ,   ACM   T ra n s.  M o d e l.   Co mp u t.   S imu l. ,  2 7 ,   1 ,   A rti c le 4 ,   p p :  1 - 21 ,   A u g u st 2 0 1 4 .   [2 ]   S u d h a n sh u   C h o u d h a ry   a n d   S h a f i  Qu re sh i ,   “ P e rf o rm a n c e   Ev a lu a ti o n   o f   M e sh - b a se d   N o Cs:  Im p lem e n tatio n   o f   a   Ne w   A rc h it e c tu re   a n d   Ro u ti n g   A lg o rit h m ” ,   IJ AC ,   A u g u st 2 0 1 2 ,   p p .  5 - 10 .   [3 ]   Ja y a n t  Ku m a r  S in g h ,   “ P e rf o rm a n c e   Ev a lu a ti o n   o f   d if f e re n t  Ro u ti n g   A lg o rit h m s  in   Ne t w o rk   o n   Ch ip ” ,   M a ste r’s  T h e sis Ju n e   2 0 1 4 .   [4 ]   Z.   S h a rif i,   e t  a l . ,   “ Co m p a riso n   o f   No C  Ro u ti n g   A lg o rit h m s  u sin g   F o r m a l  M e th o d s” ,   Ju ly   2 0 1 3 ,   p p .   1 - 15 .   [5 ]   Jin g c a o   Hu   Ra d u   M a rc u les c u ,   “ D y AD :  S m a rt  Ro u ti n g   f o r  Ne tw o rk s - o n - Ch i p ” ,   A p ril   2 5 ,   2 0 0 4 ,   p p : 1 - 10 .   [6 ]   M a k sa t  A tag o z i y e v ,   “ Ro u ti n g   A l g o rit h m s f o r  o n   Ch i p   Ne tw o rk s” ,   De c e m b e r  2 0 0 7 ,   p .   79 .   [7 ]   Ch risto p h e r   J.  G las s   a n d   L io n e l  M .   NI. ,   “ T h e   T u rn   M o d e l  f o r  A d a p ti v e   R o u t in g ” ,   S e p tem b e r  1 9 9 4 ,   p p : 1 - 10 .   [8 ]   W a n g   Zh a n g ,   e t  a l . ,  “ Co m p a riso n   Re se a rc h   b e t w e e n   X Y  a n d   Od d - Ev e n   Ro u ti n g   A l g o rit h m   o f   a   2 - Dim e n sio n   3 X 3   M e sh   T o p o lo g y   Ne two rk - on - Ch i p ” ,   W RI  Glo b a l   Co n g re ss   o n   In tell ig e n t  S y ste ms ,   GS IS ’ 0 9 ,   M a y   2 0 0 9 ,   p p .   3 2 9 - 3 3 3 .     [9 ]   P a n   Ha o ,   e t  a l . ,   “ Co m p a riso n   o f   2 D  M ES H  Ro u ti n g   A lg o rit h m   in   NO C” ,   2 0 1 1   IEE E  9 th   I n ter n a ti o n a l  C o n fer e n c e ,   p p .   7 9 1 - 795 .   [1 0 ]   M .   Nic k ra y ,   e t  a l . ,   “ A d a p ti v e   R o u ti n g   Us in g   Co n tex t - Aw a re   Ag e n ts  f o r  Ne t w o rk s  o n   Ch ip s” ,   De sig n   a n d   T e st   W o rk sh o p   ( IDT),   2 0 0 9   4 th   I n ter n a ti o n a l ,   pp .  1 - 6 ,   2 0 0 9 .   [1 1 ]   R.   Ho lsm a rk ,   e t  a l . ,   “ De a d lo c k   F re e   Ro u ti n g   A lg o rit h m s  f o r  M e sh   T o p o lo g y   No C  S y ste m s   w it h   Re g io n s ” ,   DS D   2 0 0 6 .   9 t h   EUROM ICRO  Co n fer e n c e   o n ,   p p.   6 9 6 - 7 0 3 .   Evaluation Warning : The document was created with Spire.PDF for Python.