2002 · 243 citations · 9 references
ComputingComputer ScienceComputer SystemsAlgorithmsOptimizationSchedulingAlgorithm AnalysisGreedy AlgorithmsJob SchedulingLoad BalancingMachine SchedulingPerformance OptimizationExpected Time To CompletionGreedy HeuristicsLoad Balancing StrategiesMapping AlgorithmsRelative Performance AnalysisTask Mapping
Four mapping algorithms—two naive (OLB, LBA) and two greedy—are compared, with most using expected run‑times for job assignment. The study evaluates the performance of these four mapping algorithms. Run‑time distributions were empirically derived and used in simulations to assess algorithm performance. Greedy algorithms outperform naive ones in schedule quality even when exact run‑times are unavailable, confirming the benefit of intelligent mapping.
The author studies the performance of four mapping algorithms. The four algorithms include two naive ones: opportunistic load balancing (OLB), and limited best assignment (LBA), and two intelligent greedy algorithms: an O(nm) greedy algorithm, and an O(n/sup 2/m) greedy algorithm. All of these algorithms, except OLB, use expected run-times to assign jobs to machines. As expected run-times are rarely deterministic in modern networked and server based systems, he first uses experimentation to determine some plausible run-time distributions. Using these distributions, he next executes simulations to determine how the mapping algorithms perform. Performance comparisons show that the greedy algorithms produce schedules that, when executed, perform better than naive algorithms, even though the exact run-times are not available to the schedulers. He concludes that the use of intelligent mapping algorithms is beneficial, even when the expected time for completion of a job is not deterministic.
9
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations