TY - GEN
T1 - Recursive data structure profiling
AU - Raman, Easwaran
AU - August, David I.
PY - 2005/6/12
Y1 - 2005/6/12
N2 - As the processor-memory performance gap increases, so does the need for aggressive data structure optimizations to reduce memory access latencies. Such optimizations require a better understanding of the memory behavior of programs. We propose a profiling technique called Recursive Data Structure Profiling to help better understand the memory access behavior of programs that use recursive data structures (RDS) such as lists, trees, etc. An RDS profile captures the runtime behavior of the individual instances of recursive data structures. RDS profiling differs from other memory profiling techniques in its ability to aggregate information pertaining to an entire data structure instance, rather than merely capturing the behavior of individual loads and stores, thereby giving a more global view of a program's memory accesses. This paper describes a method for collecting RDS profile without requiring any high-level program representation or type information. RDS profiling achieves this with manageable space and time overhead on a mixture of pointer intensive benchmarks from the SPEC, Olden and other benchmark suites. To illustrate the potential of the RDS profile in providing a better understanding of memory accesses, we introduce a metric to quantify the notion of stability of an RDS instance. A stable RDS instance is one that undergoes very few changes to its structure between its initial creation and final destruction, making it an attractive candidate to certain data structure optimizations.
AB - As the processor-memory performance gap increases, so does the need for aggressive data structure optimizations to reduce memory access latencies. Such optimizations require a better understanding of the memory behavior of programs. We propose a profiling technique called Recursive Data Structure Profiling to help better understand the memory access behavior of programs that use recursive data structures (RDS) such as lists, trees, etc. An RDS profile captures the runtime behavior of the individual instances of recursive data structures. RDS profiling differs from other memory profiling techniques in its ability to aggregate information pertaining to an entire data structure instance, rather than merely capturing the behavior of individual loads and stores, thereby giving a more global view of a program's memory accesses. This paper describes a method for collecting RDS profile without requiring any high-level program representation or type information. RDS profiling achieves this with manageable space and time overhead on a mixture of pointer intensive benchmarks from the SPEC, Olden and other benchmark suites. To illustrate the potential of the RDS profile in providing a better understanding of memory accesses, we introduce a metric to quantify the notion of stability of an RDS instance. A stable RDS instance is one that undergoes very few changes to its structure between its initial creation and final destruction, making it an attractive candidate to certain data structure optimizations.
UR - http://www.scopus.com/inward/record.url?scp=84958619613&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958619613&partnerID=8YFLogxK
U2 - 10.1145/1111583.1111585
DO - 10.1145/1111583.1111585
M3 - Conference contribution
AN - SCOPUS:84958619613
T3 - Proceedings of the 3rd 2005 ACM SIGPLAN Workshop on Memory Systems Performance, MSP 2005
SP - 5
EP - 14
BT - Proceedings of the 3rd 2005 ACM SIGPLAN Workshop on Memory Systems Performance, MSP 2005
PB - Association for Computing Machinery, Inc
T2 - 3rd ACM SIGPLAN Workshop on Memory Systems Performance, MSP 2005
Y2 - 12 June 2005
ER -