Benchmarking Domain-Specific Compiler Optimizations for Variational Forms

ABSTRACT

We examine the effect of using complexity-reducing relations [Kirby et al. 2006] to generate optimized code for the evaluation of finite-element variational forms. The optimizations are implemented in a prototype code named FErari, which has been integrated as an optimizing backend to the FEniCS form compiler, FFC [Kirby and Logg 2006; 2007]. In some cases, FErari provides very little speedup, while in other cases we obtain reduced local operation counts by a factor of as much as 7.9 and speedups for the assembly of the global sparse matrix by as much as a factor of 2.8 (see Figure 9).

REFERENCES

• 1: Bangerth, W., Hartmann, R., and Kanschat, G. 2006. deal.II differential equations analysis library. http://www.dealii.org/.
• 2: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
• 3: Hoffman, J., Jansson, J., Logg, A., and Wells, G. N. 2006a. DOLFIN. http://www.fenics.org/dolfin/.
• 4: Hoffman, J., Jansson, J., Logg, A., and Wells, G. N. 2006b. DOLFIN User Manual.
• 5: Hoffman, J. and Logg, A. 2002. DOLFIN: Dynamic object oriented library for finite element computation. Tech. Rep. 2002--06, Chalmers Finite Element Center Preprint Series.
• 6: Hughes, T. J. R. 1987. The Finite Element Method: Linear Static and Dynamic Finite Element Analysis. Prentice-Hall.
• 7: Robert C. Kirby , Matthew Knepley , Anders Logg , L. Ridgway Scott, Optimizing the Evaluation of Finite Element Matrices, SIAM Journal on Scientific Computing, v.27 n.3, p.741-758, 2005 [doi>10.1137/040607824]
• 8: Kirby, R. C., Knepley, M. G., and Scott, L. R. 2004. Evaluation of the action of finite element operators. Tech. Rep. TR--2004--07, University of Chicago, Department of Computer Science.
• 9: Robert C. Kirby , Anders Logg, A compiler for variational forms, ACM Transactions on Mathematical Software (TOMS), v.32 n.3, p.417-444, September 2006 [doi>10.1145/1163641.1163644]
• 10: Robert C. Kirby , Anders Logg, Efficient compilation of a class of variational forms, ACM Transactions on Mathematical Software (TOMS), v.33 n.3, p.17-es, August 2007 [doi>10.1145/1268769.1268771]
• 11: Robert C. Kirby , Anders Logg , L. Ridgway Scott , Andy R. Terrel, Topological Optimization of the Evaluation of Finite Element Matrices, SIAM Journal on Scientific Computing, v.28 n.1, p.224-240, 2006 [doi>10.1137/050635547]
• 12: Robert C. Kirby , L. Ridgway Scott, Geometric Optimization of the Evaluation of Finite Element Matrices, SIAM Journal on Scientific Computing, v.29 n.2, p.827-841, March 2007 [doi>10.1137/060660722]
• 13: Hans Petter Langtangen , D. Keyes , R. Nieminen , M. Griebel , M. Griebel Bonn , T. Schlick , D. Roose, Computational Partial Differential Equations: Numerical Methods and Diffpack Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 14: Logg, A. 2007. FFC. http://www.fenics.org/ffc/.
• 15: Logg, A., Ølgaard, K., Rognes, M. E., Wells, G. N., Jansson, J., Kirby, R. C., Knepley, M. G., Lindbo, D., and Skavhaug, O. 2007. The FEniCS project. http://fenics.org/.
• 16: Long, K. 2003. Sundance, a rapid prototyping tool for parallel PDE-constrained optimization. In Large-Scale PDE-Constrained Optimization. Lecture notes in Computational Science and Engineering. Springer.
• 17: Long, K. 2004. Sundance 2.0 tutorial. Tech. Rep. TR--2004--09, Sandia National Laboratories.
• 18: Long, K. 2006. Sundance. http://software.sandia.gov/sundance/.
• 19: Püschel, M., Moura, J. M. F., Johnson, J., Padua, D., Veloso, M., Singer, B. W., Xiong, J., Franchetti, F., Gačić, A., Voronenko, Y., Chen, K., Johnson, R. W., and Rizzolo, N. 2005. SPIRAL: Code generation for DSP transforms. Proc. IEEE, SI Program Gener. Optim. Adapt. 93, 2, 232--275.
• 20: Zienkiewicz, O. C., Taylor, R. L., and Zhu, J. Z. 2005. The Finite Element Method --- Its Basis and Fundamentals, 6th ed. Elsevier.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Finite element methods

General Terms:
Algorithms, Performance

Keywords:
FErari, FFC, Finite element method, compiler, complexity-reducing relations, optimization, variational form