On Characterizing the Data Access Complexity of Programs

Abstract : Technology trends will cause data movement to account for the majority of energy expenditure and execution time on emerging computers. Therefore, computational complexity will no longer be a sufficient metric for comparing algorithms, and a fundamental characterization of data access complexity will be increasingly important. The problem of developing lower bounds for data access complexity has been modeled using the formalism of Hong \& Kung's red/blue pebble game for computational directed acyclic graphs (CDAGs). However, previously developed approaches to lower bounds analysis for the red/blue pebble game are very limited in effectiveness when applied to CDAGs of real programs, with computations comprised of multiple sub-computations with differing DAG structure. We address this problem by developing an approach for effectively composing lower bounds based on graph decomposition. We also develop a static analysis algorithm to derive the asymptotic data-access lower bounds of programs, as a function of the problem size and cache size.
Type de document :
Communication dans un congrès
42nd Annual Symposium on Principles of Programming Languages, 2015, Jan 2015, Mumbai, India. ACM, pp.567-580, 2014
Liste complète des métadonnées

https://hal.inria.fr/hal-01104556
Contributeur : Fabrice Rastello <>
Soumis le : samedi 17 janvier 2015 - 12:53:59
Dernière modification le : lundi 30 avril 2018 - 15:02:49

Identifiants

  • HAL Id : hal-01104556, version 1

Citation

Venmugil Elango, Fabrice Rastello, Louis-Noël Pouchet, Jagannathan Ramanujam, Ponnuswamy Sadayappan. On Characterizing the Data Access Complexity of Programs. 42nd Annual Symposium on Principles of Programming Languages, 2015, Jan 2015, Mumbai, India. ACM, pp.567-580, 2014. 〈hal-01104556〉

Partager

Métriques

Consultations de la notice

338