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.

Figure 1

Lattice of target vectors for $q=3$ with the three Potts vectors (gray) and the two primitive vectors ${\overrightarrow{b}}_{\alpha }$ (black). The white (gray, black) lattice points correspond to $\sum _{}^{}{a}_j\mathrm{m}\mathrm{o}\mathrm{d}3=0(1,2)$.

Figure 2

Numerical measurements of $\Omega$ for $q=3$. Symbols are averages over ${10}^3$ random instances with $\sum _j{a}_j\mathrm{m}\mathrm{o}\mathrm{d}q=0$; lines are given by Eq. (18). The error bars of the enumeration data are smaller than the symbols.

Figure 3

${\kappa }_c$ from linear regression of the numerical data for $\Omega$ (symbols) compared to Eq. (19) (curves).

Figure 4

Number of nodes traversed by the complete greedy algorithm for $q=3$ and fixed number of bits $B$. The circles mark the critical system size $N_c$ given by Eq. (21).