Abstract
Approximate computing comprises a large variety of techniques that trade the accuracy of an application’s output for other metrics such as computing time or energy cost. Many existing approximation techniques focus on loops such as loop perforation, which skips iterations for faster, approximated computation. This paper introduces ALONA, a novel approach for automatic loop nest approximation based on polyhedral compilation. ALONA’s compilation framework applies a sequence of loop approximation transformations, generalizes state-of-the-art perforation techniques, and introduces new multi-dimensional approximation schemes. The framework includes a reconstruction technique that significantly improves the accuracy of the approximations and a transformation space pruning method based on Barvinok’s counting that removes inaccurate approximations. Evaluated on a collection of more than twenty applications from PolyBench/C, ALONA discovers new approximations that are better than state-of-the-art techniques in both approximation accuracy and performance.
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
References
Bao, W., Krishnamoorthy, S., Pouchet, L.N., Sadayappan, P.: Analytical Modeling of Cache Behavior for Affine Programs. Lang, ACM Program (2017)
Barvinok, A.I.: A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Mathematics of Operations Research (1994)
Baskaran, M.M., Ramanujam, J., Sadayappan, P.: Automatic C-to-CUDA code generation for affine programs. In: Proceedings of CC (2010)
Benabderrahmane, M., Pouchet, L., Cohen, A., Bastoul, C.: The polyhedral model is more widely applicable than you think. In: Proceedings of CC (2010)
Bondhugula, U., Acharya, A., Cohen, A.: The pluto+ algorithm: a practical approach for parallelization and locality optimization of affine loop nests. ACM TOPLAS (2016)
Bondhugula, U., Baskaran, M.M., Krishnamoorthy, S., Ramanujam, J., Rountev, A., Sadayappan, P.: Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model. In: Proceedings of CC (2008)
Campanoni, S., Holloway, G.H., Wei, G., Brooks, D.M.: HELIX-UP: relaxing program semantics to unleash parallelization. In: Proceedings of CGO (2015)
Cherubin, S., Cattaneo, D., Chiari, M., Agosta, G.: Dynamic Precision Autotuning with TAFFO. TACO (2020)
Cosenza, B., Durillo, J.J., Ermon, S., Juurlink, B.: Autotuning stencil computations with structural ordinal regression learning. In: Proceedings of IPDPS (2017)
Deiana, E.A., St-Amour, V., Dinda, P.A., Hardavellas, N., Campanoni, S.: Unconventional Parallelization of Nondeterministic Applications. SIGPLAN Not. (2018)
Esmaeilzadeh, H., Sampson, A., Ceze, L., Burger, D.: Architecture support for disciplined approximate programming. In: Proceedings of ASPLOS (2017)
Fernando, V., Franques, A., Abadal, S., Misailovic, S., Torrellas, J.: Replica: a wireless manycore for communication-intensive and approximate data. In: Proceedings of ASPLOS (2019)
Ganser, S., Größlinger, A., Siegmund, N., Apel, S., Lengauer, C.: Speeding up iterative polyhedral schedule optimization with surrogate performance models. TACO (2018)
Grosser, T., Größlinger, A., Lengauer, C.: Polly - Performing Polyhedral Optimizations on a Low-Level Intermediate Representation. Parallel Proc, Letters (2012)
Gysi, T., Grosser, T., Brandner, L., Hoefler, T.: A fast analytical model of fully associative caches. In: Proceedings of PLDI (2019)
Imani, M., Garcia, R., Huang, A., Rosing, T.: CADE: configurable approximate divider for energy efficiency. In: Proceedings of DATE (2019)
Jimborean, A., Clauss, P., Pradelle, B., Mastrangelo, L., Loechner, V.: Adapting the polyhedral model as a framework for efficient speculative parallelization. In: Proceedings of PPoPP (2012)
Khatamifard, S.K., Akturk, I., Karpuzcu, U.R.: On approximate speculative lock elision. IEEE Trans. Multi-Scale Comput. Syst. 4(2) (2018)
Lashgar, A., Atoofian, E., Baniasadi, A.: Loop perforation in OpenACC. In: Proceedings of ISPA (2018)
Li, S., Park, S., Mahlke, S.: Sculptor: Flexible approximation with selective dynamic loop perforation. In: Proceedings of ICS (2018)
Maier, D., Cosenza, B., Juurlink, B.: Local memory-aware kernel perforation. In: Proceedings of CGO (2018)
Mitra, S., Gupta, M.K., Misailovic, S., Bagchi, S.: Phase-aware optimization in approximate computing. In: Proceedings of CGO (2017)
Mittal, S.: A Survey of Techniques for Approximate Computing. ACM Comput. Surv. (2016)
Pouchet, L.N.: Polybench/c 3.2. http://www.cse.ohio-state.edu/~pouchet/software/polybench/
Pouchet, L.N., Bastoul, C., Cohen, A., Cavazos, J.: Iterative Optimization in the Polyhedral Model: Part II. Multidimensional Time, SIGPLAN Not (2008)
Pouchet, L.N., Bastoul, C., Cohen, A., Vasilache, N.: Iterative optimization in the polyhedral model: Part i, one-dimensional time. In: Proceedings of CGO (2007)
Pouchet, L., Bondhugula, U., Bastoul, C., Cohen, A., Ramanujam, J., Sadayappan, P., Vasilache, N.: Loop transformations: convexity, pruning and optimization. In: Proceedings of POPL (2011)
Pouchet, L.N., Bondhugula, U., Bastoul, C., Cohen, A., Ramanujam, R., Sadayappan, P.: Hybrid iterative and model-driven optimization in the polyhedral model (2009)
Rinard, M.: Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. In: Proceedings of ICS (2006)
Samadi, M., Jamshidi, D.A., Lee, J., Mahlke, S.: Paraprox: pattern-based approximation for data parallel applications. In: Proceedings of ASPLOS (2014)
Sampson, A., Dietl, W., Fortuna, E., Gnanapragasam, D., Ceze, L., Grossman, D.: Enerj: approximate data types for safe and general low-power computation. In: Proceedings of PLDI (2011)
Schmitt, M., Helluy, P., Bastoul, C.: Automatic adaptive approximation for stencil computations. In: Proceedings of CC (2019)
Sidiroglou-Douskos, S., Misailovic, S., Hoffmann, H., Rinard, M.: Managing performance vs. accuracy trade-offs with loop perforation. In: Proceedings of ESEC (2011)
Udupa, A., Rajan, K., Thies, W.: ALTER: exploiting breakable dependences for parallelization. In: Proceedings of PLDI (2011)
Venkatagiri, R., Mahmoud, A., Hari, S.K.S., Adve, S.V.: Approxilyzer: Towards a systematic framework for instruction-level approximate computing and its application to hardware resiliency. In: Proceedings of MICRO (2016)
Verdoolaege, S., Carlos Juega, J., Cohen, A., Ignacio Gómez, J., Tenllado, C., Catthoor, F.: Polyhedral parallel code generation for CUDA. ACM TACO (2013)
Acknowledgement
This research has been partially funded by MIUR PON Ricerca e Innovazione 2014–2020 (grant number AIM1872991-1).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Maier, D., Cosenza, B., Juurlink, B. (2021). ALONA: Automatic Loop Nest Approximation with Reconstruction and Space Pruning. In: Sousa, L., Roma, N., Tomás, P. (eds) Euro-Par 2021: Parallel Processing. Euro-Par 2021. Lecture Notes in Computer Science(), vol 12820. Springer, Cham. https://doi.org/10.1007/978-3-030-85665-6_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-85665-6_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-85664-9
Online ISBN: 978-3-030-85665-6
eBook Packages: Computer ScienceComputer Science (R0)