Phase Transition in Multiprocessor Scheduling

Abstract

The problem of distributing the workload on a parallel computer to minimize the overall runtime is known as Multiprocessor Scheduling Problem. It is NP-hard, but like many other NP-hard problems, the average hardness of random instances displays an ``easy-hard'' phase transition. The transition in Multiprocessor Scheduling can be analyzed using elementary notions from crystallography (Bravais lattices) and statistical mechanics (Potts vectors). The analysis reveals the control parameter of the transition and its critical value including finite size corrections. The transition is identified in the performance of practical scheduling algorithms.

6 pages, revtex4

Cited by in corpus (6)

• Physics of the Riemann Hypothesis
• Number partitioning as random energy model
• Analysis of the Karmarkar-Karp Differencing Algorithm
• The stability to instability transition in the structure of large scale networks
• Green Scheduling with Time-of-Use Tariffs and Machine States: Optimizing Energy Cost via Branch-and-Bound and Bin Packing Strategies
• Computational Phase Transitions: Benchmarking Ising Machines and Quantum Optimisers