For sequential circuits with given initial states, new equivalent initial s
tates must be computed for retiming, which unfortunately is:NP-hard. In thi
s paper, we present a novel polynomial time algorithm for optimal field pro
grammable gate array (FPGA) napping with forward retiming to minimize the c
lock period-with efficient initial state computation, It considers forward
retiming, initial state computation and mapping simultaneously.. Our algori
thm enables a new methodology of separating forward retiming from backward
retiming, Since we guarantee to compute an optimal mapping with forward ret
iming solution, backward retiming can be performed as a preprocessing to tr
y to push hip-hops (FF's) to primary inputs with consideration of only init
ial state computation, Thus, we can avoid the time-consuming iterations bet
ween retiming for clock period minimization and initial state computation.
This algorithm compares very favorably to both conventional approaches of m
apping followed by separate retiming and recent approaches of combined mapp
ing with retiming, but; without consideration of initial state computation
[1], [2], 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 comput
ation in the mapped and retimed circuits with only 2.8% increase in clock p
eriod over the optimal mapping with general retiming solutions, while the i
nitial state computation for the latter solutions may need prohibitively lo
ng runtime for designs with over several hundred FF's.