Automatic compilation of field programmable custom compute accelerators

grantor: University of TorontoHigh performance can be obtained on field-programmable custom computers for applications by implementing computational kernels in hardware. Significant speedups can be obtained by mapping time critical computations in the source program in hard-wired logic, and creating multiple specialized functional units in FPGAs to exploit parallelism in the program. However, design of these machines is an expensive and time consuming task and must be performed once for each given application. This dissertation describes a compiler, 'PECompiler', that generates both hardware and control software for field-programmable compute accelerators. The first goal of our compiler is to automate the design process of implementing a specialized computer for each given application. The second goal of the compiler is to exploit intrinsic parallelism in the source program that contains irregular patterns of computations. To attain these goals, we introduced a new design methodology for configurable custom computers, and created a parameterized architecture for modeling hardware features of accelerators. Through compiling the source code of an application together with part of its input, 'PECompiler' can determine the specialized processing units required by an application program, create design descriptions, expose hidden parallelism by analyzing data dependencies in the source code, and produce instruction sequences to run on the customized accelerator. Partial evaluation is the key technique that enables the compiler to optimize source code using part of the program's input. In order to generate the instructions for each application, we developed a heuristic algorithm to determine an optimized sequence for the computations to execute on the accelerator. We also developed a new algorithm to handle register allocations during the process of scheduling operations to run on the accelerator. We used 'PECompiler' to generate designs of customized accelerators for two applications, and compared the performance of each program running on the accelerator with the program running on the general-purpose computer. The results of the experiments showed that significant speedups were achieved for both applications. To provide the insight for designers for implementing the accelerators on an FCCM, we also studied several architectural issues in the accelerators, and demonstrated the impact to the performance caused by these issues.Ph.D