Reuse-distance-based Miss-rate Prediction on a PerInstruction BasisChangpeng [email protected] [email protected]¨[email protected] [email protected] of Computer ScienceMichigan Technological UniversityHoughton MI 49931-1295 USAABSTRACTFeedback-directed optimization has become an increasingly impor-tant tool in designing and building optimizing compilers. Recently,reuse-distance analysis has shown much promise in predicting thememory behavior of programs over a wide range of data sizes.Reuse-distance analysis predicts program locality by experimen-tally determining locality properties as a function of the data size ofa program, allowing accurate locality analysis when the program’sdata size changes.Prior work has established the effectiveness of reuse distanceanalysis in predicting whole-program locality and miss rates. Inthis paper, we show that reuse distance can also effectively pre-dict locality and miss rates on a per instruction basis. Rather thanpredict locality by analyzing reuse distances for memory addressesalone, we relate those addresses to particular static memory opera-tions and predict the locality of each instruction.Our experiments show that using reuse distance without cachesimulation to predict miss rates of instructions is superior to usingcache simulations on a single representative data set to predict missrates on various data sizes. In addition, our analysis allows us toidentify the critical memory operations that are likely to produce asignificant number of cache misses for a given data size. With thisinformation, compilers can target cache optimization specifically tothe instructions that can benefit from such optimizations most.Categories and Subject DescriptorsD.3.4 [Programming Languages]: Processors—compilers, opti-mizationGeneral TermsAlgorithms, Measurement, LanguagesKeywordsData locality, reuse distance, profilingPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.MSP’04, June 8, 2004, Washington, DC, USA.Copyright 2004 ACM 1-58113-941-1/04/06 ...$5.00.1. INTRODUCTIONWith the widening gap between processor and memory speeds,program performance has become increasingly dependent upon theeffective use of a machine’s memory hierarchy. To improve localityin programs, compilers have traditionally used either static analysisof regular array references [8, 13] or profiling [1] to determine thelocality of memory operations. Static analysis has limited appli-cability when index arrays are used in addressing and when deter-mining locality across multiple loop nests. Profiling can measurelocality for a larger set of references, but the results may be specificto the profiled data set. This may lead to inaccurate analysis whenthe input set is changed.Recently, Ding, et al. [3, 14], have proposed techniques to pre-dict the reuse distance of memory references across all programinputs using a few profiling runs. They use curve fitting to predictreuse distance (the number of distinct memory locations accessedbetween two references to the same memory location) as a func-tion of a program’s data size. By quantifying reuse as a functionof data size, the information obtained via a few profiled runs allowthe prediction of reuse to be quite accurate over varied data sizes.Ding, et al., have used reuse-distance predictions to accurately pre-dict whole program miss rates [14].In order to use reuse distance in program optimization, it is ben-eficial to associate reuse distance prediction with the actual instruc-tions that access those locations. By predicting the reuse distancefor individual instructions, we can identify those instructions whichmay be most amenable to cache optimization. In this paper, we ex-tend the work of Ding, et al., to apply reuse-distance prediction ona per instruction basis. We examine the reuse distance of the datareferenced by each memory operation and use that information todetermine the reuse distance of the operation as a function of thedata size. We show experimentally that the reuse distance of staticinstructions is highly predictable. Furthermore, both the L1 and L2miss rates for instructions can be predicted accurately using reuse-distance-based analysis.Reuse-distance analysis opens up new possibilities for compilerand architectural optimization of memory operations. The dynamicanalysis information provides the compiler with additional infor-mation that is impossible to compute at compile time, allowing thecompiler to have more knowledge concerning the effects of op-timization. Reuse-distance analysis may also be used in micro-architectural optimization via compiler hints to gain a more globalview of the expected behavioral patterns of a program.The most obvious application of reuse distance is to prefetch-ing those memory operations that cause the most misses. Bothhardware and software prefetching may issue many unnecessaryprefetches. By predicting the miss rate of instructions, we can60identify those instructions that are likely to provide the most benefitvia prefetching and eliminate misses through dynamic or feedback-directed optimization. In addition, hardware could be constructedto use reuse-distance information to schedule prefetches dynami-cally for important instructions.We begin the rest of this paper with a review of work related tostatic and dynamic locality analysis. Next, we describe our analysistechniques and algorithms for measuring instruction-based reusedistance. Then, we present our experiments examining the pre-dictability of instruction-based reuse distance and finish with ourintentions for application of this analysis.2. RELATED WORKThe previous work most pertinent to this paper consists of thetwo recent papers by Ding, et al. [3, 14]. They present a techniqueto predict reuse patterns of the whole program based on a coupleof training runs on small inputs [3]. A follow-up work uses thepredicted reuse distances to estimate the capacity miss rates of afully associative cache [14]. We describe their techniques in detailin Section 3.1. In contrast, our work focuses on the prediction ofreuse patterns and miss rates for each instruction. We
View Full Document
Unlocking...