James M. Stichnoth

Generating Code for High-Level Operations through Code Composition Degree Type: Ph.D. in Computer Science
Advisor(s): Thomas Gross
Graduated: August 1997

Abstract:

A traditional compiler translates each expression or statement in a high-level language into a sequence of lower-level target statements (e.g., operations in an intermediate representation, or machine instructions), in a manner fixed by the compiler writer. The output is then subject to further optimization. This compilation strategy is called custom code generation, as the compiler generates custom code for each input construct.

An alternative strategy is to generate a call to a runtime library for each high-level language construct. This approach is attractive if the source language contains complex, powerful constructs, like the distributed array assignment statement in High Performance Fortran (HPF). The decision between custom code generation and use of a runtime library involves tradeoffs between efficiency (performance of the generated code), maintainability (ease of developing and maintaining the algorithm), and generality (implementation of the general case, rather than merely a simplified canonical case).

I introduce a new compilation strategy, high-level code composition, which combines the advantages of custom code generation and runtime libraries. The compilation of each construct is controlled by code templates, which contain both target code to be generated and compile-time control instructions that specify how the templates are composed together. The templates are external to the compiler, making them easy to write and modify. The composition system executes the control code at compile time, automatically generating and optimizing the code to be executed at run time.

In this dissertation, I motivate and explore the language and implementation issues of code composition. I describe Catacomb, my implementation of a composition system, which integrates with a high-level compiler to generate custom C code. I describe the challenges in enabling Catacomb to automatically generate the best code without sacrificing a clean user model. In addition, I develop a framework for the HPF array assignment, allowing an arbitrary array assignment algorithm to be coupled with an arbitrary communication architecture to form a complete implementation. This framework leads to the first compilation system that can incorporate and compare several array assignment algorithms on several communication architectures, for the fully general array assignment statement.

Thesis Committee:
Thomas Gross (Chair)
David R. O’Hallaron
Jaspal Subhlok
Joel Saltz (University of Maryland)

James Morris, Head, Computer Science Department
Raj Reddy Dean, School of Computer Science

Keywords:
Compilers, code generation, parallelism, communication generation