Instruction based memory distance analysis and its application to optimization
- 1 January 2005
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 14th International Conference on Parallel Architectures and Compilation Techniques (PACT'05)
Abstract
Feedback-directed optimization has become an increasingly important tool in designing and building optimizing compilers as it provides a means to analyze complex program behavior that is not possible using traditional static analysis. Feedback-directed optimization offers the compiler opportunities to analyze and optimize the memory behavior of programs even when traditional array-based analysis is not applicable. As a result, both floating point and integer programs can benefit from memory hierarchy optimization. In this paper, we examine the notion of memory distance as it is applied to the instruction space of a program and to feedback-directed optimization. Memory distance is defined as a dynamic quantifiable distance in terms of memory references between two accesses to the same memory location. We use memory distance to predict the miss rates of instructions in a program. Using the miss rates, we then identify the program's critical instructions - the set of high miss instructions whose cumulative misses account for 95% of the L2 cache misses in the program - in both integer and floating-point programs. Our experiments show that memory-distance analysis can effectively identify critical instructions in both integer and floating-point programs. Additionally, we apply memory-distance analysis to memory disambiguation in out-of-order issue processors using those distances to determine when a load may be speculated ahead of a preceding store. Our experiments show that memory-distance-based disambiguation on average achieves within 5-10% of the performance gain of the store set technique which requires a hardware table.Keywords
This publication has 19 references indexed in Scilit:
- Locality phase predictionPublished by Association for Computing Machinery (ACM) ,2004
- Static identification of delinquent loadsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Cost effective memory dependence prediction using speculation levels and color setsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Automatic generation of microarchitecture simulatorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Quantifying loop nest locality using SPEC'95 and the perfect benchmarksACM Transactions on Computer Systems, 1999
- Improving data locality with loop transformationsACM Transactions on Programming Languages and Systems, 1996
- ATOMPublished by Association for Computing Machinery (ACM) ,1994
- Efficient simulation of caches under optimal replacement with applications to miss characterizationPublished by Association for Computing Machinery (ACM) ,1993
- A data locality optimizing algorithmPublished by Association for Computing Machinery (ACM) ,1991
- Evaluation techniques for storage hierarchiesIBM Systems Journal, 1970