I nte rna t io na l J o urna l o f   Rec o nfig ura ble a nd   E m bedd e d Sy s t em s   ( I J RE S)   Vo l.   10 ,   No .   3 ,  N o v em b e r   2 0 2 1 ,   p p .   1 5 7 ~ 1 6 7   I SS N : 2 0 8 9 - 4 8 6 4 ,   DOI : 1 0 . 1 1 5 9 1 /ij r es . v 10 .i 3 . p p 1 5 7 - 1 6 7       157       J o ur na l ho m ep a g e :  h ttp : //ij r es.ia esco r e. co m   H euris tic  a lg o rith ms  f o r dyna mic s cheduling  of  mo lda ble t a sks   in multicor e emb edded sy stems       T a k um a   H i k ida 1 ,   H iro k i N is hik a wa 2 ,   H iro y uk i To m iy a ma 3   1, 2, 3 G ra d u a te S c h o o l  o f  S c ien c e   a n d   E n g in e e rin g ,   Rit s u m e ik a n   U n i v e rsity ,   Ja p a n   2 Re se a rc h   F e ll o w,  Ja p a n   S o c iety   f o r  th e   P ro m o ti o n   o f   S c ien c e ,   Ja p a n       Art icle  I nfo     AB S T RAC T   A r ticle  his to r y:   R ec eiv ed   May   27 ,   2 0 21   R ev is ed   J u n   18 ,   2 0 21   Acc ep ted   Au g   2 ,   2 0 21       Dy n a m ic  sc h e d u li n g   o f  p a ra ll e l  tas k s  is  o n e   o f  th e   e fficie n t  tec h n i q u e s  to   a c h iev e   h ig h   p e rf o rm a n c e   in   m u lt ico re   sy ste m s.  M o st  e x isti n g   a l g o rit h m s  fo r   d y n a m ic  tas k   sc h e d u li n g   a ss u m e   th a t  a   tas k   r u n s   o n   o n e   o f  th e   m u l ti p le  c o re s   o r  a   fix e d   n u m b e r  o f  c o re s.  E x ist in g   re se a rc h e s  o n   d y n a m ic  tas k   s c h e d u li n g   m e th o d s  h a v e   e v a lu a ted   th e ir  m e th o d s  i n   d iffere n t   e x p e rime n tal  e n v iro n m e n ts  a n d   m o d e ls.  I n   th is  p a p e r,   t h e   d y n a m ic  tas k   sc h e d u li n g   m e th o d s   a re   sy ste m a ti c a ll y   re a rra n g e d   a n d   e v a lu a te d .   K ey w o r d s :   Dy n am ic  s ch ed u lin g   F ix ed   n u m b er   Heu r is tic  alg o r ith m   Mu ltico r e   Par allel  co m p u tin g   T h is i s  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 :   T ak u m a  Hik id a   Gr ad u ate  Sch o o l  o f   Scien ce   a n d   E n g in ee r in g   R its u m eik an   Un iv er s ity   1 - 1 - 1   No jih ig ash i,  Ku s atsu ,   S h ig a,   5 2 5 - 8 5 7 7 ,   J ap an   E m ail: ta k u m a. h ik i d a@ to m iy am a - lab . o r g       1.   I NT RO D UCT I O N   R ec en t  em b ed d e d   s y s tem s   h a v e  b ee n   eq u ip p e d   with   a  m u ltico r e  s y s tem - on - a - ch ip   to   ac h iev e  h i g h   p er f o r m an ce   an d   p o wer   ef f ici en cy .   I n   o r d er   to   f u lly   ex p lo it  th e  p o ten tial  p ar allelis m   in   t ask s   an d   m u ltico r e  ar ch itectu r es,  task   s ch e d u lin g   is   o n e   o f   th e   m o s t  im p o r tan t   tech n iq u es.  C lass ical  task   s c h ed u lin g   tech n i q u es   ex p lo it  task - lev el  p ar allelis m   b y   ass i g n in g   m u ltip le  task s   to   d if f er en t  c o r es  co n cu r r e n tly ,   b u t  th ey   ass u m e  th at   ea ch   task   r u n s   o n   a  s in g le  co r e  in   a  s in g le - th r ea d e d   m an n er .   Mo d er n   tec h n iq u es  allo w  a  m u lti - th r ea d ed   task   to   r u n   o n   m u ltip le  co r es,  wh ic h   tak es in to   ac co u n t b o th   task -   an d   d ata - p ar allelis m s .   T ask   s ch ed u lin g   ca n   b e  class if ied   f r o m   a  v ar iety   o f   p er s p ec ti v es.  On e  class if icatio n   is   wh eth er   co r es  ar e  h o m o g en eo u s   o r   h eter o g e n eo u s ,   an d   t h is   wo r k   ass u m es  h o m o g en e o u s   co r es.  An o t h er   class if icatio n   is   wh en   a  s ch ed u lin g   d ec is io n   is   m ad e.   I f   s ch e d u lin g   is   d ec id e d   at  th e  d esig n   tim e  an d   is   u n ch an g ed   at  r u n tim e ,   s u ch   s ch ed u lin g   is   ca lled   s ta tic  s ch ed u lin g .   Static  s ch ed u lin g   is   s u ited   to   s m al l - s ca le  em b ed d e d   s y s tem s   wh er e  r elea s e  tim es  ( a. k . a.   ar r iv al  tim es  o r   ac tiv atio n   tim es)   o f   th e  task s   ar e  k n o w n   a  p r io r i.  I f   a  s ch ed u lin g   d ec is io n   is   m ad e  at  r u n tim e ,   s u ch   s ch ed u lin g   is   ca lled   d y n am ic  o r   o n lin e.   Sin ce   th e  f u n ctio n ality   o f   em b ed d e d   s y s tem s   is   co n tin u ally   b ec o m in g   m o r e  c o m p l ex   an d   d y n am ic,   d y n am ic  t ask   s ch ed u lin g   h as  b ec o m e  m o r e  im p o r tan t th a n   e v er ,   an d   th is   p ap er   ad d r ess es d y n am ic  task   s ch ed u lin g .   T ask   s ch ed u lin g   ca n   b e   class if ied   b ased   o n   th e   p ar allelis m   in s id e  th e  task s .   C lass ical  task   s ch ed u lin g   ass u m es  th at  ta s k s   ar e  n o t  p ar allel.   E ac h   task   is   a s s u m ed   to   b e  s in g le - th r ea d ed   an d   r u n   o n   a  s in g le  co r e.   R ec en tly ,   p ar allel  task s   ( m u lti - th r ea d ed   task s )   h av e   b ec o m e   p o p u lar   n o t   o n ly   f o r   s u p er c o m p u tin g   b u t  also   f o r   em b ed d e d   co m p u tin g   d u e  t o   th e  in cr ea s in g   n u m b er   o f   c o r e s   in   em b ed d ed   s y s tem s .   Par allel  task s   ar e  f u r th er   Evaluation Warning : The document was created with Spire.PDF for Python.
            I SS N :   20 89 - 4 8 6 4   I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t ,   Vo l.  10 ,   No .   3 ,  No v em b er   2 0 2 1 :   157   –   1 6 7   158   class if ied   in to   g an g   task s   an d   f o r k - jo in   task s .   T h r ea d s   in   a   g an g   task   a r e  ex ec u ted   s y n ch r o n o u s ly .   All  o f   t h e   th r ea d s   g et  s tar ted   an d   co m p le ted   at  th e  s am e  tim e.   On   th e  o th er   h an d ,   th r ea d s   in   a  f o r k - jo i n   task   ar e  ex ec u ted   in d ep en d en tly   o f   o n e   an o th e r .   T h e  tim in g   b eh av io r   o f   g an g   task s   is   m o r e  p r ed ictab le  th a n   th at  o f   f o r k - jo in   task s ,   an d   th er ef o r e,   g a n g   task s   ar e  s u itab le  f o r   r ea l - tim e  em b ed d ed   s y s tem s .   T h is   p ap er   as s u m es  g an g   task s .   Fro m   an o th er   p er s p ec tiv e,   p a r allel  task s   ar e  class if ied   in t o   th r ee   ty p es,   i.e . ,   r ig id   task s ,   m o ld ab le   task s   an d   m allea b le  task s ,   b ased   o n   w h en   th e   p ar allelis m   ( th e  n u m b er   o f   co r es)   is   d ec id ed .   T h e  n u m b er   o f   co r es  ass ig n ed   to   a  r ig id   task ,   a  m o ld ab le  task   an d   a  m allea b le  ta s k   is   d ec id ed   b ef o r e  task   s ch e d u lin g ,   d u r in g   task   s ch ed u lin g   an d   at  r u n tim e,   r es p ec tiv ely .   T h is   p a p er   ass u m es m o ld ab le  g a n g   task s .   T ask   s ch ed u lin g   is   a  k i n d   o f   class ical  p r o b lem   in   t h e  f ield   o f   co m p u ter   s cien ce   an d   h as  ex ten s iv ely   b ee n   s tu d ied   f o r   s ev er al  d ec ad es.  Ver y   ea r ly   wo r k   o n   m u ltic o r e  task   s ch ed u lin g   ass u m es  t h at  task s   ar e  s in g le - th r ea d ed .   E ar ly   alg o r ith m s   tr y   to   ex ec u te  as  m an y   task s   a s   p o s s ib le  s im u ltan eo u s ly   o n   d if f er en t  c o r es  b y   ex p lo itin g   in ter - task   p a r allelis m .   Dr o zd o wsk i   [ 1 ]   p r o v id ed   an   ex h au s tiv e  s u r v e y   o f   class ic  task   s ch ed u lin g   m eth o d s   in   m u ltico r e  ar c h itec tu r es.  Sch ed u lin g   o f   task s   o n   m u ltip le  co r es  b y   ex ec u tin g   m u ltip le  in d ep e n d en t   task s   o n   m u ltip le  c o r es  in   p ar allel.   A   lis t  s ch ed u lin g   alg o r ith m   was  p r o p o s ed   i n   wh ich   s p ec if ic  p r io r ities   ar e   ca lcu lated   an d   ass ig n ed   to   ea ch   task   [ 2 ] - [ 5 ] .   T h e  lis t  s ch ed u l in g   alg o r ith m   ass ig n s   th e  h ig h est  p r io r ity   task   to   th e  f r ee   co r e  u n til  all   task s   a r e  s ch ed u le d .   L is t  s ch ed u lin g   is   g en er ally   ac ce p ted   as  an   attr ac tiv e  ap p r o ac h   b ec au s e  it  ca n   c o m b in e   lo w  c o m p lex ity   a n d   g o o d   r esu lts .   B o th   ap p r o ac h es  ass u m e  t h at  ea ch   task   is   ex ec u ted   o n   a   s in g le  c o r e   wit h o u t   co n s id er atio n   o f   d ata  p ar allelis m .   T h e   wo r k s   in   [ 1 ] - [ 5 ]   ar e   class if ied   as  s tatic  s ch ed u lin g .   I t is n o t p o s s ib le  t o   m ak e  class if icatio n s   r elate d   to   p ar allelis m   task s .   A   lis t - b ased   s ch ed u lin g   alg o r i th m   f o r   d ata - p a r allel  task s   was  p r o p o s ed   [ 6 ] .   T h eir   w o r k   as s u m es  th at   a  s et  o f   d ep e n d en t   task s   is   g i v en   in   th e   f o r m   o f   a  task   g r a p h   an d   ea c h   task   is   ass ig n ed   to   a  f i x ed   n u m b er   o f   co r es  to   m in im ize  th e  o v er all   len g th   o f   th e  s ch ed u le.   T h eir   s ch ed u lin g   is   class if ied   as  s t atic  s ch ed u lin g   f o r   r ig id   g a n g   task s .   Yan g   an d   Ha   [7 ],   an d   V y d y a n ath an   et  a l .   [ 8 ]   th e y   d ea lt  with   s tatic  s ch e d u lin g   o f   g a n g   a n d   m o ld ab le  task s .   R ec en t  p u b licatio n s   in clu d e  [ 9 ]   an d   [ 1 0 ]   f o r   m o ld a b le  g an g   task s .   Sh im ad a   et  a l .   [ 9 ]   p r o p o s ed   I L P - b ased   s ch ed u li n g .   T h e  au th o r s   o f   [ 1 0 ]   p r o p o s ed   a  s ch ed u lin g   ap p r o ac h   b ased   o n   co n s tr ain t   p r o g r a m m in g .   R esear ch er s   d e alt  with   s tatic  s ch ed u lin g   o f   g an g   a n d   m allea b le  task s   [ 1 1 ] - [ 1 4 ] .  A n   alg o r ith m   to   d eter m i n e  th e   o p tim al  s o lu t io n   f o r   task   allo ca tio n   in   a  h et er o g en e o u s   en v ir o n m en t   was  p r o p o s ed   [ 1 5 ] - [ 1 8 ] .  I t sh o u ld   b e   n o te d   th at  th e  s ch ed u lin g   a p p r o a c h es p r esen ted   in   [ 1 ] - [ 1 8 ]   ar e  n o t d y n am ic  b u t static.   Ye   et  a l .   [ 1 9 ]   attem p ted   to   d e v elo p   an   o n lin e  s ch ed u lin g   m o d el  f o r   m o ld a b le  task s .   Yan g   et  a l .   [ 2 0 ]   d ev elo p e d   a  n ew  alg o r ith m   f o r   d y n am ic  task   s ch ed u lin g   i n   a  h eter o g en eo u s   m u ltip r o c ess o r   s y s tem .   T h e  a u th o r s   o f   [ 2 1 ] - [ 2 3 ]   p r esen ted   a  n ew  s ch ed u lin g   alg o r ith m   f o r   h eter o g en eo u s   d is tr ib u ted   co m p u tin g   s y s tem s .     Dy n am ic  s ch ed u lin g   h as  also   b ee n   ap p lied   in   th e  f ield   o f   HPC .   R am ez an i  [ 2 4 ]   p r o p o s e d   C PA,  a  h eu r is tic - b ased   d y n am ic - c r itical  p ath - awa r e   s ch ed u lin g   m e t h o d   f o r   s ch ed u lin g   task   g r ap h s   o n   m u lti - FP GA  s y s tem s ,   ag ain s t  th e  b ac k g r o u n d   o f   b ei n g   p lag u ed   with   t h e  p r o b lem   o f   co m p u tin g   r es o u r ce s   to   r u n   HPC   ap p licatio n s .   Priy a   an d   Sah a n a,   [ 2 5 ]   im p lem en ted   f ir s t  co m e  f ir s t  s er v ed   ( FC FS )   in   HPC   u s in g   m ess ag e  p ass in g   ap p licatio n   p r o g r am m er   in ter f ac e  ( MPI ) .   T h is   p ap er   s tu d ies  d y n am ic  s c h ed u lin g   o f   m o ld a b le  g an g   task s ,   wh er e  task s '   ar r iv al  tim e  o r   p er io d   is   u n k n o wn   in   a d v an ce .   I n   th is   p ap er ,   d y n am ic  task   s ch ed u lin g   m eth o d s   ar e   s y s tem atica lly   r ea r r an g e d   a n d   p r o p o s e d ,   an d   ev al u ate  th em   in   a  co m m o n   e n v ir o n m en t.  C o n tr ib u tio n s   o f   th is   p ap er   ar e :   i)   n in e  s ch ed u lin g   alg o r ith m s   b ased   o n   task   s elec tio n   an d   p ar allelis m   d ec is io n   ar e   s y s tem atica lly   p r o p o s e d ,   an d   ii)  th e  n in e   alg o r ith m s   ar e   q u a n titativ ely   ev alu ate d,   a n d   d em o n s tr ate  t h at  two   alg o r ith m s   ar e   m o r e   ef f ec tiv e   th an   th e  o th er   s ev en .       2.   P RO B L E M   D E F I N I T I O N   I n   th e   s ch ed u lin g   p r o b lem s   th at  ar e  tack le d   in   th is   p a p er ,   a  s et  o f   task s   is   g iv en ,   wh er e   th e   ex ec u tio n   tim e  o f   ea ch   task   is   k n o wn   b u t  th e  ar r iv al  tim e  o r   p er io d   ar e  u n k n o wn   in   a d v an ce ,   a n d   th e  o b jectiv e  is   to   m in im ize  th e  s ch ed u le  len g t h   ( a. k . a. ,   m ak esp an ) .   T h e  ex ec t u o n   tim e   o f   ea c h   task   is   d e p e n d an t  o f   th e   d eg r ee   o f   p a r alellis m .   T ab le  1   r e p r e s en ts   an   ex am p le   o f   th e  e x e cu to n   tim e   f o r   th e   task s   in   a   task - g r ap h .   I n   t h e  f o llo win g   ex a m p le,   th e  n u m b e r   o f   co r es  in   th e  tar g et  s y s tem   is   ass u m e d   f o u r ,   an d   th e  p a r al lelis m   o f   ea ch   task   is   ass u m ed   to   r an g e   f r o m   o n e   to   f o u r .   An   i n cr ea s e  in   th e   n u m b er   o f   co r es  u s ed   d o es  n o t  n ec ess ar ily   lead   to   a   d ec r ea s e  in   ex ec u tio n   tim e.   Fo r   ex am p le,   in   T a b le  1 ,   th e  ex e cu tio n   tim e  o f   task   1   d o es n o t c h an g e  e v en   if   two   o r   m o r e  c o r es  ar e  allo ca ted .   I n   th is   ca s e,   ass u m in g   th at  th e  u p p er   p ar allelis m   lim it  f o r   task   1   is   2 ,   th e  n u m b er   o f   co r es th at  e x ce ed   th e  u p p e r   p ar allelis m   lim it f o r   ea ch   task   will n o t b e  allo ca ted .   T ask   1   tak es  3 0   tim e - u n its   wh en   ex ec u ted   o n   o n e   co r e.   I t  ta k es  2 0   tim e - u n its   if   th e   task   is   ex ec u ted   o n   two   co r es.  I f   it  ex ec u ted   o n   th r ee   o r   f o u r   co r es,  th e  ex e cu tio n   tim e  is   n o   s h o r ter   th an   2 0   tim e - u n its .   T h e  r ea s o n   wh y   th e  e x ec u tio n   tim e s   o n   th r ee   co r es  an d   f o u r   c o r es  d o   n o t  c h an g e   is   th at  th e   p er f o r m an ce   f o r   task   1   ca n   h ar d l y   b e  im p r o v ed   e v e n   if   m o r e  co r es  ar e   ass ig n ed   to   task   1   t h an   two   s in ce   th e  o v e r h ea d   f o r   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t   I SS N:  2089 - 4 8 6 4       Heu r is tic  a lg o r ith ms fo r   d yn a mic  s ch ed u lin g   o f m o l d a b le  ta s ks in   mu ltico r e  emb ed d ed   …  ( Ta ku ma   Hikid a )   159   p ar alleliza tio n   b ec o m es  lar g e .   Fo r   th is   r ea s o n ,   ass ig n m en t s   o f   t wo   c o r es  to   task   1   is   t h e  m o s t  ef f ec tiv e  s elec tio n   in   ter m s   o f   p e r f o r m a n ce   an d   r eso u r ce s .       T ab le  1 .   E x ec u tio n   tim es o f   ei g h t m o ld a b le  task s       N u mb e r   o f   c o r e s   R e l e a s e   Ti me     1   2   3   4   Ta sk   1   30   20   20   20   0   Ta sk   2   30   30   30   30   0   Ta sk   3   70   40   30   25   20   Ta sk   4   30   25   20   15   50   Ta sk   5   70   40   40   40   50   Ta sk   6   90   50   45   45   50   Ta sk   7   20   15   10   10   50   Ta sk   8   10   10   10   10   50       R ec all  th at  th is   p ap er   ass u m es   d y n am ic   s ch ed u lin g   o f   task s   wh er e  th e  task s   ar r iv al  tim e  o r   th e  p er io d   is   u n k n o wn   b ef o r eh an d .   Ho w ev er ,   f o r   co m p r eh e n s io n ,   th e   ex am p le  is   s h o wn   with   r elea s e   tim e  f o r   ea c h   task .   T ask   1   an d   task   2   ar e  ass u m ed   to   b e  ar r iv e d   at  tim e  0   an d   b ec o m e  r ea d y   to   r u n .   T ask   3   i s   ass u m ed   to   b e  ar r iv ed   at  tim e  2 0 .     Fig u r e  1   s h o ws  o n e   o f   s ch ed u lin g   r esu lts   th at  th e   task s   in   T ab le  1   a r e  m a p p ed   o n   th e  f o u r   co r es.  At   tim e  0 ,   th er e  ar e  task   1   a n d   ta s k   2   th at  ar e  ar r iv e d   an d   b ec o m e  r ea d y   f o r   th e  ex ec u tio n .   T h e  p er f o r m an ce   o f   task   1   ca n   b e  im p r o v e d   if   two   co r es  ar e  ass ig n ed .   On   th e  o th er   h an d ,   th e  p er f o r m an ce   o f   task   2   ca n n o t  b e   im p r o v e d   ev en   if   th e  co r es  a r e  ass ig n ed .   T h er ef o r e,   two   co r es  ar e  ass ig n ed   to   task   1   a n d   a  s in g le  co r e  is   ass ig n ed   to   task   2 ,   r esp ec tiv el y .   W h en   task   3   b ec o m e s   av ai lab le,   co r e  0   an d   co r e   1   a r e  r elea s ed   an d   will  b e  ex ec u ted   b y   3   co r es,  in clu d in g   co r e  3 .   No t  all  co r es  ar e  n e ce s s ar ily   to   r u n .   I n   ad d itio n ,   a t  th is   p o in t  in   tim e,   ex ec u tin g   task   3   with   4   co r es  af ter   task   2   is   co m p leted   ca n   m in im ize  th e  ex ec u tio n   tim e   f o r   th e  3   task s ,   b u t  b ec au s e  s ch ed u lin g   is   b ased   o n   th e  ass u m p tio n   t h at  th e  task   will  b e  r elea s ed   at  an y   tim e ,   t ask   3   ex ec u tio n   d o   n o t w ait  f o r   task   2   to   co m p lete   ex ec u tio n .             Fig u r e  1 .   An   ex am p le  o f   a  s ch ed u lin g   r esu lt       At  tim e  5 0 ,   task s   th at   ca n   b e   e x ec u ted   is   4 ,   5 ,   6 ,   7 ,   an d   8 .   Al th o u g h   task   4   h as  th e   u p p er   p ar allelis m   lim it  o f   4 ,   a n d   task   5   also   h as  th e  u p p er   p ar allelis m   lim it  o f   2 .   I t  ca n   b e   co n s id er ed   t h at  task   5   h as  less   wo r k lo ad   in   p a r alleliza tio n .   Fo r   th is   r ea s o n ,   a  p o licy   o f   d i s tr ib u tin g   m o r e  co r es  to   task   5   th an   t o   task   4   is   ad o p ted   h er e.   I n   th is   way ,   th e   way   th e  d is tr ib u tio n   r u les ar e  d ef in ed   a f f ec ts   th e  s ch ed u le  le n g th .   R ath er   th an   allo ca te  an o th er   c o r e  to   task   4 ,   task   8   is   allo ca te d ,   wh ich   ca n   b e  co m p lete d   im m ed iately   b y   o n e  co r e .   On ce   ta s k   8   is   co m p leted ,   task   7   is   ex ec u ted   o n   th at  c o r e.   W h en   task   4   is   co m p leted ,   task   6   is   ex ec u ted   o n   th e  co r e.   As  a  r esu lt,  at  th e  tim e  wh en   task   5   co m p letes  ex ec u tio n ,   task   6 ,   wh i ch   h as  th e  lo n g est  ex ec u tio n   tim e  o n   o n e   o f   th e s e  co r es  an d   h as  th e   g r ea test   b en e f it  wh en   ex ec u ted   o n   t wo   co r es,   co u l d   b e  ex ec u ted   o n   two   c o r es.  I n   th is   way ,   wh ich   task s   ar e  ass ig n e d   to   wh ich   co r es  in   o r d er   o f   p r io r ity   an d   b y   wh at   r u les also   af f ec t th e  s ch ed u le  len g th .         3.   T H E   P RO P O SE D  H E UR I S T I C  A L G O RI T H M S   As  s ee n   in   th e  p r ev io u s   s e ctio n ,   th e   m o ld a b le  task   s ch ed u lin g   p r o b lem   ca n   b e  s p lit  in t o   two   s u b - p r o b lem s :  task   s elec tio n   an d   p ar allelis m   d ec is io n .   I n   th is   p ap er ,   task task   s elec tio n   in clu d es  FC FS ,   S J F   ( Sh o r test   J o b   First),   an d   Ov h .   I n   th e  FC FS   p o licy ,   task s   ar e  allo ca ted   in   p r i o r ity   o r d er   o f   task   ar r iv al.   I n   t h e   SJ F  p o licy ,   task s   ar e  al lo ca ted   in   p r io r ity   o r d er   o f   b u r s t  d u r atio n   o f   task s   o n   a  co r e.   I n   th e  Ov h   p o licy ,   task s   ar e  allo ca ted   in   p r io r ity   o f   s m all  p ar alleliza tio n   o v er h ea d .   T h e  Ov h   p o licy   r ed u ce s   th e  in cr ea s e  in   to tal   Evaluation Warning : The document was created with Spire.PDF for Python.
            I SS N :   20 89 - 4 8 6 4   I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t ,   Vo l.  10 ,   No .   3 ,  No v em b er   2 0 2 1 :   157   –   1 6 7   160   wo r k lo ad   wh e n   task s   ar e  p ar allelize d .   Par allelis m   d ec i s io n   in clu d es  Sin g le,   Ma x ,   Fit ,   an d   Fair .   I n   th e  Sin g le  p o licy ,   ea c h   task   is   allo ca ted   t o   a  s in g le  c o r e.   I n   th e   Ma x   p o licy ,   ea ch   task   is   allo ca ted   to   a   m ax im u m   n u m b er   o f   co r es.  I n   th e  Fit   p o licy ,   task   s elec ti o n   p r io r ity   task   is   all o ca ted   to   m ax im u m   c o r e.   I n   th e  Fair   p o licy ,   ea c h   task   ar e  g iv en   f air   n u m b e r   o f   co r es.   T o   d escr ib e  th e  d etails  o f   th e  s ch ed u lin g   p o licies,  an o th er   ex am p le  is   p r o v id e d   with   ex ec u tio n   tim e  o f   ea ch   task   as sh o wn   i n   T ab le   2 .       T ab le  2 .   Ex ec u tio n   tim e  o f   tas k s   d ep en d e n t o f   t h e  n u m b er   o f   co r es     N u mb e r   o f   c o r e s   R e l e a s e   Ti me     1   2   3   4   Ta sk   1   40   25   15   15   0   Ta sk   2   35   20   15   10   0   Ta sk   3   45   25   25   25   10   Ta sk   4   40   30   20   15   15   Ta sk   5   55   40   20   20   20   Ta sk   6   80   50   40   30   40   Ta sk   7   70   40   30   25   50   Ta sk   8   1 0 0   60   45   30   60       3 . 1 .   Sin g le - F CF S sche du li ng   Sin g le - FC FS   s ch ed u lin g   is   a  s im p le  tech n iq u e  th at  a  task   i s   ex ec u ted   o n   a  s in g le  c o r e  in   th e  FC FS   p o licy .   T h er ef o r e,   th e  p ar allel is m   f o r   ea ch   task   is   f ix ed   as  o n e  an d   th e  task s   ar e  ex ec u ted   in   th e  o r d er   th at   th ey   ar r iv e  i n   th e  q u eu e.   I n   T a b le  2 ,   f o r   ex am p le,   th e  e x ec u ti o n   tim es  o f   task   1   a n d   task 2   a r e  4 0   a n d   3 5   tim e - u n its   d u e  to   th e  s in g le - th r ea d e d   f ash io n ,   r esp ec tiv ely ,   an d   ta s k   1   an d   task   2   ar e  a r r iv ed   at  t im e  0   s o   t h at  task   1   an d   task   2   ar e  r ea d y   to   b e   ex ec u ted   in   th e   ar r iv i n g   o r d e r   o n   a   s in g le  co r e.   Fig u r e  2   r ep r esen ts   g an tt  ch a r t  to   s h o w  o n e  o f   s ch ed lin g   r esu lts   f o r   th e   task s   in   T ab le  2 .   T h e   x - ax is   o f   th e   g an tt  c h ar t  s h o ws tim e  an d   th e   y - ax is   s h o ws  th e  co r es.  I n   th e   f ig u r e ,   ea ch   task   is   ass ig n ed   to   a  s i n g le  co r e   f r o m   tim e  0 ,   a n d   t h e  o v er all  s ch e d u le  len g th   is   r ep r esen ted   as 1 5 5 ,   wh en   task   8   f in is h e d   r u n in g .   I n   g en e r al  ,   th e  s in g le - t h r ea d e d   ex ec u tio n   m in im izes  th e  p a r alleliza tio n   o v er h ea d .   T h e   p e r f o r m a n ce   ca n n o t  b e   s ca led   lin ea r y   with   th e  n u m b er   o f   co r es  s in ce   th er e  o cc u r s   th e  p ar alleliza tio n   o v e r h ea d .   Fo r   in s tan ce ,   th e  ex ec u tio n   tim e  o f   task   1   o n   d u al  c o r es  r ep r ese n ts   2 5   tim e - u n its   f o r   a  th r e ad .   T h er ef o r e,   th e  d u al   th r ea d s   co n s u m e  5 0   tim e - u n it s   in   to tal,   wh ich   is   lo n g e r   th an   4 0   tim e - u n its   o n   a  s in g le.   On   th e  o th er   h an d ,   th e   s in g le  th r ea d   o cc u p ies  a   co r e   u n til  its   en d   s o   th at  t h e  lo n g   ex ec u tio n   o f   a  task   m ay   d eg r ad e  th e  o v er all   s ch ed u lin g   ef f ec tiv en ess .   I n   th e  ex a m p le  o f   Fig u r e   2 ,   th e   ex ec u tio n   o f   task   8   r esu lts   i n   th e   p er f o r m a n ce   d eg r ad atio n   s in ce   th e  task   r u n s   f o r   a  lo n g   tim e.             Fig u r e  2 .   An   ex am p le  o f   Sin g l e - FC FS   s ch ed u lin g       3 . 2 .   S ing le - SJ F   s ched uli ng   Sin g le - SJ F  s ch ed u lin g   is   a  s i m p le  tech n iq u e   th at  a  task   is   ex ec u ted   o n   a  s in g le  co r e   in   th e  SJ F  p o licy .   T h e r ef o r e,   th e  p ar allelis m   f o r   ea ch   task   is   f ix ed   as  o n e  an d   th e  task s   ar e  ex ec u ted   in   th e  r ea r r an g e d   q u eu e  th at   is   s o r ted   in   th e   o r d er   o f   b u r s t  d u r atio n   o f   task s   e x ec u ted   o n   a  s in g le  c o r e.   I n   Fi g u r e   3 ,   f o r   ex a m p le,   th e  ex ec u tio n   tim es  o f   task   1   an d   task   2   ar e  4 0   an d   3 5   tim e - u n its   d u e  to   th e  s in g l e - th r ea d ed   f ash io n ,   r esp ec tiv ely .   Sin ce   t h e  ex ec u tio n   tim e   o f   task   2   is   s h o r ter   th a n   th at  o f   task   1 ,   task   2   is   allo c ated   o n   C o r e  0   a n d   task   1   is   allo ca ted   o n   C o r e   1 .   I n   th e  e x am p le,   th e  s ch ed u le  le n g th s   b y   Sin g le - FC FS   an d   Sin g le - SJ F  ar e  s h o wn   as 1 5 5 ,   wh ich   is   th e  s am e  r esu lt.     3 . 3 .   M a x - F CF S schedu lin g   Max - FC FS   s ch ed u lin g   is   a  tech n iq u e   th at  a  task   is   ex ec u te d   o n   a  m ax i m u m   n u m b er   o f   c o r es  in   th e   FC F S  p o licy .   T h er e f o r e,   th e  p ar allelis m   f o r   ea ch   task   is   f i x e d   as  m ax im u m   an d   th e  task s   a r e  ex ec u ted   in   th e   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t   I SS N:  2089 - 4 8 6 4       Heu r is tic  a lg o r ith ms fo r   d yn a mic  s ch ed u lin g   o f m o l d a b le  ta s ks in   mu ltico r e  emb ed d ed   …  ( Ta ku ma   Hikid a )   161   o r d er   th at  t h ey   ar r iv e  in   th e   q u eu e.   I n   th is   p ap e r ,   th e  m ax im u m   d e g r ee   o f   p ar allelis m   f o r   ea c h   task   is   ass s u m e d   to   s et   th e  n u m b er   o f   co r es  o n   a  tar g et  s y s tem .   Ho wev er ,   as  s h o wn   in   T ab le  3 ,   if   th e  ex ec u tio n   tim e  d o es  n o t   d ec r ea s e  as  t h e  n u m b er   o f   co r es  i n cr ea s es,  th e  s m al lest   n u m b er   o f   co r es  is   r e g ar d ed   as  th e   m ax im u m   p ar allelis m .   Fo r   ex am p le,   th e  m ax im u m   p a r allelis m   o f   T ask   3   is   r ep r esen ted   as  two .   I n   T a b le  3 ,   f o r   e x am p le,   th e  ex ec u tio n   tim es  o f   task   1   an d   task   2   ar e  1 5   a n d   1 0   tim e - u n its   in   th e  Ma x   p o licy ,   r esp ec tiv ely .   As  th e  s ch ed u lin g   r esu lt,  task   1   is   e x ec u ted   o n   th r ee   co r es,  an d   t ask   2   is   ex ec u te d   o n   f o u r   c o r es.   T h e  Ma x   p o licy   lead s   th e  m ax im u m   o v er h ea d   f o r   p ar alleliza tio n .   I n   Fig u r e  4 ,   th e  s ch ed u le  len g th   b y   Ma x - FC F S   is   1 7 0 ,   wh ich   is   lo n g er   th an   th e  Sin g le  p o licy .           Fig u r e  3 .   An   ex am p le  o f   Sin g l e - SJ F sch ed u lin g       T ab le  3 .   R em ar k in g   th e  m ax i m u m   d e g r ee   o f   p ar allelis m   o f   T ab le  2     N u mb e r   o f   c o r e s   R e l e a s e   Ti me     1   2   3   4   Ta sk   1   40   25   15   15   0   Ta sk   2   35   20   15   10   0   Ta sk   3   45   25   25   25   10   Ta sk   4   40   30   20   15   15   Ta sk   5   55   40   20   20   20   Ta sk   6   80   50   40   30   40   Ta sk   7   70   40   30   25   50   Ta sk   8   1 0 0   60   45   30   60           Fig u r e  4 .   An   ex am p le  o f   Ma x - FC F S sch ed u lin g       3 . 4 .   M a x - SJ F   s cheduli ng   Max - SJ F sch ed u lin g   is   a  tech n iq u e  th at  a  task   is   ex ec u ted   o n   a  m ax im u m   n u m b er   o f   co r es   in   th e  SJ F   p o licy .   Fig u r e  5   s h o ws  th e  M ax - SJ F  s ch ed u lin g .   At  tim e  0 ,   task   2   an d   task   1   ar e  ar r iv ed   in   th e  o r d er ,   a n d   at  tim e  2 5 ,   task   3 ,   4 ,   an d   5   ar e  ar r iv ed   to   r ea d y ,   a n d   th e  q u eu e  i s   s o r ted   in   th e  o r d er   o f   task   4 ,   3 ,   an d   5   in   th e  SJ F   p o licy .   At  tim e   4 0 ,   task   6   is   ar r iv ed   in   th e   q u e u e,   a n d   t h e  q u eu e  s o r ted   in   th e   SJ F  p o licy   is   in   th e   o r d er   o f   t ask   3 ,   5 ,   an d   6   s in ce   th e  ex ec u tio n   tim e  o f   task   6   is   lo n g er   th an   th o s e  o f   task   3   an d   task   5 .   At  tim e  6 5 ,   task   7   an d   8   ar e  a r r iv ed   an d   th e   q u e u e  is   r ea r r a n g ed   in   th e   o r d er   o f   task   5 ,   7 ,   6 ,   an d   8 ,   wh ich   is   f in a lly   d eter m in e d   f o r   s ch ed u lin g .     3 . 5 .   F it - F CF S schedu l ing   Fit   p o licy   is   s im ilar   to   th e  Ma x   p o licy   in   th at  th e  Fit   p o licy   tr ies  to   ex ec u te  task s   with   th eir   m ax im u m   p ar allelis m .   I f   th e  n u m b er   o f   av ailab le  c o r es  is   s m aller   th an   t h e  m ax im u m   p ar allelis m   o f   th e  task ,   all  th e  av ailab le  co r es a r e  ass ig n ed   to   th e  tas k.   Fig u r e   6   s h o ws th e  r esu lt o f   Fit - FC FS   s ch ed u lin g .   Acc o r d in g   to   T ab le   3 ,   task   1   an d   task   2   ar e  a r r iv ed   an d   a v ailab le  in   th e   o r d er   at  tim e   0 .   task   1   is   ex ec u ted   o n   th r ee   co r es  at  th e  m ax im u m   p ar alellis m ,   an d   ass ig n ed   to   th e  co r es.  Fo r   task   2 ,   th er e  is   n o   ch o ice   b u t  to   ass ig n   th e  r est  o f   c o r e,   C o r e  3 ,   at  th e   tim e.   At  tim e  1 5 ,   wh e n   T ask   1   c o m p letes  t h e  ex ec u tio n ,   t h r ee   co r es  ar e  r elea s ed   an d   b ec o m e  av ailab le.   T h e  task s   th at  ca n   b e  ex ec u ted   at  th e  tim e  ar e  ta s k   3 ,   4 ,   an d   5 .   Du e  Evaluation Warning : The document was created with Spire.PDF for Python.
            I SS N :   20 89 - 4 8 6 4   I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t ,   Vo l.  10 ,   No .   3 ,  No v em b er   2 0 2 1 :   157   –   1 6 7   162   to   th e   FC FS   p o licy ,   task   3   h as  th e  h ig h est  p r io r ity   an d   is   ass ig n ed   t o   two   co r es.   T h e   r em ai n in g   c o r e   ex ec u tes   th e  task   4 ,   a n d   task   5   waits  u n til  th e  co r es  a r e  av ailab le.   At  tim e  3 5 ,   wh en   T ask   2   c o m p letes  th e  ex ec u tio n ,   th e  s in g le  co r e  is   as s ig n ed   to   t ask   5 .   At  tim e  4 0 ,   wh en   T ask   3   co m p l etes  ex ec u tio n   an d   task   6   is   ar r iv ed ,   task   6   is   ass ig n ed   to   two   co r es.  At  tim e  5 0 ,   w h en   task   4   c o m p letes  th e  ex ec u tio n ,   task   7   an d   task   8   ca n   b e   ex ec u ted .   T ask   7   is   av ailab le  e ar lier   th an t  task   8   i n   th e   FC FS   p o licy ;  t h er ef o r e,   task   7   is   ass g in ed   to   th e   s in g le   co r e.   task At  tim e  9 0 ,   wh en   tas k   5   an d   ask   6   co m p lete  ex ec u t io n   at  th e  s am e  tim e,   3   co r es a r e  allo ca ted   to   task   8 .   T h e  s ch e d u le  len g t h   is   r ep r e s en ted   as 1 3 5   as a   r esu lt.             Fig u r e  5 .   An   ex am p le  o f   Ma x - SJ F sch ed u lin g           Fig u r e  6 .   An   ex am p le  o f   Fit - F C FS   s ch ed u lin g       3 . 6 .   F it - SJ F   s cheduli ng   T h is   tech n iq u e  is   b ased   o n   t h e  Fit   p o licy   an d   th e  SJ F  p o licy ,   wh ich   ar e  alr ea d y   p r esen ted   in   th e   p ap er .   T h e  q u eu e  is   s o r ted   in   th e  o r d er   o f   s h o r test - jo b - f ir s t  f o r   task   s elec t io n   an d   th e  p ar allelis m   i s   d eter m in ed   th r o u g h   th e   Fit   p o licy ,   wh ich   attem ts   to   ass ig n e   as  m an y   co r es  as  p o s s ib le  wi th in   th e   m ax im u m   d eg r ee   o f   p ar allelis m   f o r   task s .   Fig u r e  7   s h o ws a  Fit - SJ F sch ed u lin g   r esu lt.   At  tim e  0 ,   b o t h   o f   task   1   a n d   t ask   2   ca n   b e  ex ec u ted ,   b u t  s in ce   task   2   h as   a  s h o r ter   ex e cu ti o n   tim e  o n   a  s in g le  co r e  th a n   task   1 ,   task   2   is   ass ig n ed   to   f o u r   co r es  i n   t h e  Fit   p o licy   d u e  to   th e   m ax i m u m   p ar allelis m   in   ac co r d an ce   with   T ab le  3 .   At  ti m e  1 0 ,   wh e n   task   2   co m p letes  th e  ex ec u tio n ,   task   1   an d   task   3   ca n   b e   ex ec u te d .   task   1   is   th e  p r ed ec ess o r   task   to   task   3   s in ce   th e  s h o r ter   task   th an   task   3 ,   an d   3   c o r es  ar e   ass ig n ed   to   task   1 .   T h e  r em ain in g   co r e   is   to   task   3 .   At  tim e  2 5 ,   wh en   task   1   co m p letes th e  ex ec u tio n ,   task   4   c an   b e  ex ec u ted .           Fig u r e  7 .   An   ex am p le  o f   Fit - SJ F  s ch ed u lin g       3 . 7 .   F a ir - F CF S schedu li ng   Fair   tr ies to   ass ig n   co r es e q u ally   to   th e  task s   in   th e  q u e u e.   Fo r   ex am p le,   if   th er e  ex is t two   ta s k s   in   th e  q u eu e  an d   two   co r es  ar e  a v ailab le,   th e  Fair   p o licy   ass ig n s   o n e  co r e  to   ea c h   task .   I f   th er e   ex is t  th r ee   task s   in   th e  q u eu e   an d   two   co r es  ar e  a v ailab le,   th e  f ir s t  an d   s ec o n d   task s   in   th e  q u eu e   ar e  s elec ted   b ased   o n   th e   FC FS .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t   I SS N:  2089 - 4 8 6 4       Heu r is tic  a lg o r ith ms fo r   d yn a mic  s ch ed u lin g   o f m o l d a b le  ta s ks in   mu ltico r e  emb ed d ed   …  ( Ta ku ma   Hikid a )   163   Similar ly ,   if   th er e  ex is t  two   task s   in   th e  q u eu e  an d   th r ee   c o r es  ar e  av ailab le,   th e  f ir s t  task   in   th e  q u eu e  is   ass ig n ed   two   co r es,  an d   th e  s e co n d   t ask   is   ass ig n ed   a  co r e.   F ig u r e  8   s h o ws a  Fair - FC FS   s c h ed u lin g   r esu lt.   At  tim e  0 ,   two   co r es  o u t  o f   f o u r   co r es  ar e  ass ig n ed   to   ea ch   o f   task   1   an d   task   2 ,   r esp ec tiv ely   in   s u ch   a  way   th at  th e  co r es  ar e  ev en l y   d is tr ib u ted .   At  tim e  2 0 ,   wh e n   task   2   co m p letes  th e  ex ec u ti o n ,   task   3 ,   4 ,   a n d   5   ar e  ar r i v ed   in   t h e  q u eu e   an d   b ec o m e   av ailab le.   Du e  t o   th e   FC F S  p o licy ,   task   3   an d   4   ar e  ex ec u ta b le  in   th is   o r d er .   T h u s ,   task   3   an d   task   4   ar e  m ap p e d   o n   th e  r em ain in g   t wo   co r es  s o   th at  a   s in g le  co r e  is   ass ig n ed   to   ea ch   o f   th em .   A t  tim e  2 5 ,   wh en   task   1   co m p letes  th e  ex ec u tio n ,   t ask   5   is   d eter m in ed   to   r u n   o n   th e  two   co r es  s in c e   task   5   is   alo n e  i n   th e  q u eu e   at  th e  tim e.   At  tim e  6 0 ,   task   6   is   m ap p ed   o n   a  s in g le  co r e. .   At  t im e  6 5 ,   3   c o r es  ar e   r elea s ed ,   an d   th e  task s   th at  ca n   b e  ex ec u te d   ar e  task   7   a n d   task   8   in   th e  o r d er .   T h u s ,   task   7   is   ass ig n ed   to   a  s in g le  co r e,   an d   task   8   is   also   ass ig n ed   to   a  co r e  in   ac co r d a n ce   with   th e  Fair   p o licy .   T h e  r est  o f   th e  co r es  is   allo ca ted   to   task   8   d u e  to   t h e  FC FS   p o licy .   As th e  r esu lt,  th e  s ch ed u le  len g t h   is   r e p r esen ted   as 1 6 5 .           Fig u r e  8 .   An   ex am p le  o f   Fair - FC F S sch ed u lin g       3 . 8 .   F a ir - SJ F   s cheduli ng   T h e  tech n iq u e  is   b ased   o n   Fair   an d   SJ F  p o licies.  T h e  d eta il  o f   th is   tech n iq u e  is   d escr ib ed   with   a  s ch ed u lin g   ex a m p le  o f   Fig u r e   9 .   At  tim e  0 ,   th e   q u e u e  is   r ea r r an g e d   s o   th at  task   2   a n d   task   1   ar e  i n   th e  o r d e r   d u e  to   th e   SJ F  p o licy .   B ased   o n   th e   Fair   p o licy ,   task   1   an d   task   2   ar e   ass ig n ed   t o   two   co r es,  r esp ec tiv ely .   At   tim e  2 0 ,   task   3 ,   4 ,   an d   5   ar e  a r r iv ed .   As  well  as  th e  p r ev io u s   ass ig n em en t,  th e  q u e u e  is   s o r ted   in   th e  o r d e r   o f   task   4 ,   3 ,   an d   5 .   At  th e  tim e ,   th e  r em ain in g   n u m b e r   o f   co r e s   is   two   an d   task   4   an d   task   3   ar e  ass ig n ed   to   a   s in g le  co r e  b ased   o n   th e  Fair   p o licy ,   r esp ec tiv ely .   At  tim e   2 5 ,   task   5   is   ass ig n ed   to   two   co r es.  At  tim e  6 0 ,   wh en   task   4   c o m p le tes  its   ex e cu tio n ,   task   6 ,   7 ,   an d   8   ar e   r ea d y   to   r u n .   T h e   q u e u e  is   r ea r r a n g ed   in to   th e  o r d er   o f   task   7 ,   6   an d   8   d u e  to   th e  SJ F  p o licy ,   ac co r d in g   to   T ab l e  3 .   T h u s ,   task   7   is   ass ig n ed   to   a  s in g le  co r e.   At  tim e  6 5 ,   task   6   is   ass ig n ed   to   two   co r es  an d   task   8   i s   ass ig n ed   to   a  co r e.   As  th e  r esu lt,  T h e  o v er all  s ch ed u le  len g th   is   1 6 5   in   th e  f ig u r e.           Fig u r e  9 .   An   ex am p le  o f   Fair - SJ F sch ed u lin g       3 . 9 .   F a ir - O v h schedu lin g   I n   Fair - Oh v   s ch ed u lin g ,   p ar all elis m   d ec is io n   is   b ased   o n   t h e   Fair   p o licy .   On   th e  o th er   h an d ,   th e   Ov h   p o licy   is   th e  task   s elec tio n   t ec h n iq u e  to   ass ig n   co r es  wh er e  th e  task   is   s elec ted   b ase d   o n   th e  m in im u m   o v er h ea d   f o r   p a r alleliza tio n   o f   th e  task s   in   th e   q u e u e.   I n   g e n er al,   th e  i n cr ea s ed   d e g r ee   o f   p ar allelis m   o cc u r s   lar g e  o v e r h ea d s   f o r   p ar alleliz atio n .   Du e  t o   th at,   th e  ef f icien cy   o f   p a r allel  co m p u tatio n   o f   task s   m ay   d eg r ad e   s o   th at  th e   ex ec u tio n   tim e   ca n   h ar d ly   b ec o m e   s h o r t   in   r esp o n s e  to   its   p ar allelis m .   I n   t h is   p ap er ,   th e   Ov h   p o licy   th at   ev e n ly   d is tr ib u tes  a  c o r e  t o   ea c h   task   an d   ass ig n e  o n e   o f   r e m a in in g   co r e s   to   th e   task   wit h   m in im u m   o v er h ea d   is   p r esen t ed .   Fig u r e  1 0   s h o ws an   e x am p le  o f   Fair - Ov h   s ch e d u lin g .   At  tim e  0 ,   task   1   an d   ta s k   2   ar e  ev en ly   ass ig en d   a  co r e.   T h en ,   o n e  o f   th e  r em ain in g   tw o   co r es  i s   ass ig n ed   to   a   task   with   m i n im u m   o v er h ea d .   T h e  o v er h ea d   c an   b e   ca lcu lated   as   f o llo ws.  I f   task   1   is   ass ig n ed   two   co r es,  th e  o v e r h ea d   is   1 0   ( = 2 × 25 − 40 ) .   On   th e  o th er   h an d ,   th e  o v er h ea d   o f   task   2   is   5   ( = 20 × 2 − 35 ) .  T h er ef o r e,   th e   task   with   th e  m in im u m   o v eh ea d   is   d eter m i n ed   as  task   2 ,   an d   a  r em ain in g   co r e   is   ad d itio n all y   Evaluation Warning : The document was created with Spire.PDF for Python.
            I SS N :   20 89 - 4 8 6 4   I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t ,   Vo l.  10 ,   No .   3 ,  No v em b er   2 0 2 1 :   157   –   1 6 7   164   ass ig n ed   to   task   2 .   No w,   task   1   is   as s ig n ed   a  co r e  an d   task   2   is   a s s ig n ed   two   co r es a n d   a  c o r e  is   s til l a v ailab le.   T h en ,   if   task   2   is   ass ig n ed   th r ee   co r es,  th e  o v e r h ea d   is   1 0   ( = 15 × 3 − 35 ) ,   ac co r d in g   to   T ab le  3 .   C o m p ar ed   th e  o v er h ea d   o f   task   1   a n d   tas k   2 ,   task   1   is   s elec ted   to   ass ig n   th e  c o r e.   I n   t h is   ca s e,   th e  o v er h ea d   o f   task   1   is   eq u al  to   t h at  o f   task   2 ,   b u t   a  co r e  is   ass ig n ed   to   task   1   li k e wis e  f o llo win g   th e  FC FS   p o li cy .   T h r o u g h o u t  th e  task   s elec tio n ,   task   1   a n d   ta s k   2   ar e   f in ally   ass ig n ed   tw o   c o r es,  r esp ec tiv ely .   At  tim e  2 0 ,   wh en   task   2   co m p letes  th e  ex ec u tio n ,   task   3 ,   4 ,   an d   5   ar e  a r r iv ed   i n   th e  o r d er .   I f   o n e  o f   th e  r em ain i n g   co r es  is   ev en l y   ass ig n ed   to   ea c h   o f   task   3   a n d   task   4 ,   all  th e   co r es   b ec o m e  o cc u p ied   b y   th e   task s .   T h er ef o r e ,   a d d itio n al   ass ig n m en t  o f   r em ai n in g   c o r e s   is   n o t  n ec ess ar y   at  th e  tim e.   At  tim e  2 5 ,   th er e  is   o n ly   task   5   to   b e  e x ec u ted   i n   th e  q u e u e.   T h u s   two   co r es  ar e  ass ig n ed   to   task   5 .   At  tim e  6 0 ,   task   6 ,   7 ,   an d   8   ar e  a r r iv ed   an d   b ec o m e  r ea d y   in   th e  q u e u e,   b u t  th er e   is   o n ly   a  co r e  av ailab le   at  th e  tim e.   I n   a cc o r d an ce   with   th e  Fair   p o licy ,   task   6   is   ass ig n ed   a  co r e,   an d   an y   o f   co r es  ca n n o t  b e   ass ig n ed   to   task s .   At  t im e  6 5 ,   task   7   an d   task   8   ca n   b e   s tar ted   o n   th e   r em ain in g   th r ee   c o r es.  A  co r e  is   ev en ly   ass ig n ed   to   ea ch   o f   th em ,   an d   th e  o v er h ea d   is   ca lcu lated   f o r   ad d itio n al  ass ig n m en t  o f   th e  co r e.   T h e  o v e r h ea d   o f   task   7   is   1 0   ( = 40 × 2 − 70 ) .   On   th e  o th er   h an d ,   t h at  o f   task   8   is   ca lcu lated   as  2 0   ( = 60 × 2 − 100 ) .   T h u s ,   th e  co r e  is   ass ig n ed   to   task   7   at  th e  tim e,   an d   two   o u t  o f   th r ee   co r es  ar e   f in ally   ass ig n ed   to   task   7   an d   a   co r e   is   as s ig n ed   to   task   8 ,   r esp ec tiv el y .   I n   th is   ca s e,   t h e  s ch ed u le  len g th   as  1 6 5   is   o b tain ed ,   as sh o wn   in   th e  F ig u r e   10 .           Fig u r e  1 0 .   An   ex am p le  o f   Fair - Ov h   s ch ed u lin g       4.   E XP E R I M E N T S   I n   th e  p r ev i o u s   s ec tio n ,   th e   s ch ed u lin g   p r o b lem s   th at  ca n   b e   s p lit  in to   two   s ec tio n :  task   s el ec tio n   an d   p ar allelis m   d ec is io n   ar e   d escr i b e d .   I n   task   s elec tio n ,   FC FS ,   SJ F,  an d   Ov h   h a v e  b ee n   p r es en ted .   On   th e   o th er   h an d ,   in   p a r alallelism  d ec is io n ,   Sin g le,   Ma x ,   Fit ,   an d   Fair   h av e  b ee n   p r esen ted .   Mo r eo v er ,   n in e   s ch ed u lin g   tech n iq u es in   co m b in atio n   with   th e  s ch ed u lin g   p o licies   ar e   p r o p o s e d .   I n   o r d e r   to   ev alu ate  th e  ef f ec tiv en ess   o f   th e  p r esen ted   s ch ed u lin g   tech n iq u es,  ex p er im e n ts   h av e  b ee n   co n d u cte d .  A   m etr ic  o f   th e   ex p er im en ts   is   in   g en e r al  th e  o v er all  s ch ed u le  len g t h   o b tain ed   th r o u g h   s ch e d u lin g   is   s u p p o s e d .   I n   th e   ex p er im e n ts ,   a  s et  o f   task s   with   eig h t  s ce n ar io s ,   ea ch   o f   wh ich   co n s is t s   o f   5 0 0   task s   o r   1 0 0 0   task s   d er iv ed   f r o m   STG  b en ch m ar k   s u ite   is   u s e d   [ 2 6 ] .   T h e   m ax im u m   p a r allelis m   f o r   ea ch   task   is   n o t  in clu d ed   in   th e  STG  b e n ch m a r k   s u ite,   wh ich   is   th er e f o r e   r an d o m ly   g en er ate d   an d   f ix ed   in   ad v an ce .   E ac h   task   is   as s u m ed   to   h av e  1 0 %  o f   o v er h ea d   to   p ar allelize .   T h e  n u m b er   o f   c o r es  o n   th e  tar g et  s y s tem   is   s et  to   eig h t   an d   s ix teen .   T h e  tech n iq u es e m p lo y ed   in   th e  e x p er im en ts   ar e  th o s e  wh ich   ar e  ea r lier   p r ese n ted   in   Sectio n   3 .   Fig u r e  1 1 ( a)   an d   Fig u r e   1 1 ( b )   s h o ws  th e   ex p e r im en tal  r esu lts   o f   n in e  s ch e d u lin g   alg o r ith m s   with   eig h t  s ce n ar io s ,   ea ch   wh ich   c o n p o s e  a  s et  o f   5 0 0   ta s k s ,   o n   8   co r es  an d   1 6   co r es,  r esp ec t iv ely .   Fig u r e  1 1 ( a)   s h o ws  th at  F it  an d   Fair   ac h i ev e  r elativ ely   g o o d   r esu lts ,   wh ich   r ed u ce   th e  s ch ed u le  len g th s   b y   2 1 . 7 %  o n   av er ag e.   On   t h e  o th e r   h an d ,   th e  Ma x   p o licy   o b v io u s ly   d eg r a d es  th e  p er f o r m an ce   s in ce   tas k s ,   wh ich   ca n n o t  b e   ex ec u ted   at  its   m ax im u m   p ar al lelis m ,   ar e  waited   u n til th e  co r es a r e  r elea s ed .   T h er ef o r e,   th e  co r es a r e  n o t f u lly   u tili ze d   in   th is   p o licy .   On   1 6   c o r es,  th e  tr e n d   o f   th e   r esu lts   is   v er y   s im ilar   to   th at  o n   8   co r es,  b u t  t h e  r esu lts   b y   Fit   an d   Fair   p o licies ar e  s ca led   f o r   th e   b etter   th an   th e  r esu lts   o n   8   c o r es.    Fig u r e  1 2 ( a)   an d   Fig u r e   1 2 ( b )   s h o ws  th e  e x p er im e n tal  r esu l ts   o n   8   co r es   an d   o n   1 6   co r es  as  well  as   Fig u r e  1 1 ,   b u t  ea ch   o f   th e  tas k   s ets  co m p o s es  1 0 0 0   task s   in   Fig u r e  1 2 .   All  th e   r esu lts   o f   s ch ed u le  len g th s   ar e   n o r m alize d   to   th e   Sin g le - FC FS   alg o r ith m   an d   ar e   s h o wn   as   th e  a v er ag e   o f   th e  n o r m alize d   s ch ed u le   len g th s   f o r   th e  s ce n a r io s .   C o m p ar e d   t h e  r esu lts   am o n g   Fair - FC FS ,   Fair - SJ F,  an d   Fair - Ov h ,   th e  Ov h   p o licy   s lig h tly   d eg r ad es  th e  p er f o r m a n ce .   Fa ir - FC FS   an d   Fair - S J F  ar e  b ett er   th an   th e  o th er s ,   b o th   o f   wh ich   ca n   o b tain   th e   s ch ed u le  len g t h s   2 5 %  s h o r ter   th an   th o s e  o f   Sin g le - FC FS .   Fair - Ov h   o b tain s   2 0 %   s h o r ter   th an   Sin g le - FC FS .   Max - SJ F r ec o r d ed   d is tin ctly   b etter   r esu lts   th an   Ma x - FC FS .   Fig u r e  1 2 ( a)   an d   Fig u r e   1 2 ( b )   s h o ws  th e  e x p er im e n tal  r esu l ts   o n   8   co r es   an d   o n   1 6   co r es  as  well  as   Fig u r e  1 1 ,   b u t  ea ch   o f   th e  tas k   s ets  co m p o s es  1 0 0 0   task s   in   Fig u r e  1 2 .   All  th e   r esu lts   o f   s ch ed u le  len g th s   ar e   n o r m alize d   to   th e   Sin g le - FC FS   alg o r ith m   an d   ar e   s h o wn   as   th e  a v er ag e   o f   th e  n o r m alize d   s ch ed u le   len g th s   f o r   th e  s ce n a r io s .   C o m p ar e d   t h e  r esu lts   am o n g   Fair - FC FS ,   Fair - SJ F,  an d   Fair - Ov h ,   th e  Ov h   p o licy   s lig h tly   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t   I SS N:  2089 - 4 8 6 4       Heu r is tic  a lg o r ith ms fo r   d yn a mic  s ch ed u lin g   o f m o l d a b le  ta s ks in   mu ltico r e  emb ed d ed   …  ( Ta ku ma   Hikid a )   165   d eg r ad es  th e  p er f o r m a n ce .   Fair - FC FS   an d   Fair - S J F  ar e  b ett er   th an   th e  o th er s ,   b o th   o f   wh ich   ca n   o b tain   th e   s ch ed u le  len g t h s   2 5 %  s h o r ter   th an   th o s e  o f   Sin g le - FC FS .   Fair - Ov h   o b tain s   2 0 %   s h o r ter   th an   Sin g le - FC FS .   Max - SJ F r ec o r d ed   d is tin ctly   b etter   r esu lts   th an   Ma x - FC FS .           ( a)   ( b )       Fig u r e  1 1 .   No r m alize d   s ch e d u le  len g th   f o r   5 0 0   task s : ( a)   8   c o r es,  ( b )   1 6   c o r es            ( a)   ( b )       Fig u r e  1 2 .   No r m alize d   s ch e d u le  len g th   f o r   1 0 0 0   task s : ( a)   8   co r es,  ( b )   1 6   c o r es       5.   CO NCLU SI O NS   T h e  liter atu r e  o n   d y n am ic  s c h ed u lin g   al g o r ith m s   f o r   m o ld ab le  task s   h av e  b ee n   p r o p o s e d   y et  h av e   n ev er   b ee n   e v alu ated   in   a  s am e  en v ir o n m e n t.  I n   th is   p ap er ,   d y n am ic  task   s ch ed u lin g   alg o r ith m s   o n   th e  ce r tain   co n d itio n s   h av e  b ee n   s y s tem atica lly   r ea r r an g e d   an d   e v alu ate d .  D y n am ic  s ch ed u lin g   o f   m o l d ab le  task s   ca n   b e  s p lit  in to   two   s u b - p r o b lem s   s u ch   as  task   s elec tio n   an d   p ar allelis m   d ec is io n   an d   h av e  p r e s en ted   two   p o licies   f o r   task   s elec tio n   an d   f o u r   p o l icies  f o r   p ar allelis m   d ec is io n   i s   ass u m ed .   I n   ad d itio n ,   th e  Ov h   p o licy   d ed icate d   to   th e  F air   task   s elec tio n   h av e  b ee n   p r o p o s ed .  I n   th e  e x p er i m en tal  s ce n ar io s ,   th e  ef f ec tiv en ess   o f   Fair - FC F S  an d   Fair - SJ F  d er iv ed   s h o r ter   s ch ed u le  len g th s   h as  b e en   d em o n s tr ate d .   I n   f u tu r e,   m o r e   ex t en s iv e  ex p er im e n ts   will b e  co n d u ct ed .  Als o ,   m o r e   s o p h is ticated   alg o r ith m s   will  b e  d ev elo p ed .       ACK NO WL E DG E M E NT S   T h is   wo r k   is   s u p p o r ted   p a r tly   b y   KAKE NHI   2 0 H0 0 5 9 0 ,   2 0 H0 4 1 6 0 ,   an d   2 0 J 2 1 2 0 8 .       RE F E R E NC E S   [1 ]   M .   Dro z d o ws k i,   " S c h e d u li n g   m u lt ip ro c e ss o r  tas k s:  A n   o v e rv iew , "   Eu ro p e a n   j o u r n a l  o f  o p e ra ti o n a l   r e se a rc h ,   v o l .   94 ,   n o .   2 2 ,   p p .   2 1 5 - 2 3 0 ,   1 9 9 6 ,   d o i :   1 0 . 1 0 1 6 /0 3 7 7 - 2 2 1 7 (9 6 )0 0 1 2 3 - 3 .   [2 ]   S .   Ve n u g o p a lan   a n d   O.  S in n e n ,   " Op ti m a l  li n e a r  p r o g ra m m in g   so lu ti o n s  f o r  m u l ti p r o c e ss o r  s c h e d u li n g   with   c o m m u n ica ti o n   d e lay s, "   In ter n a ti o n a l  C o n fer e n c e   o n   Al g o ri th ms   a n d   Arc h it e c tu re s  fo r   Pa r a ll e l  Pro c e ss in g ,   2 0 1 2 ,   p p .   1 2 9 - 138 ,   d o i:   1 0 . 1 0 0 7 /9 7 8 - 3 - 642 - 3 3 0 7 8 - 0 _ 1 0 .   0 0 . 1 0 . 2 0 . 3 0 . 4 0 . 5 0 . 6 0 . 7 0 . 8 0 . 9 1 1 . 1 N or m a l i z e d  S c he dul i ng   L e ng t h S i n g l e - F C F S S i n g l e - S JF M A X - F C F S M A X - S JF F i t - F C F S F i t - S JF F a i r - F C F S F a i r - S JF F a i r - O v h 1. 81 1. 78 0 0 . 1 0 . 2 0 . 3 0 . 4 0 . 5 0 . 6 0 . 7 0 . 8 0 . 9 1 1 . 1 N or m a l i z e d  S c he dul i ng   L e ng t h S i n g l e - F C F S S i n g l e - S JF M A X - F C F S M A X - S JF F i t - F C F S F i t - S JF F a i r - F C F S F a i r - S JF F a i r - O v h 1. 30 0 0 . 1 0 . 2 0 . 3 0 . 4 0 . 5 0 . 6 0 . 7 0 . 8 0 . 9 1 1 . 1 N or m a l i z e d  S c he dul i ng   L e ng t h S i n g l e - F C F S S i n g l e - S JF M A X - F C F S M A X - S JF F i t - F C F S F i t - S JF F a i r - F C F S F a i r - S JF F a i r - O v h 1. 78 1. 57 0 0 . 1 0 . 2 0 . 3 0 . 4 0 . 5 0 . 6 0 . 7 0 . 8 0 . 9 1 1 . 1 N or m a l i z e d  S c he dul i ng   L e ng t h S i n g l e - F C F S S i n g l e - S J F M A X - F C F S M A X - S J F F i t - F C F S F i t - S J F F a i r - F C F S F a i r - S J F F a i r - O v h 1. 30 Evaluation Warning : The document was created with Spire.PDF for Python.
            I SS N :   20 89 - 4 8 6 4   I n t J Reco n f ig u r a b le  &   E m b ed d ed   Sy s t ,   Vo l.  10 ,   No .   3 ,  No v em b er   2 0 2 1 :   157   –   1 6 7   166   [3 ]   T.   L.   Ad a m ,   K.   M .   Ch a n d y ,   a n d   J.  R.   Dic k so n ,   " A  c o m p a riso n   o f  li st  sc h e d u les   f o r  p a ra ll e l  p r o c e ss in g   sy ste m s, "   Co mm u n .   Ass.  Co m p u t .   M a c h . ,   v o l.   1 7 ,   n o .   1 2 ,   p p .   6 8 5 - 6 9 0 ,   1 9 7 4 ,   d o i:   1 0 . 1 1 4 5 /3 6 1 6 0 4 . 3 6 1 6 1 9 .   [4 ]   H.  El - Re win i,   H.  Al i  a n d   T .  Lew is,  " Tas k   sc h e d u li n g   i n   m u lt i p ro c e ss in g   sy ste m s , "   Co m p u ter ,   v o l.   2 8 ,   n o .   1 2 ,   p p .   27 - 3 7 ,   De c .   1 9 9 5 ,   d o i:   1 0 . 1 1 0 9 /2 . 4 7 6 1 9 7 .   [5 ]   G .   S in e v rio ti s  a n d   T .   S to u ra it is,  " A  n o v e l   li st - sc h e d u li n g   a l g o ri th m   fo r  t h e   l o w - e n e rg y   p ro g ra m   e x e c u ti o n , "   2 0 0 2   IEE E  In ter n a ti o n a l  S y mp o siu m  o n   Circ u it s  a n d   S y ste ms .   Pro c e e d in g s  (Ca t .   No . 0 2 CH 3 7 3 5 3 ) ,   2 0 0 2 ,   p p .   IV - IV,  d o i:   1 0 . 1 1 0 9 /I S CAS. 2 0 0 2 . 1 0 1 0 3 9 8 .   [6 ]   Y.  Li u ,   L .   M e n g ,   I.   Tan i g u c h i  a n d   H.   T o m iy a m a ,   " N o v e l   li st   sc h e d u li n g   stra teg ies   f o r   d a ta   p a ra ll e li sm   tas k   g ra p h s, "   In ter n a t io n a l  J o u rn a l  o n   Ne two rk in g   a n d   C o mp u ti n g ,   v o l .   4 ,   n o .   2 ,   p p .   2 7 9 - 290 ,   2 0 1 4 ,   d o i:   1 0 . 1 5 8 0 3 /i jn c . 4 . 2 _ 2 7 9 .   [7 ]   H.  Ya n g   a n d   S .   Ha ,   " P ip e li n e d   d a ta  p a ra ll e l  tas k   m a p p in g / sc h e d u li n g   tec h n iq u e   fo r  M P S o C, "   2 0 0 9   De sig n ,   Au to m a ti o n   &   T e st  in   E u ro p e   Co n fer e n c e   &   Exh ib it i o n ,   2 0 0 9 ,   p p .   6 9 - 7 4 ,   d o i:   1 0 . 1 1 0 9 /DATE . 2 0 0 9 . 5 0 9 0 6 3 5 .   [8 ]   N.  Vy d y a n a th a n ,   e t  a l . ,  " A n   i n t e g ra ted   a p p r o a c h   t o   l o c a li ty - c o n sc io u s  p r o c e ss o r  a ll o c a t i o n   a n d   sc h e d u li n g   o f   m ix e d - p a ra ll e l  a p p li c a ti o n s, "   i n   I EE E  T ra n s a c ti o n s  o n   P a ra ll e l   a n d   Distri b u te d   S y ste ms ,   v o l.   2 0 ,   n o .   8 ,   p p .   1 1 5 8 - 1 1 7 2 ,   A u g .   2 0 0 9 ,   d o i :  1 0 . 1 1 0 9 /T P DS. 2 0 0 8 . 2 1 9 .   [9 ]   K.  S h ima d a ,   S .   Kitan o ,   I.   Tan i g u c h i,   a n d   H.  To m iy a m a ,   " ILP - b a se d   sc h e d u li n g   fo r  p a ra ll e li z a b l e   tas k s, "   IEI CE  T ra n sa c ti o n s  o n   Fu n d a me n t a ls  o f  El e c tro n ics ,   C o mm u n ica ti o n s  a n d   C o mp u ter   S c ien c e ,   v o l.   E1 0 0 - A,  n o .   7 ,   p p .   1 5 0 3 - 1 5 0 5 ,   2 0 1 7 ,   d o i:   1 0 . 1 5 8 7 /t r a n sfu n . E 1 0 0 . A. 1 5 0 3 .   [1 0 ]   H.  Nish i k a wa ,   K.  S h ima d a ,   I.   Ta n ig u c h i   a n d   H.   To m i y a m a ,   " A  c o n stra in t   p r o g ra m m in g   a p p ro a c h   t o   sc h e d u li n g   o f   m a ll e a b le  tas k s, "   In ter n a ti o n a l  J o u rn a l  o n   Ne two rk in g   a n d   Co m p u ti n g ,   v o l.   9 ,   n o .   2 ,   p p .   1 3 1 - 1 4 6 ,   2 0 1 9 ,   d o i:   1 0 . 1 5 8 0 3 /i j n c . 9 . 2 _ 1 3 1 .   [1 1 ]   A.  S a i fu ll a h ,   K.  A g ra wa l,   C.   L u   a n d   C.   G il l,   " M u lt i - c o re   re a l - ti m e   sc h e d u li n g   f o r  g e n e ra li z e d   p a ra ll e l  tas k   m o d e ls, "   2 0 1 1   IE EE   3 2 n d   Re a l - T ime   S y ste ms   S y mp o siu m ,   2 0 1 1 ,   p p .   2 1 7 - 2 2 6 ,   d o i:   1 0 . 1 1 0 9 /RT S S . 2 0 1 1 . 2 7 .   [1 2 ]   C.   Ch e n   a n d   C.   C h u ,   " A  3 . 4 2 - Ap p r o x ima ti o n   a l g o ri th m   fo r   sc h e d u li n g   m a ll e a b le  tas k s  u n d e r  p re c e d e n c e   c o n stra in ts, "   in   IEE E  T ra n sa c ti o n s  o n   P a ra ll e l  a n d   Distrib u ted   S y ste ms ,   v o l.   2 4 ,   n o .   8 ,   p p .   1 4 7 9 - 1 4 8 8 ,   Au g .   2 0 1 3 ,   d o i:   1 0 . 1 1 0 9 /T P D S . 2 0 1 2 . 2 5 8 .   [1 3 ]   K.  Ja n se n   a n d   H.  Z h a n g ,   " S c h e d u li n g   m a ll e a b le  tas k s  wit h   p re c e d e n c e   c o n stra in ts, "   J o u rn a l  o f   Co mp u ter   a n d   S y ste m S c ien c e s ,   v o l .   7 8 ,   n o   1 ,   p p .   2 4 5 - 2 5 9 ,   2 0 1 2 ,   d o i:   1 0 . 1 0 1 6 / j. jc ss . 2 0 1 1 . 0 4 . 0 0 3 .   [1 4 ]   J.  Ba rb o sa ,   C.   M o ra is,  R.   N o b re g a ,   a n d   A.P .   M o n teiro   " S ta ti c   sc h e d u li n g   o f  d e p e n d e n t  p a ra ll e l  tas k s  o n   h e tero g e n e o u s  c lu ste rs, "   2 0 0 5   IEE E  In ter n a ti o n a l  C o n fer e n c e   o n   Clu ste r  Co m p u t in g ,   2 0 0 5 ,   p p .   1 - 8 ,   d o i :   1 0 . 1 1 0 9 /C LUS TR. 2 0 0 5 . 3 4 7 0 2 4   [1 5 ]   R.   Ku m a r,   D.   M .   Tu ll se n ,   N .   P .   Jo u p p i ,   a n d   P .   Ra n g a n a t h a n ,   " H e tero g e n e o u s  c h i p   m u l ti p r o c e ss o rs, "   J o u rn a l  o n   Co mp u ter ,   v o l.   3 8 ,   no .   1 1 ,   p p .   32 - 3 8 ,   2 0 0 5 ,   d o i:   1 0 . 1 1 0 9 /M C. 2 0 0 5 . 3 7 9 .   [1 6 ]   J.  Li u ,   K .   L i,   D .   Z h u ,   J.   Ha n ,   a n d   L.   Li ,   " M i n imiz in g   c o st   o f  sc h e d u li n g   tas k s  o n   h e tero g e n e o u s  m u l ti c o re   e m b e d d e d   sy ste m s, "   AC M   T ra n sa c ti o n s  o n   Em b e d d e d   Co m p u ti n g   S y ste ms   (T ECS ) ,  v o l.   1 6 ,   n o .   2 ,   2 0 1 7 ,   d o i:   1 0 . 1 1 4 5 / 2 9 3 5 7 4 9 .   [1 7 ]   H.  Ch e n g ,   " A  h i g h   e fficie n t  tas k   sc h e d u li n g   a lg o rit h m   b a se d   o n   h e tero g e n e o u s  m u l ti - c o re   p ro c e ss o r, "   2 0 1 0   2 n d   In ter n a t io n a l   W o rk sh o p   o n   Da t a b a se   T e c h n o l o g y   a n d   Ap p li c a t io n s ,   2 0 1 0 ,   p p .   1 - 4 ,   d o i :   1 0 . 1 1 0 9 /DBTA. 2 0 1 0 . 5 6 5 9 0 4 1 .   [1 8 ]   T.   Brid i,   A.  Ba rt o li n i,   M .   Lo m b a rd i,   M .   M il a n o ,   a n d   L .   Be n in i  " A  c o n stra in t  p r o g ra m m in g   sc h e d u ler  fo r   h e tero g e n e o u s  h i g h p e rfo rm a n c e   c o m p u ti n g   m a c h i n e s, "   i n   IEE E  T r a n sa c ti o n s  o n   P a ra ll e l  a n d   Distri b u ted   S y ste ms ,  v o l.   2 7 ,   n o .   1 0 ,   p p .   2 7 8 1 - 2 7 9 4 ,   1   Oc t.   2 0 1 6 ,   d o i:   1 0 . 1 1 0 9 /T P DS. 2 0 1 6 . 2 5 1 6 9 9 7 .   [1 9 ]   D.  Ye ,   DZ .   C h e n ,   a n d   G .   Zh a n g ,   " On li n e   sc h e d u li n g   o f   m o l d a b le   p a ra ll e l  tas k s, "   J o u r n a l   o f   S c h e d u li n g ,  v o l.   2 1 ,   p p .   647 - 6 5 4 ,   2 0 1 8 ,   d o i:   1 0 . 1 0 0 7 /s1 0 9 5 1 - 0 1 8 - 0 5 5 6 - 2 .   [2 0 ]   Y.  Ya n g ,   S .   Yu ,   a n d   X.  Bi n ,   " A  n e w  d y n a m ic  sc h e d u li n g   a l g o ri t h m   fo r  re a l - ti m e   h e tero g e n e o u s  m u lt ip r o c e ss o r   sy ste m s, "   W o rk sh o p   o n   I n telli g e n t  I n fo rm a ti o n   T e c h n o lo g y   A p p li c a ti o n   (IIT A  2 0 0 7 ) ,   2 0 0 7 ,   p p .   1 1 2 - 1 1 5 ,   d o i :   1 0 . 1 1 0 9 /II TA. 2 0 0 7 . 7 0 .   [2 1 ]   E.   Am a l,   A.  E.   Nirm e e n ,   a n d   E.   Ay m a n ,   " A  n e w  tas k   sc h e d u li n g   a lg o rit h m   fo r  m ix imiz in g   t h e   d ist rib u t e d   sy ste m s   e fficie n c y , "   I n ter n a ti o n a l  J o u rn a l  o f   C o mp u ter   Ap p li c a t io n s ,   v o l .   1 1 0 ,   no .   9 ,   p p .   9 - 1 6 ,   2 0 1 5 ,   d o i:   1 0 . 5 1 2 0 / 1 9 3 4 3 - 0 2 7 9 .   [2 2 ]   A.  G e o rg e   a n d   A.  M a ria,  " D y n a m ic  tas k   sc h e d u li n g   m e th o d s  in   h e tero g e n e o u s  sy ste m s -   a   su r v e y , "   In ter n a ti o n a l   J o u rn a l  o f  Co m p u ter   A p p l ica ti o n s ,   v o l .   1 1 0 ,   n o .   6 ,   p p .   1 2 - 18 ,   2 0 1 5 ,   d o i:   1 0 . 5 1 2 0 / 1 9 3 1 8 - 0 8 5 9 .   [2 3 ]   X.  Li n g ,   Q.  Jia z h o n g ,   L .   S h u k u a n ,   a n d   Z.   Wan t in g ,   " Dy n a m ic  tas k   sc h e d u li n g   a l g o r it h m   wit h   d e a d li n e   c o n stra i n t  in   h e tero g e n e o u s  v o lu n tee r  c o m p u ti n g   p latf o rm s , "   F u tu re   In ter n e t ,   v o l.   11 ,  n o .   6 ,   p .   1 2 1 ,  2 0 1 9 ,   d o i:   1 0 . 3 3 9 0 /f i1 1 0 6 0 1 2 1 .   [2 4 ]   R.   Ra m e z a n i,   " Dy n a m ic  sc h e d u li n g   o f  tas k   g ra p h s  in   m u lt i - FP G A  sy ste m s  u sin g   c rit ica l  p a th , "   J   S u p e rc o mp u t ,  v o l.   7 7 ,   p p .   5 9 7 - 6 1 8 ,   2 0 2 0 ,   d o i:   1 0 . 1 0 0 7 /s1 1 2 2 7 - 0 2 0 - 0 3 2 8 1 - 3 .   [2 5 ]   A.  P riy a   a n d   S .   K.   S a h a n a ,   " P r o c e ss o r  sc h e d u li n g   in   h i g h - p e rfo rm a n c e   c o m p u ti n g   e n v iro n m e n t  u sin g   M P I , "   i n   In n o v a ti o n s  i n   S o ft   C o mp u ti n g   a n d   I n f o rm a ti o n   T e c h n o lo g y ,  S in g a p o re :  S p rin g e r ,   2 0 1 9 ,   p p .   4 3 – 5 4 ,   d o i:   1 0 . 1 0 0 7 / 9 7 8 - 9 8 1 - 13 - 3 1 8 5 - 5 _ 5 .   [2 6 ]   T.   To b it a   a n d   H.  Ka s a h a ra ,   " A  st a n d a rd   tas k   g ra p h   se t  fo r  fa ir  e v a lu a ti o n   o f  m u lt i p ro c e ss o r  sc h e d u l i n g   a lg o rit h m s, "   Jo u rn a l  o f  S c h e d u li n g ,   v o l .   5 ,   n o .   5 ,   p p .   3 7 9 - 3 9 4 , 2 0 0 2 ,   d o i:   1 0 . 1 0 0 2 /j o s. 1 1 6 .           Evaluation Warning : The document was created with Spire.PDF for Python.