Articles | Volume 9, issue 10
Geosci. Model Dev., 9, 3803–3815, 2016

Special issue: The Firedrake automatic code generation system

Geosci. Model Dev., 9, 3803–3815, 2016

Development and technical paper 27 Oct 2016

Development and technical paper | 27 Oct 2016

A structure-exploiting numbering algorithm for finite elements on extruded meshes, and its performance evaluation in Firedrake

Gheorghe-Teodor Bercea1, Andrew T. T. McRae2,3,4, David A. Ham3, Lawrence Mitchell1,3, Florian Rathgeber1,5, Luigi Nardi1, Fabio Luporini1, and Paul H. J. Kelly1 Gheorghe-Teodor Bercea et al.
  • 1Department of Computing, Imperial College London, London, SW7 2AZ, UK
  • 2The Grantham Institute, Imperial College London, London, SW7 2AZ, UK
  • 3Department of Mathematics, Imperial College London, London, SW7 2AZ, UK
  • 4Department of Mathematical Sciences, University of Bath, Bath, BA2 7AY, UK
  • 5European Centre for Medium-Range Weather Forecasts (ECMWF), Reading, RG2 9AX, UK

Abstract. We present a generic algorithm for numbering and then efficiently iterating over the data values attached to an extruded mesh. An extruded mesh is formed by replicating an existing mesh, assumed to be unstructured, to form layers of prismatic cells. Applications of extruded meshes include, but are not limited to, the representation of three-dimensional high aspect ratio domains employed by geophysical finite element simulations. These meshes are structured in the extruded direction. The algorithm presented here exploits this structure to avoid the performance penalty traditionally associated with unstructured meshes. We evaluate the implementation of this algorithm in the Firedrake finite element system on a range of low compute intensity operations which constitute worst cases for data layout performance exploration. The experiments show that having structure along the extruded direction enables the cost of the indirect data accesses to be amortized after 10–20 layers as long as the underlying mesh is well ordered. We characterize the resulting spatial and temporal reuse in a representative set of both continuous-Galerkin and discontinuous-Galerkin discretizations. On meshes with realistic numbers of layers the performance achieved is between 70 and 90 % of a theoretical hardware-specific limit.

Short summary
Unstructured meshes offer flexibility but are perceived as slow. Some applications, including atmosphere or ocean simulations, admit an extruded mesh: the horizontal mesh may be unstructured, but the vertical dimension can be traversed in a structured way. By extending the Firedrake automated simulation framework to this case, we show that an extruded mesh can be traversed as fast as a structured mesh. This paves the way for highly efficient unstructured mesh models of the ocean and atmosphere.