Complete Measurement of All-window Footprints

Xiaoya Xiang
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.

Long Abstract

Back to Program