Login
Computer Science @ Rochester
Monday, December 12, 2005
11:00 AM
CSB 209
Chen Ding
U. Rochester
Locality and Phases: Dynamic Structures in Large-Scale Program Behavior
As modern software becomes larger, more complex, and increasingly interconnected, we need techniques that identify high-level composite patterns and tailor them for different tasks and environments. Locality and phases have come to play a central role in understanding the dynamic behavior of large systems. While intuitively appealing, these concepts have proven difficult to apply in practice: they suggest the need to define, measure, and verify patterns across billions of operations, and to cope with behavior that changes with program input.

In this talk I will present our findings from the past five years on behavior-based program analysis. By profiling a few runs of an application, the analysis finds common patterns in program behavior and predicts how those patterns will change in other runs, in a manner very much analogous to prediction in the physical and biological sciences. I will describe three behavoiral models. The first is quantitative, whole-program locality across inputs and cache sizes. The second is reference affinity, which uncovers the hierarchical locality structure in program data. The third is program phases, which are recurring patterns of execution involving large sections of program code. These temporal and spatial models form a new basis for unifying program analysis, offline profiling, and online adaptation and bridging between popular heuristics (frequency, distance, and topology) and the seemingly insurmountable theoretical complexity. In practice, they enable highly adaptive yet programmable techniques in whole-program locality management and parallelization. These techniques reveal emergent behaviors that are not obvious from analyzing individual program components, inputs, or machine environments. I will discuss the implications of these findings in particular the potential for producing more intelligent software through behavior-oriented programming.

This research is conducted in collaboration with many members of the computer science department.