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.   6 No .   2 J u l y   201 7 ,   p p .   69 ~ 8 1   I SS N:  2 089 - 4 864 DOI : 1 0 . 1 1 5 9 1 / i j r es . v 6 . i2 . p p 69 - 81          69       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 JR E S /in d ex   So ft w a re and H a rd w a re f o M a na g ing  Scratch  Pad  M e m o ry       Cha ba ne  H e m da ni 1 ,   Ra chi d a   Ao ud j it 2 ,   M us t a ph a   L a la m 3 ,   K ha led Sli m a ni 4   L a b o ra to ire d e   Re c h e rc h e   e n   I n f o rm a ti q u e   (L A RI)   BP   n   1 7   R P ,   U n iv e rsit y   o f   T izi  Ou z o u ,   A lg e ria       Art icle  I nfo     AB ST RAC T   A r ticle  his to r y:   R ec eiv ed   A p r   2 ,   2 0 1 7   R ev i s ed   A p r   2 0 ,   2 0 1 7   A cc ep ted   Ma y   7 ,   2 0 1 7       T h is  p a p e p ro p o se a   lo w - c o st   a rc h it e c tu re   to   i m p ro v e   th e   m a n a g e m e n S P M   (S c ra tch   P a d   M e m o r y in   d y n a m ic  a n d   m u lt it a sk in g   m o d e s.  In   th is  c o n tex t,   o u m a n a g e m e n stra teg y   S P M   b a se d   o n   P ro g ra m m a b le  A u to m a to n   im p le m e n ted   in   Xili n x   V e rtex - 5   F P G A   is  e n ti re l y   d iff e re n fro m   p rio re se a rc h   w o rk s.   S P M   is   g e n e ra ll y   m a n a g e d   b y   so f t w a re   (b y   a   stro n g   p ro g ra m m in g   lo g ic  o r   b y   c o m p i latio n ).   Bu o u r   P ro g ra m m a b le  A u to m a to n   f a c il it a tes   a c c e ss   to   S P M   in   o rd e r   to   m o v e   c o d e   o d a ta  a n d   li b e ra t e sp a c e   in   S P M .   A f ter   th is  ste p ,   so f t w a r e   ta k e o v e c o n ten m a n a g e m e n o f   S P M   (w h a t   p a rt  o f   c o d e   o d a ta  sh o u ld   b e   p lac e d   in   S P M ,   lo c a tes   sp a c e o f   He a p   a n d   S tac k ).   S o   t h e   p e rf o rm a n c e   o f   th e   p ro g ra m is  a c tu a ll y   i m p ro v e d   th a n k to   m in i m iza ti o n   o f   th e   a c c e ss   late n c y   a th e   DR A M   (D y n a m ic  R a n d o m   A c c e ss   M e m o r y   o M a in   M e m o r y ).   K ey w o r d s :   C o r   E m b ed d ed   Sy s te m s     FP GA     Scr atch   P ad   Me m o r y         Co p y rig h ©   2 0 1 7   In stit u te o 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 rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   Mu s tap h L a la m ,   L ab o r ato ir d R ec h er ch en   I n f o r m atiq u ( L AR I )   B P   n   1 7   R P   Un iv er s it y   o f   T izi  Ou zo u ,   A l g er ia .   E m ail:  lala m u s tap h a@ y a h o o . f r       1.   I NT RO D UCT I O N   A   w el f i n i s h ed   co n ce p tio n   o f   th m e m o r y   h ier ar ch y   s u b u n i ts   co n tr ib u te s   to   th i m p r o v e m en o f   t h p er f o r m a n ce s   o f   an   E m b ed d ed   Sy s te m   i n   p ar ticu lar   o n   th ti m i n g ,   th s c h ed u li n g ,   th en er g y   co n s u m p tio n ,   th m u lti - ta s k i n g   an d   th p r ed ictab ilit y .   I is   in   th i s   co n te x th at  lo ca tes  o u r   id ea   to   m an a g e   ef f ec ti v el y   lo ca s tatic  m e m o r y   S R A to   b u s ed   as  Scr atch   P ad   Me m o r y   ( SP M) .   Ou r   ap p r o ac h   o n   u s o f   t h is   SP is   in s p ir ed   f r o m   p r ev io u s   w o r k s   o f   t h l iter atu r w h ile   p r o p o s in g   an   o r ig i n al  h y b r id   s o lu t io n   t h at  i s   to   m a n a g SP b y   h ar d w ar ( P r o g r a m m ab le  Au to m a to n )   a n d   b y   S y s te m   ca lls .   SP en d o w ed   w it h   it s   co p r o ce s s o r   is   co n n ec ted   to   co r o f   m u lt i - co r s y s te m .   E v er y   co r h as   its   o w n   SP an d   th is   o n ca n   b ac ce s s ib le  b y   o th er   co r es f o r   b etter   ef f icie n c y   o f   th M u lti - T ask i n g   an d   o f   Mu lti - p r o ce s s i n g .   SR A o n   c h ip ,   ca lled   SP M,   i s   s m all  m e m o r y   o f   f ast  ac ce s s   w h ich   i s   lo ca ted   in   s p ac o f   s ep ar ate  ad d r ess in g   o f   th e   DR AM   b u t   co n n ec ted   to   th e   s a m ad d r ess es   b u s   an d   to   t h s a m d at b u s   [ 1 ] .   SP is   m an a g ed   b y   s o f t w ar e.   I n   o th er   w o r d s ,   t h s to r ed   d ata  in   SP ar m a n ag ed   b y   P r o g r a m m er s   o r   C o m p iler s   [ 2 ] .   I is   p o s s ib le  to   h av C ac h m e m o r y   an d   SP in   t h s a m E m b ed d ed   S y s te m .   C o n tr ar y   to   t h SP M,   th e   ca ch is   m an a g ed   b y   h ar d w ar e.   B u b o th   h av late n c y   o f   ac ce s s   o f   c y cle o n   t h o th er   h an d   th ac ce s s   m e m o r y   o f f   c h ip   ( g e n er all y   DR A M)   a s k s   f o r   s ev er al  c y cles  ( f r o m   1 0   to   2 0   c y cle s ) .   On o f   th e   m a in   d if f er e n ce s   b et w ee n   t h SP an d   th ca ch is   t h at  SP g u a r an tees  an   ac ce s s   ti m o f   c y cle  w h ile  t h ca ch is   s u b j ec to   th co m p u ls o r y ,   ca p ac ity   an d   co n f lict  m is s es   [ 1 ] .   Ou r   s o lu tio n   f o u n d ed   it s elf   o n   t h w o r k s   p r o p o s ed   in   [ 3 ]   in   t h p ar titi o n in g   o f   SP b u w p r o p o s an   o r ig i n al  m a n ag e m e n o f   SP b y   co m b in in g   h ar d w ar a n d   s o f t w ar ( OS  l ev el) .   Fo r   th at  p u r p o s e,   w e n d o w   SP o f   an   i m p le m e n te d   f u n ctio n   in   FP GA  cir cu it ( Xili n x   Ver te x - 5   FP GA ) .   T h is   p ap er   is   co m p o s ed   o f   6   s ec tio n s .   T h f ir s t   Sectio n   g i v e s   an   o v er v ie w   o n to   t h s tate  o f   t h ar t   o f   SP M.   T h s ec tio n   2   s h o w s   t h o r g an izatio n   o f   SP i n   f r a m es.  W th e n   c h ai n   o n   t h s tr u ctu r SH FS   ( Stac k   Hea p   Fra m e   Str u ctu r e)   s to r ed   in   D R A M   m e m o r y .   W i n tr o d u ce   f u n ctio n s   o f   A u to m ato n   i n   th e   s ec tio n   3 .   T h e   s ec tio n   4   r ec o m m e n d s   v ar io u s   A l g o r ith m ic  S tate  Ma c h i n es   th at  Au to m ato n   e x ec u tes  a s   w ell   as  D M A   m o d e   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4 864     I J R E S   V o l.  6 ,   No .   2 J u l y   2 0 1 7   :   69     8 1   70   ( Dir ec Me m o r y   A cc e s s )   ex ec u ted   u n d er   ae g is   o f   t h Op er atin g   S y s te m   ( O S).   T h f o llo w in g   s ec tio n   co m p lete s   t h h ar d w ar o f   th e   au to m a to n   u n d er   t h f o r m   o f   cir cu it  FP G A   r ea lized   u n d er   E DK.   T h s ec tio n   6   g i v es  a n   i n s ig h t   o f   s i m u lati o n   o f   th e   co p r o ce s s o r   w h ic h   w e   r ec o m m en d   a n d   t h r eso u r ce s   o f   t h c ir cu it   FP GA   u s ed   d u r in g   t h s y n th e s is   f o r   r ea lizin g   t h co p r o ce s s o r .       2.   ST A T E   O F   T H E   ART   T h u s o f   SP s h o w ed   a n   i m p r o v e m e n o f   th p er f o r m an ce   an d   r ed u ctio n   o f   t h en er g y   [ 1 ] [ 3 ] - [ 5 ] [ 16 ] - 1 9 ] .   I n   1 9 9 7 ,   [ 1 ]   p r o p o s ed   s tatic  s tr a teg y   f o r   p ar titi o n in g   s ca lar   a n d   ar r ay   v ar iab le s   i n   a n   ap p licatio n   co d in to   SP an d   o f f - ch ip   DR A ac ce s s ed   t h r o u g h   d ata  ca c h e.   T h e y   d es cr ib ed   m et h o d   o f   p ar titi o n   th at   s h o w s   t h u s e f u l n es s   o n - ch ip   SP in   ad d itio n   to   d ata  ca ch e.   [ 9 ]   P r o p o s ed   SP s ch e m w h ic h   ca n   b e m b ed d ed   o n to   FP GA's  cir cu i o r   m u lti - co r p r o ce s s o r s   ch ip s   as  co p r o ce s s o r   to   d ec r ea s th m e m o r y   ac ce s s   ti m o f   t h k e y /v a lu p air s   u s ed   d ir ec tl y   f r o m   SP to   ac ce ler ate  Ma p R ed u ce   ap p licatio n s .   T h p r o p o s ed   Ma p R ed u ce   s cr atch p ad   m e m o r y   i s   u s e d   to   r ep lace   th R ed u ce   s ta g w it h   s i n g le  s p ec ial  m e m o r y   u n it  t h at  is   u s ed   to   s to r an d   au to m atica ll y   ac cu m u late  t h v al u es  o f   th k e y s   i n   Ma p R ed u ce   ap p licatio n .   T h is   ar ch itectu r p r o p o s ed   in   [ 9 ]   d o es  n o co r r esp o n d   to   o u r   in itiati v o f   d esig n   o f   th co p r o ce s s o r   w h ich   m a n ag e s   S P M.   A cc o r d in g   to   [ 5 ] ,   [ 8 ]   p r esen ted   h ar d w ar e/ s o f t w ar ap p r o ac h   f o r   d y n a m ic  m an a g e m e n s ch e m e   o f   SP M.   T h eir   ap p r o ac h   in tr o d u c es  h ar d w ar co m p o n e n d esig n ed   s p ec ial l y   to   m an a g t h co p y i n g   o f   in s tr u ctio n s   f r o m   t h m a in   m e m o r y   i n to   SP M.   T h ey   u ti lize  in s t r u ctio n s   e x ec u tio n   f r eq u en c y   i n f o r m atio n   to   m o d el  ap p licatio n s   as  g r ap h   an d   p er f o r m   g r ap h   p ar titi o n i n g   to   d eter m i n lo ca tio n s   w it h i n   t h p r o g r a m   f o r   in it iat in g   th co p y i n g   p r o ce s s .   T h Au t h o r s   o f   [ 7 ]   s h o w ed   d if f er en ap p r o ac h   to   st atic  u s a g s c h e m f o r   SP b y   m ap p in g   ap p licatio n s   o n   t h ex is t in g   h ar d w ar [ 5 ] .   T h p ap er   [ 1 0 ]   p r o p o s e d   r u n t i m e   m e m o r y   m a n a g e m e n ap p r o ac h   f o r   SP at  t h O S - le v el  t h at  ca n   b co m b i n ed   w it h   o t h er   co m p ile - ti m ap p r o ac h es.  T h OS  m e m o r y   m a n a g er   tak es  an n o ta ti o n s   i n s er ted   in to   t h co d b y   th e   p r o g r a m m er   a s   h in ts   to   c h o o s t h m o s ap p r o p r iate  m e m o r y   ( i.e .   Ma i n   M e m o r y   o r   SP M)   f o r   ea ch   allo ca tio n .   E x p er i m en ta l   r esu lt s   co n f ir m   t h ap p r o ac h s   ef f ic ien c y   w h en   co m p ar ed   to   s i m i lar   co m p ile - t i m tec h n iq u [ 1 0 ] .   T h tech n iq u w h ich   a s s i g n s   h ea p   d ated   in   t h SP w as  p r o p o s ed   in   [ 1 4 ] .   Desp ite  o f   b ein g   th f ir s tech n iq u t h at  allo ca tes  h ea p   d ata  to   SP M,   it f o llo w s   t h d y n a m ic  co m p ile - ti m e - ap p r o ac h   [ 1 0 ] .   A cc o r d in g   to   [ 5 ] ,   [ 6 ]   p r o p o s ed   an o th er   s ta tic  m an a g e m en s c h e m f o r   r ec o r d in g   d a ta  an d   in s tr u ctio n s   m e m o r y .   T h eir   s ch e m u s es  p o ly n o m ia ti m alg o r it h m   f o r   p ar titi o n in g   a n d   in s tr u ctio n s   i n to   DR AM   an d   SP M.   T h eir   r esu lts   s h o w   en er g y   i m p r o v e m e n r an g i n g   f r o m   3 9   to   8 4   o v er   n o   p ar titi o n ed   SP M .   An o th er   w o r k   th at   d ea ls   w it h   th m a n ag e m e n t   o f   Hea p   d ata   w as   p r esen ted   in   [ 1 5 ] .   P ap er   [ 1 1 ]   s p ec if ied   th a m u lti - co r s y s te m s   h av b ee n   p o p u lar   d esig n   f o r   h i g h   p er f o r m a n ce   E m b ed d ed   S y s te m s .   T h Au t h o r s   p r o p o s o n p o l y n o m ial - ti m e   alg o r it h m   to   s o lv e   th e   d ata   allo ca tio n   p r o b lem   o n   m u lti - co r s y s te m   w it h   ex clu s i v co p y   o f   d ata.   T h p r o p o s ed   s o lu tio n   r ed u ce s   ti m co s o f   m e m o r y   ac ce s s es   b y   1 6 . 4 5   o n   a v er ag e.   T h s o lu tio n   also   ca n   r ed u ce   th e n er g y   co s s i g n i f ica n tl y .   T h er ar also   s ev er al  w o r k s   p r o p o s ed   f o r   SP Ms  o n   th m u l ti - co r S y s te m s   [ 1 ] ,   [ 1 1 ] - [ 1 3 ] .   Ou r   co n tr ib u tio n   in   th i s   d o m ai n   co n s is t s   i n   m an a g i n g   t h SP b y   h ar d w ar ( cir cu it  o f   t y p FP GA  ca lled   co p r o ce s s o r )   an d   b y   s o f t w ar e   b y   m ea n s   o f   s y s te m   ca ll s   ( OS   lev e l) .   SP en d o w ed   with   its   co p r o ce s s o r   is   co n n ec ted   w i th   C o r o f   m u lti - co r s y s te m .   E ac h   C o r h as  it s   o w n   SP a n d   th is   o n c an   b ac ce s s ib le  b y   o th er   C o r es  f o r   b etter   e f f ici en c y   o f   t h M u lt i - T ask in g .   T h co p r o ce s s o r   ab s o r b s   ce r tain   r eq u ests   o f   r ea d in g   o r   w r itin g   a n d   s o   th p er f o r m an ce   o f   t h p r o g r a m s   w ill  b ac tu all y   i m p r o v ed   t h a n k s   to   t h m in i m iza tio n   o f   ac ce s s   f r eq u e n cie s   to   DR A m e m o r y .       3.   P ARTI T I O O F   SPM   I NT O   F RAM E S     T h SP is   d iv id ed   in to   f r a m es o f   eq u al  ca p ac ities   [ 3 ] .   E ac h   o f   ( n - 1 )   f ir s f r a m es c o n tai n s   t w o   p ar ts :   a.   Sp ac f o r   h ea p ,   b.   Sp ac f o r   s tack .     E ac h   o f   t h e s e   t w o   s p ac es   is   g l an ce d   th r o u g h   a n   i n d ex   p o in te r   ( h ea p   p o in ter   an d   Stac k   p o in t r esp ec tiv el y ) .   T h e   last   f r a m o f   th SP ( SHF n - 1 )   co n tain s   t h p r o f iler s   o f   ( n - 1 )   f r a m es ,   as  s h o w n   in   Fi g u r 1 .   E v er y   ta s k   h as  it s   p r o f iler .   W h at  d o   w f in d   in t o   th p r o f iler   o f   a   f r a m SH F k   t h at  b elo n g s   to   th task   k ?   T h p r o f iler   SHF k   co n tain s :     a.   o u ts et  ad d r ess   o f   t h s tac k   in   B S ( B ac k u p   Sto r ag e)   s it u ated   in   Ma i n   Me m o r y ,     b.   o u ts et  ad d r ess   o f   t h h ea p   i n   B S,     c.   o u ts et  ad d r ess   o f   t h s tac k   in   t h SP M,   d.   Ou ts e t a d d r ess   o f   th h ea p   in   t h SP M.   T h s tack   ca n   b o n   o n o r   o n   s ev er al  f r a m e s   SHF s .   T h h ea p   ca n   also   b o n   o n o r   s ev er al  f r a m e s   SHFs .   SHF   is   i n d ep en d en tl y   a s s i g n ed   o f   t h o th er   SHF s   a n d   th er i s   n o   in ter n al  r elatio n   b e t w ee n   t h e m .   E v er y   Evaluation Warning : The document was created with Spire.PDF for Python.
I J R E     I SS N:  2089 - 4864       S o ftw a r a n d   Ha r d w a r fo r   ma n a g in g   S cra tch   P a d   Memo r ( C h a b a n Hem d a n i )   71   SHF  is   co m p letel y   u s ed   u n til   th er is   n o f r ee   p lace   an y   m o r e.   No   n e w   SHF  is   as s i g n ed   to   task   o n   t h co n d itio n   t h at  all  t h SH Fs   a s s i g n ed   to   t h is   ta s k   ar co m p letel y   f illed .   T h is   w a y   o f   o p e r atin g   i m p lie s   t h r ee   in ter est s :   a.   No   e m p t y   f r ag m en t,   b.   R ed u ctio n   o f   th co m p lex i t y   i n   th tr ac k   an d   i n   th p r eser v a tio n   o f   t h s tr u c tu r es  w h ic h   ar u s ed   to   m an a g v ar io u s   s tack s   an d   h e ap s ,   c.   Op p o r tu n it y   to   u s m u l titas k i n g .   P ar titi o n   o f   SP in to   f r a m es i s   as  f o llo w s   Fi g u r 1 :   m ec h a n is m   is   n ec e s s ar y   to   m a n a g t h ese   SH Fs   [ 3 ] .   Fo r   th at  p u r p o s e,   w p la n   s tr u c t u r e   SH FS   ( Stack   an d   Hea p   Fra m Str u ct u r es)  tak e n   u p   r esid en ce   in   M ain   Me m o r y   w h ic h   w ill  s p ec i f y   t h s ta te  o f   ev er y   SHF  an d   it s   m e m b er s h ip .   W h en   r eq u est  o f   tas k   is   t h r o w n   to   h a v f r ee   f r a m SHF,   th s tr u ct u r SHF S   w il b r e f er en ce d   b y   s y s te m   p r im iti v t o   f i n d   f r ee   p o s s ib l o n S HF  in   th e   SP a n d   att r ib u te  it  to   t h tas k .   A cr o s s   SHFS ,   t h tas k s   ar in f o r m ed   if   t h e y   ca n   m a k r eq u est  f o r   SHF  an d   w h er it  is   ex ac tl y   s it u ated .   I f   th er is   n o f r ee   s p ac a n y   m o r in   SP an d   w ca n n o allo ca te  n e w   SHF ,   w r eq u e s t h Ma i n   Me m o r y   to   ass i g n   s p ac f o r   th e   s tac k   a n d   s p ac f o r   h ea p   f o r   e v er y   tas k   at   th e   le v el  o f   t h B S.  W ass o ciate   an   ad d itio n al  s tr u c tu r B ta k en   u p   r esid en ce   i n   Ma i n   Me m o r y   f o r   th s tack   an d   t h h ea p   o f   ev er y   ta s k .   I i s   t h r o le  o f   OS  to   i n s u r t h m an a g e m e n o f   t h s tr u ct u r es  SHF an d   B S.  A l B ar cr ea ted   an d   m ain tain ed   i n   th Ma in   Me m o r y   [ 3 ] .   T h ey   w il b u n u s ed   i f   th er ar en o u g h   s p ac es  i n   SP M.   T h co n ten ts   o f   B w ill  n o b ag ain   tr an s f er r ed   to w ar d s   t h SHF s   [ 3 ] .   SP ac ce s s es  ar less   ex p e n s i v in   e n er g y   co n s u m p t io n   t h an   t h e   ac ce s s es  f o r   DR A ( o f f   ch ip   DR A M) .   T h SHFS   s tr u ct u r in   Ma i n   Me m o r y   i s   as  f o llo w s   Fig u r 2 :           Fig u r 1 .   Or g an izatio n   o f   t h SP in to   f r a m e s   [ 3 ]       Fig u r 2 .   Stru ct u r o f   SHF S ( Stack   Hea p   Fra m Stru ct u r e)   in   DR AM   Me m o r y .       4.   RO L E   O F   AU T O M AT O   T h A u to m ato n   f ill s   f o u r   f ea t u r es:   a.   So licits   t h DM AC   ( Dir ec M e m o r y   A cc e s s   C o n tr o ller ) ,   th r o u g h   t h OS  f o r   th Da ta  T r a n s f er   b y   DM f r o m   t h DR AM   to w ar d s   t h SP o r   v ice  v er s a,   b.   R ea d in g   o r   w r iti n g   in   t h Hea p   o f   th SP M,   c.   P u s h   o r   P u ll in   t h s tac k   o f   t h e   SP M,   d.   I f   t h s p ac o f   ad d r ess in g   o f   th r eq u e s o f   ac ce s s   o f   th e   d ata  is   o u t   o f   th e   li m it s   o f   t h SP M,   it  s e n d s   b ac k   th r eq u est to w ar d s   t h u p p er   lev el  o f   th h ier ar c h y   m e m o r y .     4 . 1 .   D M T ra ns f er   I n   DM A   ac ce s s ,   DM A C   ( Dir e ct  Me m o r y   A cc es s   C o n tr o ller )   f o r m u late s   r eq u est  o f   ac ce s s   to   C o r s o   th at  it  f r ee s   t h B u s es  o f   ad d r ess es  an d   d ata.   A s   s o o n   as  p o s s ib le,   C o r in f o r m s   th DM AC   b y   m ea n s   o f   a   s ig n al  o f   p er m is s io n   ( DG R ANT )   to   tak u p   b u s es  an d   u s th SP M.   C o r p u ts   its   B u s es  in   s tate  o f   h ig h   i m p ed an ce .   T h DM AC   ca n   t h en   r ea c h es SP b y   r eg ai n i n g   co n tr o l f r ee d   b u s es b y   C o r e.     4 . 2 .   Rea din g   o w rit ing   in t h H ea p o f   t he  SP M   T h au to m ato n   r ec eiv e s   r ea d   r eq u est  ( L o ad )   o r   w r ite  r eq u e s ( s to r e)   o f   th e   tas k i   a n d   it  a cc ess es   t p r o f iler   o f   th tas k i   s i tu ated   i n   SH n - 1   o f   SP to   r ea ch   T as i .   P r o f ile  o f   th T A S i = ( R e g i s ter   SH n - 1 ) + T I D i ./ ( T I D i = T ask   I d en tif ier   i) /           Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4 864     I J R E S   V o l.  6 ,   No .   2 J u l y   2 0 1 7   :   69     8 1   72   4 . 3 .   P us h o P ull   in t he  s t a ck  o f   SP M   T h au to m ato n   r ec ei v es  t h r eq u est  o f   t h tas k i   ( P u s h   o r   Pu ll)  an d   ac ce s s es  to   p r o f iler   o f   th ta s k i   s itu a ted   in   SH n - 1   o f   th SP to   r ea ch   s tack i .     4 . 4 .   Sp a ce   o f   Address i ng   o f   t he  Request  O uts ide   t he  L i m i t s   o f   SP M     I f   t h ad d r ess i n g   s p ac o f   t h r eq u e s o f   ac ce s s   to   t h d ata  is   o u o f   t h li m it s   o f   SP M ,   th e   Au to m a to n   s e n d s   b ac k   t h r eq u est  to w ar d s   th s u p er io r   h i er ar ch y   m e m o r y   ( D R A M) .   P r o g r a m m er   o f   co d s p ec if ie s ,   in   it s   co d e,   if   h w a n ts   to   allo ca te  d y n a m ic  m e m o r y   i n   SP M.   T h is   ca n   b m a d e,   f o r   ex a m p le,   b y   t y p M AL L OC 's  i n s tr u ctio n   o r   its   eq u i v alen t.  T h lib er atio n   o f   t h d y n a m ic  m e m o r y   is   m ad e,   f o r   ex a m p le,   b y   t y p FR E E ' s   i n s tr u ctio n   o r   its   eq u i v ale n t.  O n   t h m ee t in g   F R E E s   i n s tr u ctio n   in   co d e,   p r o ce d u r ( it  d o esn t   b elo n g   to   t h Au to m a to n )   r ea ch es   th e   s tr u ct u r SH FS   i n   Ma i n   Me m o r y   b y   p u tti n g   all   f ie ld s   S HF k   o f   th T ask   to   0   ( n il),   f ie ld   T DI K   to   0   an d   r elea s e s   B S k .   T h is   p r o ce d u r ca n   b i n te g r ated   in to   t h co d b y   P r o g r am m er   o f   co d e.   S y n o p tic   s ch e m o f   Au to m ato n   is   s h o w ed   i n   f o llo w i n g   Fig u r 3 :           Fig u r 3 .   I n ter n al  S y n o p tic  s c h e m o f   th a u to m ato n       5.   AL G O RI T H M I ST AT E   M ACH I NE   ( A SM )   DIAG RA M   O F   AUTOM AT O AND  DM M O DE   5 . 1 .     W e   p r ese n A l g o r ith m ic   State  Ma ch in ( A SM)   ch ar o f   Au to m ato n ,   d iag r a m   ea s ier   to   u n d er s tan d   an d   less   f o r m al  t h at  State  d ia g r a m :                           Evaluation Warning : The document was created with Spire.PDF for Python.
I J R E     I SS N:  2089 - 4864       S o ftw a r a n d   Ha r d w a r fo r   ma n a g in g   S cra tch   P a d   Memo r ( C h a b a n Hem d a n i )   73   5 . 2 .   AS M   dia g r a m   o f   H ea p blo ck   T 1             5 . 3 .   AS M   dia g r a m   o f   Sta ck   blo c k   T 2           Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4 864     I J R E S   V o l.  6 ,   No .   2 J u l y   2 0 1 7   :   69     8 1   74   5 . 4 .     AS M   dia g r a m   o f   DM T 1 - 3             6.   H ARDWA R E   RE A L I Z A T I O AND  SI M UL AT I O O F   AUTOM AT O E M B E DDED  O F P G CIR CUI T     T o   d esig n   co m p lete  s y s te m   as  s h o w n   i n   Fi g u r 4   w u s ed   E DK  ( E m b ed d ed   Dev elo p m e n Kit)   o f   Xilin x   w h o   allo w s   u s   to   co n c eiv o u r   o w n   e m b ed d ed   s y s te m   w it h   p r o ce s s o r   Mic r o   b laze   o n   th E D K.   Ou r   co p r o ce s s o r   ( S P M_ I P )   is   im p l e m en ted   as  an   I P   ( I n tellectu al   P r o p er ty )   d ir ec tl y   to   co n n ec to   th Mic r o   b laze   th r o u g h   co n n ec tio n   DFS L   ( Dir ec t Fast   Si m p le x   L in k )   an d   to   th m e m o r y   SP as s h o w n   in   Fi g u r 4 ) .           Fig u r 4 .   S y s te m   ar ch itect u r e       C o m p o n e n ts   o f   th s y s te m ,   T h s y s te m   w h ic h   w b u ilt i n cl u d es th f o llo w i n g   co m p o n e n ts :     6 . 1 .     M icro   B l a ze   Mic r o   B laze   is   an   em b ed d ed   s o f t - co r p r o ce s s o r   d esig n ed   an d   o p tim ized   f o r   th i m p le m en tatio n   i n   th FP G A   Xili n x .   Mic r o   B laze   is   R I S C   p r o ce s s o r   i n   3   f lo o r s   w it h   ar c h itect u r Har v ar d   an d   3 2   in ter n a l   r eg is ter s   o f   3 2   b its .   T h p r o c ess o r   co n tain s   ap p r o x i m atel y   7 0   o p tio n s   o f   co n f i g u r atio n   al lo w i n g   th u s er   to   s elec o r   to   p ar am eter ize  t h i n ter n al  co m p o n e n ts   ac co r d in g   to   its   n ee d s .   Am o n g   t h co n f i g u r ab le  o p tio n s ,   w e   m a y   ci te:  s ize  o f   t h ca c h e,   d ep th   o f   p ip elin e,   i n teg r ated   p er ip h er als,  MM U,   b u s   i n ter f ac e s   etc.   Xi  k er n el  is   t h o p er atin g   s y s te m   w h ich   w o r k s   o n   o u r   Mic r o   B laze .   Xi  k er n el  in cl u d es  an   A P I   o f   P OSI X.   T h is   A P I   allo w s   u s   to   d ef in e   t h v ar io u s   tas k s   ( t h r ea d s )   an d   t h e   v ar io u s   f u n c tio n s   to   r ea ch   th e   p er ip h er als o f   th s y s te m .     Evaluation Warning : The document was created with Spire.PDF for Python.
I J R E     I SS N:  2089 - 4864       S o ftw a r a n d   Ha r d w a r fo r   ma n a g in g   S cra tch   P a d   Memo r ( C h a b a n Hem d a n i )   75   6 . 2 .     SP M   SP is   i m p le m e n ted   b y   u s i n g   B R AM   o f   1 2 8   KB .   T h b l o ck   B R A M   is   co n f ig u r ab le  m e m o r y   m o d u le  ( i m p le m e n ted   i n   VH DL )   w h ic h   p o s s es s es  t w o   p o r ts   A   an d   B .   I n   o u r   ca s t h p o r A   i s   co n n ec ted   to   th B R AM   C ONT R OL L E R   w h ic h   i s   an   i n ter f ac b et w ee n   th b u s   P L B   a n d   SP M.   T h p o r B   is   co n n ec ted   to   th co p r o ce s s o r .     6 . 3 .     D M C o ntr o ller     DM A   C o n tr o ller   s u p p lies   s i m p le  s er v ices  o f   d ir ec ac ce s s   to   th m e m o r y   ( DM A )   to   p er ip h er als  an d   in   d ev ices  m e m o r y   co n n ec ted   to   th b u s   P L B .   DM A   C o n tr o ller   tr an s f er s   q u an tit y   o f   d ata  r esu lti n g   f r o m   an   ad d r ess   s o u r ce   to w ar d s   a n   ad d r ess   d esti n atio n   w it h o u i n ter v en t io n   o f   t h p r o ce s s o r .   I n   o u r   ca s e,   it   s er v e s   to   tr an s f er   th d ata  b et w ee n   SP M   an d   th DR AM   ac co r d in g   to   t h alg o r it h m   p r ev io u s l y   p r ese n ted .     6 . 4 .     DF SL   FS L   ( Fas Si m p le x   L in k )   is   b u s   o f   u n id ir ec tio n a co m m u n icat io n   ch a n n el  b ased   FIFO  u s ed   to   m ak f a s co m m u n icatio n   b et w ee n   t w o   ele m en t s   o f   FP GA .   T h d ep th   o f   FIFO  ca n   ac h iev 8 K.   T h in ter f ac F S L   is   av ailab le  o n   th p r o ce s s o r   Mic r o   B laze .   I n   o u r   s y s te m   w u s ed   th DF SL   v er s io n   ( Dir ec t   FS L )   w h ich   is   i m p le m e n ted   w it h o u FIF ( to   in cr ea s t h s p ee d   o f   co m m u n icatio n ) ,   t o   in ter co n n ec o u r   co p r o ce s s o r   to   th Mic r o   B laz e.     6 . 5 .   P L B   bu s   P L B   ( P r o ce s s o r   L o ca B u s )   s u p p lies   a n   in f r astr u ct u r o f   b u s   to   co n n ec a n   o p tio n al  n u m b er   o f   p er ip h er als  ( m a s ter s   a n d   s lav e s )   in   t h s y s te m .   I n   o u r   s y s te m   w e   also   f i n d   D R A M   o f   c ap ac it y   o f   2 5 6   MB ,   an   in ter r u p tio n   co n tr o ller   an d   ti m er .     6 . 6 .   Co pro ce s s o SP M _ I P   I n   th i s   p ar w p r esen t th s ig n als o f   SP M_ I P   as sh o w n   i n   Fi g u r 5 :           Fig u r 5 .   Sig n als o f   SP M_ I P       SP M_ I P p o s s ess es t w o   in ter f a ce s :     6 . 6 . 1 .   DF SL : c o n n ec ts   t h co p r o ce s s o r   to   th Mic r o   B laze   to   ex ch a n g t h d ata  w it h   it.   I p o s s ess es  t w o   t y p e s   o f   s i g n als:   Ma s ter ' s   d eg r ee   ( Mic r o   b laze - SP M_ I P )   an d   Slav ( SP M_ I P - Mic r o   B laze ) .     6 . 6 . 2 .   B RA M _ P O RT _ B :   co n n ec t SP M_ I P   to   B R A ( SP M )   to   b a b le  to   r ea d   an d   w r ite  i n   th lat ter .   T h in ter n al  s tr u ct u r o f   SP M_ I P   is   d escr ib e d   in   Fig u r 6 .   I t c o n s is t s   o f   f o u r   u n it s :   I NST R UC T I ON_ DE C ODE R ,   SP M_ HA ND L E R ,   SP M_ I NT E R F AC E   an d   C P U_ I NT E R FAC E .   T h is   s ep ar atio n   allo w s   r ea l i z in g   ev er y   f u n ctio n   in   a   s e p ar ate  co m p o n e n t.  T h er ef o r e,   it  f ac il itates  t h e   tr an s latio n   in   co d VHD L   t h v ar io u s   co m p o n en t s   Har d w ar in   th s y n t h esi s   to o l.     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4 864     I J R E S   V o l.  6 ,   No .   2 J u l y   2 0 1 7   :   69     8 1   76       Fig u r 6 .   I n ter n al  s tr u ct u r o f   SP M_ I P       7.   SI M UL AT I O N   Dir ec w r iti n g   in   SP to   in itia lize  it  s h o w n   in   Fi g u r 7 .           Fig u r 7 .   Dir ec w r iti n g   in   t h SP to   in itialize  it     Evaluation Warning : The document was created with Spire.PDF for Python.
I J R E     I SS N:  2089 - 4864       S o ftw a r a n d   Ha r d w a r fo r   ma n a g in g   S cra tch   P a d   Memo r ( C h a b a n Hem d a n i )   77   I n   1 ”,   co p r o ce s s o r   r ec eiv es  d ata  f r o m   Mic r o   b laze   ( FS L _ M_ W r ite = ' 1 ' ) .   First,  i r ec eiv es  t h e   in s tr u ctio n   v ia   FS L _ M_ Data   0 x 0 FF FF FF   ( C MD =0 0 ) ,   th en   th d ata  to   b w r itte n   a n d   f in all y   t h ad d r es s   0 x 8 A 2 3 1 0 0 4 .   I n   2 ”,   d ata  is   w r itten   i n   th SP M.       7 . 1 .     Rea d in TAS   I n   " 1 ",   co p r o ce s s o r   r ec eiv es  d ata  f r o m   Mic r o   B laze   ( F S L _ M_ W r ite=' 1 ' ) .   I n   " 2 " ,   it  d ec o d es  th e   in s tr u ctio n   ( C MD =1 1 ,   T A S K _ I D= 0 0 0 1 ,   R E QUE ST =0 0 1 ) .   I n   " 3 ",   SP M_ HA ND L E R   h u r r ies  u p   an d   b e g i n s   to   lo ad   r eg is ter s   4 ,   5 ,   6 ,   7 ,   8 .   P R OFI L E R _ P OI NT E R 0 x 8 A 3 0 0 0 0 4 - P R OFI L E R _ ADDR E SS :   0 x 8 A 3 1 0 0 0 4 - HE A P _ C UR R _ P T R _ SP M:   0 x 8 A 2 0 0 0 F - ST AK_ C U R R _ P T R _ SP M:   0 x 8 A 2 0 0 5 F - HE A P _ C UR R _ P T R _ DR A M 0 x 9 0 0 0 0 0 FF   ST A K_ C U R R _ P T R _ DR A M :   0 x 9 0 0 0   1 0 E F.   I n   " 8 " ,   SP M_ HA NDL E R   r ec eiv es  m e m o r y   w o r d   o f   th e   SP 0 x C C C C DDD th at  i s en d s   i t   to w ar d s   t h C P i n   " 1 0 v ia  FS L _ S_ Data   a n d   it   p o s itio n s   FS L _ S_ C o n tr o l,  FS L _ S_ E x is ts   a n d   I NT E R R R UP T   to   th h i g h   s ta te  i m p ed an ce .   R ea d   in   T AS s h o w n   i n   F ig u r 8 .           Fig u r 8 .   R ea d   in   T A S       7 . 2 .     Writ in T AS   Sh o w n   in   F ig u r 9   w r ite  i n   T AS.   Al w a y s   af ter   th lo ad   o f   r eg is ter s   P R OFI L E R _ P OI NT E R 0 x 8 A 3 0 0 0 0 4 - P R OFI L E R _ ADDR E SS :   0 x 8 A 3 1 0 0 0 4 - HE A P _ C UR R _ P T R _ SP M:   0 x 8 A 2 0 0 0 0 F - ST A K_ C UR R _ PT R _ SP M:   0 x 8 A 2 0 0 0 5 F - HE A P _ C U R R _ P T R _ DR A M :   0 x 9 0 0 0 0 0 FF   ST A K_ C U R R _ P T R _ DR A M :   0 x 9 0 0 0   1 0 E F   I n   " 1 " ,   W r itin g   o f   th d ata   0 x F2 2 2 2 2 2 2   at  th ad d r ess   HE A P _ C U R R _ P T R _ SP M= 0 x 8 A 2 0 0 0 F+4 =0 x 8 A 2 0 0 0 1 3 .   I n   " 2 "   A n d   " 3 " ,   Up d ate d   HE A P _ C U R R _ P T R _ SP 0 x 8 A 2 0 0 0 1 3 )   an d   HE A P _ C UR R _ P T R _ DR A ( 0 x 9 0 0 0 0 0 FF +4 =0 x 9 0 0 0 0 1 0 3 )   in   th SP M.   I n   " 4 ",   s en d in g   s u ite  o f   A ,   0 x AAAA AAAA   a s   r eq u est  to   i n f o r m   th Mic r o   B laze   th at  DM tr an s f er   ( SP to w ar d s   DR AM )   is   n ec es s ar y .     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4 864     I J R E S   V o l.  6 ,   No .   2 J u l y   2 0 1 7   :   69     8 1   78       Fig u r 9 .   W r ite  in   T A S       7 . 3 .   P ull   t he  s t a ck   Sh o w n   in   F ig u r 1 0   p u ll th s t ac k .   A l w a y s   a f ter   th lo ad   o f   t h r eg is ter s   P R OFI L E R _ P OI NT E R 0 x 8 A 3 0 0 0 0 4 - P R OFI L E R _ ADDR E SS 0 x 8 A 3 1 0 0 0 4 - HE A P _ C UR R _ P T R _ SP M 0 x 8 A 2 0 0 0 0 F - ST A K_ C UR R _ PT R _ SP M 0 x 8 A 2 0 0 0 5 F - HE A P _ C U R R _ P T R _ DR A M 0 x 9 0 0 0 0 0 FF   ST A K_ C U R R _ P T R _ DR A M 0 x 9 0 0 0   1 0 E .           Fig u r 1 0 .   P u ll th s tack       I n   " 1 " ,   r ea d in g   d ata  0 x D AAA E E E f r o m   ad d r ess   ST AK_ C UR R _ P T R _ SP M:  0 x 8 A 2 0 0 0 5 F.  I n   " 2 " ,   u p d atin g   o f   ST A K_ C UR R _ P T R _ SP ( 0 x 8 A 2 0 0 0 5 F + 4 = 0 x 8 A 2 0 0 0 6 3 )   in   th SP M.   I n   " 3 " ,   s en d in g   d ata  to   th Mic r o   B laze .     7 . 4 .   P us h in t he  s t a ck   Sh o w n   in   F ig u r 1 1   P u s h   in   t h s tack A l w a y s   a f ter   th lo ad   o f   r eg is ter s   P R OFI L E R _ P OI NT E R 0 x 8 A 3 0 0 0 0 4 - P R OFI L E R _ ADDR E SS 0 x 8 A 3 1 0 0 0 4 - HE A P _ C UR R _ P T R _ SP M 0 x 8 A 2 0 0 0 0 F   Evaluation Warning : The document was created with Spire.PDF for Python.