Page - 182 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 76 Dueto theofflineschedulingmodel, thereleasedateofaworkflow rj=0.However, therelease dateofataskr′i isnotavailablebeforethetaskisreleased. Tasksarereleasedonlyafteralldependencies havebeensatisfiedanddataareavailable.At itsreleasedate,a taskcanbeallocatedtoaDSP-processor foranuninterruptedperiodof time p′i. cj is completiontimeof the job j. Totalworkflowprocessingtime pGj andcriticalpathexecutioncost pj areunknownuntil the job hasbeenscheduled.Weallowmultiprocessorworkflowexecution;hence, tasksof Jj canberunon differentDSPs. 2.2. PerformanceMetrics Threecriteriaareusedtoevaluateschedulingalgorithms:makespan,criticalpathwaitingtime, and critical path slowdown. Makespan is used toqualify the efficiencyof scheduling algorithms. Toestimate thequalityofworkflowexecutions,weapply twoworkflowmetrics: criticalpathwaiting timeandcriticalpathslowdown. LetCmax=max i=1..n {Ci}bethemaximumcompletiontime(makespan)ofall tasks in theschedule C∗max(I). Thewaiting timeofa task twi= c′i−p′i−r′i is thedifferencebetween thecompletion time of the task, its execution time, and its release date. Note that a task is not preemptable and it is immediatelyreleasedwhentheinputdata itneedsfrompredecessorsareavailable.However,notethat wedonotrequire thata job isallocatedtoprocessors immediatelyat its submissiontimeas insome onlineproblems. Waiting timeof a critical path is thedifferencebetween the completion timeof theworkflow, lengthof its criticalpathanddata transmissiontimebetweenall tasks in thecriticalpath. It takes into accountwaitingtimesofall tasks in thecriticalpathandcommunicationdelay. Thecriticalpathexecutiontime pjdependsontheschedule thatallocates tasksontheprocessor. Theminimal value of pj includes only execution timeof the tasks that belong to the critical path. Themaximalvalue includesmaximaldata transmissiontimesbetweenall tasks in thecriticalpath. The waiting time of a critical path is defined as cpwj = cj− pj. Critical path slowdown cpsj=1+cpwj/pj is the relative criticalpathwaiting timeandevaluates thequalityof the critical pathexecution.Aslowdownofone indicateszerowaitingtimes forcriticalpath tasks,whileavalue greater thanone indicates that thecriticalpathcompletion is increasedby increasing thewaiting time ofcriticalpathtasks.Meancriticalpathwaitingtimeis cpw= 1/n∑nj=1cpwj, andmeancriticalpath slowdownis cps= 1/n∑nj=1cpsj. 2.3.DSPCluster DSP-clustersconsistofm integratedmodules (IM). Each IMi contains kiDPS-processorswith theirownlocalmemory.DataexchangebetweenDPS-processorsof thesame IM isperformedthrough localports. TheexchangeofdatabetweenDPS-processors fromdifferent IM isperformedviaexternal memory,whichneeds a longer transmission time than through the local ports. The speedofdata transferbetweenprocessorsdependsontheirmutualarrangement in thecluster. Let fijbethedataratecoefficient fromtheprocessorof the IMi totheprocessorof IMj.Weneglect the communication delay ε insideDSP; however, we take into account the communication delay betweenDSP-processorsof thesame IM. Dataratecoefficientsof this communicationarerepresented asamatrixDof thesizeki× ki.Weassumethat the transmissionratesbetweendifferent IMareequal toα ε. Table1showsacompletematrixofdataratecoefficients foraDSP-clusterwith four IMs. 182