Mapping-Aware Constrained Scheduling for LUT-Based FPGAs

Scheduling plays a central role in high-level synthesis, as it inserts clock boundaries into the untimed behavioral model and greatly impacts the performance, power, and area of the synthesized circuits. While current scheduling techniques can make use of pre-characterized delay values of individual operations, it is difficult to obtain accurate timing estima-tion on a cluster of operations without considering technol-ogy mapping. This limitation is particularly pronounced for FPGAs where a large logic network can be mapped to only a few levels of look-up tables (LUT). In this paper, we propose MAPS, a mapping-aware con-strained scheduling algorithm for LUT-based FPGAs. In-stead of simply summing up the estimated delay values of individual operations, MAPS jointly performs technology mapping and scheduling, creating the opportunity for more aggressive operation chaining to minimize latency and re-duce area. We show that MAPS can produce a latency-optimal solution, while supporting a variety of design timing requirements expressed in a system of difference constraints. We also present an efficient incremental scheduling technique for MAPS to effectively handle resource constraints. Exper-imental results with real-life benchmarks demonstrate that our proposed algorithm achieves very promising improve-ments in performance and resource usage when compared to a state-of-the-art commercial high-level synthesis tool tar-geting Xilinx FPGAs. 1