Three Specialized Computer Architectures for Functional Program Execution

Sammanfattning: Functional programming languages offer a new programming paradigm with many advantages over the more conventional imperative or procedural programming languages. However, these new languages are not as well adapted to the existing computers as the conventional languages, which results in low performance. They also offer many opportunities for parallel execution of subcomputations which are not always easy to exploit in conventional computers.

This has triggered efforts to be made in two directions to bridge the gap between computers and functional languages. The first direction is to develop new program compilation techniques and the second is to develop new computer architectures, i.e. new program execution models and organizations for computers. Both these directions are necessary and complement each other.

This thesis presents investigations of three different attempts to develop computer architectures that are intended to support the execution of functional programs. This work has involved development of architectures, programming methods and performance analysis. The investigations have been performed within three separate projects.

The first project presented is an attempt to design a microprocessor implementation of the G-machine, a functional language execution model adapted for implementation in conventional architectures. Performance estimates for the processor architecture show a slightly better performance than what can be achieved with a G-machine implementation on a state-of-the-art work station.

The second project is an attempt to design an accelerator for frequently used smaller parts of functional programs. The results include an architecture that consists of several simple processors and a compilation technique that allows some functional programs to be automatically compiled for the architecture. The architecture was found to give about ten to fifty times speed-up compared to a work station. However, the restrictions imposed on the types of computations that can be executed are too severe to make the architecture truly useful.

The third project extends the ideas in the previous project and allows a wide range of computations written in a functional language to be executed on a so-called processor array architecture. This type of architecture has many interesting properties such as being well adapted for VLSI implementation, having a high potential for fault tolerance, and being capable of exploiting fine-grained parallelism. However, they have traditionally been used mostly for specialized applications. The basic idea in this project is to compile functional programs into so-called data flow graphs which are mapped onto a processor array so that each processor is assigned the execution of one operation in the program. A performance analysis of the architecture is presented that shows that the utilization of hardware resources in the architecture is low for applications not usually executed on processor arrays. The reasons for this are discussed and methods to improve the utilization are presented.