Scalably scheduling processes with arbitrary speedup curves

Abstract

We give a scalable ((1+ϵ)-speed O(1)-competitive) nonclairvoyant algorithm for scheduling jobs with sublinear nondecreasing speedup curves on multiple processors with the objective of average response time.

References

1. Bansal, N., Krishnaswamy, R., and Nagarajan, V. 2009. Better scalable algorithms for broadcast scheduling. In Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming (ICALP'09).
2. Becchetti, L. and Leonardi, S. 2004. Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. J. ACM 51, 4, 517--539.
3. Berman, P. and Coulston, C. 1999. Speed is more powerful than clairvoyance. Nordic J. Comput. 6, 2, 181--193.
4. Chan, H.-L., Edmonds, J., Lam, T. W., Lee, L.-K., Marchetti-Spaccamela, A., and Pruhs, K. 2009a. Nonclairvoyant speed scaling for flow and energy. In Proceedings of the Symposium on Theoretical Aspects of Computer Science. 255--264.
5. Chan, H.-L., Edmonds, J., and Pruhs, K. 2009b. Speed scaling of processes with arbitrary speedup curves on a multiprocessor. In Proceedings of the Symposium on Parallel Algorithms and Architectures. 1--10.
6. Chekuri, C., Im, S., and Moseley, B. 2009. Minimizing maximum response time and delay factor in broadcast scheduling. In Proceedings of the European Symposium on Algorithms.
7. Chekuri, C. and Moseley, B. 2009. Online scheduling to minimize the maximum delay factor. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 1116--1125.
8. Edmonds, J. 2000. Scheduling in the dark. Theor. Comput. Sci. 235, 109--141.
9. Edmonds, J. 2004. On the competitiveness of AIMD-TCP within a general network. In Proceedings of the Latin American Symposium on Theoretical Informatics. 567--576.
10. Edmonds, J., Datta, S., and Dymond, P. 2003. TCP is competitive against a limited adversary. In Proceedings of the ACM Symposium on Parallel Algorithms and Architectures. 174--183.
11. Edmonds, J. and Pruhs, K. 2003. Multicast pull scheduling: When fairness is fine. Algorithmica 36, 3, 315--330.
12. Im, S. and Moseley, B. 2010. An online scalable algorithm for average flowtime in broadcast scheduling. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.
13. Kalyanasundaram, B. and Pruhs, K. 2000. Speed is as powerful as clairvoyance. J. ACM 47, 4, 617--643.
14. Kalyanasundaram, B. and Pruhs, K. 2003. Minimizing flow time nonclairvoyantly. J. ACM 50, 4, 551--567.
15. Merritt, R. 2008. CPU designers debate multi-core future. EE Times.
16. Motwani, R., Phillips, S., and Torng, E. 1994. Non-Clairvoyant scheduling. Theor. Comput. Sci. 130, 17--47.
17. Phillips, C., Stein, C., Torng, E., and Wein, J. 2002. Optimal time-critical scheduling via resource augmentation. Algorithmica 32, 2, 163--200.
18. Pruhs, K. 2007. Competitive online scheduling for server systems. SIGMETRICS Perform. Eval. Rev. 34, 4, 52--58.
19. Pruhs, K., Sgall, J., and Torng, E. 2004. Online scheduling. In Handbook on Scheduling, CRC Press.
20. Robert, J. and Schabanel, N. 2007a. Non-Clairvoyant batch sets scheduling: Fairness is fair enough. In Proceedings of the European Symposium on Algorithms. 741--753.
21. Robert, J. and Schabanel, N. 2007b. Pull-based data broadcast with dependencies: be fair to users, not to items. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.
22. Robert, J. and Schabanel, N. 2008. Non-clairvoyant scheduling with precedence constraints. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 491--500.

Index Terms

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making