Fast Minimum-Register Retiming via Binary Maximum-Flow

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