Prediction and trace compression of data access addresses through nested loop recognition

Abstract : This paper describes an algorithm that takes a trace (i.e., a sequence of numbers or vectors of numbers) as input, and from that produces a sequence of loop nests that, when run, produces exactly the original sequence. The input format is suitable for any kind of program execution trace, and the output conforms to standard models of loop nests. The first, most obvious, use of such an algorithm is for program behavior modeling for any measured quantity (memory accesses, number of cache misses, etc.). Finding loops amounts to detecting periodic behavior and provides an explanatory model. The second application is trace compression, i.e., storing the loop nests instead of the original trace. Decompression consists of running the loops, which is easy and fast. A third application is value prediction. Since the algorithm forms loops while reading input, it is able to extrapolate the loop under construction to predict further incoming values. Throughout the paper, we provide examples that explain our algorithms. Moreover, we evaluate trace compression and value prediction on a subset of the SPEC2000 benchmarks.
Type de document :
Communication dans un congrès
6th annual IEEE/ACM international symposium on Code generation and optimization, Apr 2008, Boston, United States. ACM, pp.94-103, 2008, Proceedings of the 6th annual IEEE/ACM international symposium on Code generation and optimization. 〈10.1145/1356058.1356071〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00504597
Contributeur : Philippe Clauss <>
Soumis le : mardi 20 juillet 2010 - 16:42:19
Dernière modification le : jeudi 11 janvier 2018 - 06:22:09

Identifiants

Collections

Citation

Alain Ketterlin, Philippe Clauss. Prediction and trace compression of data access addresses through nested loop recognition. 6th annual IEEE/ACM international symposium on Code generation and optimization, Apr 2008, Boston, United States. ACM, pp.94-103, 2008, Proceedings of the 6th annual IEEE/ACM international symposium on Code generation and optimization. 〈10.1145/1356058.1356071〉. 〈inria-00504597〉

Partager

Métriques

Consultations de la notice

257