Load Balancing and Scheduling in a Neighbourhood-Based Multiprocessor

Abstract

The Flagship Parallel Reduction Machine is designed to execute declarative language programs based on a packet graph-reduction model of computation. The machine uses a dynamic load balancing scheme to distribute work evenly over the processors. This paper describes a neighbourhood scheme used to restrict programs with insufficient parallelism to run only on a subset (neighbourhood) of the processors. A new technique for load balancing within the neighbourhoods of processors is proposed.