Skip to Main content Skip to Navigation
New interface
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 : Tuesday, November 29, 2022 - 12:06:07 PM


  • 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 {ACM} {SIGPLAN-SIGACT} Symposium on Principles of Programming Languages, {POPL} 2015, Jan 2015, Mumbai, India. pp.567-580. ⟨hal-01104556⟩



Record views