PPoPP 2008 START Conference Manager    

All-Window Profiling of Concurrent Executions (poster presentation)

Chen Ding and Trishul Chilimbi

The 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2008)
Salt Lake City, Utah, February 20-23, 2008


The basic problem in modeling concurrent executions is to estimate the interaction between different programs or different threads of the same program. Since an execution window of a thread may overlap with another window of another thread, it is often desirable to measure the average or the expected behavior for execution windows of all sizes. The number of different execution windows for a trace is quadratic to the length of the trace. However, if a user is satisfied with a relative accuracy, for example, 99.9%, this paper gives an algorithm that runs in O(n log n) time and O(log n) space, where is n is the length of the trace. The paper discusses two uses of the algorithm. One is evaluating the expected footprint in any execution window. The other is evaluating the average load balance between any set of threads. Both are necessary in analyzing the memory performance of concurrent executions including the miss rate in a shared cache or the frequency of coherence invalidations. In the footprint case, the time and space cost can be reduced to O(n log m) and O(log m), where $m$ is the size of program data.

START Conference Manager (V2.54.5)