On constructing DAG‐schedules with large areas. (25th June 2015)

• Record Type: Journal Article
• Authors: Roche, Scott T.; Rosenberg, Arnold L.; Rajaraman, Rajmohan
• Is Part Of: Concurrency and computation. Volume 27:Number 16(2015:Nov.)
• Page Start: 4107
• Page End: 4121
• Publication Date: 2015-06-25
• Subjects: DAG scheduling algorithms -- cloud computing -- dynamic heterogeneity; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.3560
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: The Area of a schedule Σ for a directed acyclic graph (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 executeDAG s faster on platforms that are dynamically heterogeneous : the platform's processors change power and availability status in unpredictable ways and at unpredictable 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‐structuredDAG s. Our first result shows that the problem of crafting Area‐maximal schedules for generalDAG s isNP ‐complete, hence likely computationally intractable. We also provide an efficient algorithm that approximates optimal Area to within a factor of 1 / ( 2 n ), where n is the number of tasks in theDAG —a factor that is likely interesting only for smallDAG s. The lack of efficient Area‐maximizing schedulers for generalDAG s has instigated the development of several heuristics for producingDAG ‐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 aDAG . (1) Simulations onDAG s having random structure yield the following results. TheSIDNEY heuristic produces schedules whose Areas: (a) are at least 85% of maximal; and (b) are at least 1.25 times greater than previously known heuristics. (2) Simulations onDAG s having the structure of random LEGO ®; DAG s (as formulated in earlier studies) indicate that the schedules produced by theSIDNEY 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 ofDAG ‐schedules produced by theSIDNEY heuristic are at least 85% of the Area value produced by the (unrounded) LP. (3) The reported results on randomDAG s are essentially matched by a second heuristic, which producesDAG ‐schedules by rounding the results of the LP formulation. Copyright © 2015 John Wiley & Sons, Ltd.