Balancing Priorities and Load for State Space Search On Large Parallel Machines
Authors:
Jonathan A. Booth
Parallel Programming Laboratory, Department of Computer Science, University
of Illinois at Urbana-Champaign
M.S. Thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, August 2003.
Parallel applications require load balance to achieve good performance. Many regular, iterative applications can be statically or dynamically load balanced by moving a small bit of the domain from one processor to another. Other applications, such as searches, don't operate over a regular domain. These applications must still have their work balanced to achieve good performance. This paper seeks to find load balancers that give good performance for applications such as searches on machines with thousands of processors. Balancing strategies and results are presented for three different load balancers.