A Fast Code Generator for Point Free Form
Sean Pettge · 2005
Program-optimisation and program-parallelisation are challenging tasks in computer science. These tasks are often made more difficult by the properties of the language used to express program code. Bird-Meertens Formalism (BMF) is a notation designed to ease the task of program transformation by enabling changes to a program through the application of simple rewrite rules. In addition, BMF has many constructs that are readily mapped to parallel architectures. Unfortunately, where the target architecture consists of distributed processors of conventional design, a naive mapping of BMF code to each conventional processor results in large overheads due to repeated copying of potentially large data arrays, as well as frequent allocation and deallocation of memory. There is a need for automated analysis to make this mapping produce more efficient code. This project has focused on this automated translation, starting with the construction of a baseline automated translator that uses a simple mapping, which suffers from the problems outlined above. A more advanced translator was then constructed, which focused on moving the evaluation of routing functions functions which only change the shape of the data, not the data itself into the compiler, rather than having them in the produced program. This technique has produced improvements in both program execution time and memory usage over the baseline system.