A structure-exploiting numbering algorithm for finite elements on extruded meshes, and its performance evaluation in Firedrake
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 n...
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Copernicus Publications
2016-10-01
|
| Series: | Geoscientific Model Development |
| Online Access: | http://www.geosci-model-dev.net/9/3803/2016/gmd-9-3803-2016.pdf |
| _version_ | 1818472132285300736 |
|---|---|
| author | G.-T. Bercea A. T. T. McRae D. A. Ham L. Mitchell F. Rathgeber L. Nardi F. Luporini P. H. J. Kelly |
| author_facet | G.-T. Bercea A. T. T. McRae D. A. Ham L. Mitchell F. Rathgeber L. Nardi F. Luporini P. H. J. Kelly |
| author_sort | G.-T. Bercea |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-14T04:01:06Z |
| format | Article |
| id | doaj.art-37c6927295694e98b35a709da8ac5176 |
| institution | Directory Open Access Journal |
| issn | 1991-959X 1991-9603 |
| language | English |
| last_indexed | 2024-04-14T04:01:06Z |
| publishDate | 2016-10-01 |
| publisher | Copernicus Publications |
| record_format | Article |
| series | Geoscientific Model Development |
| spelling | doaj.art-37c6927295694e98b35a709da8ac51762022-12-22T02:13:32ZengCopernicus PublicationsGeoscientific Model Development1991-959X1991-96032016-10-019103803381510.5194/gmd-9-3803-2016A structure-exploiting numbering algorithm for finite elements on extruded meshes, and its performance evaluation in FiredrakeG.-T. Bercea0A. T. T. McRae1D. A. Ham2L. Mitchell3F. Rathgeber4L. Nardi5F. Luporini6P. H. J. Kelly7Department of Computing, Imperial College London, London, SW7 2AZ, UKThe Grantham Institute, Imperial College London, London, SW7 2AZ, UKDepartment of Mathematics, Imperial College London, London, SW7 2AZ, UKDepartment of Computing, Imperial College London, London, SW7 2AZ, UKDepartment of Computing, Imperial College London, London, SW7 2AZ, UKDepartment of Computing, Imperial College London, London, SW7 2AZ, UKDepartment of Computing, Imperial College London, London, SW7 2AZ, UKDepartment of Computing, Imperial College London, London, SW7 2AZ, UKWe 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.http://www.geosci-model-dev.net/9/3803/2016/gmd-9-3803-2016.pdf |
| spellingShingle | G.-T. Bercea A. T. T. McRae D. A. Ham L. Mitchell F. Rathgeber L. Nardi F. Luporini P. H. J. Kelly A structure-exploiting numbering algorithm for finite elements on extruded meshes, and its performance evaluation in Firedrake Geoscientific Model Development |
| title | A structure-exploiting numbering algorithm for finite elements on
extruded meshes, and its performance evaluation in Firedrake |
| title_full | A structure-exploiting numbering algorithm for finite elements on
extruded meshes, and its performance evaluation in Firedrake |
| title_fullStr | A structure-exploiting numbering algorithm for finite elements on
extruded meshes, and its performance evaluation in Firedrake |
| title_full_unstemmed | A structure-exploiting numbering algorithm for finite elements on
extruded meshes, and its performance evaluation in Firedrake |
| title_short | A structure-exploiting numbering algorithm for finite elements on
extruded meshes, and its performance evaluation in Firedrake |
| title_sort | structure exploiting numbering algorithm for finite elements on extruded meshes and its performance evaluation in firedrake |
| url | http://www.geosci-model-dev.net/9/3803/2016/gmd-9-3803-2016.pdf |
| work_keys_str_mv | AT gtbercea astructureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT attmcrae astructureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT daham astructureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT lmitchell astructureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT frathgeber astructureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT lnardi astructureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT fluporini astructureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT phjkelly astructureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT gtbercea structureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT attmcrae structureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT daham structureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT lmitchell structureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT frathgeber structureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT lnardi structureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT fluporini structureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake AT phjkelly structureexploitingnumberingalgorithmforfiniteelementsonextrudedmeshesanditsperformanceevaluationinfiredrake |