On Characterizing the Data Access Complexity of Programs

International audienceTechnology trends will cause data movement to account for the majorityof energy expenditure and execution time on emerging computers.Therefore, computational complexity will no longer be a sufficientmetric for comparing algorithms, and a fundamental characterization ofdata access complexity will be increasingly important. The problem ofdeveloping lower bounds for data access complexity has been modeledusing the formalism of Hong \& Kung's red/blue pebble game forcomputational directed acyclic graphs (CDAGs). However, previouslydeveloped approaches to lower bounds analysis for the red/blue pebblegame are very limited in effectiveness when applied to CDAGs of realprograms, with computations comprised of multiple sub-computationswith differing DAG structure. We address this problem by developing anapproach for effectively composing lower bounds based on graphdecomposition. We also develop a static analysis algorithm toderive the asymptoticdata-access lower bounds of programs, as a function of theproblem size and cache size