Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Computational Science, Engineering & Technology Series
ISSN 1759-3158
Edited by: B.H.V. Topping, J.M. Adam, F.J. Pallarés, R. Bru and M.L. Romero
Chapter 3

Definition of a Generic Mesh Data Structure in the High Performance Computing Context

F. Ledoux1, J.-C. Weill1 and Y. Bertrand2

1Commissionership to Atomic Energy, Arpajon, France
2Department of Signal, Image and Communication, University of Poitiers, France

Full Bibliographic Reference for this chapter
F. Ledoux, J.-C. Weill, Y. Bertrand, "Definition of a Generic Mesh Data Structure in the High Performance Computing Context", in B.H.V. Topping, J.M. Adam, F.J. Pallarés, R. Bru and M.L. Romero, (Editors), "Developments and Applications in Engineering Computational Technology", Saxe-Coburg Publications, Stirlingshire, UK, Chapter 3, pp 49-80, 2010. doi:10.4203/csets.26.3
Keywords: mesh representation, data structure, generic programming, C++, memory optimisation, distributed memory context.

One of the main building blocks of computational simulations is the mesh data structure. Depending on the numerical approximation methods or the meshing algorithm to implement, the mesh data structure can have to provide drastically different features. Some algorithms require a full tetrahedral mesh where nodes and tetrahedra are stored while others require a full hexahedral mesh with the knowledge of faces and specific topological connections. As each application requires different features, a usual issue is to develop a mesh data structure tailored for each application. We claim that this approach is not the right one in an industrial context. First, from a software engineering point of view, it is better to reuse existing solutions and thus to consider at least the object-oriented paradigm. Second, the development of a mesh data structure is a difficult and time-consuming task, especially in the high performance computing context (HPC) context, i.e. massive parallel distributed-memory architectures.

For these reasons, the need for general meshing infrastructures has been recognised and several development efforts have been undertaken in the last few years. But none of these different solutions fits our requirements: we want a generic framework allowing the developer to select the type of cells and the incidence and adjacency relationships that must be stored in the mesh; the mesh data structure must efficiently support mesh modification in sequential and in parallel and it must not consume too much memory. This last point is particularly crucial in the HPC context. Indeed, HPC architectures tend to use more and more processors and to have a global distributed memory space that expands, but the memory space per processor tends to decrease. Thus, we have developed a mesh data framework which is a C++ library called GMDS, for generic mesh data structure. Generic is used here with two meanings: first, this data structure can handle any combination of available cells and connections; second, it is based on the generic programming paradigm. Currently, GMDS provides two mesh representations. The first one is a traditional cell-based model that is optimised in memory consumption while the second one is based on the combinatorial map model, which is greedier in memory consumption.

In this chapter, we review different existing mesh representations and libraries and we describe the main specificity of the GMDS framework. Especially, we show how generic programming and the usage of local ids, instead of pointers, help us to minimise the memory consumption. We also show the parallelism model used in GMDS. This model is based on a traditional master-slave model that minimises the duplication of data on each processor. Moreover, we give some details about the cell migration process, which is implemented in GMDS.

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

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