Performance optimization of pipelined circuits

The problem of minimizing the cycle time of a given pipelined circuit is considered. Existing approaches are sub-optimal since they do not consider the possibility of simultaneously resynthesizing the combinational logic and moving the latches using retiming. In the work of S. Malik et al. (Proc. of the Hawaii Inter. Conf. on System Sciences, 1990) the idea of simultaneous retiming and resynthesis was introduced. The authors use the concepts presented in that work to optimize a pipelined circuit to meet a given cycle time. Given an instance of the pipelined performance optimization problem, an instance of a combinational speedup problem is constructed. A constructive proof is given that the pipelined problem has a solution if and only if the combinational problem has a solution. This result is significant since it shows it is enough to consider only the combinational speedup problem and all known techniques for that domain can be directly applied to generate a solution for the pipelined problem.