Title :
An efficient algorithm for performance-optimal FPGA technology mapping with retiming
Author :
Cong, Jason ; Wu, Chang
Author_Institution :
Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA
fDate :
9/1/1998 12:00:00 AM
Abstract :
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
Keywords :
equivalent circuits; field programmable gate arrays; iterative methods; logic CAD; logic partitioning; minimisation of switching nets; sequential circuits; table lookup; timing; FPGA technology mapping; O(K|Pv|) space; O(K2nln|Pv|logn) run time; SeqMapII algorithm; area minimization; labeling iterations; lookup-table-based FPGA; low-cost K-cut computation; partial flow network; performance-optimal FPGA technology; retiming; sequential circuits; Circuit synthesis; Clocks; Combinational circuits; Field programmable gate arrays; Iterative algorithms; Minimization; Programmable logic arrays; Sequential circuits; Space technology; Table lookup;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
