In this paper, Cong and Zhang introduce a new approach for behavioral scheduling that is scalable, efficient, and relatively simple based on a “system of difference constraints”. This ILP formulation can handle a large variety of different optimization constraints, including data and resource constraints, frequency and relative timing constraints, latency constraints and more. The LP formulation guarantees an integer solution and the authors prove that their ILP formulation was specifically designed to allow it to be solved in polynomial time, providing a high-quality solution much faster than previous ILP schedulers. The authors also demonstrate scheduling results that are superior to the state of the art academic behavioral system at the time of the publication.
In the past 16 years since this has been published, this scheduling approach has become widely used in modern HLS tools, and has enabled these tools to provide fast, high-quality, and scalable scheduling solutions. The SDC scheduling approach has served as the basis for many subsequent works, including research work that has focused on pipelined modulo scheduling [1], scalable optimal scheduling [2], specialized HLS schedulers and more, and continues to be used in many of the latest HLS research papers.
[1] A. Canis, S. D. Brown and J. H. Anderson, “Modulo SDC scheduling with recurrence minimization in high-level synthesis,” 2014 24th International Conference on Field Programmable Logic and Applications (FPL), 2014, pp. 1-8, doi: 10.1109/FPL.2014.6927490.
[2] Steve Dai, Gai Liu, and Zhiru Zhang. 2018. A Scalable Approach to Exact Resource-Constrained Scheduling Based on a Joint SDC and SAT Formulation. In Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA ’18). Association for Computing Machinery, New York, NY, USA, 137–146. DOI:https://doi.org/10.1145/3174243.3174268
Endorsement by: Jeff Goeders and Mike Wirthlin, Brigham Young University