Compiling SA-C to reconfigurable computing systems

Abstract

Field Programmable Gate Arrays (FPGAs) have been available for approximately fifteen years and have experienced speed and density improvements similar to those of microprocessors. Current FPGAs can be reprogrammed in a matter of milliseconds, making them interesting candidates for reconfigurable computing, where specialized circuits can be produced for specific programs to execute more efficiently than a sequential program. Algorithms that are highly regular and exhibit parallelism may benefit from the use of FPGAs. A significant roadblock to this use of FPGAs is the difficult nature of programming them. Hardware description languages have been the predominant tools for creating FPGA circuit configurations, but these languages are low level and require digital circuit expertise its well as explicit handling of timing. To bring FPGAs into mainstream use by conventional programmers, familiar algorithmic language paradigms must be available, with compilers that can convert high level codes to FPGA configurations. This research presents SA-C (derived from "Single-Assignment C"), a pure functional algorithmic language intended for the expression of image processing (IP) applications. SA-C's functional nature makes the compiler's job easier, as compared with imperative languages: parallelism is easy to detect, and analysis and transformations are more straightforward. Perhaps the most important part of the language is its loop window generators, which not only express many IP operations in an elegant way but are highly useful in expressing optimizing transformations within the compiler. A Data Dependence and Control Flow (DDCF) hierarchical graph form is also presented, as an intermediate form with which the SA-C compiler performs its optimizations. These optimizations fall into two broad categories: graph simplifying and loop restructuring. The former are primarily conventional optimizations such as common subexpression elimination and constant folding. The loop restructuring optimizations include loop unrolling, stripmining and fusion, applied as DDCF-to-DDCF transformations using window generators. The compiler, after performing optimizations, is able to convert many inner loops to a low-level, flat dataflow graph designed for translation to VHDL and finally to FPGA configurations. The effects of the compiler's optimizations have been measured on some small kernel codes, and the loop restructuring optimizations are shown to be highly effective.