Data decomposition

The numerical domain decomposition is described as a Gambit (Fluent) unstructured hexahedral cell mesh, however, the geometrical arrangement in question may allow for a regular data decomposition for parallelisation. Unstructured codes such as CABARET have a potentially high degree of instruction parallelism, but their data accesses requires a large amount of indirection, which increases memory operations for the indexing information and usually results in poor spatial locality and higher latencies for data access. This is not to say that the underlying algorithms will not scale as efficiently to as many cores as a structured grid based scheme would.

Unstructured grids require a list of the connectivity which specifies the way that a given set of apexes form the individual cells (indirect referencing). This is not required in a structured approach since we can usually deal with the local to global references via offsets. The performance of the parallel CABARET code will rely heavily upon an efficient data partitioning. Both in terms of performing the actual decomposition itself and also giving a well load balanced and communication optimized simulation.

Algorithms for finding efficient partitions of unstructured grids must ensure that the number of cells assigned to each processor is roughly the same, and also that the number of adjacent cells assigned to different processors is minimised. The goal of the first condition is to achieve efficient load balancing for the computations among the processors. The second condition ensures that the communication pattern resulting from the placement of adjacent cells to different processors can be optimised.

Phil Ridley 2011-02-01