Login
Computer Science @ Rochester
Tuesday, July 17, 2007
2:00 PM
Computer Science Bldg. Room 601
Chengliang Zhang
University of Rochester
"Behavior Models for Computer Programs"
Today's software systems are becoming more and more complex. In many senses, a software system is very similar to a live organism. This motivates us to study a software system by investigating its behavior. A program's behavior is decided by not only the code and data defined by the program itself, but also the user inputs and the execution environment such as the hardware, the operating system, and possibly multiple layers of virtual machines.

Program behavior analysis complements the traditional code-based analysis such as data and control flow analysis and dependence theory. Deeper understanding of the program's behavior can help us improve performance by better utilizing the modern hardware. Based on the traces of a program execution, we build statistical models and identify recurring large-scale patterns. These models are then used to predict the future program behavior and expose opportunities for program optimization.

In this thesis, we investigate three behavior models: reference affinity, data locality quality, and program phases. We prove the hardness of reference affinity and show its application in divide-and-conquer type computations. We also propose a sampling-based method to find approximately the reference affinity groups. We propose a new component-based definition of spatial locality. With the locality we attempt to find the limits to improvement of spacial locality.

Based on the behavior models, we adapt programs to improve their performance. From the spatial aspect, we propose to improve the layout of matrix multiplication and code layout based on reference affinity. From the resource aspect, we propose a new resource-based memory management scheme and its extension in multi-programming environments. From the temporal aspect, we propose to monitor program memory usage, detect memory leaks and trigger preventive garbage collection based on the program phase behavior. We also propose layout auditing to improve the spatial data locality by continuously measuring and selecting the best garbage collection method during a long-running Java program execution.