Dynamic Load Balancers for a Multithreaded Multiprocessor System

Prasad Kakulavarapu, Olivier C. Maquelin, José Nelson Amaral, and Guang Gao

Designing multi-processor systems that deliver a reasonable
price-performance ratio using off-the-shelf processor and compiler
technologies is a major challenge.  For an important class of
applications, it is critical to explore fine-grain parallelism to
achieve reasonable performance.  In such parallel systems it is
essential to efficiently manage communication latencies, bandwidth,
and synchronization overheads.  In this paper we study load balancing
strategies for the runtime system of a multi-threaded system.  EARTH
(Efficient Architecture for Running Threads) is a multi-threaded
programming and execution model that supports fine-grain,
non-preemptive, threads in a distributed memory environment.  We
describe the design and implementation of a set of dynamic load
balancing algorithms, and study their performance in
divide-and-conquer, regular, and irregular applications.  Our
experimental study on the distributed memory multi-processor IBM SP-2
indicate that a randomized load balancer perform as well as, and often
better than, history based load balancers.

Return to José Nelson Amaral's Publications

Send comments to: amaral AT cs DOT ualberta DOC ca

Return to Amaral's home page