2009 · 17 citations · 13 references
ComputingComputer EngineeringComputer ScienceAlgorithmsHeterogeneous ComputingSchedulingAlgorithm AnalysisCritical Path AnalysisParallel Computing SystemsTask SchedulingDirected Acyclic Graph SchedulingHeterogeneous SchedulingHeterogeneous Task SchedulingList SchedulingMultiprocessor SchedulingNp-complete ProblemsParallel SchedulingScheduling In Multiprocessor Systems
Scheduling a parallel application on a set of processors is a well-known NP-complete problem. The problem becomes more complex when the base system is composed of heterogeneous processors. In this paper, we present a low-complexity task scheduling algorithm for heterogeneous computing systems, which we call the multiple critical path dominator (MCPD) algorithm. This algorithm is based on task duplication and its complexity is o(v <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ). An application for scheduling is represented by a directed acyclic graph (DAG). The MCPD algorithm employs a novel list scheduling algorithm for prioritizing tasks. This list-scheduling algorithm considers the variation of the critical paths in the DAG statistically whereby the MCPD algorithm attempts to schedule tasks on the processor according to the importance of the parent. We base our decisions on mean values of computation and communication cost of nodes and edges in the unscheduled DAG.
13
NP-complete scheduling problems
Jeffrey D. Ullman · Journal of Computer and System Sciences · 1975 · 1.4K citations