Introduction
Memory traces—comprehensive logs of every memory address accessed during program execution—are essential for architectural simulation and performance modeling. However, their sheer size (often reaching terabytes for scientific workloads) and sensitivity to input changes make them difficult to store, share, and reuse. This research presents a framework for creating "approximate memory traces" that significantly reduce storage requirements while maintaining high fidelity for performance analysis.
Methodology: Stride Patterns and Application Signatures
The proposed framework employs a two-pronged strategy to achieve lossy but effective trace compression by exploiting the inherent stability of program behavior.
1. Stride Pattern Detection
The core idea is to shift focus from global address streams to individual instructions. Most instructions exhibit "stability," meaning they access memory in predictable, constant steps known as strides. The framework classifies instructions based on a threshold ($R$):
- Stable Instructions: Those using fewer than $R$ different strides are recorded exactly.
- Random Instructions: Those exceeding the threshold are treated as statistically random. Instead of storing every address, the trace records the address range and uses a synthetic generator to mimic the behavior during simulation.
2. Application Signatures
To handle program logic, the framework uses instrumentation to analyze control flow and group basic blocks into "regions" such as loops or functions. For complex or unstable regions, it generates a "signature"—a compact representation of execution paths and iteration counts. This allows the reconstruction of a program's memory behavior on the fly without needing a full, literal trace.
Key Insights: Embracing "Good Enough" Randomness
A pivotal observation of this work is that in many scientific applications, the exact address of a random access is less critical for performance modeling than the statistical nature of the access itself. By treating randomness as a known quantity rather than data to be stored, the framework bypasses traditional compression hurdles. Furthermore, the authors found that while control flow may vary with input, the memory access behavior of individual instructions remains remarkably consistent, allowing for cross-input trace reuse.
Results and Performance
Evaluation using SPEC2000 and NAS Parallel Benchmarks (NPB) demonstrates the framework's efficiency:
- Massive Compression: For the
IS.Sbenchmark, a 98MB full trace was compressed to just 18KB—a reduction of several orders of magnitude. - High Accuracy: Error in total instruction counts remained below 0.3%.
- Simulation Fidelity: When predicting cache hit rates across various architectures (e.g., Power 4, Alpha EV67), the error for loops with random patterns was approximately 2.5%, while regular loops showed negligible differences from original traces.
Conclusion
By exploiting the inherent stability of instruction-level memory behavior and utilizing statistical models for randomness, this framework makes memory tracing a practical tool for large-scale architectural research. Future work aims to improve accuracy by modeling correlations between different random instructions and refining the detection of "false randomness" caused by unpredictable branching.
Summary updated