Optimised Grid-Partitioning for Block Structured Grids in Parallel Computing
Daniel Junglas · Technischen Universität Darmstadt · 2008
Simulation of turbulent flows in complex geometries is nowadays usually performed by application of grid-based algorithms on parallel computers. In this approach it is not only important to have a clever discretisation and an appropriate grid. One must also use (or develop) algorithms that are convergent and numerically stable. As a final ingredient to success the different work packages of the simulation must be distributed over the set of available processors. This distribution must be performed so as to optimally exploit the computational resources provided by processors, thereby minimising simulation time. Our work will focus on this last optimisation problem and develop models as well solution algorithms for it. To this end we assume that a block structured as well as a suitable simulation algorithm are fixed and look for an optimal mapping of blocks to processors. We restrict ourselves to block structured grids for two reasons: one the one hand, this class of grids is most widely used in simulation of turbulent flows in complex geometries. On the other hand block structured grids can be partitioned into a relatively small number of blocks and the mapping problem can be restricted to the set of blocks. This last aspect allows application of integer programming methods to find optimal mappings. As opposed to standard approaches in the literature, we not only aim at balancing computational load over the processors, but also consider communication overhead induced by data dependencies between blocks mapped to different processors. The communication model we apply is an exact representation of the restrictions our hardware imposes on inter-processor communication. Seeking to minimise simulation time leads to a highly complex combinatorial optimisation problem the solution of which is the aim of our work. To this end we formulate the problem as integer program. Since it is a new problem that has – to the best of our knowledge – not been investigated in the literature we do not stick with a single optimisation model. Instead, we propose different formulations and consider tradeoffs between them. Finally, we investigate the polyhedra defined by the various integer programs in order to implement the valid and facet-defining inequalities found in Branch-and-Cut algorithms. As we cannot expect to solve large problem instances by integer programming methods in an acceptable amount of time, we also develop several local-search heuristics that produce good solutions in a reasonable amount of time. Computational results show that our models and solution algorithms – both of which are dedicated to a certain hardware model – are highly superior to generic approaches described in the literature. We were thus able to improve the usage of CPU resources during simulation of turbulent flows in complex geometries. Let us finally remark that our approach is not limited to this concrete application of finite-element or finite-volume procedures. Instead it can be applied in any situations where small or block structured grids arise and the hardware model is at least similar to the one assumed in our work.