Freeze: engineering a fast repeater insertion solver for power minimization using the ellipsoid method

This paper presents a novel repeater insertion algorithm for the power minimization of realistic interconnect trees under given timing budgets. Our algorithm judiciously combines a local optimizer based on the dynamic programming technique and a global search engine using the ellipsoid method. As a result, our approach is capable of producing high-quality solutions at a very fast speed. Furthermore, our scheme is robust and does not need any manual tuning of the iteration-control parameters. We have developed a repeater insertion tool, called Freeze, using the proposed algorithm and applied it to various interconnect trees with different timing targets. Experimental results demonstrate the high effectiveness of our approach. In comparison with the state-of-the-art low-power repeater insertion schemes, Freeze requires 5.8 times fewer iterations on the average, achieving up to 27 times speedup with even better power savings. When compared with a dynamic programming based scheme, which guarantees the optimal solution, our tool delivers up to 50 times speedup with 0.9% power increase on the average.