Seite - 190 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 76 infrastructure informationandworkflowproperties.Weconductedacomprehensiveperformance evaluationstudyofsixworkflowschedulingstrategiesusingsimulation.Weanalyzedstrategies that includedtask labeling,prioritization, resourceselection,andDSP-clusterscheduling. Toprovide effective guidance in choosing the best strategy,weperformeda joint analysis of threemetrics (makespan,meancriticalpathwaitingtime,andcriticalpathslowdown)accordingto adegradationmethodologyandmulti-criteriaanalysis, assumingtheequal importanceofeachmetric. Our goal was to find a robust and well-performing strategy under all test cases, with the expectation that it would also performwell under other conditions, for example, with different clusterconfigurationsandworkloads. Ourstudyresulted inseveral contributions: (1) WeexaminedoverallDSP-clusterperformancebasedonreal imageandsignalprocessingdata, consideringLigoandMontageapplications; (2) We took into account communication latency, which is a major factor in DSP scheduling performance; (3) Weshowedthatefficient joballocationdependsnotonlyonapplicationpropertiesandconstraints but also on the nature of the infrastructure. To this end,we examined three configurations ofDSP-clusters. Wefoundthatanappropriatedistributionof jobsover theclustersusingapessimisticapproach hadahigherperformance thananallocationof jobsbasedonanoptimisticone. Therewere twodifferences toPHEFT strategy, compared to its originalHEFTversion. First, thedatatransfercostwithinaworkflowwasset tomaximalvaluesforagiveninfrastructuretosupport pessimistic scenarios.Alldata transmissionswereassumedtobemadebetweendifferent integrated modulesanddifferentDSPs toobtain theworstdata transmissionscenariowith themaximaldata ratecoefficient. Second,PHEFThadreduced timecomplexity compared toHEFT. Itdidnotneed to consider everycombinationofDSPs,where the twogiventaskswereexecuted,anddidnotneedto take into account thedata transfer ratebetweenthe twonodes tocalculatearankvalue(upwardrank)based onmeancomputationandcommunicationcosts. Lowcomplexity is important for industrial signal processingsystemsandreal-timeprocessing. Weconcludethat forpracticalpurposes, theschedulerPHEFTcanimprovetheperformanceof workflowschedulingonDSPclusters.Although,morecomprehensivealgorithmscanbeadopted. AuthorContributions:Allauthorscontributedto theanalysisof theproblem,designingalgorithms,performing theexperiments,analysisofdata,andwriting thepaper. Acknowledgments:ThisworkwaspartiallysupportedbyRFBR,projectNo.18-07-01224-a. Conflictsof Interest:Theauthorsdeclarenoconflictof interest. References 1. Conway,R.W.;Maxwell,W.L.;Miller,L.W.TheoryofScheduling;Addison-Wesley:Reading,MA,USA,1967. 2. Błaz˙ewicz, J.; Ecker, K.H.; Pesch, E.; Schmidt, G.; Weglarz, J. Handbook on Scheduling: From Theory to Applications; Springer: Berlin,Germany,2007. 3. Myakochkin,Y.32-bit superscalarDSP-processorwithfloatingpointarithmetic.Compon. Technol. 2013,7, 98–100. 4. TigerSHARCEmbeddedProcessorADSP-TS201S.Availableonline: http://www.analog.com/en/products/ processors-dsp/dsp/tigersharc-processors/adsp-ts201s.html#product-overview(accessedon15May2018). 5. Muchnick, S.S. Advanced Compiler Design and Implementation; Morgan Kauffman: San Francisco, CA, USA,1997. 6. Novikov, S.V.Global SchedulingMethods forArchitectureswithExplicit InstructionLevel Parallelism. Ph.D.Thesis, InstituteofMicroprocessorComputerSystemsRAS(NIISI),Moscow,Russia,2005. 190