Non-Clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics |
| |
| Authors: | Jeff Edmonds Donald D. Chinn Tim Brecht Xiaotie Deng |
| |
| Affiliation: | (1) York University, Toronto, Canada;(2) University of Washington, Seatle, USA;(3) University of Waterloo, Waterloo, Canada;(4) City University of Hong Kong, Kowloon, Hong Kong SAR, People's Republic of China |
| |
| Abstract: | This work theoretically proves that Equi-partition efficiently schedules multiprocessor batch jobs with different execution characteristics. Motwani, Phillips, and Torng (Proc. 4th Annu. ACM/SIAM Symp. on Discrete Algorithms, pp. 422–431, Austin, 1993) show that the mean response time of jobs is within two of optimal for fully parallelizable jobs. We extend this result by considering jobs with multiple phases of arbitrary nondecreasing and sublinear speedup functions. Having no knowledge of the jobs being scheduled (non-clairvoyant) one would not expect it to perform well. However, our main result shows that the mean response time obtained with Equi-partition is no more than  times the optimal. The paper also considers schedulers with different numbers of preemptions and jobs with more general classes of speedup functions. Matching lower bounds are also proved. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
