Scalably scheduling processes with arbitrary speedup curves

ABSTRACT

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

REFERENCES

• 1: Luca Becchetti , Stefano Leonardi, Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines, Journal of the ACM (JACM), v.51 n.4, p.517-539, July 2004 [doi>10.1145/1008731.1008732]
• 2: Piotr Berman , Chris Coulston, Speed is more powerful than clairvoyance, Nordic Journal of Computing, v.6 n.2, p.181-193, Summer 1999
• 3: Jeff Edmonds, Scheduling in the dark, Theoretical Computer Science, v.235 n.1, p.109-141, March 17, 2000 [doi>10.1016/S0304-3975(99)00186-3]
• 4: Jeff Edmonds. On the competitiveness of aimd-tcp within a general network. In LATIN, pages 567--576, 2004.
• 5: Jeff Edmonds , Suprakash Datta , Patrick Dymond, TCP is competitive against a limited adversary, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777440]
• 6: Jeff Edmonds and Kirk Pruhs. Multicast pull scheduling: When fairness is fine. Algorithmica, 36(3):315--330, 2003.
• 7: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• 8: Bala Kalyanasundaram , Kirk R. Pruhs, Minimizing flow time nonclairvoyantly, Journal of the ACM (JACM), v.50 n.4, p.551-567, July 2003 [doi>10.1145/792538.792545]
• 9: Rick Merritt. Cpu designers debate multi-core future. EE Times, June 2008.
• 10: Rajeev Motwani , Steven Phillips , Eric Torng, Nonclairvoyant scheduling, Theoretical Computer Science, v.130 n.1, p.17-47, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90151-1]
• 11: Cynthia Phillips, Cliff Stein, Eric Torng, and Joel Wein. Optimal time-critical scheduling via resource augmentation. Algorithmica, pages 163--200, 2002.
• 12: Kirk Pruhs, Competitive online scheduling for server systems, ACM SIGMETRICS Performance Evaluation Review, v.34 n.4, March 2007 [doi>10.1145/1243401.1243411]
• 13: Kirk Pruhs, Jiri Sgall, and Eric Torng. Online scheduling. In Handbook on Scheduling. CRC Press, 2004.
• 14: Julien Robert and Nicolas Schabanel. Non-clairvoyant batch sets scheduling: Fairness is fair enough. In European Symposium on Algorithms, pages 741--753, 2007.
• 15: Julien Robert , Nicolas Schabanel, Pull-based data broadcast with dependencies: be fair to users, not to items, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.238-247, January 07-09, 2007, New Orleans, Louisiana
• 16: Julien Robert , Nicolas Schabanel, Non-clairvoyant scheduling with precedence constraints, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.491-500, January 20-22, 2008, San Francisco, California

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling