An efficient algorithm for performance-optimal FPGA technology mapping with retiming

It is known that most field programmable gate array (FPGA) mapping algorithms consider only combinational circuits. Pan and Liu [1996] recently proposed a novel algorithm, named SeqMapII, of technology mapping with retiming for clock period minimization. Their algorithm, however, requires O(K3n5log(Kn2)logn) run time and O(K2n2) space for sequential circuits with n gates. In practice, these requirements are too high for targeting K-lookup-table-based FPGA's implementing medium or large designs. In this paper, we present three strategies to improve the performance of the SeqMapII algorithm significantly. Our algorithm works in O(K2 nln|Pv|logn) run time and O(K|Pv|) space, where nl is the number of labeling iterations and |Pv | is the size of the partial flow network. In practice, both nl and |Pv| are less than n. Area minimization is also considered in our algorithm based on efficient low-cost K-cut computation