Comparison of the Efficiency of Partitioners

Due to the unstructured grid used within the main CABARET algorithm, the choice of whether to use an external partitioning package or a structured decomposition depends upon the geometry in question. Wherever possible it is recommended to use a structured approach based on partitioning along the cartesian planes. If however, the geometrical arrangement is more complex where it is not possible to obtain a reasonable (structured) partition which gives a well load balanced problem and optimum communication arrangement, then an unstructured partitioning algorithm is required such as METIS [7], [9] or Scotch [8], [10]. The parallel CABARET code has been designed so that it is capable of running with either a structured or unstructured data decomposition.

The METIS partitioner uses a multi-level k-way approach [12] whereas the Scotch package employs a dual recursive bipartitioning approach [11]. In terms of performance, for the time taken to partition a 10⁵ cell backward facing step geometry, both METIS and Scotch give similar results, when producing 32, 50, 100 and 250 partitions. For this test case Scotch does give slightly better performance - a 5% reduction in CABARET run time. But METIS is slightly easier to use since it does allow the user to provide it with input which is close to that of the original unstructured grid whereas Scotch requires the input to be in the form of a dual graph. Figure  illustrates how a 3D backward facing step geometry is partitioned with an unstructured partitioner.

Figure: Simple unstructured decomposition with four partitions.