Source-linked AI summary
Optimisations for quadrature representations of finite element tensors through automated code generation
Kristian B. Ølgaard, Garth N. Wells
TL;DR
Complicated variational forms challenge tensor-contraction code generation, while automated form compilation offers a route to building finite-element solvers. The paper develops quadrature-code optimisations and compares both representations; their relative performance varies substantially by form. It concludes that using both representations lets a solver choose the more appropriate one for each form.
Problem
Tensor contraction does not scale well for moderately complicated and complicated forms, despite the need to automate their development and optimisation.
Source: §1 · pp. 2–3Method
The authors implement automated optimisations for quadrature representations in FFC and compare them with tensor contraction across variational forms.
Source: §1 · p. 3, §5 · pp. 20–21Results
Relative performance varies substantially by form: tensor contraction is close to 60 times faster for mixed Poisson, while quadrature is close to 6 times faster for the pressure equation.
Source: §4.1 · p. 14, §5 · p. 21Takeaways & Limitations
Using both representations in a solver allows the most appropriate representation to be chosen for each form.
Source: §5 · p. 21For the most complicated cases, tensor-contraction code generation can exhaust memory after many hours, whereas quadrature code was generated for all cases.
Source: §4.3 · p. 18
Abstract
from arXiv · showhide
We examine aspects of the computation of finite element matrices and vectors which are made possible by automated code generation. Given a variational form in a syntax which resembles standard mathematical notation, the low-level computer code for building finite element tensors, typically matrices, vectors and scalars, can be generated automatically via a form compiler. In particular, the generation of code for computing finite element matrices using a quadrature approach is addressed. For quadrature representations, a number of optimisation strategies which are made possible by automated code generation are presented. The relative performance of two different automatically generated representations of finite element matrices is examined, with a particular emphasis on complicated variational forms. It is shown that approaches which perform best for simple forms are not tractable for more complicated problems in terms of run time performance, the time required to generate the code or the size of the generated code. The approach and optimisations elaborated here are effective for a range of variational forms.
1. INTRODUCTION
Automated form compilation can pair rapid solver development with high performance, but representation choice becomes difficult for complicated variational forms. This work targets those forms with optimisations for quadrature-generated code and compares quadrature with tensor contraction.
1. INTRODUCTION
- A form compiler translates high-level variational forms into low-level element-tensor code, reconciling rapid development with high performance.Generated code serves as input to a finite element assembler.Source: §1 · pp. 1–2
- Tensor contraction decomposes element tensors into a form-and-basis tensor that can be computed before runtime and a geometry-dependent tensor, and can outperform quadrature for some problem classes [Kirby and Logg 2006; Ølgaard et al. 2008].The approach is less readily extended to non-affine isoparametric mappings and is ineffective for some nonlinear problems requiring functions outside a finite element space.Source: §1 · p. 2
- The tensor contraction approach can become impractical for complicated forms through excessive generation time, code size or runtime, and may fail from memory or library limits.Complicated forms commonly arise when nonlinear equations are linearised and involve numerous function products.Source: §1 · pp. 2–3
- The paper develops automated optimisations for quadrature representations, targeting complicated forms where tensor contraction performs poorly.The optimisations are intended to be difficult to implement by hand.Source: §1 · p. 3
- The comparison considers generated-code runtime, code size and code-generation speed, whose relative importance can shift during solver development.The paper reports a typical correlation among these three considerations.Source: §1 · p. 3
2. FINITE ELEMENT TENSORS AND AUTOMATED COMPUTER CODE GENERATION
The section introduces FFC's generation of finite-element tensor code from variational forms, then describes quadrature and tensor-contraction representations. It explains their computational structure and key assumptions.
2.1 Overview
- FFC turns variational-form input into element-tensor code and degree-of-freedom mappings for an assembler, with support for differential operators and cell or interior-facet integrals.The paper's example input describes a weighted Laplacian using continuous piecewise cubic functions on tetrahedra.Source: §2.1 · pp. 3–5
2.2 Quadrature representation
- The quadrature representation numerically integrates local element tensors at runtime, assuming a shared local basis and an affine map from the reference element to each cell.Coefficient functions are assumed to be interpolated in a finite element space; direct quadrature functions may produce matrices and vectors different from tensor contraction.Source: §2.2 · p. 5
2.3 Tensor contraction representation
- Tensor contraction separates a reference integral independent of cell geometry from geometry-dependent terms, enabling the reference tensor to be precomputed and the contraction to be unrolled.Unrolling permits zero-valued reference-tensor entries to be omitted, while increasing numbers of functions and derivatives increase tensor rank and contraction complexity.Source: §2.3 · p. 6
3. A PRIORI OPTIMISATIONS FOR QUADRATURE REPRESENTATION
The section presents three low-cost, a priori optimizations for quadrature-generated element tensors. Loop optimization yields several orders of magnitude of runtime improvement over quadrature code without optimized loops for complicated forms.
3. A PRIORI OPTIMISATIONS FOR QUADRATURE REPRESENTATION
- The authors report that simple optimizations offer greater rewards than sophisticated strategies that may consume prohibitive time and memory on complex forms.Element-tensor evaluation can become negligible relative to tasks such as inserting entries into a sparse matrix.Source: §3 · pp. 6–7
- The three implemented a priori optimizations aim to reduce floating-point operations without adversely affecting code-generation time.They are basis-function tabulation, elimination of operations on terms that are zero at every integration point, and loop-invariant code motion.Source: §3 · p. 7
- Tabulating basis functions and their derivatives at integration points avoids repeatedly evaluating them in the generated code.The compiler also generates functions for evaluating basis functions and derivatives at arbitrary runtime points.Source: §3 · p. 7
- Eliminating terms that are zero at all quadrature points reduces loop dimensions, but index mapping can impair contiguous memory access.Unlike unrolled tensor-contraction code, quadrature code can eliminate only contributions that are zero at every quadrature point; unrolled code can be longer and slower to compile.Source: §3 · p. 7
- Loop-invariant code motion moves expressions independent of summation indices outside those loops, reducing repeated work in quadrature evaluation.For the weighted Laplacian example, this permits each local tensor entry to be computed in three operations for each combination of two indices.Source: §3 · pp. 7, 9
- For complicated forms, optimized quadrature loops improved runtime by several orders of magnitude over automatically generated code without loop optimization.Earlier approaches using only basis-function tabulation performed poorly; runtime zero tests improved performance but increased C++ compilation time, while a priori zero elimination improved runtime and compilation time.Source: §3 · p. 9
4. PERFORMANCE COMPARISONS
The comparisons show that no single representation dominates: tensor contraction performs well for simple forms, while quadrature remains tractable as forms become more complex. Runtime, code size, and code-generation feasibility all inform the comparison.
4.1 Performance for a selection of forms
- For the mixed Poisson form, tensor contraction is nearly 60 times faster, whereas quadrature is nearly 6 times faster for the pressure equation.The contrasting runtimes make choosing a representation non-trivial for arbitrary forms.Source: §4.1 · p. 14
4.2 Performance for common, simple forms
- For the 3D mass matrix at q = 4, tensor contraction computes the element matrix 358 times faster, but its overall speed-up falls to 2.76 when insertion is included.The authors note that accounting for other finite-element steps would bring the runtime ratio closer to unity.Source: §4.2 · p. 15, Table III · p. 15
- For elasticity-like matrices, tensor contraction's advantage over quadrature is less dramatic than for mass matrices, but remains substantial for higher-order functions in 3D.The comparisons cover two- and three-dimensional cases and multiple polynomial orders.Source: §4.2 · p. 15, Table V · p. 16, Table VI · p. 16
4.3 Performance for forms of increasing complexity
- With more premultiplying functions and higher polynomial orders, tensor contraction's operation-count advantage drops sharply; in 3D, its generated code can become infeasible to compile.Tensor contraction is generally more efficient with few premultiplying functions; quadrature code generation succeeded for all tested cases.Source: §4.3 · pp. 17–18, Table VII · p. 17, Table VIII · p. 18
- For 3D elasticity-like forms, tensor contraction generation fails for some complex cases, while quadrature succeeds; file size can also rule out tensor contraction even when its operation ratio predicts an advantage.The authors say these results make broad claims about the best representation difficult.Source: §4.3 · p. 18, Table X · p. 19
- For a vector-valued Poisson form premultiplied by derivatives, tensor contraction uses fewer operations in only a very limited number of the considered cases.The comparison increases complexity by adding derivatives of vector-valued functions.Source: §4.3 · pp. 19–20, Table XI · p. 20
5. CONCLUSIONS
Automated quadrature optimizations can substantially speed generated code with negligible code-generation overhead. The better tensor representation depends on the form, with quadrature generally faster for more complicated forms.
5. CONCLUSIONS
- Automated quadrature optimizations add negligible code-generation overhead but can substantially speed runtime over non-optimized code.The techniques automate simple strategies that are tedious to implement by hand, making them applicable generically across a range of problems.Source: §5 · pp. 20–21
- For the investigated problems, optimized generated code often makes inserting entries into the sparse global matrix the assembly bottleneck.This qualifies runtime gains from optimizing element-tensor computation.Source: §5 · p. 21
- For complicated forms, quadrature is generally significantly faster and generates code faster and smaller than tensor contraction.Operation counts vary by form: tensor contraction used about 300 times fewer operations for some forms, while quadrature required about 100 times fewer for others; some quadrature code files were nearly 10 times smaller.Source: §5 · p. 21
- The relative performance of tensor contraction and quadrature varies with the form: tensor contraction suits high-order bases with few coefficients, while quadrature suits more coefficients and derivatives.For complicated forms, quadrature is generally significantly faster.Source: §5 · p. 21
- Choosing the best representation automatically remains non-trivial; operation-count selection requires generating code for each case, and selection by inspecting the form is ongoing work.A sophisticated solver may assemble forms of differing complexity, so both representations can be useful.Source: §5 · p. 21