A Survey of Miss-Ratio Curve Construction Techniques <s> Tree <s> Stack processing, and in particular stack processing for the least recently used replacement algorithms, may present computational problems when it is applied to a sequence of page references with many different pages. This paper describes a new technique for LRU stack processing that permits efficient processing of these sequences. An analysis of the algorithm and a comparison of its running times with those of the conventional stack processing algorithms are presented. Finally we discuss a multipass implementation, which was found necessary to process trace data from a large data base system. <s> BIB001 </s> A Survey of Miss-Ratio Curve Construction Techniques <s> Tree <s> On modern computer systems, the memory performance of an application depends on its locality. For a single execution, locality-correlated measures like average miss rate or working-set size have long been analyzed using reuse distance—the number of distinct locations accessed between consecutive accesses to a given location. This article addresses the analysis problem at the program level, where the size of data and the locality of execution may change significantly depending on the input. The article presents two techniques that predict how the locality of a program changes with its input. The first is approximate reuse-distance measurement, which is asymptotically faster than exact methods while providing a guaranteed precision. The second is statistical prediction of locality in all executions of a program based on the analysis of a few executions. The prediction process has three steps: dividing data accesses into groups, finding the access patterns in each group, and building parameterized models. The resulting prediction may be used on-line with the help of distance-based sampling. When evaluated on fifteen benchmark applications, the new techniques predicted program locality with good accuracy, even for test executions that are orders of magnitude larger than the training executions. The two techniques are among the first to enable quantitative analysis of whole-program locality in general sequential code. These findings form the basis for a unified understanding of program locality and its many facets. Concluding sections of the article present a taxonomy of related literature along five dimensions of locality and discuss the role of reuse distance in performance modeling, program optimization, cache and virtual memory management, and network traffic analysis. <s> BIB002
In tree-based stack distance calculations we exploit the logarithmic search time in balanced tree structure. Methods in this class have developed towards approximation of distances by getting to a leaf node that represents a close enough stack distance. Partial Sums Tree by Bennet et. al. BIB001 . Bennet introduces a partial sums tree based on binary vectors representing the stack distance of a reference. But rst they introduce the concept of using a hash table to store the previous location p of a reference. Second, they maintain a binary vector, B, at time t for a given reference x with the following property: Now the number of 1s in B t is the stack distance of reference x. As t increases the idea is to create a hierarchy of partial sums out of B so that we don't have to scan B each time we calculate the stack distance for x. For example, imagine that every 3 time intervals we add up all the 1s counted so far and store them as a partial sum B i , then for every 3 partial sums B i we make a new nal sum. To calculate the stack distance now, we do a tree traversal from our current time t to the previous use time p. Since each lookup in the hash table is O(1) and each stack distance calculation is O(lo (n)), then for a trace of N references the running time is now O(N * lo (n)). Interval tree by Almasi et. al.  . Almasi interprets Bennet's binary vectors in a di erent manner. They use only the 0s from the vector, calling them holes. The calculation for stack distance now becomes: Where t is current time, p is previous time, and holes(x p ) represents the number of holes (0s) between t and p in B. Now we represent a hole's index as h i and let the interval [h i , h j ] represent the time between two consecutive holes. Since these intervals of holes are non-overlapping, they can be represented as AVL or red-black trees. For N references this takes O(N * lo (n)), similar to Bennet's asymptotic bound, but in practice it performs signi cantly better because the tree is well balanced. Although we are still at the point of using a large amount of memory, O(M), where M is unique number of accesses. Search Tree  . Olken proposed ordering the LRU stack as a binary tree based on access times so that an in-order traversal gives the LRU stack position. For a given reference at the root, the right side of the tree represents references used more recently and the left side represents older references. At each node in the tree, we store a count of the number of nodes in the right subtree (more recent) and the number of nodes in the left subtree (older). In order to calculate a stack distance, on a reference to x, we have to search the tree for its location and traverse our way to the top of the tree, recording the number of nodes in the right subtree of each node that we visited. In order to keep this tree balanced we should use an AVL or Splay tree as suggested by Olken. This algorithm runs in O(N * lo (n)) time and needs to store M number of nodes, where M is the number of unique accesses. Scale Tree BIB002 . In Zhong et. al. they produce a modi ed version of Olken's search tree by modifying it to support a range of times at each node. This maps several references to one node and allows for much faster searches. The amount of error incurred by using a range of times at each node is bounded by the range. The overall run time is reduced to O(N * lo (lo (M)), but we still require O(M) space. SHARDS  . Spatially hashed reuse distances (stack distances), or SHARDS, is a recent advancement to constant space use. They achieve this by sampling accesses based on the hashed value of their location, hence spatially hashed. These samples are then put into an interval tree to compute their stack distance. After computing stack distance, it is recorded in the stack distance histogram so that we can solve for the miss-ratio curve. The achievement in this work is running in O(1) through sampling and linear run time since it only requires one scan through the set of accesses.