DocumentCode :
1272581
Title :
Optimal FPGA mapping and retiming with efficient initial state computation
Author :
Cong, Jason ; Wu, Chang
Author_Institution :
Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA
Volume :
18
Issue :
11
fYear :
1999
fDate :
11/1/1999 12:00:00 AM
Firstpage :
1595
Lastpage :
1607
Abstract :
For sequential circuits with given initial states, new equivalent initial states must be computed for retiming, which unfortunately is NP-hard. In this paper, we present a novel polynomial time algorithm for optimal field programmable gate array (FPGA) mapping with forward retiming to minimize the clock period with efficient initial state computation. It considers forward retiming, initial state computation and mapping simultaneously. Our algorithm enables a new methodology of separating forward retiming from backward retiming. Since we guarantee to compute an optimal mapping with forward retiming solution, backward retiming can be performed as a preprocessing to try to push flip-flops (FFs) to primary inputs with consideration of only initial state computation. Thus, we can avoid the time-consuming iterations between retiming for clock period minimization and initial state computation. This algorithm compares very favorably to both conventional approaches of mapping followed by separate retiming and recent approaches of combined mapping with retiming, but without consideration of initial state computation. Our results show that our algorithm can reduce the clock period by 17.5% over conventional approaches of separate mapping with retiming. On the other hand, our algorithm can guarantee efficient initial state computation in the mapped and retimed circuits with only 2.8% increase in clock period over the optimal mapping with general retiming solutions, while the initial state computation for the latter solutions may need prohibitively long runtime for designs with over several hundred FFs
Keywords :
circuit CAD; circuit optimisation; field programmable gate arrays; flip-flops; integrated circuit design; logic CAD; sequential circuits; timing; backward retiming; clock period minimization; field programmable gate array; flip-flops; forward retiming; initial state computation; optimal FPGA mapping; optimal FPGA retiming; polynomial time algorithm; sequential circuits; Algorithm design and analysis; Clocks; Data preprocessing; Field programmable gate arrays; Flip-flops; Minimization; Polynomials; Runtime; Sequential circuits; Simultaneous localization and mapping;
fLanguage :
English
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
0278-0070
Type :
jour
DOI :
10.1109/43.806805
Filename :
806805
Link To Document :
بازگشت