My research interests are in programming language design and implementation, with a systems focus. I have worked on compilers for parallel machines, domain-specific languages, and program analysis. I am also interested in high-performance computer architecture, and have done some work on multiprocessor cache coherence.
I started my research career with the Wisconsin Wind Tunnel project at the University of Wisconsin-Madison. In this project, we investigated the design and programming of shared-memory parallel computers. My dissertation addressed the problem of compiling a high-level language to run efficiently on a hybrid shared-memory and message-passing parallel machine. After I graduated in October 1997, I joined the Software Production Research Department of Bell Laboratories. Since then, I have been working on program analysis for software tools, and on domain-specific languages.
Here is a summary of contributions I have made in these areas, presented in reverse chronological order.
More recently, I have been interested in the problem of scaling whole program analyses, in particular, pointer analysis. Scalability of analyses has a bearing on the size of programs that tools, such as physical type checker, can handle. Along with a summer intern, Atanas Rountev (Rutgers), I have looked at the scalability of flow- and context-insensitive points-to analysis. In particular, we studied the practical limits of performing Andersen's analysis, a relatively precise points-to analysis but with cubic worst-case time complexity. The space and time requirements of this analysis become prohibitive for large (several hundred thousand lines) programs, even with a very efficient implementation. We have developed a preprocessing step to Andersen's analysis that alters the input program in a way that substantially reduces the space and time costs of performing the analysis, without sacrificing precision.
We have designed a domain-specific language for writing cache-coherence protocols. Cache coherence is of concern when parallel and distributed systems make local replicas of shared data to improve scalability and performance. In both distributed shared memory systems and distributed file systems, a coherence protocol maintains agreement among the replicated copies as the underlying data are modified by programs running on the system. Cache-coherence protocols are notoriously difficult to implement, debug, and maintain. Moreover, protocols are not off-the-shelf, reusable components, because their details depend on the requirements of the system under consideration. The complexity of engineering coherence protocols can discourage users from experimenting with new, potentially more efficient protocols. We have designed and implemented Teapot, a domain-specific language that attempts to address this complexity. Teapot's language constructs, such as a state-centric control structure and continuations, are better suited to expressing protocol code than those of a typical systems programming language. Teapot also facilitates automatic verification of protocols, so hard to find protocol bugs, such as deadlocks, can be detected and fixed before encountering them on an actual execution.
In recent work with Pete McCann, I am looking at using domain-specific abstractions in the construction of networking software, such as implementation of protocols and network monitoring applications. Specifically, we have worked on Packet Types, a type system for describing network packets. Much of the low-level networking code deals with issues of packing and unpacking values into a linear network packet, whose format is standardized at the bit level. This low-level style is both tedious and error-prone. Our type system enables a programmer to describe the packet layout at a high-level, and generate all the packing and unpacking code automatically. Furthermore, the generated code runs almost as efficiently as hand-written code.
Compilers for parallel machines have historically generated code either for a shared-memory, or a message-passing interface. From a compiler's perspective, both targets have advantages and disadvantages. Shared memory provides a simpler, transparent global address space, but extracts a coherence overhead on all programs. Communication generation for message passing is much more difficult, but for programs in which a compiler can easily compute the communication patterns, good efficiency has been demonstrated.
In distributed (a.k.a. virtual) shared memory, since the global address space is implemented in software, a compiler can potentially use the low-level messaging layer in addition to the system-implemented shared memory. The challenge here is to manage an application's data in such a way that direct updating (via messages) of data does not conflict with the cache-coherence mechanisms, since accesses via transparent shared memory still rely on a consistent shared memory. My dissertation addressed this challenge by making the compiler aware of the working of the coherence protocol, and formulating a contract between the compiler and the protocol for them to collaborate. I demonstrated my ideas by implementing them in an industry-strength parallelizing compiler for High Performance Fortran (Portland Group's pghpf compiler). I showed that by generating code for a hybrid of shared-memory and message-passing interfaces, shared-memory overheads can be reduced sufficiently to make the performance comparable to native message-passing performance. At the same time, a compiler can handle programs that are too complicated to generate message-passing code directly, yet have exploitable data parallelism.
We investigated tradeoffs in the design of shared-memory multiprocessors, particularly in the choice of the cache-coherence protocol that they implement in hardware. Using detailed simulations, and by studying carefully applications' memory reference characteristics, we found that a simple cache-coherence protocol, requiring few simple hardware mechanisms, can deliver performance comparable to protocols with higher hardware complexity. The small performance gap is due to the low degree of sharing inherent in applications, and due to the use of performance directives that reduce coherence costs in running these applications.
We also studied the strengths and weaknesses of shared-memory and message-passing mechanisms with respect to running parallel programs efficiently. The study compared equivalent, well-written message-passing and shared-memory programs running on similar hardware. To ensure that our measurements are comparable, we produced two carefully-tuned versions of each program and measured them on closely-related simulators of a message-passing and a shared-memory machine, both of which were based on the same underlying hardware assumptions. We examined the behavior and performance of each program carefully. Although the cost of computation in each pair of programs was similar, synchronization and communication differed greatly. We found that message-passing's advantage over shared-memory is not clear-cut. Three of the four shared-memory programs ran at roughly the same speed as their message-passing equivalent, even though their communication patterns were different.