SHF: Small: Automated Analysis and User Feedback on Data Movement Bottlenecks in Programs

Louisiana State University, Baton Rouge LA

Investigators

Abstract

The cost of data movement through the memory hierarchy is very high in current computer systems, relative to the cost of performing arithmetic operations, both in terms of time and energy. It is expected to become even more dominant in future computer systems. Therefore optimizing data access costs will become increasingly critical in the coming years. This has great impact on algorithm design and implementation on such systems. A characterization of data access complexity is only known today for a few classes of algorithms, such as dense linear algebra, and has required the use of problem-specific analysis techniques. This proposal presents novel ideas for developing automated tools and techniques to characterize the inherent data access complexity of arbitrary algorithms. An automatable general approach for data access complexity of programs will have significant impact on deriving highly effective algorithms and their implementations, understanding the impact of future architectures on algorithm design, and on advances in compilers aimed at improving data access costs of programs. The proposal develops novel ideas to address a fundamental problem of increasing importance -- developing tools and techniques for characterization of the inherent data access complexity of algorithms. The work develops the following: (i) the first unifying approach for developing both upper and lower bounds for the inherent data access complexity of a CDAG under a common underlying theoretical model; (ii) an approach to remove a fundamental current limitation in the use of the popular reuse distance analysis metric; (iii) a scalable and versatile dynamic analysis infrastructure of use to application developers, compiler writers and architecture designers.