Name
Abstract | ||
|---|---|---|
The Area of a schedule sigma for a directed acyclic graph (DAG) G is a quality metric that measures the rate at which sigma renders G's nodes eligible for execution. Specifically, AREA(sigma) is the average number of nodes of G that are eligible for execution as sigma 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 unpredictable times. (Clouds and desktop grids exemplify such platforms.) While Area-maximal schedules can provably be found for everyDAG, 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 <sans-serif>NP</sans-serif>-complete, hence likely computationally intractable. We also provide an efficient algorithm that approximates optimal Area to within a factor of 1/(2<mml:msqrt>n</mml:msqrt>), where n is the number of tasks in the DAGa factor that is likely interesting only for small DAGs. 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; and (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. Copyright (c) 2015 John Wiley & Sons, Ltd. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1002/cpe.3560 | CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE |
Keywords | Field | DocType |
DAG scheduling algorithms,cloud computing,dynamic heterogeneity | Heuristic,Computer science,Parallel computing,Directed acyclic graph,Rounding,Schedule,Heuristics,Linear programming,Distributed computing,Cloud computing | Journal |
Volume | Issue | ISSN |
27 | SP16 | 1532-0626 |
Citations | PageRank | References |
3 | 0.38 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Scott T. Roche | 1 | 19 | 2.20 |
| Arnold L. Rosenberg | 2 | 2107 | 640.21 |
| Rajmohan Rajaraman | 3 | 2038 | 250.08 |