Seite - 185 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 76 AlthoughHEFT iswell-known, the studyofdifferentpossibilities for computing rankvalues in a heterogeneous environment is limited. In some cases, the use of themean computation and communicationas therankvalue in thegraphmaynotproduceagoodschedule [26]. In thispaper,weconsider twomethodsofcalculatingtherank: bestandworst. Thebestversion assumesthat tasksareallocatedto thesameDSP.Hence,nodata transmission isneeded.Alternatively, theworstversionassumesthattasksareallocatedtotheDSPfromdifferentnodes,sodatatransmission ismaximal. Todetermine thecriticalpath,weneed toknowtheexecution timeofeach taskof the graphandthedata transfer time,consideringeverycombinationofDSPs,where the twogiventasks maybeexecutedtaking intoaccount thedata transfer ratebetweenthe twoconnectednodes. Tasks labelingprioritizesworkflowtasks. Labelsarenotchangednorrecomputedoncompletion ofpredecessor tasks. Thisalsodistinguishesourmodel frompreviousresearch(see, for instance [22]). Tasklabelsareusedtoidentifypropertiesofagivenworkflow.Wedistinguishfourlabelingapproaches: BestDownwardRank(BDR),WorstDownwardRank(WDR),BestUpwardRank(BUR),andWorst UpwardRank(WUR). BDRestimates the lengthof thepathfromconsideredtasktoarootpassingasetof immediate predecessors in aworkflowwithout communication costs. WDRestimates the lengthof thepath fromconsidered task to a rootpassing a set of immediatepredecessors in aworkflowwithworst communications. The descending order of BDR and WDR supports scheduling tasks by the depth-firstapproach. BURestimates the lengthof thepath fromtheconsidered task toa terminal start taskpassing asetof the immediatesuccessors inaworkflowwithoutcommunicationcosts. Table3.Taskallocationstrategies. Description Rand Allocates taskTk toaDSPwith thenumberrandomlygeneratedfromauniformdistribution in therange[1,m] BC(bestcore) Allocates taskTk to theDSPthatcanstart the taskasearlyaspossibleconsideringcommunicationdelayofall inputdata PESS(pessimistic) Allocates taskTk fromtheordered list to theDSPaccordingtoWorstDownwardRank(WDR). OPTI (optimistic) Allocates taskTk fromtheordered list to theDSPaccordingtoBestDownwardRank(BDR). PHEFT(pessimisticHEFT) Allocates taskTk fromtheordered list to theDSPaccordingtoWorstUpwardRank(WUR) OHEFT(optimisticHEFT) Allocates taskTk fromtheordered list to theDSPaccordingtoBestUpwardRank(BUR) WURestimates the lengthof thepathfromtheconsideredtasktoaterminal taskpassingaset of immediatesuccessors inaworkflowwiththeworstcommunicationcosts. Thedescendingorder ofBURandWURsupports scheduling taskson thecriticalpathfirst. Theupwardrankrepresents theexpecteddistanceofanytaskto theendof thecomputation. Thedownwardrankrepresents the expecteddistanceofanytaskfromthestartof thecomputation. 5. ExperimentalSetup Thissectionpresents theexperimental setup, includingworkloadandscenarios,anddescribes themethodologyusedfor theanalysis. 185