Rent exponent prediction methods

A wide variety of models for estimating the distribution of on-chip net len gths assume an accurate estimate for an empirical parameter called the Rent exponent. Due to its definition as an exponent, these models are sensitive to its precise value, and careful selection is essential for good estimate s of layout requirements and cycle times. in addition, it is also important to be able to predict changes in the Rent exponent with (possibly disconti nuous) changes in interconnect technology. This paper presents a range of m ethods for estimating the Rent exponents of arbitrarily large gate placemen ts as a function of optimization procedure and the level of fan-out present in the netlist. The first part of the paper describes a rapid algorithmic approach which combines the self-similar, or fractal, attributes of small w iring cells with a Monte Carlo sampling method. This method is shown to acc urately account for variations in both the wiring signature of the netlist and for the effects of most algorithms used for placement optimization. The second part of the paper presents an analytical model for Rent exponent pr ediction, based on a renormalization group transformation. This transformat ion is designed to filter out information which does not contribute to the scale-invariant properties of the optimized netlist enabling the derivation of a closed-form expression for the Rent exponent.