Home → Thesis and sources → Thesis Summary

Thesis Summary

Rule-based Compilation of Data-parallel Programs

Certain computational problems are too big or complex for a conventional single-processor system to solve in a reasonable amount of time. In such cases, parallel computing is an approach that might be considered instead: by having several processors work on the problem simultaneously, the total execution time can be brought down to acceptable levels.

Unfortunately, writing explicitly parallel programs is a skill that does not come very naturally to human beings. It is difficult to correctly keep track of the different parallel program threads, and the need for communication and synchronisation between these programs only adds to the complexity.

This is why much research has gone into the creation of high-level parallel programming languages in which the user is shielded from (too much) explicit parallelism. These languages allow the programmer to pretend to a considerable extent that they are working in a conventional, single-thread model of computation.

This has been a quite successful approach as far as the applications programmer is concerned, but under the hood the complexity and the programming difficulties have not gone away, but have merely been shifted around. The high-level programs must still somehow be converted to explicitly parallel applications, only now it is the compilation software, not the programmer, that is responsible for achieving this, preferably in a manner that will lead to highly efficient target code. Consequently, compilation techniques for parallel programming languages have also become a fruitful area for research. Both the compilation algorithms themselves, and the way in which they can be specified by the compiler builder are of interest.

This thesis investigates particular technologies that can make the task of writing compilers for parallel programming languages more manageable and less error-prone. A compiler-generator framework called Rotan is described. Rotan can be used to create a programmable compiler for a programming language. This compiler can be programmed by the compiler builder in a high-level, pattern-matching transformation language called the Rule Language. This turns the compiler from the conventional static ‘black box’ systems into a more dynamic, open transformation system, that allows easy and modular experimentation, debugging, and extension of compilation and optimisation algorithms.

Chapter 1 (Introduction) contains a general introduction to the thesis and discusses the research question.

In Chapter 2 (Data Parallelism) we give a brief general introduction to parallel programming, followed by a closer explanation of the data-parallel programming model that will be the focus for the remainder of the thesis. In data-parallel programming, the programmer specifies the distribution of data over the processors. It is left to the compiler to choose and implement the efficient distribution of the actual computations over the processors, and this is precisely where the challenge lies.

In Chapter 3 (Compiler Construction Tools) existing compilation models for sequential and parallel programming are described, and an overview of existing compilation tools and approaches is given. This chapter also contains a review of general-purpose transformation systems. The programmable compiler framework called the Rotan system is proposed as a means of obtaining the levels of flexibility, expressive power, and maintainability a compiler for (data-)parallel programming languages requires.

Chapter 4 (The Rule Language) introduces the Rule Language, the rule-based transformation language that forms one of the key components in the Rotan framework. The Rule Language allows the compiler builder to implement translations and optimisations by specifying them as high-level transformations on the parse tree of a source program. This chapter explains the syntax and gives an informal operational semantics of the Rule Language as implemented in the current Rotan prototype.

Chapter 5 (A Rotan Compiler for Vnus) describes the major test case for the Rotan system: an implementation of a semi-automatically parallelising compiler for the Vnus language. Vnus is a programming language used as an intermediate format in the compilation process of higher-level (data-)parallel programming languages; the word ‘semi-automatic’ signifies the fact that the compiler has help during translation, in the form of the data distributions specified by the user. The parallelisation and communication schemes used in this compiler are discussed, and examples of their implementation as rewrite rules are given.

Chapter 6 (Experimental Results) presents a number of case studies in which the Vnus compiler described in Chapter 5 is applied to data-parallel Vnus programs. Since a higher abstraction level is generally associated with a decrease in efficiency, this chapter investigates the extent to which this holds true for the target code generated by the Rotan Vnus compiler. The performance results of these programs are then compared to those achieved by other compilers. As it turns out, there is indeed a performance penalty, but one that remains within the bounds of acceptability.

Chapter 7 (Evaluation) evaluates the experiences with the general Rotan system both in terms of its own design criteria as well as in comparison to a different compilation system in use at the Delft University of Technology. The evaluations show that the expected advantages of a high-level, rule-based compilation system are real and significant.

Chapter 8 (Conclusion) finishes with a summary and discussion of the presented research topics, concluding with some suggestions for future research directions.

Leo Breebaart