Efficient Static Buffering to Guarantee Throughput-Optimal FPGA Implementation of Synchronous Dataflow Graphs

Hojin Kee1,  Shuvra Bhattacharyya1,  Jacob Kornerup2
1Department of Electrical and Computer Engineering, University of Maryland, 2National Instruments Corp.


When designing DSP applications for implementation on field programmable gate arrays (FPGAs), it is often important to minimize consumption of limited FPGA resources while satisfying real-time performance constraints. In this paper, we develop efficient techniques to determine dataflow graph buffer sizes that guarantee throughput-optimal execution when mapping synchronous dataflow (SDF) representations of DSP applications onto FPGAs. Our techniques are based on a novel two-actor SDF graph Model (TASM), which efficiently captures the behavior and costs associated with SDF graph edges (flowgraph connections). With our proposed techniques, designers can automatically generate upper bounds on SDF graph buffer distributions that realize maximum achievable throughput performance for the corresponding applications. Furthermore, our proposed techinque is characterized by low polynomial time complexity, which is useful for rapid prototyping in DSP system design.