A comparison of trace-sampling techniques for multi-megabyte caches
IEEE Transactions on ComputersPublished 1 June 1994Open access
R. E. Kessler, M.D. Hill, David A. Wood
Citations147
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The paper compares the trace-sampling techniques of set sampling and time sampling using the multi-billion reference traces of A.A. Borg et al. (1990) and applies both techniques to multi-megabyte caches, where sampling is most valuable, to find that set sampling meets the 10% sampling goal, while time sampling does not.
Abstract
The paper compares the trace-sampling techniques of set sampling and time sampling. Using the multi-billion reference traces of A. Borg et al. (1990), we apply both techniques to multi-megabyte caches, where sampling is most valuable. We evaluate whether either technique meets a 10% sampling goal: a method meets this goal if, at least 90% of the time, it estimates the trace's true misses per instruction with /spl les/10% relative error using /spl les/10% of the trace. Results for these traces and caches show that set sampling meets the 10% sampling goal, while time sampling does not. We also find that cold-start bias in time samples is most effectively reduced by the technique of D.A. Wood et al. (1991). Nevertheless, overcoming cold-start bias requires tens of millions of consecutive references.>
Keywords
Computer ScienceEngineering
Computer Architecture: A Quantitative Approach
9,536 Citations1989John L. Hennessy, David A. Patterson
This best-selling title, considered for over a decade to be essential reading for every serious student and practitioner of computer design, has been updated throughout to address the most important trends facing computer designers today.
ACM Computing SurveysCache Memories
1,702 Citations1982Alan Jay Smith
Specific aspects of cache memories investigated include: the cache fetch algorithm (demand versus prefetch), the placement and replacement algorithms, line size, store-through versus copy-back updating of main memory, cold-start versus warm-start miss ratios, mulhcache consistency, the effect of input /output through the cache, the behavior of split data/instruction caches, and cache size.
Improving direct-mapped cache performance by the addition of a small fully-associative cache prefetch buffers
1,288 Citations1998Norman P. Jouppi
Together, victim caches and stream buffers reduce the miss rate of the first level in the cache hierarchy by a factor of two to three on a set of six large benchmarks.
IEEE Transactions on ComputersEvaluating associativity in CPU caches
600 Citations1989Mark D. Hill, Alan Jay Smith
All-associativity simulation is theoretically less efficient than forest simulation or stack simulation (a commonly used simulation algorithm), in practice it is not much slower and allows the simulation of many more caches with a single pass through an address trace.
Lockup-free instruction fetch/prefetch cache organization
561 Citations1998David Kroft
A cache organization is presented that essentially eliminates a penalty on subsequent cache references following a cache miss and has been incorporated in a cache/memory interface subsystem design, and the design has been implemented and prototyped.
Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers
440 Citations2002Norman P. Jouppi
ACM Transactions on Computer SystemsCache performance of operating system and multiprogramming workloads
268 Citations1988Anant Agarwal, John L. Hennessy +1 more
A program tracing technique called ATUM (Address Tracing Using Microcode) is developed that captures realistic traces of multitasking workloads including the operating system that shows that both the operating System and multiprogramming activity significantly degrade cache performance, with an even greater proportional impact on large caches.
IEEE Transactions on ComputersAccurate low-cost methods for performance evaluation of cache memory systems
191 Citations1988S. Laha, J.H. Patel +1 more
New methods of simulation based on statistical techniques are proposed for decreasing the need for large trace measurements and for predicting true program behavior, and a new concept of primed cache is introduced to simulate large caches by the sampling-based method.
Scholarworks (University of Massachusetts Amherst)Analysis of cache replacement-algorithms
130 Citations1985Thomas R. Puzak
The model shows that the majority of the cache misses that OPT avoids over LRU come from the most-recently-discarded lines of the LRU cache, which leads to three realizable near-optimal replacement algorithms that try to duplicate the replacement decisions made by OPT.
A model for estimating trace-sample miss ratios
127 Citations1991David A. Wood, Mark D. Hill +1 more
This paper provides empirical evidence that μ is much larger than the overall miss ratio (e.g., 0.40 vs. 0.02), and develops a model that explains the empirical results for long trace samples and extends the model to handle short trace samples, which leads to better estimates of overall miss ratios.
Microprocessors and MicrosystemsHigh-performance computer architecture
115 Citations1989Alan Clements
ACM SIGARCH Computer Architecture NewsGeneration and analysis of very long address traces
108 Citations1990Anita Borg, R. E. Kessler +1 more
IEEE Transactions on Software EngineeringTwo Methods for the Efficient Analysis of Memory Address Trace Data
90 Citations1977Alan Jay Smith
There is little or no loss in accuracy using reduced traces for many purposes for a wide range of memory sizes and degrees of reduction.
Mache: no-loss trace compaction
81 Citations1989A. Dain Samples
This technique is unlike previously reported trace compression techniques in that it compresses without loss of information and, therefore, does not affect trace-driven simulation time or accuracy.
ACM Transactions on Computer SystemsEfficient trace-driven simulation methods for cache performance analysis
69 Citations1991Wen-Hann Wang, Jean-Loup Baer
Parallel trace-driven cache simulation by time partitioning
66 Citations1990Philip Heidelberger, Harold S. Stone
ACM SIGARCH Computer Architecture NewsCharacteristics of performance-optimal multi-level cache hierarchies
57 Citations1989Steven A. Przybylski, Mark Horowitz +1 more
Efficient trace-driven simulation method for cache performance analysis
51 Citations1990Wen-Hann Wang, Jean-Loup Baer
This work reduces the program traces to the extent that exact performance can still be obtained from the reduced traces and devise an algorithm that can produce performance results for a variety of metrics for a large number of set-association write-back caches in just a single simulation run.
Communications of the ACMCold-start vs. warm-start miss ratios
49 Citations1978Malcolm C. Easton, Ronald Fagin
It is shown how to obtain, under simple assumptions, the cache miss ratio for multiprogramming from cold-start miss ratio values and how to obtaining approximate cold- start miss ratios from warm-start misses ratios.
1990 Winter Simulation Conference ProceedingsParallel trace-driven cache simulation by time partitioning
47 Citations2002Philip Heidelberger, Harold S. Stone
The authors describe a technique for performing parallel simulation of a trace of address references for the purpose of evaluating different cache structures, and found that after simulating the trace in parallel, a small amount of resimulation can produce the correct counts of cache hits and misses.
Characteristics of performance-optimal multi-level cache hierarchies
44 Citations1989Steven A. Przybylski, Mark Horowitz +1 more
It is shown that a first-level cache dramatically reduces the number of references seen by a second- level cache, without having a large effect on the numberof second-level caches misses, which makes associativity more attractive and increases the optimal cache size for second-levels caches over what they would be for an equivalent single-level Cache system.
Blocking: exploiting spatial locality for trace compaction
42 Citations1990Anant Agarwal, Minor Huffman
A technique called blocking and a variant called blocking with temporal data are presented that compress traces by exploiting spatial locality and show that blocking filtering combined with cache filtering can reduce trace length by nearly two orders of magnitude.
Generation and analysis of very long address traces
37 Citations2002A. Borg, R. E. Kessler +1 more
Minds at UW (University of Wisconsin)Analysis of multi-megabyte secondary CPU cache memories
36 Citations1992R. E. Kessler
This dissertation introduces and solves the problems caused by the interaction of virtual memory and real-indexed multi-megabyte caches and develops software techniques that can make a hardware direct-mapped cache appear about 50% larger.
Long Address Traces from RISC Machines: Generation and Analysis
34 Citations1999Anita Borg, R. E. Kessler +2 more
The implementation of trace generation and onthe-fly analysis is described and preliminary results from the analysis of user traces containing many billions of memory references are reviewed, both useful and necessary for understanding the behavior of large, fast systems.
ACM SIGMETRICS Performance Evaluation ReviewMache: no-loss trace compaction
32 Citations1989A. Dain Samples
Characteristics Of Performance-Optimal Multi-level Cache Hierarchies
25 Citations2005Steven A. Przybylski, Mark Horowitz +1 more
Performance directed memory hierarchy design
21 Citations1988John L. Hennessy, Steven A. Przybylski
This thesis concludes with a succinct set of guidelines that will aid designers in finding the memory hierarchy that maximizes system performance given particular implementation constraints.
Design and Evaluation of In-Cache Address Translation
11 Citations1990David A. Wood
This dissertation studies in- cache address translation, a new approach to implementing virtual memory that combines the functions of the traditional translation lookaside buffer with a virtual address cache, and proposes a variation of the algorithm, called inverted in-cache translation, which reduces this sensitivity.