Tree-Traversal Orientation Analysis
Kevin Andrusky, Stephen Curial and Jose Nelson Amaral
The 19th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2006)
New Orleans, Louisiana, November 2-4, 2006
Abstract
This paper presents a profiling-based analysis to determine the traversal orientation of link-based tree data structures. Given the very-high memory-hierarchy latencies in modern computers, once the compiler has identified that a pointer-based data structure represents a tree, it would be useful to determine the predominant orientation of traversal for the tree. Optimizing compilers can implement the static shape analysis proposed by Ghiya and Hendren to determine if a linked data structure is a tree [1]. However no techniques have been reported to enable an optimizing compiler to determine the predominant traversal orientation of a tree. This paper describes an analysis that collects data during an instrumented run to determine if the traversal is predominantly breadth-first or depth-first. The analysis determined, with high accuracy, the predominant orientation of traversal of trees in programs written by us as well as in the Olden benchmark suite. This profile-based analysis is storage efficient - it uses only 7\% additional memory in comparison with the non-instrumented version of the code. Determining the predominant orientation of traversal of a tree data structure will enable several client optimizations such as improved software-based prefetching, data-storage remapping and better memory allocators.
[1] R. Ghiya and L. J. Hendren. Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C. In Symposium on Principles of Programming Languages (POPL), pages 1 15, St. Petersburg, Florida, January 1996.