Scalable global load redistribution: implementing and testing a scalable global load redistribution algorithm that requires only O(log p) computation and O(1) local storage

Typically, HPC codes distribute the workload by assigning an identically-sized section of grid space to each parallel process; this approach, although suitable for simulations where the workload is inherently uniform, such as a uniform particle distribution, will not perform well should the workload possess marked spatial variations. Hence there is a need to develop alternative schemes, whereby processes may be assigned differently-sized sections of grid space in order to balance workload, eg, number of particles. Dividing the grid according to some property requires a curve that visits every grid cell: furthermore, any two adjacent points on the curve must always refer to neighbouring grid cells. The Hilbert space-filling curve meets these requirements, it allows us to represent a multi-dimensional space as a one-dimensional function.

However, balancing the workload in this way gives rise to another problem, where to store the data mapped by the space-filling curve such that any process can access any part of it. Storing such information on a single node inevitably limits the grid space that can be modelled. The aim of this project is to implement and test a scalable global load redistribution algorithm that requires only O(log p) computation and O(1) local storage. The key parts of this algorithm are a parallel prefix operation and a distributed binary search, which are good candidates for using a single-sided message passing or some other PGAS approach (eg UPC or CAF).