The Eighteenth International Conference on
Raleigh, North Carolina. September 12-16, 2009.
Complete Measurement of All-window Footprints
Advisor: Chen Ding
Computer Science Department, University of Rochester
We have presented an all-window working-set analysis, which combines single-window relative-precision approximation and all-window constant-precision approximation to obtain an asymptotic cost of O(CKlogM). We have implemented the algorithm and tested it on the SPEC2K benchmark suite. The new algorithm is faster than a previous algorithm, with O(NlogM) asymptotic complexity, by a factor of 100 on average, reducing the measurement time for small tests from 2 hours to 1 minute. The new algorithm has successfully measured the all-window working sets for all full-size tests. It is the first time such complete measurement is made. The results may have uses in modeling memory behavior of parallel programs that share a memory hierarchy.