Page - 186 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 76 5.1. Parameters Toprovideaperformancecomparison,weusedworkloadsfromaparametricworkloadgenerator that produces workflows such as Ligo and Montage [27,28]. They are a complex workflow of parallelizedcomputations toprocess larger-scale images. WeconsideredthreeclusterswithdifferentnumbersofDSPsandtwoarchitecturesof individual DSPs(Table4). Theirclockfrequencywasconsideredtobeequal. Table4.Experimental settings. Description Settings Workloadtype 220Montageworkflows,98Ligoworkflows DSPclusters 3 Cluster1 5 IMs inaclusterB, 4DSPpermodule Cluster2 2 IMs inaclusterA, 4DSPpermodule Cluster3 5 IMs inaclusterA, 4DSPpermodule Data transmissioncoefficientK 0—within thesameDSP 1—betweenconnectedDSPs ina IM; 20—betweenDSPofdifferent IMs Metrics Cmax, cpw, cps Numberofexperiments 318 5.2.MethodologyofAnalysis Workflowscheduling involvesmultipleobjectivesandmayusemulti-criteriadecisionsupport. Theclassicalapproach is touseaconceptofParetooptimality.However, it isverydifficult toachieve the fast solutionsneededforDSPresourcemanagementbyusingtheParetodominance. In this paper, we converted the problem to a single objective optimization problem by multiple-criteria aggregation. First,wemadecriteria comparablebynormalizing themto thebest values foundduring eachexperiment. To this end,weevaluated theperformancedegradationof eachstrategyundereachmetric. Thiswasdonerelative to thebestperformingstrategyfor themetric, as follows: (γ−1)·100, withγ= strategymetric value best foundmetric value . Toprovide effective guidance in choosing the best strategy,weperformeda joint analysis of severalmetricsaccordingto themethodologyusedin[14,29].Weaggregatedthevariousobjectives to a single oneby averaging their values and ranking. Thebest strategywith the lowest average performancedegradationhadarankof1. Note thatwetriedto identifystrategies thatperformedreliablywell indifferentscenarios; that is,we tried tofinda compromise that considered all of our test caseswith the expectation that it alsoperformedwellunderotherconditions, forexample,withdifferentDSP-clusterconfigurations andworkloads. Forexample, the rankof the strategycouldnotbe the same foranyof themetrics individuallyoranyof thescenarios individually. 6. ExperimentalResults 6.1. PerformanceDegradationAnalysis Figure4andTable5showtheperformancedegradationofall strategies forCmax, cpw, and cps. Table5alsoshowsthemeandegradationof thestrategiesandrankingwhenconsideringallaverages andall test cases. 186