A graph theoretic optimal algorithm for schedule compression in time-multiplexed FPGA partitioning
Huiqun Liu, Martin D. F. Wong · International Conference on Computer Aided Design · 1999
This paper presents an optimal algorithm to solve the schedule compression problem, which is an open problem proposed by Trimberger [1] for time-multiplexed FPGA partitioning. Time-multiplexed FPGAs have the potential to dramatically improve logic density by time-sharing logic. Schedule compression is an important step in partitioning for time-multiplexed FPGAs [1,4,9,10] and can greatly influence the quality of the partitioning solution. We exactly solve the schedule compression problem by converting it to a constrained min-max path problem. We further extend our algorithm to minimize the communication cost during schedule compression. Experiments show that our optimal algorithm outperforms the existing heuristics and runs very efficiently.