greenline
rgstripes
Otto-Bild Stephan Mertens - Publications
Home | Research | Publications | Teaching | Smorgasbord
greenline

Phase Transition in Multiprocessor Scheduling

Heiko Bauke, Stephan Mertens and Andreas Engel


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.


BiBTeX Entry

@article{bme:03,
  author = {Heiko Bauke and Stephan Mertens and Andreas Engel},
  title = {Phase Transition in Multiprocessor Scheduling},
  year = {2003},
  journal =      {Phys. Rev. Lett.},
  volume =       {90},
  number =       {15},
  pages =        {158701},
  note =  {\url{http://arxiv.org/abs/cond-mat/0208081}}
}

Download:
PRL58701.ps.gz (gzip'ed postscript, 129 k), PRL58701.pdf (pdf, 129 k)

greenline
rgstripes
top Home | Research | Publications | Teaching | Smorgasbord
greenline

© by Stephan Mertens
URL: http://
updated on Wednesday, November 05th 2003, 14:04:41 CET;