Concurrent flip-flop and buffer insertion with adaptive blockage avoidance

Given a routing tree for a multi-pin net, two algorithms extending the van Ginneken algorithm (van Ginneken, 1990) for concurrent flip-flop and buffer insertion were presented in (Cocchini, 2002). One algorithm called MiLa targets at minimizing the latency, and the other algorithm called GiLa aims to find a feasible solution subject to given latency constraints imposed on sinks. However, they both do not consider the case where buffer/flip-flop blockages are present. In this paper, we enhance the MiLa algorithm and GiLa algorithm to consider blockage avoidance by finding alternative registered-buffered paths between each internal node inside a blockage and its parent node. The experimental results show that in comparison to the MiLa algorithm, our approach is able to find a solution with the same latency (for about half of the test cases) or even better latency (for the remaining test cases) and the same wirelength, while the buffer/flip-flop usage and CPU time are comparable or acceptable. In comparison to the GiLa algorithm, our approach is able to find a feasible solution for each test case while the Gila algorithm fails to do so for several test cases.