VPSS: A DAG scheduling heuristic with improved response time bound

Real-time and embedded systems are shifting from single-core to multi-core platforms, on which software must be parallelized to fully utilize the computation power of multi-core hardware. Most current real-time parallel tasks can be modeled as directed acyclic graphs (DAG). Scheduling DAG tasks on multi-core processors is a key issue for high-performance computing, and in real-time scenario, a good scheduler should not only achieves a competitive performance in practice, but also needs to be predictable from a theoretical point of view. Graham's list scheduling algorithm performs well, but often suffers from pessimism, i.e., the gap between the exact response time and Graham's response time bound is larger than 50% or more for some cases. In this paper, we propose a novel heuristic for scheduling a DAG task, called the vertex-partition-and-subset-scheduling (VPSS) algorithm, which has two phases: first, we partition DAG's vertices into several disjoint subsets, and then we sequentially schedule these vertex subsets. The VPSS algorithm yields a response time bound that totally dominates Graham's bound. Experimental work shows that our response time bound is 8% smaller than Graham's bound on average, and our bound is even 80% smaller than Graham's bound for some special cases.