Abstract
Optimizing the performance of compute-bound codes requires, among other techniques, the elimination of redundant computations. The well-known concept of common subexpression elimination can achieve this in parts, and almost every production compiler conducts such an optimization. However, due to the conservative nature of these compilers, an external redundancy elimination can additionally increase the performance. For stencil codes using finite volume discretizations, an extension to eliminate redundancies between loop iterations is also very promising. We integrated both a classic common subexpression elimination and an extended version in the Exastencils code generator and present their impact on a real-world application.
S. Kronawitter—This work is supported by the German Research Foundation (DFG), as part of Priority Programme 1648 “Software for Exascale Computing” in project ExaStencils under contracts RU 422/15 and LE 912/15.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
References
Aceto, L., Ingolfsdottir, A., Saabas, A., Uustalu, T.: Program and proof optimizations with type systems. J. Logic Algebraic Prog. 77(1–2), 131–154 (2008)
Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers - Principles, Techniques and Tools, 2nd edn. Addison-Wesley, Boston (2007)
Click, C.: Global code motion/global value numbering. In: Proceedings of ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation (PLDI), pp. 246–257. ACM, June 1995
Cocke, J.: Global common subexpression elimination. In: Proceedings of Symposium on Compiler Optimization, pp. 20–24. ACM, Jul 1970
Cocke, J., Schwartz, J.T.: Programming Languages and Their Compilers: Preliminary Notes, 2nd edn. Courant Institute of Mathematical Sciences, New York University (1970)
Debray, S.K.: Compiler optimizations for low-level redundancy elimination: An application of meta-level prolog primitives. In: Pettorossi, A. (ed.) META 1992. LNCS, vol. 649, pp. 120–134. Springer, Heidelberg (1992). doi:10.1007/3-540-56282-6_8
Faber, P., Griebl, M., Lengauer, C.: Loop-carried code placement. In: Sakellariou, R., Gurd, J., Freeman, L., Keane, J. (eds.) Euro-Par 2001. LNCS, vol. 2150, pp. 230–235. Springer, Heidelberg (2001). doi:10.1007/3-540-44681-8_34
Hackbusch, W.: Multi-Grid Methods and Applications. Springer-Verlag, Heidelberg (1985)
Hammes, J., Böhm, A.P.W., Ross, C., Chawathe, M., Draper, B.A., Rinker, B., Najjar, W.A.: Loop fusion and temporal common subexpression elimination in window-based loops. In: Proceedings of 8th IPDPS Reconfigurable Architectures Workshop (RAW), 8 p. IEEE Computer Society, April 2001
Kamal, H., Lee, J., Koo, B.: An improved non-CSD 2-bit recursive common subexpression elimination method to implement FIR filter. ETRI J. 33(5), 695–703 (2011)
Kronawitter, S., Lengauer, C.: Optimizations applied by the ExaStencils code generator. Technical Report MIP-1502, Faculty of Informatics and Mathematics, University of Passau, 10 p., January 2015
Lengauer, C., et al.: ExaStencils: advanced stencil-code engineering. In: Lopes, L., et al. (eds.) Euro-Par 2014. LNCS, vol. 8806, pp. 553–564. Springer, Heidelberg (2014). doi:10.1007/978-3-319-14313-2_47
Muchnick, S.S.: Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers Inc., San Francisco (1997)
Patankar, S.V., Spalding, D.B.: A calculation procedure for heat, mass and momentum transfer in three-dimensional parabolic flows. Int. J. Heat Mass Transfer 15(10), 1787–1806 (1972)
Schmitt, C., Kuckuk, S., Hannig, F., Köstler, H., Teich, J.: ExaSlang: A domain-specific language for highly scalable multigrid solvers. In: Proceedings of 4th International Workshop on Domain-Specific Languages and High-Level Frameworks for High Performance Computing (WOLFHPC), pp. 42–51. ACM (2014)
Trottenberg, U., Osterlee, C.W., Schüller, A.: Multigrid. Academic Press, New York (2000)
Vasco, D.A., Moraga, N.O., Haase, G.: Parallel finite volume method simulation of three-dimensional fluid flow and convective heat transfer for viscoplastic non-Newtonian fluids. Numer. Heat Transf. Part A: Appl. 66(2), 990–1019 (2014)
Versteeg, H.K., Malalasekera, W.: An Introduction to Computational Fluid Dynamics: The Finite Volume Method, 2nd edn. Pearson Education Limited, Upper Saddle River (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Kronawitter, S., Kuckuk, S., Lengauer, C. (2016). Redundancy Elimination in the ExaStencils Code Generator. In: Carretero, J., et al. Algorithms and Architectures for Parallel Processing. ICA3PP 2016. Lecture Notes in Computer Science(), vol 10049. Springer, Cham. https://doi.org/10.1007/978-3-319-49956-7_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-49956-7_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-49955-0
Online ISBN: 978-3-319-49956-7
eBook Packages: Computer ScienceComputer Science (R0)