My research interests include programming languages and compilers for parallel architectures.
In the area of programming languages, my students and I have worked on using declarative languages, such as functional and logic programming languages, for programming parallel machines. Conventional languages like FORTRAN are designed around the notion of global, updatable store, and parallelism in such programs is constrained by so-called false dependencies that arise from reuse of storage locations. In contrast, parallelism in declarative language programs is constrained only by true dependencies. Our work in this area has focused on incorporating ideas from logic programming languages, specifically logic variables, into functional languages. This permits the programmer to build data structures incrementally without suffering the well-known copy overhead incurred in building data structures incrementally using purely functional constructs. An open problem in this area was the formulation of a proper semantic account of functional languages with logic variables. In recent work, we have shown how such languages can be given a formal denotational semantics and have shown that the resulting semantics is fully abstract with respect to the operational semantics. In the process, we have invented new semantic techniques relating equation solving to properties of closure operators on Scott domains; these techniques are now being used in the logic programming community to give semantics to constraint-based logic programming languages.
In the area of compiling, we have developed restructuring techniques for compiling programs to distributed memory and non-uniform memory access (NUMA) architectures like the Intel iPSC/i860 and KSR-1. Memory in these architectures can be viewed as a hierarchy in which a processor can access local memory faster than it can access non-local memory. To get good performance on such architectures, the compiler must not only decide what should be done in parallel but must also ensure locality of reference by matching code and data distribution; when non-local references must be made, it is preferable to transfer data using block transfers rather than by using many small messages. We have developed a novel loop restructuring technique called access normalization which transforms loop nests for increased locality and potential for block transfers. We are implementing these ideas in a restructuring compiler that takes FORTRAN programs as input and produces code for the iPSC/i860 and the BBN Butterfly.
Our experience in writing aggressive compilers has led us to invent a new framework for program analysis and optimization. This new framework is based on a program representation called the dependence flow graph (DFG). The DFG knits together the data and control dependence information of a program, and permits the development of fast optimization algorithms that generate better code than is possible with competing approaches. Our investigations into the dependence flow graph have produced results that are of independent interest; for example, we have recently invented a fast algorithm that computes the control dependence graph of a program in time linear to the size of the program, thereby solving a problem that has been open for almost a decade. We are working closely with a number of compiler groups in the industry to transfer this technology to them.