Keywords: parallel flow simulation, partitioning, optimisation, complex geometries, mixed integer program, block structured grids, efficient algorithms.

The simulation of turbulent flow in complex configurations is one of the big challenges in technical applications of numerical methods. Direct Numerical Simulation (DNS) and Large Eddy Simulation (LES) are the most accurate methods known for computing turbulent flow fields. Due to the three-dimensionality and time dependency of turbulence, both methods require extensive computational time and memory. The spatial discretisation effort for a DNS increases exponentially with the Reynolds number. Modelling the sub-grid scales lowers the discretisation effort of LES, but the lack of any satisfactory wall model demands an extremely fine discretisation near the wall.

Thus, the accurate solving of complex technically relevant flows is restricted by the capacities of the computers. Therefore, the only way to get quantitatively accurate results in an acceptable time is through the usage of efficient numerical solution procedures combined with parallel computing [1].

The usage of block-structured grids is an acceptable compromise for calculating flow in complex geometries by using efficient algorithms. Such a block structured grid can be made up of more than hundreds of blocks, each containing different numbers of control volumes.

In general, the data structures of flow solvers are based on spatial discretisation. To parallelise the code, this geometric block structure (GBS) has to be distributed onto the required processors. The resulting parallel block structure (PBS) has to be created such that there is an equal load on each processor - the processor with the greatest load determines the computation time - and minimal communication between the processors. Data exchange between neighbouring blocks is essential. Putting neighbouring blocks on one processor or on the next in the communication hierarchy will reduce communication time.

The task to optimise load balancing efficiency with respect to communications leads to a very difficult, in terms of complexity theory, NP-hard problem. For a small number of blocks, it is possible to solve this problem manually. However, if the number of blocks increases, i.e., in complex three-dimensional configurations, it is impractical, if not impossible.

In this paper we present an algorithm for accomplishing this task automatically. We first decompose the blocks appropriately and develop a mixed integer program for the problem of assigning the decomposed blocks to the processors. We solve this problem with a branch-and-cut algorithm for general mixed integer programs [3] and merge the solution into the final block structure.

An exemplary application of LES for a technically relevant configuration will be considered to illustrate the functionality of our approach and to discuss its efficiency. Here to compute the flow field we use a parallelised finite-volume code for three-dimensional problems, which works with a SIP-solver in a full multi-grid environment [2] and the Crank-Nicolson time discretisation scheme.

1

S. Turek, "Perspektiven für Computational Fluid Dynamics", FEM-, CFD-, und MKS Simulation, 2/2003.

2

F. Durst, M. Peric, M. Schäfer, E. Schreck, "Parallelization of Efficient Numerical Methods for Flows in Complex Geometries", Notes in Numerical Fluid Mechanics, Vol. 38, S.79-92, Vieweg, 1993.

3

A. Martin, "General Mixed Integer Programming: Computational Issues for Branch-and-Cut Algorithms", in Computational Combinatorial Optimization, D. Naddef and M.  Juenger, eds., Springer, Berlin, 1, 2001.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)