Instruction -based memory distance analysis and its application

With the widening gap between processor and memory speeds, program performance has become increasingly dependent upon the effective use of a machine's memory hierarchy. Cache optimization and load speculation are two important approaches to improve memory system performance. Researchers in both areas have been eagerly seeking novel avenues to analyze memory behaviors in order to optimize programs with complex memory access patterns which can not be handled well with traditional approaches. We propose a novel analysis framework to study the behaviors of memory references, and apply the framework to predict cache misses and to determine memory dependences for load speculation.;We examine the notation of memory distance as it is applied to the instruction space of a program and to the optimization of the memory hierarchy. Memory distance is defined as a dynamic quantifiable distance in terms of memory references between two accesses to the same memory location. We build an effective framework to analyze and predict the instruction-based memory distance. Evaluation on a set of SPEC CPU2000 benchmarks shows that our framework can accurately predict memory distance distribution of an instruction when program input changes. Furthermore, we propose a novel approach to investigate memory distance on paths leading to an instruction.;Applying our analysis framework, we propose a memory-distance-based model to predict data locality for memory instructions in a program when input changes. Our model first uses the predicted memory distance to predict the cache miss rates for an instruction. Based on the predicted miss rates, our model then identifies the program's critical instructions---the set of high miss instructions whose cumulative misses account for 95% of the L2 cache misses in a program. Our experiments show that memory distance analysis can accurately predict L1 and L2 miss rates, and effectively identify critical instructions in both integer and floating-point programs.;Based on memory distance analysis, we propose a compiler/architecture cooperative approach for memory disambiguation in out-of-order superscalar processors. Our approach determines memory dependences between loads and stores statically through an extensive analysis of the instruction-based memory distance. By means of instruction annotation, the dependence information is then communicated to the micro-architecture for the processors to disambiguate memory addresses and make load speculation decisions accordingly. Compared with the state-of-the-art hardware-based schemes, the proposed approach consumes much less on-chip memories while achieving a comparable or better performance.;To summarize, this dissertation studies the memory access behaviors of programs. Through memory distance analysis, we propose a framework to predict memory behaviors when program input changes. When applied to data locality analysis and memory disambiguation, our framework produces promising results.