Linear-time Modeling of Program Working Set in Shared Cache
Citations Over TimeTop 10% of 2011 papers
Abstract
Many techniques characterize the program working set by the notion of the program footprint, which is the volume of data accessed in a time window. A complete characterization requires measuring data access in all O(n 2 ) windows in an n-element trace. Two recent techniques have significantly reduced the measurement time, but the cost is still too high for real-size workloads. Instead of measuring all footprint sizes, this paper presents a technique for measuring the average footprint size. By confining the analysis to the average rather than the full range, the problem can be solved accurately by a linear-time algorithm. The paper presents the algorithm and evaluates it using the complete suites of 26 SPEC2000 and 29 SPEC2006 benchmarks. The new algorithm is compared against the previously fastest algorithm in both the speed of the measurement and the accuracy of shared-cache performance prediction.
Related Papers
- → Geometric morphometric footprint analysis of young women(2013)51 cited
- → Estimation of foot pressure from human footprint depths using 3D scanner(2016)9 cited
- → Comparing Three Footprint Grades to Evaluate Footprint Indexes for Flat Foot Diagnosis(2019)1 cited
- → Footprint Nicaragua Handbook(2002)2 cited
- A TENTATIVE DISCUSSION ON "ACQUISITION FOOTPRINT" IN SEISMIC EXPLORATION(2011)