research-article

An Algorithm for the Optimization of Finite Element Integration Loops

Authors:

Fabio Luporini,

Paul H. J. KellyAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 44, Issue 1

Article No.: 3, Pages 1 - 26

https://doi.org/10.1145/3054944

Published: 27 March 2017 Publication History

Abstract

We present an algorithm for the optimization of a class of finite-element integration loop nests. This algorithm, which exploits fundamental mathematical properties of finite-element operators, is proven to achieve a locally optimal operation count. In specified circumstances the optimum achieved is global. Extensive numerical experiments demonstrate significant performance improvements over the state of the art in finite-element code generation in almost all cases. This validates the effectiveness of the algorithm presented here and illustrates its limitations.

References

[1]

Martin Sandve Alnæs. 2016. UFLACS—UFL Analyser and Compiler System. Retrieved from https://bitbucket.org/fenics-project/uflacs.

[2]

M. S. Alnæs, A. Logg, K. B. Ølgaard, M. E. Rognes, and G. N. Wells. 2014. Unified form language: A domain-specific language for weak formulations of partial differential equations. ACM Trans. Math. Softw. 40, 2, Article 9 (2014), 9:1--9:37 pages.

Digital Library

[3]

Martin Sandve Alnæs, Anders Logg, Garth Wells, Lawrence Mitchell, Marie E. Rognes, Miklós Homolya, Aslak Bergersen, David A. Ham, Johannes Ring, chrisrichardson, and Kent-Andre Mardal. 2016. ufl: The Unified Form Language.

[4]

G.-T. Bercea, A. T. T. McRae, D. A. Ham, L. Mitchell, F. Rathgeber, L. Nardi, F. Luporini, and P. H. J. Kelly. 2016. A structure-exploiting numbering algorithm for finite elements on extruded meshes, and its performance evaluation in firedrake. Geosci. Model Dev. 9, 10 (2016), 3803--3815.

[5]

Uday Bondhugula, Albert Hartono, J. Ramanujam, and P. Sadayappan. 2008. A practical automatic polyhedral parallelizer and locality optimizer. In Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’08). ACM, New York, NY, 101--113.

Digital Library

[6]

Firedrake. 2016. petsc4py: The Python interface to PETSc.

[7]

Miklós Homolya and Lawrence Mitchell. 2016. TSFC—Two-Stage Form Compiler. Retrieved from https://github.com/firedrakeproject/tsfc.

[8]

Robert C. Kirby and Anders Logg. 2006. A compiler for variational forms. ACM Trans. Math. Softw. 32, 3 (Sept. 2006), 417--444.

Digital Library

[9]

Robert C. Kirby and Anders Logg. 2007. Efficient compilation of a class of variational forms. ACM Trans. Math. Softw. 33, 3, Article 17 (Aug. 2007).

Digital Library

[10]

Samuel Larsen and Saman Amarasinghe. 2000. Exploiting superword level parallelism with multimedia instruction sets. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI’00). ACM, New York, NY, 145--156.

Digital Library

[11]

Anders Logg, Martin Sandve Alnæs, Marie E. Rognes, Garth Wells, Johannes Ring, Lawrence Mitchell, Johan Hake, Miklós Homolya, Florian Rathgeber, Fabio Luporini, Graham Markall, Aslak Bergersen, Lizao Li, David A. Ham, Kent-Andre Mardal, Jan Blechta, Gheorghe-Teodor Bercea, Tuomas Airaksinen, Nico Schlömer, Hans Petter Langtangen, Colin J Cotter, Ola Skavhaug, Thomas Hisch, mliertzer, Joachim B Haga, and Andrew T. T. McRae. 2016. ffc: The FEniCS Form Compiler.

[12]

Anders Logg, Kent-Andre Mardal, Garth N. Wells, and others. 2012. Automated Solution of Differential Equations by the Finite Element Method. Springer.

Digital Library

[13]

Fabio Luporini. 2016. Firedrake-generated code using different form compilers.

[14]

Fabio Luporini, Lawrence Mitchell, Miklós Homolya, Florian Rathgeber, David A. Ham, Michael Lange, Graham Markall, and Francis Russell. 2016. COFFEE: A Compiler for Fast Expression Evaluation.

[15]

Fabio Luporini, Ana Lucia Varbanescu, Florian Rathgeber, Gheorghe-Teodor Bercea, J. Ramanujam, David A. Ham, and Paul H. J. Kelly. 2015. Cross-loop optimization of arithmetic intensity for finite element local assembly. ACM Trans. Archit. Code Optim. 11, 4, Article 57 (Jan. 2015).

Digital Library

[16]

Lawrence Mitchell, David A. Ham, Florian Rathgeber, Miklós Homolya, Andrew T. T. McRae, Gheorghe-Teodor Bercea, Michael Lange, Colin J Cotter, Christian T. Jacobs, Fabio Luporini, Simon Wolfgang Funke, Henrik Büsing, Tuomas Kärnä, Anna Kalogirou, Hannah Rittich, Eike Hermann Mueller, Stephan Kramer, Graham Markall, Patrick E. Farrell, Geordie McBain, and Asbjørn Nilsen Riseth. 2016. firedrake: An automated finite element system.

[17]

Kristian B. Ølgaard and Garth N. Wells. 2010. Optimizations for quadrature representations of finite element tensors through automated code generation. ACM Trans. Math. Softw. 37, 1, Article 8 (Jan. 2010).

Digital Library

[18]

Florian Rathgeber, David A. Ham, Lawrence Mitchell, Michael Lange, Fabio Luporini, Andrew T. T. Mcrae, Gheorghe-Teodor Bercea, Graham R. Markall, and Paul H. J. Kelly. 2016a. Firedrake: Automating the finite element method by composing abstractions. ACM Trans. Math. Softw. 43, 3, Article 24 (Dec. 2016).

Digital Library

[19]

Florian Rathgeber, Fabio Luporini, and Lawrence Mitchell. 2016b. firedrake-bench: firedrake bench optimality paper release.

[20]

Florian Rathgeber, Lawrence Mitchell, Fabio Luporini, Graham Markall, David A. Ham, Gheorghe-Teodor Bercea, Miklós Homolya, Andrew T. T. McRae, Hector Dearman, Christian T. Jacobs, gbts, Simon Wolfgang Funke, Kaho Sato, and Francis Russell. 2016c. PyOP2: Framework for performance-portable parallel computations on unstructured meshes.

[21]

Marie E. Rognes, Anders Logg, David A. Ham, Miklós Homolya, Nico Schlömer, Jan Blechta, Andrew T. T. McRae, Aslak Bergersen, Colin J. Cotter, Johannes Ring, and Lawrence Mitchell. 2016. fiat: The Finite Element Automated Tabulator.

[22]

Francis P. Russell and Paul H. J. Kelly. 2013. Optimized code generation for finite element local assembly using symbolic manipulation. ACM Trans. Math. Softw. 39, 4 (2013), 1--29.

Digital Library

[23]

Barry Smith, Satish Balay, Matthew Knepley, Jed Brown, Lois Curfman McInnes, Hong Zhang, Peter Brune, sarich, stefanozampini, Dmitry Karpeyev, Lisandro Dalcin, tisaac, markadams, Victor Minden, VictorEijkhout, vijaysm, Karl Rupp, Fande Kong, and SurtaiHan. 2016. petsc: Portable, Extensible Toolkit for Scientific Computation.

Cited By

Kadlubiak KMeca OŘíha LBrzobohatý T(2024)An approach for dynamically adaptable SIMD vectorization of FEM kernelsComputer Physics Communications10.1016/j.cpc.2024.109319(109319)Online publication date: Jul-2024
https://doi.org/10.1016/j.cpc.2024.109319
Trotter JLangguth JCai X(2023)Targeting performance and user-friendlinessParallel Computing10.1016/j.parco.2023.103051118:COnline publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1016/j.parco.2023.103051
Macià SMartínez-Ferrer PAyguadé EBeltran V(2023)Assessing Saiph, a task-based DSL for high-performance computational fluid dynamicsFuture Generation Computer Systems10.1016/j.future.2023.04.035147(235-250)Online publication date: Oct-2023
https://doi.org/10.1016/j.future.2023.04.035
Show More Cited By

Index Terms

An Algorithm for the Optimization of Finite Element Integration Loops
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations in finite fields
  2. Mathematical software

Recommendations

Cross-Loop Optimization of Arithmetic Intensity for Finite Element Local Assembly

We study and systematically evaluate a class of composable code transformations that improve arithmetic intensity in local assembly operations, which represent a significant fraction of the execution time in finite element methods. Their performance ...
Finite Element Integration on GPUs

We present a novel finite element integration method for low-order elements on GPUs. We achieve more than 100GF for element integration on first order discretizations of both the Laplacian and Elasticity operators on an NVIDIA GTX285, which has a ...
Meshfree-enriched electromagnetic finite element formulation using nodal integration

This paper presents a meshfree-enriched finite element formulation using nodal integration for electrostatic analysis. The meshfree-enriched finite element method, originally proposed to solve the incompressible constraint in mechanical problem, is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 44, Issue 1

March 2018

308 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/3071076

Editor:
Daniel Kressner
EPF Lausanne, Switzerland

Issue’s Table of Contents

Copyright © 2017 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 March 2017

Accepted: 01 February 2017

Revised: 01 January 2017

Received: 01 April 2016

Published in TOMS Volume 44, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Engineering and Physical Sciences Research Council
Natural Environment Research Council

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
494
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)2

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kadlubiak KMeca OŘíha LBrzobohatý T(2024)An approach for dynamically adaptable SIMD vectorization of FEM kernelsComputer Physics Communications10.1016/j.cpc.2024.109319(109319)Online publication date: Jul-2024
https://doi.org/10.1016/j.cpc.2024.109319
Trotter JLangguth JCai X(2023)Targeting performance and user-friendlinessParallel Computing10.1016/j.parco.2023.103051118:COnline publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1016/j.parco.2023.103051
Macià SMartínez-Ferrer PAyguadé EBeltran V(2023)Assessing Saiph, a task-based DSL for high-performance computational fluid dynamicsFuture Generation Computer Systems10.1016/j.future.2023.04.035147(235-250)Online publication date: Oct-2023
https://doi.org/10.1016/j.future.2023.04.035
Roberts KOlender AFranceschini LKirby RGioria RCarmo B(2022)spyro: a Firedrake-based wave propagation and full-waveform-inversion finite-element solverGeoscientific Model Development10.5194/gmd-15-8639-202215:23(8639-8667)Online publication date: 30-Nov-2022
https://doi.org/10.5194/gmd-15-8639-2022
Trotter JCai XFunke S(2022)On Memory Traffic and Optimisations for Low-order Finite Element Assembly Algorithms on Multi-core CPUsACM Transactions on Mathematical Software10.1145/350392548:2(1-31)Online publication date: 26-May-2022
https://dl.acm.org/doi/10.1145/3503925
Betteridge JFarrell PHam D(2021)Code Generation for Productive, Portable, and Scalable Finite Element Simulation in FiredrakeComputing in Science & Engineering10.1109/MCSE.2021.308510223:4(8-17)Online publication date: 1-Jul-2021
https://doi.org/10.1109/MCSE.2021.3085102
Williams JWechsung FTurney BWaters SMoulton D(2021)Shape optimisation for faster washout in recirculating flowsJournal of Fluid Mechanics10.1017/jfm.2020.1119914Online publication date: 5-Mar-2021
https://doi.org/10.1017/jfm.2020.1119
Paganini AWechsung F(2021)Fireshape: a shape optimization toolbox for FiredrakeStructural and Multidisciplinary Optimization10.1007/s00158-020-02813-yOnline publication date: 11-Feb-2021
https://doi.org/10.1007/s00158-020-02813-y
Khouzami NSchütze LIncardona PKraatz LSubic TCastrillon JSbalzarini I(2021)The OpenPME Problem Solving Environment for Numerical SimulationsComputational Science – ICCS 202110.1007/978-3-030-77961-0_49(614-627)Online publication date: 16-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-77961-0_49
Sun TMitchell LKulkarni KKlöckner AHam DKelly P(2020)A study of vectorization for matrix-free finite element methodsThe International Journal of High Performance Computing Applications10.1177/1094342020945005(109434202094500)Online publication date: 31-Jul-2020
https://doi.org/10.1177/1094342020945005
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents