Six different partitioning techniques have been included in the benchmark test. The first partitioning technique is a part of GrACE. The next four partitioning techniques are part of the parallel SAMR partitioning library Vampire, which combines structured and unstructured partitioning techniques. The last algorithm is from ParMetis, a tool for unstructured graphs. For some of the partitioning techniques, granularity may be varied. In this context, granularity is determined by the atomic unit, the smallest entity the partitioner can "see" and work with. Large atomic units always result in coarse granularity partitionings. Small atomic units, however, may or may not result in fine granularity partitionings. In theory, fine granularity enables perfect load balance, but induces lot of communication and overhead. Conversely, coarse granularity promotes good communication patterns but prohibits good load balance.

Space-Filling Curve based Partitioning (SFC):

The SFC partitioning scheme is based on a recursive linear representation of a multi-dimensional grid hierarchy generated using space-filling mappings. These mappings are computationally efficient, recursive mappings from N-dimensional space to 1-dimensional space. The solution space is first partitioned into blocks of a minimum acceptable granularity that may be dictated by the system and/or the application. The space-filling curve then passes through these blocks.

Geometric Multi-level Inverse Space-filling curve Partitioning (G-MISP) with variable grain size:

The G-MISP technique is a multi-level algorithm similar to SFC described above. It starts by creating a matrix of workloads from the SAMR grid hierarchy, and viewing this matrix as a one-vertex graph. The matrix entries correspond to grid points in the application base grid along with their refinements, and its workload is the total work required to advance the solution in the area covered by the matrix entry. The G-MISP scheme successively refines the graph by splitting vertices with total weight greater than a threshold. The minimum vertex size is bounded by the atomic unit parameter. Therefore, the resulting partitioning granularity is a function of the threshold, the atomic unit, and the current state of the grid hierarchy. The splitting of the vertices is structured. A vertex is split at the geometrical mid point, and the orientation is determined by the Hilbert space-filling curve. As a result of this splitting, a one-dimensional list of blocks having approximately the same weight is created. Load balance is now trivially achieved by assigning the same number of blocks to each processor. The G-MISP approach favors speed at the expense of load balance.

Geometric Multi-level Inverse Space-filling curve Partitioning with Sequence Partitioning (G-MISP+SP) with variable grain size:

The G-MISP+SP is a "smarter" variant of the G-MISP technique. It uses sequence partitioning to assign blocks from the one-dimensional list to processors, instead of just assigning the same number of blocks to each processor. Sequence partitioning is the problem to partition a sequence of n numbers into k intervals (k < n) by finding k-1 delimiters such that the sum of the numbers in the interval with the largest sum is minimized. As a result, the load balance improves. The scheme is however computationally more expensive.

p-way Binary Dissection Inverse Space-filling curve Partitioning (pBD-ISP):

The pBD-ISP scheme is a generalization of the binary dissection algorithm, extending this scheme in two ways. First, the domain is partitioned into "p" partitions without restrictions on p. The binary dissection is performed in such a way that each split divides the load as evenly as possible, taking the available numbers of processors into account, i.e. if there are, for example, 15 processors available, the cut is made such that 8/15 of the load is in one part and 7/15 is in the other part. Second, the orientation of the cuts is determined by the Hilbert space-filling curve, hence incorporating unstructuredness into the scheme.

"Pure" Sequence Partitioning with Inverse Space-filling curve Partitioning (SP-ISP) with variable grain size:

In this scheme, the domain is sub-divided into p * b equally sized blocks by a generalization of the parameterized binary dissection (BD) algorithm. The BD algorithm is extended in two ways. First, it is a dual-level algorithm, enabling different parameter settings for each level. In the first level, the domain is split into b blocks. In the second level, all b blocks are further divided into p blocks each. Second, the orientation of the cuts is determined by the Hilbert SFC. In the case of SAMR grid hierarchies, blocks generated will have different workloads due to adaptation of the grid. These blocks are ordered according to the SFC to form a one-dimensional list, which is then partitioned using sequence partitioning. SP-ISP is potentially a fine granularity partitioning scheme, leading to good load balance at the expense of increased communication, overhead, and a higher computational cost.

Wavefront Diffusion (WD) based on global work load:

The wavefront diffusion algorithm is based on global work load and is part of the suite of partitioning algorithms included in ParMetis. This algorithm specializes in repartitioning graphs where the refinements are scattered. This feature is lacking in the other techniques studied. ParMetis is designed for unstructured grids and requires a node graph as its input. In the case of SAMR block-structured grids, it is not feasible to work with grid graphs where each point in the computational grid corresponds to a vertex in the graph. This is because the time required to generate the graph will be prohibitive and the resulting partitioning will be extremely irregular, and jagged. As a result, grid blocks of size greater than or equal to the atomic unit are used as vertices of the node graph. The WD scheme results in fine grain partitionings with jagged partitioning boundaries and potentially increased communication costs and overheads.