Page - 184 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 76 IMs are interconnected by a bus. In the currentmodel, for each connection, different data transmissioncoefficientsareused.Data transferwithin thesameDSPhasacoefficientof0,between adjacentDSPsinasingle IMhasacoefficientof1,andbetween IMs,hasadatatransmissioncoefficient of10. 3.RelatedWork Stateof theart studies tackledifferentworkflowschedulingproblemsby focusingongeneral optimization issues; specificworkflowapplications; minimization of critical path execution time; selection of admissible resources; allocation of suitable resources for data-intensive workflows; QualityofService (QoS)constraints; andperformanceanalysis, amongother factors. [5–17]. ManyheuristicshavebeendevelopedforschedulingDAG-basedtaskgraphs inmultiprocessor systems[18–20]. In [21], theauthorsdiscussedclusteringDAGtasks intochainsandallocatingthem to singlemachines. In [22], two strategieswere considered: Fairness Policy based on Finishing Time(FPFT)andFairnessPolicybasedonConcurrentTime(FPCT).BothstrategiesarrangedDAGsin ascendingorderoftheirslowdownvalue,selectedindependenttasksfromtheDAGwiththeminimum slowdown, and scheduled them using Heterogeneous Earliest Finishing Time first (HEFT) [23] orHybrid.BMCT [24]. FPFT recalculates the slowdown of aDAG each time the task of aDAG completesexecution,whileFPCTrecalculates theslowdownofallDAGseachtimeanytask inaDAG completesexecution. HEFT is considered as an extension of the classical list scheduling algorithm to copewith heterogeneity and has been shown to produce good results more often than other comparable algorithms.Manyimprovementsandvariations toHEFThavebeenproposedconsideringdifferent rankingmethods, lookingaheadalgorithms,clustering,andprocessorselection, forexample [25]. Themulti-objectiveworkflowallocationproblemhasrarelybeenconsideredsofar. It is important, especially inscenarios thatcontainaspects thataremulti-objectivebynature:QualityofService (QoS) parameters, costs, systemperformance, response time,andenergy, forexample [14]. 4. ProposedDSPWorkflowSchedulingStrategies Theschedulingalgorithmassigns toeachgraph’s taskstartexecutiontime. The timeassignedto thestoptask is themainresultmetricof thealgorithm.The lower the time, thebetter theschedulingof thegraph. The algorithmuses a list of ready for scheduling tasks andawaiting list of scheduling tasks. If allpredecessorsof the taskare scheduled, then it is inserted into thewaiting list. If all incoming dataareready, thenthe task is inserted into thereadylist,otherwise, into thewaiting list.Available DPS-processorsareplaced into theappropriate list. Thelistof tasksthatarereadytobestartedismaintained. Independenttaskswithnopredecessors andwithpredecessors thatcompleted theirexecutionandavailable inputdataareentered into the list. Allocationpoliciesareresponsible forselectingasuitableDSPfor taskallocation. We introduce five task allocation strategies: PESS (Pessimistic), OPTI (Optimistic), OHEFT (Optimistic Heterogeneous Earliest Finishing Time), PHEFT (Pessimistic Heterogeneous Earliest FinishingTime),andBC(BestCore). Table3brieflydescribes thestrategies. OHEFT and PHEFT are based on HEFT, a workflow scheduling strategy used in many performanceevaluationstudies. HEFTschedulesDAGsin twophases: job labelingandprocessorselection. In the job labeling phase,a rankvalue (upwardrank)basedonmeancomputationandcommunicationcosts isassigned toeachtaskofaDAG.Theupwardrankofa task i is recursivelycomputedbytraversingthegraph upward,startingfromtheexit task,as follows: ranku(i)=wi+maxj∈succ(i) ( di,j +ranku(i) ) ,where succ(i) is thesetof immediatesuccessorsof task i;di,j is theaveragecommunicationcostof arc(i, j) overallprocessorpairs; andwi is theaverageof thesetofcomputationcostsof task i. 184