Load balancing and multiprogramming in the Flagship Parallel Reduction Machine

Investigations into load balancing and multiprogramming for a multiprocessor supporting declarative programming are reported. The Flagship Parallel Reduction Machine uses a packet-based graph reduction model of computation to exploit the parallelism in functional languages. The abstract architecture comprises a set of closely coupled processor-store pairs connected by a multistage delta communication network. In such a system, where program parallelism is not easily predictable at compile time, dynamic scheduling of work is necessary; the load-balancing scheme must therefore provide a dynamic mapping of program parallelism over the processor configuration. Investigations to enhance the load-balancing scheme and to determine multiprogramming efficiency in the Flagship Machine are described