I nte rna t io na l J o urna l o f   Rec o nfig ura ble a nd   E m be dd e d Sy s t e m s   ( I J R E S)   Vo l.  14 ,   No .   2 J u ly   20 25 ,   p p .   375 ~ 3 8 7   I SS N:  2089 - 4864 DOI 1 0 . 1 1 5 9 1 /i j r es . v 1 4 . i 2 . pp 3 7 5 - 387          375       J o ur na l ho m ep a g e h ttp : //ij r es.ia esco r e. co m   An appro x i m a te  m o del  SpM V on  FP G A as sis ting  H LS  o pti m i z a tions  f o lo w  po w er and hig h perf o r m a nce       Alden C .   Sh a j i,  Z a ina b A iza z K a v it a   K ha re   D e p a r t me n t   o f   El e c t r o n i c s a n d   C o mm u n i c a t i o n ,   M a u l a n a   A z a d   N a t i o n a l   I n st i t u t e   o f   T e c h n o l o g y ,   B h o p a l ,   I n d i a       Art icle  I nfo     AB ST RAC T   A r ticle  his to r y:   R ec eiv ed   Ma y   4 ,   2 0 2 4   R ev i s ed   J u n   4 ,   2 0 2 5   A cc ep ted   J u n   1 0 ,   2 0 2 5       Hig h   p e rf o rm a n c e   c o m p u ti n g   ( HP C)  i n   e m b e d d e d   sy ste m is  p a rti c u larly   re lev a n w it h   th e   rise   o f   a rti f icia l   in telli g e n c e   (A I)  a n d   m a c h in e   lea rn in g   a th e   e d g e .   De e p   lea rn in g   m o d e ls  re q u ire  su b sta n ti a l   c o m p u tatio n a p o w e r,   a n d   r u n n i n g   th e se   m o d e ls  o n   e m b e d d e d   sy ste m w it h   li m it e d   re so u rc e p o se sig n if ica n c h a ll e n g e s.  T h e   e n e rg y - e ff icie n n a tu re   o f   f ield - p ro g ra m m a b le  g a te   a rra y (F P G A s) ,   c o u p led   w it h   th e ir  a d a p tab il it y ,   p o siti o n t h e m   a c o m p e ll in g   c h o ice f o o p ti m izin g   th e   p e rf o rm a n c e   o sp a rse   m a tri x - v e c to m u lt ip li c a ti o n   (S p M V ) ,   w h ich   p lay a   sig n i f ica n ro le  in   v a rio u s   c o m p u tatio n a tas k with in   th e se   f ield s.  T h is  a rti c le  i n i ti a ll y   d id   a n a ly sis  to   f in d   a   p o w e a n d   d e la y   e ff ici e n S p M V   m o d e k e rn e u sin g   h ig h   lev e s y n th e sis   (HL S o p ti m iza t io n w h ich   i n c o r p o ra tes   lo o p   p ip e li n i n g ,   va ried   m e m o r y   a c c e ss   p a tt e rn s,  a n d   d a ta  p a rti ti o n in g   stra teg ies ,   a ll   o f   th is  e x e rt  in f lu e n c e   o n   th e   u n d e rly in g   h a rd w a r e   a rc h it e c tu re .   A f t e id e n ti f y in g   th e   m in im u m   re so u rc e   u ti li z a ti o n   m o d e l,   w e   p ro p o se   a n   a p p ro x im a te  m o d e a lg o rit h m   o n   S p M V   k e rn e to   r e d u c e   th e   e x e c u ti o n   ti m e   in   X il in x   Zy n q - 7 0 0 0   F P G A .   T h e   e x p e ri m e n ta re su lt s   sh o w th a t   th e   F P G A   p o w e r   c o n su m p ti o n   w a re d u c e d   b y   5 0 %   w h e n   c o m p a re d   to   a   p re v io u sly   im p le m e n ted   stre a m in g   d a ta f lo w   e n g in e   (S DE)  f lo w ,   a n d   th e   p ro p o se d   a p p ro x im a te  m o d e i m p ro v e d   p e rf o r m a n c e   b y   2 ×   ti m e c o m p a re d   to   th a o f   o rig in a c o m p re ss e d   sp a rse   ro w   (CS R)   sp a rse   m a tri x .   K ey w o r d s :   Field - p r o g r a m m ab le  g ate  ar r ay   Hig h   lev el  s y n t h esi s   Hig h   p er f o r m a n ce   co m p u t in g   Op ti m izatio n   m e th o d s   Sp ar s m atr i x - v ec to r   m u ltip licatio n   T h is i a n   o p e n   a c c e ss   a rticle   u n d e r th e   CC B Y - SA   li c e n se .     C o r r e s p o nd ing   A uth o r :   A ld e n   C .   S h aj i   Dep ar t m en t o f   E lectr o n ics a n d   C o m m u n icat io n ,   Ma u la n A z ad   Natio n al  I n s ti tu te  o f   T ec h n o lo g y   B h o p al,   I n d ia   E m ail: a ld en c s h aj i@ g m ail. co m       1.   I NT RO D UCT I O N   Hig h   p er f o r m a n ce   co m p u ti n g   ( HP C )   p la y s   v ital   r o le  in   t h f ield   o f   ar ti f icia i n telli g e n ce   ( A I )   b y   p r o v id in g   co m p u tat io n al  p o wer   r eq u ir ed   f o r   tr ain i n g   an d   r u n n i n g   co m p lex   m o d els.  M an y   HP C   s y s te m s   in co r p o r ate  s p ec ialized   h ar d w ar ac ce ler ato r s ,   s u c h   as   f ield - p r o g r a m m ab le  g ate  ar r a y s   ( F P GA s )   o r   g r ap h ic s   p r o ce s s in g   u n its   ( GP Us),   to   o f f lo ad   f lo ati n g - p o i n co m p u t atio n s   f r o m   tr ad itio n al  C P Us.   T h ese  ac ce ler ato r s   ar o p tim ized   f o r   p ar allel  p r o ce s s in g   a n d   ca n   s ig n i f ica n tl y   b o o s p er f o r m an ce   f o r   f lo a tin g - p o i n t - in te n s iv e   w o r k lo ad s   [ 1 ] .   Flo atin g - p o in t   ac ce ler ato r s   ar en g i n ee r ed   t o   d eliv er   r o b u s co m p u tatio n a ca p ab ilit ies  w h ile   also   tak in g   in to   ac co u n e n er g y   e f f icie n c y ,   cr itical  co n s id er atio n   in   HP C   s y s te m s   w h er p o w er   co n s u m p tio n   an d   h ea m a n ag e m e n ar m aj o r   ch allen g e s .   A l s o ,   s o m o f   th k e y   c h alle n g e s   ass o ciate d   w it h   s p ar s m atr i x - v ec to r   m u lt ip licatio n   ( Sp MV )   co m p u tat io n   o n   FP GAs  ar ir r eg u lar   m e m o r y   ac ce s s   p atter n s ,   lo ad   im b ala n ce ,   li m ited   on - ch ip   m e m o r y   r eso u r ce s   an d   en er g y   e f f icie n c y .   T h f lex ib ilit y   o f   FP G A s ,   b ein g   p r o g r a m m ab l e   h ar d w ar e,   allo w s   f o r   th cu s to m izat io n   o f   f lo atin g - p o in t   ac ce ler ato r s   to   s u it  s p ec if i w o r k lo ad s .   T h is   ad ap tab ilit y   g i v ad v an ta g in   HP C   ap p licatio n s ,   b y   p r o v id in g   s o l u tio n s   th at  ca n   d eliv er   o p ti m al  p er f o r m a n ce   f o r   d iv er s co m p u ta tio n al  ta s k s   [ 2 ] ,   [ 3 ] .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4864   I n t J   R ec o n f i g u r ab le  &   E m b ed d ed   Sy s t ,   Vo l.  14 ,   No .   2 J u l y   20 25 375 - 3 8 7   376   Sp MV   is   f o u n d atio n a o p er atio n   w ith in   HP C   a n d   h o l d s   v ital  s i g n i f ican ce   ac r o s s   s cien t if ic,   en g i n ee r i n g ,   a n d   d ata  an al y s is   d o m ai n s .   T h is   o p er atio n   en tails   t h m u ltip licatio n   o f   s p ar s m atr i x   d is tin g u is h ed   b y   s u b s ta n tial   v o lu m o f   ze r o   elem e n t s   w it h   d en s v ec to r .   Sp MV   u tili t y   ex te n d s   to   task s   s u c h   as   s o l v in g   lin ea r   eq u atio n   s y s te m s ,   s i m u lati n g   p h y s ical  p h en o m en a,   an d   co n d u cti n g   g r ap h   co m p u tatio n s ,   u n d er - s co r i n g   i ts   ess e n tial  r o le  in   d iv er s ap p licatio n s   [ 4 ] .   C u s to m   m e m o r y   ac ce s s   p atter n s   ar cr itical  f o r   i m p r o v i n g   t h p er f o r m a n ce   o f   Sp MV   o n   e m b ed d ed   FP GA s .   B y   ta ilo r in g   m e m o r y   h ier ar ch ie s   an d   d ata  s tr u ctu r e s ,   FP GAs  ca n   m in i m ize  m e m o r y   late n c y   an d   m a x i m ize  b an d w id th ,   le ad in g   to   en h a n ce d   ef f icien c y   i n   Sp MV   co m p u tati o n s   [ 5 ] .   Sp MV   in v o lv e s   ac ce s s in g   n o n - co n ti g u o u s   m e m o r y   lo ca tio n s   o w i n g   to   th s p ar s n at u r o f   m atr ices .   T h is   ir r eg u lar   m e m o r y   ac ce s s   p atter n   ca n   lead   to   ca ch m is s es,  ca u s i n g   in cr ea s ed   m e m o r y   late n c y   a n d   af f ec tin g   t h o v er all  p er f o r m a n ce   o f   b o th   C P Us  a n d   GP Us  [ 6 ] ,   [ 7 ] .   I n   ad d itio n ,   t h w o r k l o ad   in   Sp MV   is   n o t   ev en l y   d is tr ib u ted   a m o n g   t h e   p r o ce s s in g   ele m e n ts   o w i n g   t o   th v ar y i n g   s p ar s it y   o f   t h m atr ices.  T h is   lo ad   i m b alan ce   ca n   lead   to   in e f f ici en u tili za t io n   o f   r eso u r ce s ,   e s p ec iall y   o n   GP Us  w h er th r ea d - lev el   p ar allelis m   is   cr u cial.   C o n s eq u en tl y ,   C P Us  an d   GP Us  m a y   n o b th m o s s u itab le  p lat f o r m s   f o r   ac ce ler atin g   Sp MV   k er n el s .   I n   co n tr ast,  FP GAs  e m er g as  p r o m i s i n g   s o l u ti o n   f o r   Sp MV   ac ce ler atio n .   FP GA s   b o ast  lar g e     o f f - c h ip   s to r ag b an d w id t h ,   a llo w i n g   th e m   to   e f f icie n tl y   h a n d le  m e m o r y   b o u n d   ap p licatio n s .   T h eir   tailo r ed   lo g ical  co m p o n e n ts   a n d   ef f ici en f lo atin g - p o in co m p u tatio n s   en h an ce   it s   s ta n d in g   e v en   m o r in   FP GA s   a s   a n   attr ac tiv p lat f o r m   f o r   ac ce ler atin g   Sp MV   co m p u tatio n s   [ 8 ] .   R esear ch   f i n d in g s   i n d icate   th at  h i g h   le v el  s y n t h es i s   ( HL S)  h o ld s   p r o m i s f o r   f u r n is h in g     h ig h - p er f o r m a n ce ,   en er g y - e f f icie n s o l u tio n s ,   th er eb y   ex p ed itin g   ti m e - to - m ar k et  an d   tack li n g   th e   co m p le x itie s   o f   m o d er n   s y s te m s   co n cu r r en tl y   [ 9 ] ,   [ 1 0 ] .   Ou r   in v est ig at io n   f o cu s e s   o n   ex p lo r in g   th e   ap p licatio n   o f   H L S,  tec h n iq u th at   is   g ai n i n g   p o p u l ar it y   f o r   ac ce ler atin g   al g o r it h m s   o n   e m b ed d ed   h eter o g e n eo u s   p lat f o r m s .   Af t er   f in d i n g   t h e f f ic ien o p ti m i za tio n   tech n iq u w ca lc u late d   th k er n el  p o w er   co n s u m p tio n   in   t h e m b ed d ed   FP GA ,   th e n   p r o p o s t w o   n o v el  ap p r o x i m ate  co m p r es s ed   s p ec tr al  r eg r ess io n   ( C SR )   m atr ix   to   m i n i m ize  th ex ec u t io n   ti m f o r   th k er n e l i n   th h ar d w ar e.   T h r em ai n d er   o f   t h is   p ap er   is   o r g an ized   as  f o llo w s .   Sectio n   2   p r o v id es  b ac k g r o u n d   in f o r m atio n   an d   r elate d   w o r k   o n   th Sp MV   an d   HL f lo w s .   Sec tio n   3   p r e s en ts   t h m et h o d o lo g y   u s ed   in   t h is   s tu d y   p ap er   to   b r in g   o u t   th r e s u l ts ,   i n clu d i n g   t h u s ag o f   p r ag m as  a n d   n o v el  ap p r o x i m atio n   m o d el  al g o r ith m .   T h r esu l an d   d is cu s s io n   ar e   p r esen ted   in   s ec tio n   4 .   T h p ap er   co n clu d es  w it h   t h co n c lu s io n   a n d   f u t u r s co p in   s ec tio n   5 .       2.   T H E   CO M P RE H E NS I VE   T H E O RE T I CA L   B ASI S   2 . 1 .     Sp a rse  m a t rix - v ec t o m ultiplica t io n   Sp ar s m atr ice s ,   in   co n tr ast   to   d en s m atr ices  th at   h o l d   s u b s ta n tial   a m o u n o f   r ed u n d an t   in f o r m atio n ,   p r i m ar il y   co n s i s t   o f   ze r o   v alu e s ,   lead in g   to   m o r ef f icie n m e m o r y   u s ag e.   Sp MV   in v o lv e s   th e   m u ltip licatio n   o f   s p ar s m a t r ix   w it h   d en s v ec to r ,   u lti m atel y   p r o d u cin g   n e w   v ec to r   th at  r ep r esen t s   t h e   lin ea r   tr an s f o r m atio n   o f   t h o r ig i n al  d ata  ex p r ess ed   as ( 1 ) .     =  × ,  = 0       0    = 0   ( 1 )     Sp ar s m atr ices  ar t y p icall y   en co d ed   in   co n d en s ed   f o r m at s   th at  o n l y   co n tai n   t h n o n - ze r o   m e m b er s   in   o r d er   t o   r estrict  th d ata   c o llectio n   n ee d ed .   T h r atio   o f   to tal  ze r o   elem en ts   to   to tal  e le m e n ts   in   s p ar s e   m atr i x   d eter m i n es  th m at r i x 's  s p ar s it y .   Fi g u r 1   p r o v id es  an   o v er v ie w   o f   th e   Sp MV   p r o ce s s   alo n g   w it h   t h e   co m m o n   co m p r ess ed   f o r m at s   u s ed   to   s to r e   s p ar s m atr ice s .   T h ex am p le  Sp MV   k er n e in   Fig u r e   1 ( a)   is   r ep r esen ted   u s i n g   t h r ee   co m m o n l y   u s ed   co m p r ess ed   f o r m ats   C OOr d in ate  ( C OO) ,   c o m p r ess ed   s p ar s co lu m n   ( C SC ) ,   a n d   co m p r ess ed   s p ar s r o w   ( C S R )   as  s h o w n   i n   Fi g u r e   1 ( b ) .   Ou o f   t h ese  w id el y   u s ed   is   C S R   f o r m at.   T h v al  v ec to r   h o ld s   th n o n - ze r o   elem e n ts   m en t io n ed   b y   n n z   d eter m i n es  t h eir   s ize  an d   th eir   co r r esp o n d in g   co lu m n   i n d ices  ar s av ed   in   c o v ec to r .   I n   p tr   v ec to r ,   th d i f f er en ce   b et w ee n   ad j ac en ce lls   g i v es  t h n o .   o f   n o n - ze r o   ele m e n ts   ( nnz )   p r esen i n   co r r esp o n d in g   r o w   in   s p ar s m atr ix .   T h C S R   f o r m a is   ap p r o p r iate   f o r   co m p u ti n g   w it h   s tr ea m i n g   d ata  an d   o n l y   r eq u ir es  b r ie f   p r ep ar atio n   s ta g [ 1 1 ] .   A l s o ,   C SR   r ed u ce   t h m e m o r y   n ee d ed   f r o m   O( m × n )   to   O( 2 n n z +m )   d u to   th is   w h av u s ed   it i n   o u r   w o r k .   Sp MV   is   v er s atile  o p er atio n   w it h   ap p licatio n s   in   w id e   r an g o f   f ie ld s ,   o f f er i n g   co m p u tat io n al   ef f icien c y   an d   m e m o r y   s a v i n g s   w h en   d ea lin g   w it h   s p ar s d ata  s tr u ctu r es.  I ts   b r o ad   ap p licab ilit y   m ak e s   it  f u n d a m en ta o p er atio n   in   v ar io u s   s cien tific ,   en g i n ee r i n g ,   an d   d ata - d r iv en   d is cip li n es.  Sp MV   ap p licatio n   in   co n v o lu tio n al  n eu r al  n et w o r k s   ( C NN)   tr ain in g   is   s h o w n   i n   Fig u r e   2 ,   th is   tr ai n in g   s c h e m w a s   u s ed   in   [ 1 2 ]   to   g et  f a s e x ec u t io n   o f   C NN  o n   GP Us.  Du r i n g   th f o r w ar d   p ass   o f   C N tr ain i n g ,   Sp MV   is   ap p lied   w h en   co m p u ti n g   t h o u tp u o f   co n v o lu tio n al  la y er s .   T h s p ar s w ei g h m atr ice s   ar m u ltip lie d   b y   th in p u d ata   v ec to r s ,   an d   th r es u lti n g   s p a r s v ec to r   co n tr ib u tes  to   t h ac tiv atio n   o f   n e u r o n s   in   s u b s e q u en la y er s .   I n   t h e   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   R ec o n f i g u r ab le  &   E m b ed d ed   Sy s t     I SS N:   2089 - 4864       A n   a p p r o xima te  mo d el  S p MV  o n   F P GA   a s s is tin g   HLS   o p tim iz a tio n s   fo r   lo w   p o w er   … ( A ld en   C .   S h a ji )   377   b ac k w ar d   p as s   ( b ac k p r o p ag atio n )   d u r i n g   tr ain i n g ,   g r ad ie n ts   w it h   r esp ec to   t h w e i g h t s   ar ca lc u lated   ef f icien tl y ,   tak in g   ad v a n ta g o f   t h s p ar s it y   i n   b o th   t h in p u t   d ata  an d   t h w ei g h m atr ice s .   T h is   en ab les   f a s ter   u p d ates to   th w ei g h ts   d u r i n g   o p tim izatio n .           ( a)   ( b )     Fig u r 1 .   Sp ar s m atr ix - v ec to r   m u l tip licatio n   a n d   co n v e n tio n al  co m p r es s   f o r m at  ( a)   an   ex a m p le  o f   Sp MV   an d   ( b )   co n v en tio n a l c o m p r es s ed   f o r m at s           Fig u r 2 .   Sp MV   ap p licatio n   in   C NN  tr ain in g       2 . 2 .     H i g lev el  s y nthesis   Vitis   H L is   to o p r o v id ed   b y   Xili n x   th a tak e s   h i g h - lev e C   o r   C ++   f u n ctio n s   an d   tr an s l ates  th e m   in to   R T L   co d e ,   w h ic h   ca n   th e n   b im p le m en ted   in   th p r o g r a m m ab le  lo g ic  r eg io n   o f   s y s te m   o n   ch ip   ( So C ) .   I g en er ates  h ar d w ar s o l u tio n   b y   co n s id er in g   th e   d e f i n ed   tar g et  f lo w ,   d ef a u lt  to o s ettin g s ,   d esi g n   co n s tr ain ts ,   an d   o p ti m izatio n   p r ag m a s   p r o v id ed .   Op tim iz atio n   d ir ec tiv es  ar u tili ze d   to   cu s to m ize  an d   m an a g t h i n ter n al  lo g ic  a n d   in p u t/o u tp u p o r ts   i m p le m en t atio n ,   s u p er s ed in g   th to o l’ s   d ef au lt  ac tio n s   a n d   co n f i g u r atio n s .   T o   attain   o p ti m al  p er f o r m a n ce   f r o m   th h a r d w ar g en er ated ,   th HL to o n ee d s   to   id en tify   an d   u tili ze   p ar alleli s m   i n h er en in   s eq u e n tial  co d e,   en h a n cin g   o v er all  p er f o r m an ce .   Sp MV   p s eu d o   co d e   i m p le m en ted   u s i n g   HL S is   s h o w n   in   F ig u r 3   [ 8 ] .           Fig u r 3 .   Sp MV   ke r n el  p s e u d o   co d in   HL S e n v ir o n m e n t   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4864   I n t J   R ec o n f i g u r ab le  &   E m b ed d ed   Sy s t ,   Vo l.  14 ,   No .   2 J u l y   20 25 375 - 3 8 7   378   I n   h i g h   le v el  la n g u a g p r o g r a m s ,   t h ar r a y s   ar ess e n tia l   f o r   s to r in g   a n d   m a n ag in g   d ata.   W h en   tr an s lati n g   t h is   to   h ar d w ar e,   a r r ay s   ar r ea lized   as  eith er   m e m o r y   o r   r eg is ter s   d u r i n g   s y n t h esi s .   Me m o r y   ca n   b eith er   lo ca o r   g lo b al,   w i th   g lo b al  m e m o r y   o f te n   c o r r esp o n d in g   to   d o u b le  d ata  r ate  ( DDR)   o r   h ig h - b an d w id t h   m e m o r y   ( HB M)   m e m o r y   b an k s .   Acc ess in g   g l o b al   m e m o r y   in c u r s   h i g h er   l aten c y   an d   m u ltip le   c y cles,  w h er ea s   lo ca m e m o r y   ac ce s s   is   f as ter   an d   t y p icall y   co m p leted   w it h in   f e w   c y cles .   E f f icie n m e m o r y   acces s   is   e s s e n tial  to   m i n i m i ze   th o v er h ea d   as s o ciate d   w it h   ac ce s s i n g   g lo b al  m e m o r y .   On s tr ateg y   f o r   o p tim izatio n   i n v o l v es  co n s o li d atin g   ac ce s s ,   m ax i m is i n g   co n s ec u ti v ac ce s s e s   to   en ab le  b u r s tin g .   B u r s ac ce s s   ef f ec tiv e l y   m a s k s   m e m o r y   ac ce s s   late n c y   a n d   en h a n ce s   m e m o r y   b an d w id t h .   W h ile  t h p r o ce s s   o f   b lo ck s   o f   d ata,   s ev er al  lo o p s   o r   n ested   lo o p s   ar e   n ee d ed .   W ith   th co m b i n atio n   o f   m icr o - le v el  H L p r ag m as,  it  ca n   p er f o r m   u n r o ll,  p ip elin o p er a tio n s   f o r   lo o p   o r   n ested   lo o p s   [ 1 3 ] .   HL to o ls   ap p l y   v ar io u s   o p tim i za tio n s   to   i m p r o v th p er f o r m a n ce ,   ar ea ,   an d   p o w er   ch a r ac ter is tics   o f   th g e n er ated   h ar d w ar e.   HL S   to o ls   o f te n   p r o v id s i m u latio n   an d   v er if ica tio n   ca p a b ilit ies,  it  h elp s   to   s i m u late  t h b eh av io u r   o f   th e   g en er ated   h ar d w ar b ef o r th ac tu al  s y n t h e s is .   T h o u tp u o f   HL ca n   b e   tar g eted   f o r   i m p le m e n tatio n   o n   FP GAs  f o r   r ap id   p r o t o ty p i n g   p r o v id in g   f lex ib il it y   i n   th ch o ice  o f   h ar d w ar p latf o r m .     2 . 3 .     Rela t ed  wo rk   T h co n ce p o f   s p ar s m atr ic es  an d   r elate d   o p er atio n s   lik e   Sp MV   ca n   b tr ac ed   b ac k   t o   th ea r l y   d ay s   o f   n u m er ical   co m p u t in g   an d   f i n ite  ele m e n an al y s i s .   Var io u s   alg o r it h m s   an d   s t o r ag f o r m ats  w er e   d ev elo p ed   to   ac ce ler ate  Sp M V,   f i n d in g   u n iq u ch ar ac ter is tics   o f   s p ar s m atr ice s   in   [ 1 4 ] ,   [ 1 5 ] .   I n   v ar io u s   s tu d ie s   th e y   h a v i n v e s ti g ated   th o p ti m izat io n   o f   S p MV   o n   FP GAs [ 1 6 ] ,   [ 1 7 ] .   T h m aj o r ity   o f   t h ese  r esear c h   en d ea v o r s   co n ce n tr ate  o n   le v er ag i n g   h i g h - e n d   FP G A s   an d   i m p le m e n ti n g   ap p r o ac h es  g ea r ed   to w ar d s   p r o ce s s in g   b i g   d ata  ef f icie n tl y   in   [ 1 8 ] .   Du   et  a l.   [ 1 9 ]   in v es ti g ate  s p ar s m atr i x   f o r m at  s p ec if icall y   d e s i g n ed   f o r   HB M.   A n o t h er   co m p ar ab le  ef f o r t,  R eDE SK  [ 2 0 ]   h as  ex a m in ed   Sp MV   o p ti m iza tio n s   in   t h co n te x o f   h eter o g e n eo u s   co m p u ti n g ,   it  i s   d esig n ed   to   en ab le  s tr ea m in g   p r o ce s s   o n   th FP GA   s id an d   d ata  p r ef etch i n g   o n   th C P s id e.   Desig n   o f   b a n d w id th   e f f icien Sp MV   o n   FP G A   is   t h m a i n   th e m i n   [ 5 ] [ 2 1 ] .   Fo w er s   et  a l.   [ 2 2 ]   p r o p o s ed   an   ar ch itectu r f o r   Sp MV   b ased   o n   F P GA ,   alo n g   w i th   tech n iq u f o r   s p ar s m atr i x   d ec o d in g   to   lev er ag p ar alleli s m   ac r o s s   m atr ix   r o w s .   T h d esig n   as s u m e s   th p r ese n ce   o f   t w o   d i s ti n ct   DR A m o d u les   in   th s y s te m ,   f ea tu r t h at  m a y   n o t b co m m o n l y   f o u n d   in   m a n y   e x is tin g   e m b ed d ed   s y s te m s .   Ho s s ei n ab ad y   an d   Nu n ez - Ya n ez   [ 8 ]   in v es tig a ted   o n   h o p ar alleliza tio n   an d   p ip elin i n g   ca n   b ef f ec tiv e l y   ap p lied   u s i n g   H L to   in cr ea s t h p er f o r m a n c o f   Sp MV   o n   FP G A   p lat f o r m s .   T h is   in cl u d es   s tr ateg ie s   f o r   o p ti m izi n g   d ata  m o v e m en an d   m e m o r y   ac c ess es.  Gar ib o tti  et  a l .   [ 1 0 ]   s u g g e s ted   e m p lo y in g   co m m er cial  H L to o ls   alo n g   w it h   d y n a m ic  an a l y s is   to   p r o d u ce   h ig h er   q u alit y   d esi g n s .   C r ea tin g   an   ef f ec tiv e   f lo ati n g - p o in ac c u m u la to r ,   w h ic h   en co m p a s s e s   b o th   m u ltip lier   an d   ad d er   co m p o n e n ts ,   to   i m p r o v t h e   p er f o r m a n ce   o f   Sp MV   is   th o b j ec tiv in   [ 2 3 ] ,   [ 2 4 ] .   R ec en tl y ,   w o r k   [ 2 5 ]   c o m p ar es  th Sp MV   ca lcu latio n ,   s h o w ca s in g   t h p er f o r m an ce   a n d   en er g y   co m p u tatio n   o n   GP an d   FP G A .   Fu r t h er m o r e,   c u r r en t o p ti m izatio n s   p r im ar il y   tar g et  h al f   p r ec is io n   f lo ati n g   p o in d ata  ty p es,  o v er l o o k in g   s u p p o r f o r   r e d u ce d   p r ec is io n   f i x ed   p o in t   ar ith m etic  [ 2 6 ] .   Ho w ev er ,   r ec en s tu d ies   h a v i n v esti g ated   s tr ateg ies  f o r   b len d i n g   s i n g le  a n d   d o u b le  p r ec is io n   f lo ati n g - p o in t a r it h m etic  [ 2 7 ] .   Fin all y ,   i n   co n tr ast  to   o th er   w o r k s ,   th i s   p ap er   p r o p o s ed   a   n o v el  ap p r o x i m atio n   m o d el  Sp MV   to   r ed u ce   th p o w er   an d   ex ec u t io n   ti m e,   u s i n g   w h ic h   ca n   s i g n i f ica n tl y   tr an s f o r m   th FP GA   ac ce ler ato r .   W h av co m p ar ed   th p o w er   co n s u m p tio n   a n d   ex ec u t io n   ti m o f   s a m m atr ices  w it h   t h i m p le m en ta tio n   i n   [ 8 ]   in   t h r es u lt s .   E x p er i m e n tal  w o r k   o n   H L p r ag m as   an d   a p p r o x im a te  al g o r ith m s   ar d is cu s s ed   i n   d etail  i n   f u r t h er   s ec tio n s .       3.   M E T H O D   AND  E XP E R I M E NT AL   S E T UP   I n   th is   s ec tio n ,   th d etails  o f   th d esig n   m o d el  u s ed   f o r   Sp MV   im p le m en ta tio n   o n   FP GA   ar p r o v id ed .   I n itiall y ,   w f in d   o u t h tr ad e - o f f   b et w ee n   e x ec u tio n   ti m a n d   th e   r eso u r ce   u tili za tio n   u s in g   th e   HL S   o p ti m izatio n   tec h n iq u es .   T h en   w s elec t h e f f icie n tec h n iq u b ased   o n   h ar d w ar e m u latio n   a n d   i m p le m en ta tio n .   Af ter   th a we  ap p lied   th ap p r o x im atio n   m o d el  al g o r ith m   to   t h s p ar s e   m atr ix   a n d   d id   th an al y s is .   W h a v co m p ar ed   th r es u lt s   o b tain ed   i n   o u r   tar g et  h ar d w ar Z y b o   Z 7 - 2 0   b o a r d   w ith   Xili n x   Z C U1 0 2   ev alu atio n   b o ar d   u s ed   in   [ 8 ] .     3 . 1 .     H i g h lev el  s y nthesis   o pti m iza t io t ec hn iqu e s   Utilizatio n   o f   H L to o ls   is   to   h ar n e s s   t h p r o d u cti v it y   b en e f its   o f   tr an s lati n g   C /C ++   co d in to   R T L   f o r   h ar d w ar e,   o r   o b j ec tiv is   to   ac ce ler ate  s u b s et   o f   C /C ++   al g o r ith m   b y   r u n n i n g   it  o n   s p ec ialize d   h ar d w ar b u ilt  w it h   p r o g r a m m i n g   lo g ic.   Fu n ctio n s   i m p le m en ted   in   C / C ++   a n d   tr a n s f o r m ed   i n to   c u s to m   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   R ec o n f i g u r ab le  &   E m b ed d ed   Sy s t     I SS N:   2089 - 4864       A n   a p p r o xima te  mo d el  S p MV  o n   F P GA   a s s is tin g   HLS   o p tim iz a tio n s   fo r   lo w   p o w er   … ( A ld en   C .   S h a ji )   379   h ar d w ar u s i n g   p r o g r a m m ab l lo g ic  ca n   o p er ate  at  n o tab le   h ig h er   s p ee d s   co m p ar ed   to   w h at  is   attai n ab le  o n   t y p ical  GP U/C P s etu p s ,   r esu lti n g   in   h i g h er   th r o u g h p u an d   p er f o r m a n ce .   T h p r o p o s ed   Sp MV   i m p le m en ta tio n   h a v 3   p r i m a r y   tas k s   in v o lv ed Ta s A r e ad in g   o f   d ata  i n to   th e   FP G m e m o r y Ta s B in itiat in g   t h s tr ea m   co m p u ta tio n   en g i n e ,   an d   Ta s C tr a n s f er r i n g   o u tp u o f   FP G A   to   m ai n   m e m o r y T h f o llo w in g   o p ti m izatio n   tec h n i q u es a r u s ed   to   i m p le m e n t t h Sp MV   co m p u tatio n .     3 . 1 . 1 .   L o o pip elinin g   L o o p s   ar cr u cial  co n s tr u c ts   w i th i n   a n   Sp MV .   Sin ce   lo o p   b o d y   i s   e x ec u ted   r ep ea t ed ly ,   th i s   ch ar ac ter is tic  ca n   b ef f ec ti v el y   lev er a g ed   to   en h an ce   p ar allelis m   an d   o p ti m ize  p er f o r m an ce .   T o   en h an ce   th r o u g h p u a n d   m a k m o r e f f icien u s o f   co m p u tatio n al   r eso u r ce s ,   v al u ab le  ap p r o ac h   i s   to   i n tr o d u ce   p ip elin in g   in   o p er ato r s ,   lo o p s   an d   f u n ctio n s .   Fig u r e   4   s h o w s   th ex a m p l f lo w   o f   3   task s   ( ea ch   to o k   1 0   u n it s   to   co m p lete)   b ef o r an d   a f ter   p ip elin in g .   T o   f i n is h   t h f ir s t   w o r k lo ad   it   to o k   3 0   u n it s ,   i s   ca lled   th iter atio n   laten c y .   Af ter   th co m p let io n   o f   f ir s w o r k lo ad ,   n ex t wo   w o r k lo ad s   o n l y   ta k 1 0   u n its   ea c h ,   ca lled   th e   i n itiat io n   i n ter v a ( I I ) .   T h o v er all  co m p letio n   o f   al t h w o r k lo ad s   i s   ca lled   t h to tal  laten c y ,   w h ich   i s   5 0   h er e.   T h g en er al  f o r m u la  f o r   f i n d in g   to tal  laten c y   f o r   n o .   o f   w o r k lo ad s   is   g iv e n   i n   ( 2 ) .           =        +    × ( 1 )   ( 2 )     I n   p ip elin ed   f u n ctio n   o r   lo o p ,   n e w   i n p u t s   ca n   b p r o ce s s ed   ev er y   s p ec if ied   II  clo c k   c y cles.  II =1   i m p lies   p r o ce s s in g   n e w   i n p u e v er y   clo c k   c y cle.   T h m a x i m u m   t h r o u g h p u t h at  p ip e lin ed   lo o p   ca n   r ea ch   w it h o u u n r o lli n g   is   attain ed   at  th is   p o in t.  So m eti m es  th i s   n o p o s s ib le,   d u to   r eso u r ce   c o n s tr ain ts   a n d   lo o p   ca r r ied   d ep en d en cies.  T h p ip elin ed   lo o p   w i ll  a u to m atica ll y   u n w in d   a n y   n e s ti n g   lo o p s .   co m m o n   i s s u i n   p ip elin ed   lo o p   is   m e m o r y   co n f lict.  T h er ar f o u r   lo o p s   in   t h k er n e co d in   w h ich   w a p p lied   p ip elin o n   ev er y   lo o p   w it h   II =1 ,   co n s id er ed   b o th   th ca s es o f   w i th   a n d   w it h o u t p ip elin i n g   t h lo o p s .           Fig u r 4 .   P ip elin in g   f lo w   f o r   th r ee   task s       P ip elin in g   r ed u ce s   th e   late n cy   o f   th e   co m p u ta tio n   b y   allo w i n g   t h cr ea tio n   o f   n e w   lo o p   iter atio n s   b ef o r th co m p letio n   o f   p r ev io u s   o n es.  T h is   i s   cr u cial  i n   Sp MV   w h er th d ata  d ep en d en cie s   ar o f te n   s p ar s e,   an d   o v er lap p in g   co m p u tatio n s   ca n   s ig n i f ica n tl y   i m p r o v o v er all  p er f o r m a n ce .   I ca n   c o n tr ib u te  to   ac h iev in g   h ig h er   clo ck   f r eq u e n cies b y   b r ea k i n g   d o w n   t h co m p u tat io n   i n to   s m aller ,   m o r m an a g ea b le  s ta g es.     3 . 1 . 2 .   AXI  bu rst  t ra ns f er   B u r s tin g   i s   an   o p ti m izatio n   s tr ateg y   ai m ed   at  s m ar tl y   co n s o lid atin g   m e m o r y   ac ce s s es  t o   DDR   i n   o r d er   to   r ed u ce   laten c y   a n d   i n cr ea s t h r o u g h p u b an d w id t h .   T h A XI 4   p r o to co l' s   b u r s f u n ctio n alit y   b o o s ts   th lo ad - s to r f u n ct io n s   t h r o u g h p u b y   e n ab lin g   t h e m   to   r ea d   o r   w r ite  a   lar g g r o u p   o f   d ata  to   o r   f r o m   t h e   g lo b al  m e m o r y   in   s in g le  r eq u est.  T h th r o u g h p u in cr e ases   w it h   th s ize  o f   th d at b ein g   tr an s f er r ed .   Op ti m i s in g   d i f f er en HL S i n te r f ac m e tr ics,  s u c h   as   p o r w id th ,   b u r s t a cc es s ,   late n c y ,   n u m e r o u s   p o r ts ,   an d   t h e   n u m b er   o f   u n f i n i s h ed   r ea d s   an d   w r ite s ,   is   n ec es s ar y   to   d ev elo p   ef f ec tiv lo ad - s to r f u n ct io n s .   Utilizi n g   lo ca b u f f er s   to   s to r s e g m en t s   o f   t h m atr i x   o r   v ec to r   d u r in g   co m p u tatio n   p r o v e s   b en e f icial   b y   m iti g ati n g   m e m o r y   ac ce s s   late n c y   a n d   en h a n cin g   d ata  r eu s e.   T h is   s tr ateg y   i n v o l v es   te m p o r ar il y   h o ld i n g   s u b s et s   o f   t h d ata   w it h i n   th f ast  o n - c h ip   m e m o r y ,   allo w in g   t h p r o ce s s o r   t o   ac ce s s   an d   m a n ip u late  th e   in f o r m a tio n   m o r e   ef f icien tl y .   B y   m in i m izi n g   t h n ee d   f o r   f r eq u e n o f f - ch i p   m e m o r y   ac ce s s e s ,   lo ca b u f f er s   co n tr ib u te  to   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4864   I n t J   R ec o n f i g u r ab le  &   E m b ed d ed   Sy s t ,   Vo l.  14 ,   No .   2 J u l y   20 25 375 - 3 8 7   380   o p tim izin g   o v er all  co m p u tati o n   p er f o r m a n ce .   I n   t h h ar d w ar w h a v f o u r   6 4 - b it  AXI   h ig h - p er f o r m a n ce   m e m o r y   p o r ts   to   tr an s f er   d ata  f r o m   p r o g r a m m i n g   lo g ic  to   D DR   m e m o r y .     3 . 1 . 3 .   L o o un ro llin g   A i m s   to   i m p r o v e   p er f o r m a n ce   b y   r ed u ci n g   lo o p   o v er h e ad   an d   in cr ea s i n g   p ar allelis m .   I n   lo o p   u n r o lli n g   m u ltip le  it er atio n s   o f   th s a m lo o p   ar e   p er f o r m e d   w i th i n   s in g le  iter atio n .   Un r o llin g   f ac to r   is   th e   n o .   o f   iter atio n s   to   ex ec u te  in   ea ch   u n r o lled   iter atio n .   T h l o o p   ca n   b p ar tially   o r   co m p l etel y   u n r o lled   w it h   th UNR OL L   p r ag m a.   Fu ll y   u n r o llin g   m a k e s   d u p licate  o f   th lo o p   b o d y   f o r   ea ch   iter atio n ,   en ab lin g   co n cu r r en o p er atio n   o f   t h wh o le  lo o p .   On   th o th er   h an d ,   p ar tial  u n r o lli n g   e n tail s   s ett in g   f ac to r   to   m a k e   co p ies  o f   th lo o p   b o d y   an d   d ec r ea s th lo o p   iter atio n s   ap p r o p r iately .   T h li m it s   o f   lo o p   m u s t   b k n o w n   at  co m p ile  ti m in   o r d er   to   f u ll y   u n r o ll  it.  L o o p   u n r o llin g   n ee d s   m o r co m p u tatio n   a n d   s to r ag r eso u r ce s   h en ce   it  i s   tr ad e - o f f   b et w ee n   p er f o r m a n ce   a n d   r eso u r ce s .   I n   o u r   e x p er i m e n ts   w i m p l e m en ted   th k er n el  co d w i th   u n r o ll  f ac to r   o f   2   an d   4 .   Th m o s e f f ec tiv u n r o ll  f ac t o r   f o r   lo o p   u n r o llin g   i n   Sp MV   u s i n g   Vit is   H L d ep en d s   o n   t h u n iq u ch ar ac ter is tic s   o f   t h tar g eted   FP GA   ar c h itect u r an d   t h s p ec if ic  at tr ib u tes  o f   t h Sp MV   p r o b lem   b ei n g   ad d r ess ed .   C o n d u cti n g   e x p er i m en ts   w i th   v ar io u s   u n r o ll  f a c t o r s   an d   lev er ag in g   p er f o r m a n ce   p r o f ilin g   th r o u g h   Vitis   H L r ep o r ts   is   cr u cia f o r   id en tify i n g   th o p ti m a co n f i g u r atio n   t h at  m a x i m i ze s   co m p u tatio n al   ef f icien c y .   T h is   iter ativ p r o c ess   en ab les  f in e - t u n in g   an d   cu s to m izat io n ,   en s u r in g   th Sp MV   k er n el  is   tai lo r ed   f o r   o p tim a l p er f o r m a n ce   o n   th s p ec if ic  FP G A   p latf o r m   an d   p r o b lem   d o m ai n .     3 . 1 . 4 .   Arr a y   pa r t it io nin g   I in v o lv e s   b r ea k i n g   d o w n   s in g le  ar r a y   i n to   s m aller ,   i n d ep en d en p ar ts   o r   s u b s et s   s u c h   t h at  ea c h   p ar ca n   b e   im p le m e n ted   as  B R A M,   s o   th at  ca n   ac c ess   th e m   at  th s a m ti m e.   A g g r eg ate  t y p es  ca n   b d iv id ed   in to   s m aller   m e m o r ie s   o r   in to   th eir   co m p o n e n p ar ts ,   w h ic h   in cr ea s e s   th m e m o r y   b an d w id t h   an d   in cr ea s es  t h n u m b er   o f   m e m o r y   ac ce s s e s   o n   ea ch   c y cle.   B lo ck ,   cy c lic,   an d   co m p lete  ar r a y   p ar titi o n in g   ar th th r ee   t y p e s   av ailab le.   T h o p tio n s   lik t y p a n d   d i m   f o r   th m e m o r y   p ar titi o n   p r ag m s p ec if y   t h p ar titi o n   t y p an d   d i m en s io n ,   r esp ec ti v el y .   L ar g ar r a y   s ize  w ill  b s y n th e s ized   in to   B R A Ms  i n   FP GA .   Her w e   d ec lar ed   th v ar iab les  w ith   ar r a y   p ar titi o n   i n   c y clic  f ac to r   w i th   d i m =1 .   Usi n g   # p r ag m H L A R R A Y _ P A R T I T I ON  v ar iab le= x   co m p lete  d i m =1   p ar titi o n s   th i n p u m a tr ix   x   alo n g   it s   r o w s   ( s p ec if ied   b y   d i m =1 ) .   C o m p lete  p ar titi o n in g   is   e m p lo y ed ,   in d icat in g   t h at  ea ch   p ar tit io n   co m p r is e s   a n   e n tire   s et  o f   r o w s   f r o m   t h m atr i x .   T h is   o p t i m izatio n   ai m s   to   b o o s p ar allelis m   b y   en ab li n g   co n cu r r en p r o ce s s in g   o f   m u l tip le  r o w s   w i th i n   th m a tr ix .   W ith in   th co m p u tatio n   lo o p ,   p a r tial  s u m s   ar ca lcu lated   f o r   ea ch   r o w   b y   le v er ag i n g   th p ar titi o n ed   m atr i x   an d   t h in p u v ec to r .   T h is   ap p r o ac h   en h an ce s   p ar allel  ex ec u tio n ,   t h er eb y   o p ti m izi n g   m e m o r y   ac ce s s   p atter n s   a n d   i m p r o v in g   t h o v er all  p er f o r m a n ce   o f   Sp MV   k er n el s   o n   FP G A   p latf o r m s .     3 . 1 . 5 .   B ind   s t o ra g e   I lin k s   co d v ar iab le  to   ce r tain   m e m o r y   t y p in   th R T L .   T h m e m o r y   t y p a s s o ciate d   w it h   th e   ar r ay   i n f lu e n ce s   th n u m b er   an d   k i n d   o f   p o r ts   r eq u ir ed   in   th R T L ,   m a k i n g   th i s   ele m e n i m p o r ta n f o r   th e   ar r ay s   o n   th to p - lev el  f u n c t io n   in ter f ac e.   T h ese  v ar iab le s   m u s u s t h s to r ag e_ t y p e   an d   s to r ag e_ i m p o p tio n s   o f   th B I ND_ ST OR A GE   p r ag m to   s p ec if y   th m e m o r y   t y p an d   i m p le m e n t atio n .   T h laten c y   o p tio n   f o r   B R A Ms  o n   th i n ter f ac en ab les  th m e m o r y   t o   b e   im p le m e n ted   u s i n g   m o r p ip elin ed   s tag es.   T im i n g   i s s u es t h at  ar is d u r i n g   R T L   s y n th e s is   ca n   b ef f ec ti v el y   r eso l v ed   b y   ad d in g   e x t r p ip elin s ta g es.     3 . 2 .     Sp a rse  m a t rix - v ec t o m ultiplica t io n - k er nel   A   k er n el  t y p ica ll y   r e f er s   to   co m p u tatio n al  r o u tin o r   alg o r ith m   t h at  is   s p ec ialized   f o r   p ar ticu lar   o p er atio n .   Sp MV   k er n el  is   s p ec if ic  i m p le m e n tat io n   o r   r o u tin d esig n ed   to   ef f ici en tl y   p er f o r m   t h e   m u ltip licatio n   o f   s p ar s m atr i x   w it h   d en s v ec to r .   Min i m ize  d y n a m ic  m e m o r y   al lo ca tio n s   a n d   d ea llo ca tio n s   d u r i n g   t h co m p u tatio n   to   av o id   u n n ec e s s ar y   o v er h ea d .   A cc ess   p atter n s   s h o u ld   b d esi g n ed   to   m i n i m ize  ca ch m is s es d u r in g   th m u ltip lica tio n   a n d   ac cu m u latio n   s tep s .   T h s o u r ce   co d e   f o r   th Sp M k er n el  is   g iv e n   in   Fi g u r 5   w h ic h   is   r ef er en ce d   f r o m   [ 8 ] .   T h p s eu d o   co d co n tain s   f o u r   f o r   lo o p s ,   in   w h ic h   d ata  f etc h in g   f r o m   th s p ar s m atr i x   is   h ap p en e d   f ir s t,  th e n   it  w ill   u n co m p r e s s   t h C S R   f o r m at  m atr i x   b y   f etc h i n g   ea ch   d ata  v alu f r o m   ea c h   r o w   o f   th m at r ix .   Af ter   g e tti n g   all   th n n z’ s   th e n   m u ltip licatio n   w it h   th co r r esp o n d in g   ele m e n in   th d en s v ec to r   an d   ac cu m u late  t h r esu l t   f r o m   th m u l tip licatio n   s tep   i n to   th co r r esp o n d in g   en tr y   o f   th o u tp u v ec to r .   R ep ea th m u ltip lica tio n   an d   ac cu m u lat io n   s tep s   f o r   all  n o n - ze r o   ele m e n t s   in   th s p ar s e   m a tr ix .   T h last   lo o p   is   f o r   th tr an s f er   o f   th e   o u tp u t d ata  co n tai n i n g   t h r es u lt o f   t h Sp MV   o p er atio n   to   th o u tp u t te r m i n al.     Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   R ec o n f i g u r ab le  &   E m b ed d ed   Sy s t     I SS N:   2089 - 4864       A n   a p p r o xima te  mo d el  S p MV  o n   F P GA   a s s is tin g   HLS   o p tim iz a tio n s   fo r   lo w   p o w er   … ( A ld en   C .   S h a ji )   381       Fig u r 5 .   Sp MV   ke r n el  p s e u d o   co d w it h   p ip elin i n g       3 . 3 .     Appro x i m a t s pa rse  m a t rix - v ec t o m ultip lica t io n   a lg o rit h m   As  f ar   as  w ar a w ar e,   th e r is   cu r r en tl y   n o   ex i s ti n g   r esear ch   th a f o cu s es  o n   o p ti m izi n g   t h e   co m p u tatio n   o f   ap p r o x i m ate   m o d el  Sp MV   o n   FP GA .   Desp ite  p r ev io u s   s t u d ies  ad d r ess in g   o p ti m izi n g   tech n iq u es  o n   FP G A   f o r   d en s m atr i x   m u ltip licatio n s   a n d   d ee p   lear n in g ,   t h er ap p ea r s   to   b g ap   in   t h e   liter atu r r eg ar d in g   th s p ec if i o p tim izat io n   o f   ap p r o x i m ate   m o d el  Sp MV   o n   th ese  h ar d w ar p latf o r m s .   T h e   co m p u tatio n al  p er f o r m a n ce   o f   C P Us  in   t h is   ta s k   i s   in h er en t l y   li m ited   b y   t h eir   r estricte d   m e m o r y   b an d w id th   an d   th d if f icu l t y   o f   e f f ic ien t l y   e x ec u tin g   f r eq u en r an d o m   ac ce s s es.  T h is   li m itatio n   ar is e s   f r o m   th f ac th at   th er ar n o   ass u r an ce s   th a t h r e q u ir ed   v al u es  h av n o b ee n   tak e n   f r o m   t h ca ch e,   i m p ed in g   t h ab ilit y   to   ac ce s s   d ata  q u ick l y   a n d   r eliab ly .   T h m o tiv at io n   b eh in d   ap p r o x i m ate  Sp MV   alg o r it h m s   i s   t o   ac ce ler ate  th co m p u tatio n   o f   m a tr ix - v ec to r   m u ltip licat io n   i n   s ce n ar io s   w h er an   e x ac s o lu t io n   is   n o s tr ictl y   n ec e s s ar y .   T h is   is   co m m o n   i n   m ac h in lear n in g ,   s i g n al  p r o ce s s i n g ,   a n d   o th er   ap p licatio n s   w h er an   ap p r o x i m ate  r es u lt   is   ac ce p tab le.   T h e   k e y   tr ad e - o f f   in   ap p r o x i m ate   Sp MV   alg o r ith m s   is   b et w e en   co m p u tatio n al  s p ee d   an d   s o lu tio n   ac cu r ac y .   A p p r o x i m ate  Sp MV   m o d el s   ca n   b d esig n ed   to   s ca le  b ett er   w it h   i n cr ea s i n g   m atr i x   s ize s .   T h is   is   esp ec iall y   b en ef icia w h e n   d ea lin g   w it h   l ar g d atasets   i n   s cie n ti f ic  s i m u latio n s   o r   m ac h i n lear n i n g   ap p licatio n s .   I n   th i s   s ec tio n ,   w s u g g e s te d   u n iq u ap p r o x i m a te  m o d el  ap p r o ac h   f o r   Sp MV ,   to   s h o r ten   t h e   ex ec u t io n   ti m e.   E f f icien c y   in   Sp MV   is   o f ten   ac h ie v ed   th r o u g h   al g o r ith m s   an d   d ata  s tr u ct u r es  th at  les s en   t h e   n u m b er   o f   ar it h m etic   o p er atio n s   a n d   m e m o r y   ac ce s s   b y   tak in g   ad v a n ta g o f   th m atr i x ' s   s p ar s it y .   W h a v t ak en   th s p ar s m atr i x   S o   as  t h in p u a n d   o b tain   th ap p r o x i m ate  C SR   f o r m at  m atr ice s   S t   an d   S v   as  o u tp u ts .   I m p le m e n tatio n   r esu lts   ar s h o w n   in   s ec tio n   5 T h is   alg o r ith m   co n tai n s   t w o   t y p es o f   ap p r o x i m atio n :   AX - 1 h er t h ap p r o x i m at io n   o f   Sp MV   is   b ased   o n   t h r es h o ld in g   th e   r o w   co u n o f   th e   m a tr ix .   O n l y   tak i n g   t h d ata  v alu es  w h ic h   ar h ig h er   th a n   th th r es h o ld   an d   s to r es  it  in   S t .   T h r esh o ld   is   ca lcu lated   as  th e   m ea n   o f   m a x   an d   m i n   r o w   co u n v al u es  o f   th s p ar s m atr i x .   I n   A l g o r ith m   1 ,   s tep   4 1 1   co r r esp o n d s   to   th is   ap p r o x im a tio n .   AX - 2 h er t h ap p r o x i m atio n   is   b ased   o n   t h ac c u r ac y   o f   t h d ata  v alu e.   A f ter   s o r tin g   t h i n p u t   s p ar s m atr ix   b ased   o n   d ata  v alu e,   it  is   class if ied   i n to   p o s itiv m atr i x   ( S p )   an d   n eg ati v m atr ices   ( S n ) .   T h en   tak en   o n l y   t h h ig h   ac cu r ac y   v alu e s   o f   7 0 o f   to tal  N N Z s .   B o th   m a tr ix e s   ar j o in ed   to g e th er   in   S v   an d   ag ai n   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4864   I n t J   R ec o n f i g u r ab le  &   E m b ed d ed   Sy s t ,   Vo l.  14 ,   No .   2 J u l y   20 25 375 - 3 8 7   382   d o   th s o r tin g   b ased   o n   th r o w   v alu e s .   I is   th e n   co n v er ted   in to   th C SR   f o r m at.   I n   A l g o r ith m   1 ,   s tep   1 2 1 9   co r r esp o n d s   to   th is   ap p r o x i m a tio n .     A l g o r ith m   1 .   A p p r o x i m ate  Sp MV   alg o r ith m   I n p u t:   T h o r ig in al  s p ar s m a tr ix ,   S o ;   Ou tp u t:   T h tar g et  ap p r o x im ate  C S R   f o r m at,   S t   an d   S v ;   1 : O b tain   th m atr i x   p ar a m ete r s   f r o m   S o ;   2 : Co u n t t h n o .   o f   N N Z’ s   i n   ea ch   r o w   a n d   s to r in   r o w _ co u n t ;   3 : I n itial ize  th m atr i x   S t S v   w ith   r o w s   o f   s p ec i f ied   N N Z s ,   j =0 ;   4 : O b tain   th m ax   a n d   m i n   r o w _ co u n t   v alu es;   5 : Fin d   th th r e s h o ld   b y   ta k in g   m ea n   o f   v al u es  f r o m   4 ;   6 w hil e   N N do   7 :           if   r o w _ co u n t   th r esh o ld   t hen   8:             s k ip   ad d in g   t h o s r o w s   v alu e s   to   S t ;   9 :           else  ad d   th o s r o w s   to   S t   an d   in cr e m e n t t h s ize;   1 0 :       a d d   co r r esp o n d in g   co l   an d   d ata  v alu to   S t     1 1 end w hil e   1 2 s o rt   S b ased   o n   ab s o lu te  d ata  v alu e;    1 3 : Cl ass i f y   S o   i n to   t w o   m atr ic es a s   S p ,   S n   b ased   o n   in teg er ;   1 4 : Co u n t t h n o .   o f   ele m en ts   in   S p S n   an d   s to r in   p n ;   1 5 f o r   i:  p × 0 . 3   to   p     1 6 :       c o p y   th co r r esp o n d in g   v alu e s   f r o m   S p   to   S ;   1 7 f o r   i:  1   to   n × 0 . 7     1 8 :       c o p y   th co r r esp o n d in g   v alu e s   f r o m   S n   to   S ;   1 9 s o rt   S b ased   o n   r o w   v al u e ;   2 0 : Co n v er m a tr ix   S t   an d   S in to   C SR   f o r m at;     3. 4   E x peri m ent a s et up   T o   ev alu ate  t h p r o p o s ed   m et h o d s ,   w s e tu p   th h o s e n v ir o n m e n w i th   p r o ce s s o r   I n tel  C o r i5 - 7 5 0 0   @   3 . 4   GHz ×4 ,   Me m o r y   o f   7 . 6   GiB .   T h tar g et  d ev ice  as  Z y b o   Z 7 - 2 0   co n tain s   t h FP G A   Z y n q - 7 0 0 0   p latf o r m   w h ic h   co n s i s ts   o f   XC 7 Z 0 2 0 - 1 C L G4 0 0 C   ch ip   an d   it  also   co n tai n s   d u al - co r AR C o r te x - A 9   p r o ce s s o r .   Ou r   d esig n   u tili ze s   t h f o u r   6 4 - b it   h i g h   p er f o r m a n ce   m e m o r y   p o r ts   in   t h p r o g r a m m ab le  lo g i c.   I s u p p o r ts   d ata   tr an s f er   f r o m   p r o ce s s i n g   s y s te m   to   DDR  m e m o r y   w it h   m e m o r y   b an d w id t h   o f   1 2 . 2   GB /s .   I also   co n tain s   a n   on - c h ip   m e m o r y   o f   2 5 6   KB   w h ic h   i s   u s e f u i n   r ed u ci n g   t h t h r o u g h p u w h ile  co m p u tin g .   W s e t h f r eq u en c y   to   1 5 0   MH o n   FP GA   f o r   th ex ec u tio n   o f   Sp MV   ac ce ler ato r .   T h to o l   u s ed   f o r   im p le m en tatio n   o f   th d esi g n   i s   Viti s   H L S 2 0 2 0 . 2 .   I n s talled   P etaL in u x   an d   Viti s   H L S,  t w o   d is ti n ct  to o ls   p r o v id ed   b y   Xil in x   t h at  s er v d if f er e n t   p u r p o s es.  P etaL in u x   is   p r i m a r il y   u s ed   f o r   b u ild i n g   an d   cu s to m izi n g   L i n u x   d is tr ib u tio n s   f o r   Xilin x   d ev ices,   w h ile  Viti s   HL is   f o cu s ed   o n   HL S ,   co n v er ti n g   C ,   C ++ ,   a n d   Op en C L   co d in to   h ar d w a r im p le m en tatio n s .   B y   r u n n in g   co n f ig ,   b u ild   an d   p ac k ag f o r   P etaL in u x   to o w ill  g en er ate  th b o o i m ag t h at  in clu d es  t h f ir s t   s tag b o o t lo ad er   ( FS B L ) ,   b its tr ea m ,   an d   o th er   n ec e s s ar y   co m p o n en ts .   As  in p u d ata  f o r   th ex p er i m en t,  w u s ed   s et  o f   s p ar s m atr ices  f r o m   th U n i v er s it y   o f   Flo r id a' s   s p ar s m atr i x   co llectio n   [ 2 8 ] .   T h s elec ted   m a tr ices  d i m e n s i o n   an d   N N Z s   ar les s   th a n   1 0 6 ,   r esp ec tiv el y .   T h f ea t u r es  o f   th s p ar s m atr ice s   ar g iv en   i n   T ab le   1 ,   ac co r d in g   to   th at  all  th m a tr ices  h av s p ar s it y   ab o v e   9 8 an d   f o u r   m atr i x es  i n   th e   s elec ted   ar f lo atin g   p o in t y p an d   r em ain i n g   o n is   in te g er   ty p v al u e.   T h e   o p tim izatio n   tech n iq u e s   u s e d   in   t h Sp MV   k er n e ar e   m o d elled   in to   8   t y p es  a s   s h o w n   i n   T ab le  2 C o m b i n atio n   o f   d i f f er e n o p ti m izatio n   tec h n iq u es  ar u s ed   w it h   HL p r ag m as  in   m o d elli n g   an d   o b tain ed   t h e   p er f o r m a n ce   r es u lts   i n   Vit is   H L S.       T ab le  1 .   Sp ar s m atr ix   s tati s ti cs   M a t r i x   n a me   R o w   si z e   C o l   si z e   NNZ   S p a r si t y   ( %)   Ty p e   c - 4 8 . mt x   1 8 3 5 4   1 8 3 5 4   9 2 2 1 7   9 9 . 9 7   F P   v a l u e   c a g e 8 . m t x   1 0 1 5   1 0 1 5   1 1 0 0 3   9 8 . 9 3   F P   v a l u e   g 7 j a c 0 8 0 . m t x   2 3 6 7 0   2 3 6 7 0   2 9 3 9 7 6   9 9 . 9 5   F P   v a l u e   mh d 4 8 0 0 a . mt x   4 8 0 0   4 8 0 0   1 0 2 2 5 2   9 9 . 5 6   F P   v a l u e   TF 1 6 . mt x   1 9 3 2 1   1 5 4 3 7   2 1 6 1 7 3   9 9 . 9 3   I N T   v a l u e     Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   R ec o n f i g u r ab le  &   E m b ed d ed   Sy s t     I SS N:   2089 - 4864       A n   a p p r o xima te  mo d el  S p MV  o n   F P GA   a s s is tin g   HLS   o p tim iz a tio n s   fo r   lo w   p o w er   … ( A ld en   C .   S h a ji )   383   T ab le  2 .   Op tim izatio n   m o d el   M o d e l   O p t i mi z a t i o n   t e c h n i q u e   A   P i p e l i n e   O F F   B   P i p e l i n e   O F F   a n d   u n r o l l   f a c t o r =2   C   P i p e l i n e   O F F   a n d   u n r o l l   f a c t o r =4   D   P i p e l i n e   O F F   a n d   a r r a y   p a r t i t i o n   E   P i p e l i n e   O N   F   P i p e l i n e   O N   a n d   u n r o l l   f a c t o r =2   G   P i p e l i n e   O N   a n d   a r r a y   p a r t i t i o n   H   P i p e l i n e   O N   a n d   b i n d   st o r a g e       4.   RE SU L T S AN D I SCU SS I O N   T h is   s eg m en an al y s e s   th p r o p o s ed   Sp MV   a p p r o x im ate  a lg o r ith m   w it h   o p ti m izatio n   te ch n iq u es.   I n itiall y ,   s er ie s   o f   5   s p ar s m atr ices  c h o s e n   as  b e n ch m ar k s   f o r   t h p u r p o s o f   e x a m in in g   t h ef f ec t s   o f   ea c h   o p tim izatio n   tec h n iq u d escr ib ed .   Z y b o   Z 7 - 2 0   tak e n   as  o u r   tar g et  b o a r d ,   w h ic h   co n tai n s   Z y n q   7 0 0 0   FP GA  an d   w it h   Vitis   H L to o w im p le m e n ted   s o f t w ar e m u lati o n ,   h ar d w ar e m u latio n ,   an d   h ar d w ar b u ild .   T h ex ec u t io n   ti m i n   F ig u r e   6   is   tak e n   af ter   p as s i n g   t h te s w h ile  r u n n i n g   s o f t w ar e m u l atio n .   I n   h ar d w ar e   e m u latio n ,   it  ch ec k s   th f u n c ti o n al  co r r ec tn ess   o f   th R T L   co d s y n th e s ized   f r o m   t h Op e n C L   k er n el  co d e.   I g iv e s   t h r eso u r ce   u t ilizatio n ,   esti m a ted   f r eq u e n c y   a n d   th n u m b er   o f   c y c les  ta k en   f o r   th ex ec u tio n   o f   t h e   task   i n   th tar g et  d ev ice.   I n   h ar d w ar b u ild   th to o w ill  g e n er ate  th FP G A   b its tr ea m   f o r   th co r r esp o n d in g   d ev ice  af ter   r u n n i n g   s e v er al  s tep s   in cl u d in g   lo g ic  p lace m e n t,  o p ti m izatio n ,   r o u ti n g ,   ti m i n g   o p ti m iza tio n   i n   Vitis   to o l.  T h r eso u r ce   u t iliz atio n   f o r   ea ch   m o d el  is   g iv e n   in   T ab le  3 ,   ac co r d in g   to   t h at  w h a v ca lc u lated   th p o w er   co n s u m p tio n   f o r   ea ch   m o d el  u s i n g   Xi lin x   p o w er   esti m ato r .           Fig u r 6 .   E v alu atio n   o f   d eig n   p er f o r m a n ce   i n   Viti s   H L S       T ab le  3 .   Op tim izatio n   m o d el   M o d e l   D S P   ( 2 2 0 )   B R A M _ 1 8 K   ( 2 8 0 )   F F   ( 1 0 6 4 0 0 )   L U T   ( 5 3 2 0 0 )   A   12   1 0 0   4 1 1 5   7 6 4 5   B   6   1 0 0   4 3 9 2   7 8 7 9   C   6   1 0 0   5 0 2 2   9 8 0 5   D   12   1 0 0   4 0 9 9   7 7 8 3   E   12   1 0 0   4 4 6 2   7 7 5 1   F   6   1 0 0   5 2 2 5   8 0 0 8   G   12   1 0 0   4 5 7 1   7 9 5 1   H   12   1 0 0   4 4 6 2   7 7 1 7   3 0 . 2 2 1 6 . 8 3 3 7 . 6 2 5 5 . 3 9 8 . 1 9 4 3 . 1 2 5 . 9 2 3 7 . 9 7 3 2 . 5 35 4 0 . 2 3 2 . 5 3 2 . 6 3 2 . 4 3 2 . 6 3 2 . 6 1 3 1 . 7 1 3 1 . 7 1 3 1 . 7 1 3 1 . 7 1 3 6 . 9 1 3 6 . 9 1 3 6 . 9 1 3 6 . 9 A B C D E F G H 1 2 9 1 3 0 1 3 1 1 3 2 1 3 3 1 3 4 1 3 5 1 3 6 1 3 7 1 3 8 0 10 20 30 40 50 60 A B C D E F G H E st i m a t e d   Fr e q   ( M Hz) Op t i m i z a t i o n     M o d e l Ex ec T i m e  (s ) C y c l es / 1 0 Est F r e q .  (MH z ) Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4864   I n t J   R ec o n f i g u r ab le  &   E m b ed d ed   Sy s t ,   Vo l.  14 ,   No .   2 J u l y   20 25 375 - 3 8 7   384   Fro m   th r esu l ts   o f   s o f t w ar an d   h ar d w ar e m u latio n s ,   w e   co n clu d th at  m o d el  w h ic h   is   u s in g   P ip elin w it h   ar r a y   p ar titi o n   i s   g i v in g   b etter   r esu lt s   f o r   co m m o n   s p ar s m atr i x   as  s h o w n   in   F ig u r e   5 .   T h m o d el s   w h ich   u s p ip eli n is   tak in g   a n   esti m ated   ti m o f   7 . 3   n s   f o r   tar g et  ti m o f   6 . 7   n s   w it h   s lac k   o f     - 0 . 6   n s ,   an d   t h m o d els  w it h o u p ip elin i n g   is   ta k i n g   a n   es ti m ated   ti m o f   7 . 6   n s   w i th   s l ac k   o f   - 0 . 9   n s .   T h u s ,   p ip elin in g   is   e f f icie n f o r   r ed u cin g   t h s lack   a n d   i m p r o v i n g   t h p er f o r m a n ce   in   H L S.  E x ce p B   an d   C   m o d els,   r e m ain in g   all  m o d el s   tak i n g   3 2 6 - 3 2 4   cy cles to   co m p lete  t h task .   P o w er   co n s u m p tio n   d ep en d s   o n   v ar io u s   f ac to r s ,   i n clu d in g   t h h ar d w ar ar ch itect u r e,   clo ck   f r eq u en c y ,   r eso u r ce   u ti lizatio n ,   an d   th n at u r o f   th o p er atio n s   p er f o r m ed   b y   t h m o d els.  E x a m i n th e   r eso u r ce   u tili za tio n   r ep o r ts   f r o m   Vit is   HL to   u n d er s tan d   h o w   m u c h   o f   th FP G A   r eso u r ce s   ea ch   m o d el  is   co n s u m i n g .   T h is   i n cl u d es  d etails  o n   lo o k - u p   tab les  ( L UT s ) f lip - f lo p s   ( FF s ) ,   B R A M s ,   d ig i tal  s i g n al   p r o ce s s o r s   ( DSP s ) ,   an d   o th er   r eso u r ce s .   Hig h er   clo ck   f r eq u en cie s   g e n er all y   lead   to   b ett er   p er f o r m an ce   b u t   ca n   also   i n cr ea s p o w er   co n s u m p t io n .   D y n a m ic  p o w er   co n s u m p tio n   is   i n f l u en ce d   b y   t h ac tiv it y   an d   s w itc h in g   o f   lo g ic  ele m e n ts   d u r in g   o p er atio n   w h er ea s   s ta tic  p o w er   co n s u m p t io n   is   as s o ci ated   w it h   th leak ag e   p o w er   o f   t h FP G A.   T h is   co m p o n e n i s   i n d ep en d en o f   t h ac ti v it y   a n d   ca n   b s i g n i f ica n i n     lo w - p o w er   ap p licatio n s .   P o w er   u tili za t io n   f o r   ea ch   m o d el  is   ca lc u lated   b y   Xili n x   p o w er   est i m a to r   w i th   th r eso u r ce   u tili za t io n   g o f r o m   t h Vi t is   HL to o l.  Fro m   t h ca l cu latio n   m o d el  B   is   tak i n g   th lo w e s p o w er   co n s u m p tio n .   T h p o w er   u t il izatio n   co m p ar is o n   o f   o u r   m o d el  w ith   t h s tr ea m i n g   d ata f lo w   en g i n ( SDE)   Sp MV   m o d el  f r o m   [ 8 ]   is   g iv e n   in   Fi g u r e   7 .   T h ey   h av u s ed   Z C U1 0 2   ev alu a tio n   b o ar d   w h ich   co n tain s   Z y n q   Ultr aSca le+   MP So C   a s   t h eir   t ar g et  d ev ice,   w h ic h   i s   h ig h er   en d   d ev ice  a s   co m p ar ed   to   Z y n q - 7 0 0 0 .   Fro m   th e   co m p ar is o n   c h ar f o r   th e   Sp M m o d el,   o u r   m o d el  i s   ta k in g   al m o s h alf   o f   th e   p o w er   co n s u m p tio n   tak e n   b y   SDE  m o d el.           Fig u r 7 .   P o w er   u t ilizatio n   co m p ar i s o n   c h ar t       I n   o p tim iza tio n   m o d el  w ca lcu lated   th ex ec u tio n   ti m ( m illi   s ec o n d s )   is   s h o w n   i n   Fig u r e   8   f o r   5   s elec ted   s p ar s m a tr ices  m en t io n ed   in   T ab le  1 .   T h ap p r o x i m ate  al g o r ith m   ap p lied   to   th m atr ices  g i v en   to   th m o d el  S p MV   k er n el  a n d   an al y ze d   th ex ec u tio n   ti m in   t h tar g et  FP G A .   W f i n d   o u th at  AX - ap p r o x im a tio n   m o d el  is   r ea c h in g   5 0 r ed u ctio n   i n   ex ec u tio n   ti m f o r   f lo ati n g   p o in v alu s p ar s m a tr ix   co m p ar ed   to   its   o r ig in al.   B u f o r   in teg er   t y p v al u s p ar s m atr i x   A X - 2   ap p r o x im a tio n   m o d el  g et tin g   m u c h   r ed u ctio n   th a n   o th er .   A l s o   o b s er v ed   th at  th r ed u ctio n   is   h i g h er   w h e n   th N N Z s   ar lar g er .   E x ec u tio n   ti m e   tak en   f o r   b o th   ap p r o x i m ate  m o d el  A X - 1   an d   A X - 2   f o r   th s p ar s m atr ices  i n   co m p ar is o n   w it h   S DE   m o d el  i n   [ 8 ]   is   s h o w n   i n   Fig u r e   8 .   I n   [ 8 ]   th e y   h a v u s ed   tar g e d ev ice  as  Z y n q   U ltra Scale+   MP So C   FP G A   w i th   f r eq u en c y   o f   2 0 0   MH z,   w h ic h   r ed u ce s   th ex ec u tio n   ti m s i g n i f ica n tl y .       63 61 68 63 64 64 65 64 1 0 6 . 5 0 20 40 60 80 1 0 0 1 2 0 0 2 4 6 8 10 Po w e r   U tili z a tio n   (m W ) M o d e l Ou Wo rk Re f.   [8 ] Evaluation Warning : The document was created with Spire.PDF for Python.