Document Open Access Logo

Scheduling with Communication Delay in Near-Linear Time

Authors Quanquan C. Liu, Manish Purohit, Zoya Svitkina, Erik Vee, Joshua R. Wang

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.47.pdf
  • Filesize: 0.97 MB
  • 23 pages

Document Identifiers

Author Details

Quanquan C. Liu
  • MIT, CSAIL, Cambridge, MA, US
Manish Purohit
  • Google Research, Mountain View, CA, USA
Zoya Svitkina
  • Google Research, Mountain View, CA, USA
Erik Vee
  • Google Research, Mountain View, CA, uSA
Joshua R. Wang
  • Google Research, Mountain View, CA, USA

Cite AsGet BibTex

Quanquan C. Liu, Manish Purohit, Zoya Svitkina, Erik Vee, and Joshua R. Wang. Scheduling with Communication Delay in Near-Linear Time. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 47:1-47:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.47

Abstract

We consider the problem of efficiently scheduling jobs with precedence constraints on a set of identical machines in the presence of a uniform communication delay. Such precedence-constrained jobs can be modeled as a directed acyclic graph, G = (V, E). In this setting, if two precedence-constrained jobs u and v, with v dependent on u (u ≺ v), are scheduled on different machines, then v must start at least ρ time units after u completes. The scheduling objective is to minimize makespan, i.e. the total time from when the first job starts to when the last job finishes. The focus of this paper is to provide an efficient approximation algorithm with near-linear running time. We build on the algorithm of Lepere and Rapine [STACS 2002] for this problem to give an O((ln ρ)/(ln ln ρ))-approximation algorithm that runs in Õ(|V|+|E|) time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
Keywords
  • near-linear time scheduling
  • scheduling with duplication
  • precedence-constrained jobs
  • graph algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ishfaq Ahmad and Yu-Kwong Kwok. On exploiting task duplication in parallel program scheduling. IEEE Transactions on Parallel and Distributed Systems, 9(9):872-892, September 1998. URL: https://doi.org/10.1109/71.722221.
  2. Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC '96, pages 20-29, 1996. URL: https://doi.org/10.1145/237814.237823.
  3. Evripidis Bampis, Aristotelis Giannakos, and Jean-Claude König. On the complexity of scheduling with large communication delays. European Journal of Operational Research, 94:252-260, 1996. Google Scholar
  4. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan. Counting distinct elements in a data stream. In Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, RANDOM '02, pages 1-10, 2002. Google Scholar
  5. Doruk Bozdag, Fusun Ozguner, and Umit V Catalyurek. Compaction of schedules and a two-stage approach for duplication-based DAG scheduling. IEEE Transactions on Parallel and Distributed Systems, 20(6):857-871, 2008. Google Scholar
  6. Peter Brucker. Scheduling Algorithms. Springer Publishing Company, Incorporated, 5th edition, 2010. Google Scholar
  7. Israel Casas, Javid Taheri, Rajiv Ranjan, Lizhe Wang, and Albert Y Zomaya. A balanced scheduler with data reuse and replication for scientific workflows in cloud computing systems. Future Generation Computer Systems, 74:168-178, 2017. Google Scholar
  8. P. Chassaing and L. Gerin. Efficient estimation of the cardinality of large data sets. Discrete Mathematics & Theoretical Computer Science, pages 419-422, 2006. Google Scholar
  9. S. Darbha and D. P. Agrawal. Optimal scheduling algorithm for distributed-memory machines. IEEE Transactions on Parallel and Distributed Systems, 9:87-95, 1998. Google Scholar
  10. Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, and Yihao Zhang. Scheduling with communication delays via LP hierarchies and clustering. In FOCS, 2020. Google Scholar
  11. Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, and Yihao Zhang. Scheduling with communication delays via LP hierarchies and clustering II: weighted completion times on related machines. In SODA 2021, pages 2958-2977. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.176.
  12. Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. In AofA: Analysis of Algorithms, pages 137-156, 2007. URL: https://hal.inria.fr/hal-00406166.
  13. R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math., 17:416-429, 1969. Google Scholar
  14. R. L. Graham. Bounds on multiprocessing anomalies and related packing algorithms. In Proceedings of the May 16-18, 1972, Spring Joint Computer Conference, AFIPS '72 (Spring), pages 205-217, New York, NY, USA, 1971. Association for Computing Machinery. URL: https://doi.org/10.1145/1478873.1478901.
  15. Claire Hanen and Alix Munier. An approximation algorithm for scheduling dependent tasks on m processors with small communication delays. Discret. Appl. Math., 108(3):239-257, 2001. URL: https://doi.org/10.1016/S0166-218X(00)00179-7.
  16. J.A. Hoogeveen, J.K. Lenstra, and B. Veltman. Three, four, five, six, or the complexity of scheduling with communication delays. Operations Research Letters, 16(3):129-137, 1994. URL: https://doi.org/10.1016/0167-6377(94)90024-8.
  17. Daniel M. Kane, Jelani Nelson, and David P. Woodruff. An optimal algorithm for the distinct elements problem. In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '10, pages 41-52, 2010. URL: https://doi.org/10.1145/1807085.1807094.
  18. Janardhan Kulkarni, Shi Li, Jakub Tarnawski, and Minwei Ye. Hierarchy-based algorithms for minimizing makespan under precedence and communication constraints. In Proceedings of the Fortieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2020. Google Scholar
  19. Renaud Lepère and Christophe Rapine. An asymptotic O(ln ρ/ln ln ρ)-approximation algorithm for the scheduling problem with duplication on large communication delay graphs. In STACS, volume 2285 of Lecture Notes in Computer Science, pages 154-165, 2002. URL: https://doi.org/10.1007/3-540-45841-7_12.
  20. Quanquan C. Liu, Manish Purohit, Zoya Svitkina, Erik Vee, and Joshua R. Wang. Scheduling with communication delay in near-linear time. CoRR, abs/2108.02770, 2021. URL: http://arxiv.org/abs/2108.02770.
  21. Biswaroop Maiti, Rajmohan Rajaraman, David Stalfa, Zoya Svitkina, and Aravindan Vijayaraghavan. Scheduling precedence-constrained jobs on related machines withcommunication delay. In FOCS, 2020. Google Scholar
  22. Alix Munier. Approximation algorithms for scheduling trees with general communication delays. Parallel Computing, 25(1):41-48, 1999. Google Scholar
  23. Alix Munier and Claire Hanen. Using duplication for scheduling unitary tasks on m processors with unit communication delays. Theoretical Computer Science, 178(1):119-127, 1997. URL: https://doi.org/10.1016/S0304-3975(97)88194-7.
  24. Alix Munier and Jean-Claude König. A heuristic for a scheduling problem with communi-cation delays. Operations Research, 45(1):145-147, 1997. Google Scholar
  25. Rasmus Pagh, Morten Stöckel, and David P. Woodruff. Is min-wise hashing optimal for summarizing set intersection? In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '14, pages 109-120, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2594538.2594554.
  26. Michael A. Palis, Jing-Chiou Liou, and David S. L. Wei. Task clustering and scheduling for distributed memory parallel architectures. IEEE Transactions on Parallel and Distributed Systems, 7(1):46-55, 1996. Google Scholar
  27. Christos H. Papadimitriou and Mihalis Yannakakis. Towards an architecture-independent analysis of parallel algorithms. SIAM journal on computing, 19(2):322-328, 1990. Google Scholar
  28. Christophe Picouleau. New complexity results on scheduling with small communication delays. Discret. Appl. Math., 60(1-3):331-342, 1995. URL: https://doi.org/10.1016/0166-218X(94)00063-J.
  29. Victor J Rayward-Smith. UET scheduling with unit interprocessor communication delays. Discrete Applied Mathematics, 18(1):55-71, 1987. Google Scholar
  30. Kyu-Young Whang, Brad T. Vander-Zanden, and Howard M. Taylor. A linear-time probabilistic counting algorithm for database applications. ACM Trans. Database Syst., 15(2):208-229, June 1990. URL: https://doi.org/10.1145/78922.78925.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact