Article

Scheduling DAGs on asynchronous processors

Authors:

Michael A. Bender,

Cynthia A. PhillipsAuthors Info & Claims

SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures

Pages 35 - 45

https://doi.org/10.1145/1248377.1248384

Published: 09 June 2007 Publication History

Abstract

This paper addresses the problem of scheduling a DAG of unit-length tasks on asynchronous processors, that is, processors having different and changing speeds. The objective is to minimize the makespan, that is, the time to execute the entire DAG. Asynchrony is modeled by an oblivious adversary, which is assumed to determine the processor speeds at each point in time. The oblivious adversary may change processor speeds arbitrarily and arbitrarily often, but makes speed decisions independently of any random choices of the scheduling algorithm.

This paper gives bounds on the makespan of two randomized online firing-squad scheduling algorithms, All and Level. These two schedulers are shown to have good makespan even when asynchrony is arbitrarily extreme. Let W and D denote, respectively, the number of tasks and the longest path in the DAG, and let π_ave denote the average speed of the p processors during the execution.

In All each processor repeatedly chooses a random task to execute from among all ready tasks (tasks whose predecessors have been executed). Scheduler All is shown to have a makespan T_p=

Θ(W<over>pπ_ave), when W<over>D ≥ p log p

Θ((log p)^α W<over>pπ_ave + (log p) ^1-α D<over>π_ave), when W<over>D= p(log p)^1-2α, for α ∈ [0, 1]

Θ (D<over>π_ave, when W<over>D ≤ p<over>log p,

both expected and with high probability. A family of DAGs is exhibited for which this analysis is tight.

In Level each of the processors repeatedly chooses a random task to execute from among all critical tasks (ready tasks at the lowest level of the DAG). This second scheduler is shown to have a makespan of.

References

[1]

D. P. Anderson, J. Cobb, E. Korpela, M. Lebofsky, and D. Werthimer. Seti@home: an experiment in public-resource computing. Commun. ACM, 45(11):56--61, 2002.

Digital Library

[2]

Y. Aumann, M. A. Bender, and L. Zhang. Efficient execution of nondeterministic parallel programs on asynchronous systems. In Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 270--276, 1996.

Digital Library

[3]

Y. Aumann, M. A. Bender, and L. Zhang. Efficient execution of nondeterministic parallel programs on asynchronous systems. Information and Computation, 139(1):1--16, 25 Nov. 1997.

Digital Library

[4]

Y. Aumann, Z. M. Kedem, K. V. Palem, and M. O. Rabin. Highly efficient asynchronous execution of large-grained parallel programs. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 271--280, 1993.

Digital Library

[5]

Y. Aumann and M. O. Rabin. Clock construction in fully asynchronous parallel systems and pram simulation. Theoretical Computer Science, 128:3--30, 1994.

Digital Library

[6]

A. Baratloo, P. Dasgupta, V. Karamcheti, and Z. M. Kedem. Metacomputing with milan. In Proceedings of the Eighth Heterogeneous Computing Workshop (HCW), page 169, 1999.

Digital Library

[7]

A. Baratloo, P. Dasgupta, and Z. M. Kedem. Calypso: A novel software system for fault-tolerant parallel processing on distributed platforms. In Proceedings of the 4th International Symposium on High Performance Distributed Computing (HPDC), pages 122--129, 1995.

Digital Library

[8]

A. Baratloo, M. Karaul, Z. M. Kedem, and P. Wijckoff. Charlotte: metacomputing on the web. 9th International Conference on Parallel and Distributed Computing Systems (PDCS), 1996.

[9]

M. A. Bender and M. O. Rabin. Scheduling Cilk multithreaded computations on processors of different speeds. In Proceedings of the 12th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 13--21, July 2000.

Digital Library

[10]

M. A. Bender and M. O. Rabin. Online scheduling of parallel programs on heterogeneous systems with applications to Cilk. Theory of Computing Systems Special Issue on SPAA00, 35:289--304, 2002.

[11]

R. D. Blumofe and C. E. Leiserson. Scheduling multithreaded computations by work stealing. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), pages 356--368, Santa Fe, New Mexico, Nov. 1994.

Digital Library

[12]

R. P. Brent. The parallel evaluation of general arithmetic expressions. Journal of the ACM, 21(2):201--206, April 1974.

Digital Library

[13]

C. Chekuri and M. A. Bender. An efficient approximation algorithm for minimizing makespan on uniformly related machines. In Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization (IPCO), volume 1412, pages 383--393, 1998.

[14]

C. Chekuri and M. A. Bender. An efficient approximation algorithm for minimizing makespan on uniformly related machines. Journal of Algorithms, 41:212--224, 2001.

Digital Library

[15]

F. A. Chudak and D. B. Shmoys. Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds (extended abstract). In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 581--590, New Orleans, Louisiana, 5--7 Jan. 1997.

Digital Library

[16]

F. A. Chudak and D. B. Shmoys. Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. Journal of Algorithms, 30(2):323--343, February 1999.

Digital Library

[17]

R. Cole and O. Zajicek. The expected advantage of asynchrony. In Proc. of the ACM Symposium on Parallel Architectures and Algorithms, pages 85--94, 1989.

Digital Library

[18]

I. Foster and C. Kesselman. Globus: A metacomputing infrastructure toolkit. The International Journal of Supercomputer Applications and High Performance Computing, 11(2):115--128, 1997.

Digital Library

[19]

M. Frigo, C. E. Leiserson, and K. H. Randall. The implementation of the cilk-5 multithreaded language. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation (PLDI), pages 212--223, 1998.

Digital Library

[20]

P. B. Gibbons. A more practical PRAM model. In Proc. of the 1st ACM Symposium on Parallel Architectures and Algorithms, pages 158--168, June 1989.

Digital Library

[21]

R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(2):416--429, Mar. 1969.

Digital Library

[22]

J. M. Jaffe. An analysis of preemptive multiprocessor job scheduling. Mathematics of Operations Research, 5(3):415--421, Aug. 1980.

Digital Library

[23]

J. M. Jaffe. Efficient scheduling of tasks without full use of processor resources. Theoretical Computer Science, 12:1--17, Aug. 1980.

[24]

P. C. Kanellakis and A. A. Shvartsman. Efficient parallel algorithms can be made robust. Distributed Computing, 5(4):201--217, 1992.

Digital Library

[25]

Z. M. Kedem, K. V. Palem, M. O. Rabin, and A. Raghunathan. Efficient program transformation for resilient parallel computation via randomization. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing (STOC), pages 306--317, May 1992.

Digital Library

[26]

Z. M. Kedem, K. V. Palem, A. Raghunathan, and P. G. Spirakis. Combining tentative and definite executions for very fast dependable parallel computing. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC), pages 381--390, May 1991.

Digital Library

[27]

Z. M. Kedem, K. V. Palem, and P. G. Spirakis. Efficient robust parallel computations. In Proceedings of the 22rd Annual ACM Symposium on Theory of Computing (STOC), pages 138--148, May 1990.

Digital Library

[28]

S. C. Kontogiannis, G. E. Pantziou, P. G. Spirakis, and M. Yung. Robust parallel computations through randomization. Theory of Computing Systems, 33(5/6):427--464, 2000.

[29]

G. Malewicz. Parallel scheduling of complex dags under uncertainty. In Proceedings of the 17th Ann. ACM Symp. Parallelism in Algorithms and Architectures (SPAA), pages 66--75, 2005.

Digital Library

[30]

C. Martel, A. Park, and R. Subramonian. Asynchronous PRAMs are (almost) as good as synchronous PRAMs. In Proceedings of the 31st Annual Symposium on the Foundations of Computer Science (FOCS), pages 590--599, 1990.

Digital Library

[31]

M. O. Neary and P. Cappello. Advanced eager scheduling for java-based adaptive parallel computing: Research articles. Concurrency and Computation: Practice and Experience, 17(7-8):797--819, 2005.

Digital Library

[32]

N. Nishimura. Asynchronous shared memory parallel computation. In Proc. of the 2nd ACM Symposium on Parallel Architectures and Algorithms, pages 76--84, 1990.

Digital Library

[33]

A. Panconesi and A. Srinivasan. Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM J. Comput., 26(2):350--368, 1997.

Digital Library

[34]

A. Srinivasan. Distributions on level-sets with applications to approximation algorithms. In Proceedings of the 42 Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 588--597, 2001.

Digital Library

[35]

J. Ullman. NP-complete scheduling problems. Journal Computing System Science, 10:384--393, 1975.

Digital Library

Cited By

Cordasco GDe Chiara RRosenberg A(2015)An AREA-Oriented Heuristic for Scheduling DAGs on Volatile Computing PlatformsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2014.234618926:8(2164-2177)Online publication date: 1-Aug-2015
https://doi.org/10.1109/TPDS.2014.2346189
Roche SRosenberg ARajaraman R(2015)On constructing DAG‐schedules with large areasConcurrency and Computation: Practice and Experience10.1002/cpe.356027:16(4107-4121)Online publication date: 25-Jun-2015
https://doi.org/10.1002/cpe.3560
Roche SRosenberg ARajaraman R(2014)On Constructing DAG-Schedules with Large AREAsEuro-Par 2014 Parallel Processing10.1007/978-3-319-09873-9_52(620-631)Online publication date: 2014
https://doi.org/10.1007/978-3-319-09873-9_52
Show More Cited By

Index Terms

Scheduling DAGs on asynchronous processors
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Scheduling on Unrelated Machines under Tree-Like Precedence Constraints

We present polylogarithmic approximations for the R|prec|C _max and R|prec|∑_j w _j C _j problems, when the precedence constraints are “treelike”—i.e., when the undirected graph underlying the precedences is a forest. These are the first non-trivial ...
Preemptive online scheduling with rejection of unit jobs on two uniformly related machines

We consider preemptive online and semi-online scheduling of unit jobs on two uniformly related machines. Jobs are presented one by one to an algorithm, and each job has a rejection penalty associated with it. A new job can either be rejected, in which ...
Non-clairvoyant scheduling with precedence constraints
SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

We consider Edmonds's model (1999) extended by precedence constraints. In our setting, a scheduler has to schedule non-clairvoyantly jobs consisting in DAGs of tasks arriving over time, each task going through phases of different degrees of parallelism, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures

June 2007

376 pages

ISBN:9781595936677

DOI:10.1145/1248377

General Chair:
Phillip B. Gibbons
Intel Research, USA
,
Program Chair:
Christian Scheideler
Technische Universität München, Germany

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SPAA07

Sponsor:

SPAA07: 19th ACM Symposium on Parallelism in Algorithms and Architectures

June 9 - 11, 2007

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Upcoming Conference

SPAA '25

Sponsor:
sigact
sigact

37th ACM Symposium on Parallelism in Algorithms and Architectures

July 28 - August 1, 2025

Portland , OR , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
422
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cordasco GDe Chiara RRosenberg A(2015)An AREA-Oriented Heuristic for Scheduling DAGs on Volatile Computing PlatformsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2014.234618926:8(2164-2177)Online publication date: 1-Aug-2015
https://doi.org/10.1109/TPDS.2014.2346189
Roche SRosenberg ARajaraman R(2015)On constructing DAG‐schedules with large areasConcurrency and Computation: Practice and Experience10.1002/cpe.356027:16(4107-4121)Online publication date: 25-Jun-2015
https://doi.org/10.1002/cpe.3560
Roche SRosenberg ARajaraman R(2014)On Constructing DAG-Schedules with Large AREAsEuro-Par 2014 Parallel Processing10.1007/978-3-319-09873-9_52(620-631)Online publication date: 2014
https://doi.org/10.1007/978-3-319-09873-9_52
López-Ortiz ASalinger A(2013)On the Sublinear Processor Gap for Parallel ArchitecturesTheory and Applications of Models of Computation10.1007/978-3-642-38236-9_18(193-204)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38236-9_18
Hartley TSaule EÇatalyürek í(2012)Improving performance of adaptive component-based dataflow middlewareParallel Computing10.1016/j.parco.2012.03.00538:6-7(289-309)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1016/j.parco.2012.03.005
Cordasco GDe Chiara RRosenberg A(2012)On scheduling dag s for volatile computing platformsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2012.06.00772:10(1347-1360)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1016/j.jpdc.2012.06.007
Olteanu APop FDobre CCristea V(2012)A dynamic rescheduling algorithm for resource management in large scale dependable distributed systemsComputers & Mathematics with Applications10.1016/j.camwa.2012.02.06663:9(1409-1423)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1016/j.camwa.2012.02.066
Hartley TSaule ECatalyurek U(2010)Automatic dataflow application tuning for heterogeneous systems2010 International Conference on High Performance Computing10.1109/HIPC.2010.5713173(1-10)Online publication date: Dec-2010
https://doi.org/10.1109/HIPC.2010.5713173
Cordasco GMalewicz GRosenberg A(2010)Extending IC-scheduling via the Sweep AlgorithmJournal of Parallel and Distributed Computing10.1016/j.jpdc.2009.11.00170:3(201-211)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1016/j.jpdc.2009.11.001
Cordasco GMalewicz GRosenberg A(2008)Extending IC-Scheduling via the Sweep AlgorithmProceedings of the 16th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP 2008)10.1109/PDP.2008.16(366-373)Online publication date: 13-Feb-2008
https://dl.acm.org/doi/10.1109/PDP.2008.16

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten