Intercepting Functions for Memoization: A Case Study Using Transcendental Functions

Arjun Suresh 1 Bharath Narasimha Swamy 1 Erven Rohou 1 André Seznec 1
1 ALF - Amdahl's Law is Forever
Inria Rennes – Bretagne Atlantique , IRISA-D3 - ARCHITECTURE
Abstract : Memoization is the technique of saving result of executions so that future executions can be omitted when the input set repeats. Memoization has been proposed in previous literature at the instruction level, basic block level and function level using hardware as well as pure software level approaches including changes to programming language. In this paper, we focus on software memoization for procedural languages like C and Fortran, at the granularity of a function. We propose a simple linker based technique for enabling software memoization of any dynamically linked pure function by function interception and we illustrate our framework using a set of computationally expensive pure functions – the transcendental functions. The transcendental functions are those which cannot be expressed in terms of a finite sequence of algebraic operations (like trigonometric functions, exponential function etc.) and hence are computationally expensive. Our technique does not need the availability of source code and thus can even be applied to commercial applications as well as applications with legacy codes. As far as users are concerned, enabling memoization is as simple as setting an environment variable. Our framework does not make any specific assumptions about the underlying architecture or compiler tool-chains, and can work with a variety of current architectures. We present experimental results for x86-64 platform using both gcc and icc compiler tool-chains, and for ARM cortex-A9 platform using gcc. Our experiments include a mix of real world programs and standard benchmark suites: SPEC and Splash2x. On standard benchmark applications that extensively call the transcendental functions we report memoization benefits of upto 50% on Intel Ivy bridge and upto 10% on ARM Cortex-A9. Memoization was also able to regain a performance loss of 76% in bwaves due to a known performance bug in the GNU implementation of pow function. The same benchmark on ARM Cortex-A9 benefited by more than 200%.
Type de document :
Article dans une revue
ACM Transactions on Architecture and Code Optimization (TACO) , ACM, 2015, 12 (2), pp.23. 〈10.1145/2751559〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01178085
Contributeur : Erven Rohou <>
Soumis le : vendredi 17 juillet 2015 - 14:01:04
Dernière modification le : mercredi 11 avril 2018 - 01:51:11
Document(s) archivé(s) le : mercredi 26 avril 2017 - 07:27:45

Fichier

memoization.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Arjun Suresh, Bharath Narasimha Swamy, Erven Rohou, André Seznec. Intercepting Functions for Memoization: A Case Study Using Transcendental Functions. ACM Transactions on Architecture and Code Optimization (TACO) , ACM, 2015, 12 (2), pp.23. 〈10.1145/2751559〉. 〈hal-01178085〉

Partager

Métriques

Consultations de la notice

549

Téléchargements de fichiers

517