Systems Seminar: Dr. James Larus, Microsoft Research

Whole Program Paths

Abstract

A central challenge facing computer architects, compiler writers, and mere mortal programmers is to understand a program's dynamic behavior. Events that occur while a program runs are often elusive, but they provide a basis for understanding the program's behavior and improving its performance. Program paths or traces--sequences of consecutively executed basic blocks--offer one of the few clear windows into a program's dynamic behavior. Paths, unlike other techniques, such as profiles, capture aspects of a program's dynamic control flow, not just its aggregate behavior.

Paths, in fact, have long provided a unifying context for performance tuning. Programmers have improved the performance of large, complex systems, such as operating systems and databases, by identifying heavily executed paths and streamlining them into "fast paths." In compilers as well, trace scheduling and, more recently, path-based compilation demonstrate that program optimization can benefit from a focus on a program's dynamic control flow. Recently designed computer architectures have also directly exploited traces to enhance instruction caching and execution.

This talk describes a new approach to measuring a program's control flow that captures a complete picture of the program's dynamic behavior. The technique introduces whole program paths (WPP), which are a complete, compact record of a program's entire control flow. A whole program path crosses both loop and procedure boundaries, and so provides a practical basis for interprocedural path profiling. This talk explains how to record a WPP, describes its representation, shows that this representation can be used to analyze program behavior, and demonstrates the technique's practicality on SPEC benchmarks and Microsoft application programs.

Speaker Bio

James Larus is currently a researcher at Microsoft Research starting a new group called Software Productivity Tools. Before that, he was a professor at the University of Wisconsin-Madison for 10 years. During that time, he applied programming language and compiler technology to a wide range of problems, most notably efficient program measurement and fine-grain distributed shared memory. His MS and PhD are from the University of California, Berkeley.