Compiling C-like Languages to FPGA Hardware: Some Novel Approaches Targeting Data Memory Organisation

Qiang Liu, George A. Constantinides, Konstantinos Masselos, Peter Y. K. CheungBCS Int. Acad. Conf 2008 · OpenReview

Abstract

BCS, The Chartered Institute for IT, promotes wider social and economic progress through the advancement of information technology science and practice. BCS serve over 68,000 members including practitioners, businesses, academics and students, in the UK and internationally.

Introduction

Field-Programmable Gate Arrays (FPGAs) provide a platform for massive parallel computation, yet they are notoriously difficult to program. While High-Level Synthesis (HLS) tools aim to bridge this gap by allowing developers to use C-like languages, they frequently encounter the "memory wall." Computationally intensive kernels are often limited by off-chip memory bandwidth. Traditional HLS compilers typically optimize the datapath and memory subsystem in isolation, which can lead to inefficient hardware. If parallelism is prioritized, the required memory bandwidth may exceed chip capacity; conversely, prioritizing memory reuse can unnecessarily restrict parallelism. This research addresses this challenge by introducing a framework that concurrently optimizes memory organization and loop parallelization.

Methodology

The proposed framework employs a two-pronged algorithmic strategy to navigate the complex design space of FPGA hardware:

  1. Modular Address Mapping: To minimize the on-chip memory footprint, the authors move away from sparse, directly generated address functions. By applying formal methods such as Fourier-Motzkin elimination and Smith Normal Form, they derive modular mappings. This ensures that on-chip "scratch-pad" buffers are precisely sized to the unique data elements required, eliminating redundancy and reducing memory requirements by up to 30 times.
  2. Joint Optimization via Geometric Programming: The interdependence between buffer placement (at specific loop levels) and loop "strip-mining" for parallelism is modeled as an integer geometric programming problem. This mathematical formulation allows the framework to minimize execution cycles while strictly adhering to hardware constraints, such as the number of available on-chip RAM blocks.

Results and Discussion

The framework was evaluated using the Full Search Motion Estimation (FSME) algorithm, a standard video processing kernel, synthesized for a Xilinx XC2v8000 FPGA.

The automated exploration capability of the framework is demonstrated in the design space analysis. By utilizing a geometric programming solver, the system efficiently identifies the Pareto frontier—the set of designs offering the best performance for any given memory budget.

Design space exploration showing the Pareto frontier of proposed designs versus other possibilities.

Key performance metrics indicate significant advantages over traditional methods. The optimized FPGA design achieved a 33x speedup compared to a 2.8 GHz general-purpose CPU. Most notably, the joint optimization approach demonstrated a 4.3x performance improvement over the "FRSP" method, which optimizes data reuse and parallelism sequentially.

Comparison of execution time between the proposed framework and the decoupled FRSP method, highlighting the 4.3x improvement.

Conclusion

This work demonstrates that the interdependency between memory organization and parallelism is a critical factor in FPGA HLS. By jointly optimizing these elements through modular mapping and geometric programming, developers can achieve substantial performance gains and memory efficiency. Future research will focus on extending this framework to support non-affine loop structures and more complex multi-channel memory architectures.

Summary updated

Abstract

BCS, The Chartered Institute for IT, promotes wider social and economic progress through the advancement of information technology science and practice. BCS serve over 68,000 members including practitioners, businesses, academics and students, in the UK and internationally.
BibTeX
@inproceedings{liu2008compiling,
  author = {Qiang Liu and George A. Constantinides and Konstantinos Masselos and Peter Y. K. Cheung},
  title = {{Compiling C-like Languages to FPGA Hardware: Some Novel Approaches Targeting Data Memory Organisation}},
  booktitle = {BCS Int. Acad. Conf},
  year = {2008},
  url = {https://openreview.net/forum?id=EekAaQjfbv},
}

Loading related content...

Figure