Balanced Scheduling and Operation Chaining in High-Level Synthesis for FPGA Designs

David Zaretsky1,  Gaurav Mittal1,  Robert Dick2,  Prith Banerjee1
1University of Illinois at Chicago, 2Northwestern University


Abstract

In high-level synthesis for FPGA designs, scheduling and chaining of operations for optimal performance remain challenging problems. In this paper, we present a balanced scheduling routine that uniformly distributes operations across states to reduce critical timing paths in the absence of accurate functional unit delay models. On average, results show improvements in frequency and run times for balanced scheduling over ASAP, ALAP, and force-directed scheduling. Additionally, we provide a methodology for precision-based delay modeling of operations. We present a balanced chaining routine that, given a target frequency, uses this modeling technique to reduce the number of clock cycles in the design. Experimental results show approximately 20% improvement on average in run times when incorporating our balanced chaining routine with scheduling. Incorporating balanced chaining in a high-level synthesis tool allowed performance improvements ranging from 8–29× for large, complex applications. Accordingly, our method for modeling operation delays is shown to be accurate in estimating delays for operation chaining during high-level synthesis.