Mache: no-loss trace compaction
Published 1 April 1989
A. Dain Samples
Citations81
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
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.
Abstract
Execution traces can be significantly compressed using their referencing locality. A simple observation leads to a technique capable of compressing execution traces by an order of magnitude; instruction-only traces are compressed by two orders of magnitude. 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.
Keywords
Computer Science
American Journal of Physics<i>The Fractal Geometry of Nature</i>
21,750 Citations1983Benoît B. Mandelbrot, John Wheeler
IEEE Transactions on Information TheoryA universal algorithm for sequential data compression
5,467 Citations1977J. Ziv, A. Lempel
The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable- to-block codes designed to match a completely specified source.
IEEE Transactions on Information TheoryCompression of individual sequences via variable-rate coding
3,452 Citations1978J. Ziv, A. Lempel
The proposed concept of compressibility is shown to play a role analogous to that of entropy in classical information theory where one deals with probabilistic ensembles of sequences rather than with individual sequences.
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.
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.
ACM SIGPLAN NoticesRegister windows vs. register allocation
79 Citations2004David W. Wall
By combining profiling, instrumentation, and in-line simulation, this work measured the effectiveness of several register management schemes, including compile-time and link-time schemes for allocating registers, and register window schemes using fixed-size or variable-sized windows.
ACM SIGARCH Computer Architecture NewsInformation content of CPU memory referencing behavior
66 Citations1977Dan Hammerstrom, Edward S. Davidson
Information content of CPU memory referencing behavior
39 Citations1977Dan Hammerstrom, E. S. Davidson
Techniques are developed for analyzing the effectiveness of the addressing architecture and Memory/CPU traffic of existing machines with respect to the information theoretic bound for a given trace.
Register windows vs. register allocation
35 Citations1988D. W. Wall
By combining profiling, instrumentation, and in-line simulation, this work measured the effectiveness of several register management schemes, including compile-time and link-time schemes for allocating registers, and register window schemes using fixed-size or variable-sized windows.
Code Reorginazation for Instruction Caches
15 Citations1988A. Dain Samples, Paul Hilfinger
This paper addresses the question whether reorganization could benefit programs on machines with instruction caches by determining the efficacy of restructuring using simple reordering algorithms and profile data, and concludes that performance improvement can be obtained relatively cheaply.
Trace compaction using cache filtering with blocking
6 Citations1987Anant Agarwal
A technique called cache filtering with blocking is presented that compresses traces by exploiting both the temporal and spatial locality in the trace, and can reduce trace length by nearly two orders of magnitude.