Optimal FPGA mapping and retiming with efficient initial state computation

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.