Phys. Rev. Lett. 90, 158701 (2003) [4 pages]Phase Transition in Multiprocessor SchedulingReceived 5 August 2002; published 17 April 2003 An “easy-hard” phase transition is shown to characterize the multiprocessor scheduling problem in which one has to distribute the workload on a parallel computer such as to minimize the overall run time. The transition can be analyzed in detail by mapping it on a mean-field antiferromagnetic Potts model. The static phase transition, characterized by a vanishing ground state entropy, corresponds to a transition in the performance of practical scheduling algorithms. © 2003 The American Physical Society URL:
http://link.aps.org/doi/10.1103/PhysRevLett.90.158701
DOI:
10.1103/PhysRevLett.90.158701
PACS:
89.20.Ff, 02.60.Pn, 64.60.Cn, 89.70.+c
|
|
About | Terms and Conditions | Subscriptions | Search | Help
Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.