  The goal of load balancing (grid partitioning) is to minimize overall
computations and communications, and to make sure that all processors have a
similar workload. Geometric methods divide a grid by using a location of a cell
while topological methods work with connectivity of cells, which is generally
described as a graph. This paper introduces a Hilbert space-filling curve
method. A space-filling curve is a continuous curve and defines a map between a
one-dimensional space and a multi-dimensional space. A Hilbert space-filling
curve is one special space-filling curve discovered by Hilbert and has many
useful characteristics, such as good locality, which means that two objects
that are close to each other in a multi-dimensional space are also close to
each other in a one dimensional space. This property can model communications
in grid-based parallel applications. The idea of the Hilbert space-filling
curve method is to map a computational domain into a one-dimensional space,
partition the one-dimensional space to certain intervals, and assign all cells
in a same interval to a MPI. To implement a load balancing method, a mapping
kernel is required to convert high-dimensional coordinates to a scalar value
and an efficient one-dimensional partitioning module that divides a
one-dimensional space and makes sure that all intervals have a similar
workload.
  The Hilbert space-filling curve method is compared with ParMETIS, a famous
graph partitioning package. The results show that our Hilbert space-filling
curve method has good partition quality. It has been applied to grids with
billions of cells, and linear scalability has been obtained on IBM Blue Gene/Q.
