Novel Approaches to Automatic Hardware Acceleration of High-Level Software

Abstract

Reconfigurable computing combines traditional processors together with FPGAs, creating heterogeneous architectures ripe for massively improving application performance. Yet, hardware development for FPGAs is notoriously difficult and far-removed from software design, leaving this potential unrealised. This thesis explores two major techniques to address this gap. The first technique is the seamless integration of dedicated hardware data structures within existing software applications, an area which has received very little attention. Implementing data structures in hardware and exposing them at run-time, can boost the performance of applications. A case study explored the use of a hardware priority queue in graph algorithms. This implementation attained much better performance characteristics compared to software-only counterparts. Seamless communication between accelerator and the host CPU has been achieved by developing an application abstraction layer with runtime support to choose underlying implementations. This approach increases ease of use given the minimal modifications required to the original application. Moreover, hardware/software co-design is employed to create a hybrid priority queue. This provides tangible benefits, serving as the driver for new features that would be difficult to implement with hardware alone. Complete application experiments showed a moderate overall performance speedup but, more importantly, demonstrated the promise of the concept. The second technique, the major focus of this thesis, is polyhedralassisted accelerator generation for loop kernels. Nested loop kernels consisting of numeric operations is a primary, but non-trivial, target for FPGA acceleration. High-level application synthesis addresses the design challenge by attempting to generate accelerators based on the existing software implementation of the kernel. This thesis extends this concept, using the polyhedral model for the analysis and transformation of the input codes based on a user-specified scattering function. An experimental tool-chain, named polyAcc, was developed which provides a semi-automated implementation of the proposed methodology. The foundation of this approach is the development of an innovative architectural framework that is amenable to the mapping of accelerator codes. One of the novel proposals is a technique for the exploitation of embedded memories on the FPGA to leverage high bandwidth for computation. Polyhedral compilation techniques, driven from the behaviour expressed by input scattering functions, form the basis for scheduling and building the accelerator. The thesis investigates methods to generate the datapath, interconnection network, and the accelerator control program from the target polyhedron schedule. Furthermore, scalability and performance are enhanced by applying pipelining and tiling techniques to the designs. Extensive experimental testing has shown success with different common scientific input kernels. Performance scaled admirably with resource consumption and proved competitive with powerful x86 CPUs.