2008 Research Summary

Maximum-Flow-Based Minimum-Register Retiming

View Current Project Information

Aaron P. Hurst and Alan Mishchenko

The goal of this project is to develop and refine a new formulation of retiming to minimize the number of registers in a design by iterating a maximum network flow problem. Existing methods solve this problem as an instance of minimum-cost network flow, an asymptotically and practically more difficult problem than maximum flow. The new approach is also advantageous because the retiming returned will be the optimum one, which involves the minimum amount of register movement. Furthermore, because all flows are unitary, the problem can be simplified to binary marking. Our algorithm has a worst-case bound of O(R2E), where R is the number of registers and E the number of pair-wise connections. We have demonstrated on a set of circuits that our algorithm is 5x faster than minimum-cost-based methods [1].

We are currently in the process of extending this technique to incorporate constraints on both the performance and initialization behavior of the sequential circuit.

[1]

A. Hurst, A. Mishchenko, and R. Brayton, "Fast Minimum Register Retiming Via Binary Maximum-Flow," Proceedings of the Conference on Formal Methods of Computer Aided Design, 2007.