A Survey of Miss-Ratio Curve Construction Techniques <s> Mattson's Stack Distance Algorithm <s> The design of efficient storage hierarchies generally involves the repeated running of "typical" program address traces through a simulated storage system while various hierarchy design parameters are adjusted. ::: ::: This paper describes a new and efficient method of determining, in one pass of an address trace, performance measures for a large class of demand-paged, multilevel storage systems utilizing a variety of mapping schemes and replacement algorithms. ::: ::: The technique depends on an algorithm classification, called "stack algorithms," examples of which are "least frequently used," "least recently used," "optimal," and "random replacement" algorithms. The techniques yield the exact access frequency to each storage device, which can be used to estimate the overall performance of actual storage hierarchies. <s> BIB001 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> Mattson's Stack Distance Algorithm <s> 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. <s> BIB002
Mattson et. al. BIB001 developed the rst algorithm to use stack distance as a method for calculating the miss-rate for a given cache size. It has ve main steps for each reference x: (1) Search stack to nd the current location of x (if any) (2) Calculate the distance d from the top of the stack (3) Update cache miss counters for all sizes ≥ d (4) Update cache hit counters for all sizes ≤ d (5) Push x onto the stack and remove the last location of x (if any) The algorithm runs in O(N * M) time, where N is total number of references and M is unique number of references. Many works improve on this algorithm by using more e cient data structures, sampling, and estimated stack distances. Fang et. al. BIB002 showed that the stack distance distribution of a program's typical workload could be predicted accurately given a signi cantly smaller version of the workload. They predicted the stack distance distribution for the reference input set of the SPEC2K benchmark using only the train and test input sets. These results encouraged researchers to move towards sampling the references in order to build the distribution while still achieving accurate stack distance distributions.