Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game

Authors William Kuszmaul, Shyam Narayanan



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.85.pdf
  • Filesize: 0.68 MB
  • 20 pages

Document Identifiers

Author Details

William Kuszmaul
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Shyam Narayanan
  • Massachusetts Institute of Technology, Cambridge, MA, USA

Cite AsGet BibTex

William Kuszmaul and Shyam Narayanan. Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 85:1-85:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.85

Abstract

The p-processor cup game is a classic and widely studied scheduling problem that captures the setting in which a p-processor machine must assign tasks to processors over time in order to ensure that no individual task ever falls too far behind. The problem is formalized as a multi-round game in which two players, a filler (who assigns work to tasks) and an emptier (who schedules tasks) compete. The emptier’s goal is to minimize backlog, which is the maximum amount of outstanding work for any task. Recently, Kuszmaul and Westover (ITCS, 2021) proposed the variable-processor cup game, which considers the same problem, except that the amount of resources available to the players (i.e., the number p of processors) fluctuates between rounds of the game. They showed that this seemingly small modification fundamentally changes the dynamics of the game: whereas the optimal backlog in the fixed p-processor game is Θ(log n), independent of p, the optimal backlog in the variable-processor game is Θ(n). The latter result was only known to apply to games with exponentially many rounds, however, and it has remained an open question what the optimal tradeoff between time and backlog is for shorter games. This paper establishes a tight trade-off curve between time and backlog in the variable-processor cup game. We show that, for a game consisting of t rounds, the optimal backlog is Θ (b (t)) where b(t) = t (if t ≤ log n) t^{1/3} log^{2/3} ({n^3}/t + 1) (if log n < t ≤ n^3) n (if n ^ 3 < t). An important consequence is that the optimal backlog is Θ(n) if and only if t ≥ Ω(n³). Our techniques also allow for us to resolve several other open questions concerning how the variable-processor cup game behaves in beyond-worst-case-analysis settings.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
  • Theory of computation → Parallel algorithms
  • Theory of computation → Scheduling algorithms
Keywords
  • Cup Games
  • Potential Functions
  • Greedy

Metrics

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

References

  1. Micah Adler, Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul Goldberg, and Mike Paterson. A proportionate fair scheduling rule with good worst-case performance. In Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 101-108, 2003. URL: https://doi.org/10.1145/777412.777430.
  2. Amihood Amir, Martin Farach, Ramana M. Idury, Johannes A. La Poutré, and Alejandro A. Schäffer. Improved dynamic dictionary matching. Inf. Comput., 119(2):258-282, 1995. URL: https://doi.org/10.1006/inco.1995.1090.
  3. Amihood Amir, Gianni Franceschini, Roberto Grossi, Tsvi Kopelowitz, Moshe Lewenstein, and Noa Lewenstein. Managing unbounded-length keys in comparison-driven data structures with applications to online indexing. SIAM Journal on Computing, 43(4):1396-1416, 2014. Google Scholar
  4. Yossi Azar and Arik Litichevskey. Maximizing throughput in multi-queue switches. Algorithmica, 45(1):69-90, 2006. Google Scholar
  5. Amotz Bar-Noy, Ari Freund, Shimon Landa, and Joseph (Seffi) Naor. Competitive on-line switching policies. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 525-534, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545452.
  6. Amotz Bar-Noy, Aviv Nisgav, and Boaz Patt-Shamir. Nearly optimal perfectly periodic schedules. Distributed Computing, 15(4):207-220, 2002. Google Scholar
  7. S. K. Baruah, N. K. Cohen, C. G. Plaxton, and D. A. Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15(6):600-625, June 1996. URL: https://doi.org/10.1007/BF01940883.
  8. Sanjoy K Baruah, Johannes E Gehrke, and C Greg Plaxton. Fast scheduling of periodic tasks on multiple resources. In Proceedings of the 9th International Parallel Processing Symposium, pages 280-288, 1995. Google Scholar
  9. Michael Bender, Rathish Das, Martín Farach-Colton, Rob Johnson, and William Kuszmaul. Flushing without cascades. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020. Google Scholar
  10. Michael Bender, Martín Farach-Colton, and William Kuszmaul. Achieving optimal backlog in multi-processor cup games. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), 2019. Google Scholar
  11. Michael A Bender, Rezaul A Chowdhury, Rathish Das, Rob Johnson, William Kuszmaul, Andrea Lincoln, Quanquan C Liu, Jayson Lynch, and Helen Xu. Closing the gap between cache-oblivious and cache-adaptive analysis. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 63-73, 2020. Google Scholar
  12. Michael A Bender, Rezaul A Chowdhury, Rathish Das, Rob Johnson, William Kuszmaul, Andrea Lincoln, Quanquan C Liu, Jayson Lynch, and Helen Xu. Closing the gap between cache-oblivious and cache-adaptive analysis. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 63-73, 2020. Google Scholar
  13. Michael A Bender, Roozbeh Ebrahimi, Jeremy T Fineman, Golnaz Ghasemiesfeh, Rob Johnson, and Samuel McCauley. Cache-adaptive algorithms. In Proceedings of the twenty-fifth annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 958-971. SIAM, 2014. Google Scholar
  14. Michael A Bender and William Kuszmaul. Randomized cup game algorithms against strong adversaries. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2059-2077. SIAM, 2021. Google Scholar
  15. Peter Damaschke and Zhen Zhou. On queuing lengths in on-line switching. Theoretical computer science, 339(2-3):333-343, 2005. Google Scholar
  16. Paul Dietz and Daniel Sleator. Two algorithms for maintaining order in a list. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC), pages 365-372, 1987. URL: https://doi.org/10.1145/28395.28434.
  17. Paul F. Dietz and Rajeev Raman. Persistence, amortization and randomization. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 78-88, 1991. URL: http://dl.acm.org/citation.cfm?id=127787.127809.
  18. Johannes Fischer and Paweł Gawrychowski. Alphabet-dependent string searching with wexponential search trees. In Annual Symposium on Combinatorial Pattern Matching (CPM), pages 160-171, 2015. Google Scholar
  19. Rudolf Fleischer and Hisashi Koga. Balanced scheduling toward loss-free packet queuing and delay fairness. Algorithmica, 38(2):363-376, February 2004. URL: https://doi.org/10.1007/s00453-003-1064-z.
  20. H Richard Gail, G Grover, Roch Guérin, Sidney L Hantler, Zvi Rosberg, and Moshe Sidi. Buffer size requirements under longest queue first. Performance Evaluation, 18(2):133-140, 1993. Google Scholar
  21. Leszek Gasieniec, Ralf Klasing, Christos Levcopoulos, Andrzej Lingas, Jie Min, and Tomasz Radzik. Bamboo garden trimming problem (perpetual maintenance of machines with different attendance urgency factors). In International Conference on Current Trends in Theory and Practice of Informatics, pages 229-240. Springer, 2017. Google Scholar
  22. Michael H. Goldwasser. A survey of buffer management policies for packet switches. SIGACT News, 41(1):100-128, 2010. URL: https://doi.org/10.1145/1753171.1753195.
  23. Michael T Goodrich and Paweł Pszona. Streamed graph drawing and the file maintenance problem. In International Symposium on Graph Drawing, pages 256-267. Springer, 2013. Google Scholar
  24. Nan Guan and Wang Yi. Fixed-priority multiprocessor scheduling: Critical instant, response time and utilization bound. In 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum, pages 2470-2473. IEEE, 2012. Google Scholar
  25. Sungjin Im, Benjamin Moseley, and Rudy Zhou. The matroid cup game. Operations Research Letters, 49(3):405-411, 2021. Google Scholar
  26. Tsvi Kopelowitz. On-line indexing for general alphabets via predecessor queries on subsets of an ordered list. In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 283-292, 2012. Google Scholar
  27. William Kuszmaul. Achieving optimal backlog in the vanilla multi-processor cup game. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020. Google Scholar
  28. William Kuszmaul. How asymmetry helps buffer management: achieving optimal tail size in cup games. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1248-1261, 2021. Google Scholar
  29. William Kuszmaul and Alek Westover. The variable-processor cup game. In 12th Innovations in Theoretical Computer Science Conference (ITCS). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  30. Andrea Lincoln, Quanquan C Liu, Jayson Lynch, and Helen Xu. Cache-adaptive exploration: Experimental results and scan-hiding for adaptivity. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 213-222, 2018. Google Scholar
  31. Ami Litman and Shiri Moran-Schein. On distributed smooth scheduling. In Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 76-85, 2005. Google Scholar
  32. Ami Litman and Shiri Moran-Schein. Smooth scheduling under variable rates or the analog-digital confinement game. Theor. Comp. Sys., 45(2):325-354, June 2009. URL: https://doi.org/10.1007/s00224-008-9134-x.
  33. Ami Litman and Shiri Moran-Schein. On centralized smooth scheduling. Algorithmica, 60(2):464-480, 2011. Google Scholar
  34. Chung Laung Liu. Scheduling algorithms for multiprocessors in a hard real-time environment. JPL Space Programs Summary, 1969, 1969. Google Scholar
  35. Chung Laung Liu and James W Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM (JACM), 20(1):46-61, 1973. Google Scholar
  36. Richard T Mills, Andreas Stathopoulos, and Dimitrios S Nikolopoulos. Adapting to memory pressure from within scientific applications on multiprogrammed cows. In Proc. 8th International Parallel and Distributed Processing Symposium (IPDPS), page 71, 2004. Google Scholar
  37. Mark Moir and Srikanth Ramamurthy. Pfair scheduling of fixed and migrating periodic tasks on multiple resources. In Proceedings of the 20th IEEE Real-Time Systems Symposium, pages 294-303, 1999. Google Scholar
  38. Christian Worm Mortensen. Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 618-627, 2003. Google Scholar
  39. Michael Rosenblum, Michel X Goemans, and Vahid Tarokh. Universal bounds on buffer size for packetizing fluid policies in input queued, crossbar switches. In Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), volume 2, pages 1126-1134, 2004. Google Scholar
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