Using precomputation in architecture and logic resynthesis

Although tremendous advances have been accomplished in logic synthesis in the past two decades, in some cases logic synthesis still cannot attain the improvements possible by clever designers. This, in part, is a result of logic synthesis not optimizing across register boundaries. We focus on precomputation as a resynthesis technique capable of resynthesizing across register boundaries. By using precomputation, a critical signal is computed earlier in time, thus allowing it to be combinationally optimized with logic from previous pipeline stages. Precomputation automatically discovers some standard circuit transformations like bypassing and lookahead. In addition, precomputation can be used in conjunction with combinational logic synthesis to resynthesize a circuit to obtain better performance. The paper contributes to the understanding and development of precomputation. First, it provides a synthesis algorithm for precomputation. Second, it demonstrates how precomputation can be used to improve sequential logic resynthesis and reports the results of applying a heuristic to a subset of the MCNC benchmarks. Third, it illustrates how precomputation generalizes and unifies bypassing and lookahead-two important and practical architectural transformations often used in processor design and high level synthesis of DSP processors. Finally, it clarifies the relationships among precomputation, retiming, and implicit retiming.