On Constructing DAG-Schedules with Large AREAs

Abstract. The Area of a schedule Σ for a DAG G is a quality metric that measures the rate at which Σ renders G’s nodes eligible for execution. Specifically, AREA(Σ) is the average number of nodes of G that are eligible for execution as Σ executes G node by node. Extensive simulations suggest that, for many distributions of processor availability and power, DAG-schedules having larger Areas execute DAGs faster on platforms that are dynamically heterogeneous: the platform’s processors change power and availability status in unpredictable ways and at unpre-dictable times. (Clouds and desktop grids exemplify such platforms.) While Area-maximal schedules can provably be found for every DAG, efficient generators of such schedules are known only for families of well-structured DAGs. Our first result shows that the problem of crafting Area-maximal schedules for general DAGs is NP-complete, hence likely computationally intractable. The lack of efficient Area-maximizing schedulers for general DAGs has instigated the development of several heuristics for producing DAG-schedules that have large Areas. We propose a novel polynomial-time heuristic that produces schedules having quite large Areas; the heuristic is based on the Sidney decomposition of a DAG. (1) Simulations on DAGs having random structure yield the following results. The Sidney heuristic produces schedules whose Areas: (a) are at least 85 % of maximal; (b) are at least 1.25 times greater than previously known heuristics. (2) Simulations on DAGs having the structure of random “LEGO R© ” DAGs (as formulated in earlier studies) indicate that the schedules produced by the Sidney heuristic have Areas that are at least 1.5 times greater than previously known heuristics. The “85% ” result is obtained from formulating the Area-maximization problem as a Linear Program (LP); the Areas of DAG-schedules produced by the Sidney heuristic are at least 85 % of the Area-value produced by the (unrounded) LP. (3) The reported results on random DAGs are essentially matched by a second heuristic, which produces DAG-schedules by rounding the results of the LP formulation.