Phase transition in multiprocessor scheduling.
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.
Bauke
Heiko
H
Institut für Theoretische Physik, Otto-von-Guericke Universität, PF4120, 39016 Magdeburg, Germany. heiko.bauke@physik.uni-magdeburg.de
Mertens
Stephan
S
Engel
Andreas
A