In this paper, a novel repeater insertion algorithm is presented to minimize the power dissipation of interconnect trees under given timing budgets and slew rate constraints. In contrast to traditional bottom-up dynamic programming approaches, the proposed algorithm combines a Lagrangian relaxation framework and a graph-based search method to derive possible solutions in a top-down fashion. As a result, it is capable of analyzing repeater slew rates efficiently. In addition, our scheme incorporates accurate circuit models and is therefore able to capture the precise delay and slew rate information, leading to high-quality interconnect designs.We have applied our scheme to interconnects of different topologies and various timing and slew rate constraints. Experimental results demonstrate the effectiveness of our approach in comparison with previous low-power repeater insertion schemes. Under tight timing constraints, our scheme can always derive repeater insertion solutions that meet both delay and slew rate requirements, whereas other schemes often fail. Under loose timing constraints, our algorithm achieves up to a 23% average power dissipation reduction for different interconnects specifications with shorter runtimes.

This paper investigates the problem of repeater insertion for low power under a given timing budget. A novel repeater insertion algorithm is proposed to compute the optimal repeater number and width in the discrete solution space, as defined by a given repeater library. Using the proposed algorithm, two practical and highly important questions are addressed. Given a certain tolerance to the degradation of repeater power dissipation: 1) how coarse could the repeater size granularity be? 2) What range should repeater widths be in? The experimental results provide valuable insights into repeater library design. Specifically, the investigation reveals that coarse repeater size granularities can be used to reduce the library size by more than 87% with merely a 4% power degradation. Moreover, for two-pin interconnects with various wire lengths and timing targets, the range of optimal repeater sizes for low power is limited, indicating that a low-cost small-size repeater library, if well designed, is adequate to provide high-quality repeater insertion solutions. The proposed scheme can be used in early design stages to generate a compact repeater library that is passed on to other repeater insertion algorithms.

Previous repeater-insertion algorithms for power minimization of realistic interconnect trees under given timing budgets are often time consuming. In this paper, the problem of runtime reduction for low-power repeater insertion is investigated. Specifically, a power-sensitivity analysis that links the algorithm runtime and the power dissipation result to the selection of repeater library and candidate repeater locations is performed. Based on the analysis, possible repeater locations and potential repeater widths are selected to increase the efficiency of the low-power repeater-insertion algorithm, achieving a judicious tradeoff between runtime and power savings. Moreover, a novel repeater-insertion algorithm based on the Lagrangian relaxation framework is proposed. The proposed algorithm combines a local optimizer based on the dynamic programming (DP) technique and a fast global search engine using the "ellipsoid method." As a result, the proposed approach is capable of producing high-quality solutions at a very fast speed and without manual tuning of the algorithm parameters. A repeater-insertion tool called Freeze, which uses the proposed algorithm, is developed and applied to various interconnect trees with different timing targets. Experimental results demonstrate the high effectiveness of the proposed 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 a speedup of up to 9.1 times with even better power savings. When compared with a DP-based scheme, which guarantees the optimal solution, the proposed tool delivers a speedup of up to 14.6 times with less than 2% power increase on the average

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.

The paper presents a novel repeater insertion algorithm for interconnect power minimization. The novelty of our approach is in the judicious integration of an analytical solver and a dynamic programming based method. Specifically, the analytical solver chooses a concise repeater library and a small set of repeater location candidates such that the dynamic programming algorithm can be performed fast with little degradation of the solution quality. In comparison with previously reported repeater insertion schemes, within comparable runtimes, our approach achieves up to 37% higher power savings. Moreover, for the same design quality, our scheme attains a speedup of two orders of magnitude.

In this paper, we perform the first quantitative study on the sensitivities of repeater power to available repeater width and candidate location, two key parameters of the dynamic programming (DP) based repeater insertion algorithms. Based on our analysis, we propose a simple yet effective scheme to select repeater widths and locations for DP-based algorithms, achieving an excellent trade-off between the solution quality and runtime. Experimental results have shown that, when combined with our sensitivity-guided scheme, the DP algorithm can attain more than 6 times speedup with negligible power degradation.

In this paper, we investigate the problem of repeater insertion for low power under a given timing budget. We propose a novel repeater insertion algorithm to compute the optimal repeater number and width in the discrete solution space, as defined by a given repeater library. Using our algorithm, we show that rounding the solution under the continuity assumption to the closest discrete solution candidate may result in suboptimal designs, or it may even fail to find an existing solution. Given a certain tolerance to the degradation of repeater power dissipation, we address two practical and highly important questions: (1) How coarse could the repeater size granularity be? (2) What range should the repeater size be in?Experimental results demonstrate the high effectiveness of the proposed scheme and provide valuable insights into repeater library design. Our approach achieves up to 23 power reduction in comparison to rounding-based approaches. With a 4 power degradation tolerance, repeater size granularity as coarse as 8 can be used, reducing the library size by more than 87. For interconnects with various wire lengths and timing targets, our investigation reveals that the range of optimal repeater sizes for low-power is limited, indicating that a low-cost small-size repeater library, if well designed, is adequate to provide high quality repeater insertion solutions.

In this paper, we present a simple yet highly effective power macromodeling technique for global interconnects that considers optimal repeater insertion. Specifically,our model estimates the interconnect power dissipation from the interconnect length, the timing budget, the repeater location flexibility, and the signal activity using an analytical function that is derived for a given repeater library and fabrication technology. In experiments with different standard cell libraries, the average error of our technique is less than 2%.