Phase Transition in Multiprocessor Scheduling

Details Phase Transition in Multiprocessor Scheduling Phase Transition in Multiprocessor Scheduling

2002-08-05

arxiv.org/abs/cond-mat/0208081v2

Physics

Condensed Matter

Disordered Systems and Neural Networks

6 pages, revtex4

Scientific paper

10.1103/PhysRevLett.90.158701

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.

Affiliated with

Also associated with

No associations

Rating

Phase Transition in Multiprocessor Scheduling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Phase Transition in Multiprocessor Scheduling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Phase Transition in Multiprocessor Scheduling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-250877