Page - 190 - in Algorithms for Scheduling Problems
Image of the Page - 190 -
Text of the Page - 190 -
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
back to the
book Algorithms for Scheduling Problems"
Algorithms for Scheduling Problems
- Title
- Algorithms for Scheduling Problems
- Authors
- Frank Werner
- Larysa Burtseva
- Yuri Sotskov
- Editor
- MDPI
- Location
- Basel
- Date
- 2018
- Language
- English
- License
- CC BY 4.0
- ISBN
- 978-3-03897-120-7
- Size
- 17.0 x 24.4 cm
- Pages
- 212
- Keywords
- Scheduling Problems in Logistics, Transport, Timetabling, Sports, Healthcare, Engineering, Energy Management
- Categories
- Informatik
- Technik