Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Fabrice Rastello Connect in order to contact the contributor
Submitted on : Saturday, January 17, 2015 - 12:53:59 PM
Last modification on : Thursday, October 21, 2021 - 3:50:27 AM


  • HAL Id : hal-01104556, version 1


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. pp.567-580. ⟨hal-01104556⟩



Record views