Premium
On constructing DAG‐schedules with large areas
Author(s) -
Roche Scott T.,
Rosenberg Arnold L.,
Rajaraman Rajmohan
Publication year - 2015
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.3560
Subject(s) - directed acyclic graph , computer science , heuristics , schedule , scheduling (production processes) , heuristic , parallel computing , directed graph , metric (unit) , distributed computing , mathematical optimization , algorithm , mathematics , operations management , artificial intelligence , economics , operating system
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 execute DAG 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‐structured DAG s. Our first result shows that the problem of crafting Area‐maximal schedules for general DAG s is NP ‐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 the DAG —a factor that is likely interesting only for small DAG s. The lack of efficient Area‐maximizing schedulers for general DAG s 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 DAG s having random structure yield the following results. The SIDNEY 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 on DAG s having the structure of random LEGO ®; DAG s (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 DAG s are essentially matched by a second heuristic, which produces DAG ‐schedules by rounding the results of the LP formulation. Copyright © 2015 John Wiley & Sons, Ltd.