Path-based reuse distance analysis

Abstract. Profiling can effectively analyze program behavior and provide criti-cal information for feedback-directed or dynamic optimizations. Based on mem-ory profiling, reuse distance analysis has shown much promise in predicting data locality for a program using inputs other than the profiled ones. Both whole-program and instruction-based locality can be accurately predicted by reuse dis-tance analysis. Reuse distance analysis abstracts a cluster of memory references for a particu-lar instruction having similar reuse distance values into a locality pattern. Prior work has shown that a significant number of memory instructions have multi-ple locality patterns, a property not desirable for many instruction-based memory optimizations. This paper investigates the relationship between locality patterns and execution paths by analyzing reuse distance distribution along each dynamic path to an instruction. Here a path is defined as the program execution trace from the previous access of a memory location to the current access. By differentiat-ing locality patterns with the context of execution paths, the proposed analysis can expose optimization opportunities tailored only to a specific subset of paths leading to an instruction. In this paper, we present an effective method for path-based reuse distance profil-ing and analysis. We have observed that a significant percentage of the multiple locality patterns for an instruction can be uniquely related to a particular execu-tion path in the program. In addition, we have also investigated the influence of inputs on reuse distance distribution for each path/instruction pair. The experi-mental results show that the path-based reuse distance is highly predictable, as a function of the data size, for a set of SPEC CPU2000 programs.