Rent's Rule

Rent's Rule pertains to the organization of computing logic, specifically the relationship between the number of external signal connections to a logic block (i.e., the number of "pins") with the number of logic gates in the logic block, and has been applied to circuits ranging from small digital circuits to mainframe computers.

E.F. Rent's Discovery and First Publications

In the 1960's, E.F. Rent, an IBM employee, found a remarkable trendbetween the number of pins (terminals T) at the boundaries of
integrated circuit designs at IBM and the number of internal components (g),such as logic gates or standard cells. On a $log-log$ plot, these datapointswere on a straight line, implying a power-law relation $T\; =\; t\; g^p$ wheret and p are constants (, and generally ).Rent disclosed his findings in IBM-internal memoranda, but the relation was describedin 1971 by Landman and Russo [1] . They performed a hierarchical circuit partitioningin such a way that at each hierarchical level (top-down) the least number ofinterconnections had to be cut to partition the circuit (in more or less equal parts).At each partitioning step, they noted the number of terminals and thenumber of components in each partition and then partitioned the sub-partitions further.They found the power law rule applied to the resulting T versus g plot and named it"Rent's rule".It is crucial to recognise that Rent's rule is an empirical result based on observations of existing designs, and therefore it is less applicable to the analysis of non-traditional circuit architectures. Having said that, it does provide a useful framework with which to compare similar architectures.

Theoretical Basis

Christie and Stroobandt [2] later derived Rent's rule theoreticallyfor homogeneous systems and pointed out that the amount of optimizationachieved in placement is reflected by the parameter $p$,the "Rent exponent", which also depends on the circuit topology. In particular, values correspond to a greater fraction of short interconnects.The constant t in Rent's rule can be viewed as the average numberof terminals required by a single logic block since $T\; =\; t$when $g\; =\; 1$.

Special Cases and Applications

Random arrangement of logic blocks typically have $p=1$.Larger values are impossible since the maximum number of terminalsfor any region containing g logic components in a homogeneous system isgiven by $T\; =\; t\; g$. Lower bounds on p depend on the interconnectiontopology since it is generally impossible to make all wires short.This lower bound $p*$ is often called the "intrinsic Rent exponent",a notion first introduced in [3] . It can be used to characterizeoptimal placements and also measure the interconnection complexityof a circuit. Higher (intrinsic) Rent exponent values correspondto a higher topological complexity. One extreme example ($p=0$)is a long chain of logic blocks, while a clique has $p=1$.In realistic 2D circuits, $p*$ ranges from 0.5 forhighly-regular circuits (such as SRAM)to 0.75 for random logic [4] .

Estimating Rent's Exponent

To estimate Rent's exponent, one can use top-down partitioning,as used in min-cut placement. For every partition, countthe number of terminals connected to the partition andcompare it to the number of logic blocks in the partition.Rent's exponent can then be found by fitting these datapointson a log-log plot, resulting in an exponent p'.For optimally partitioned circuits, $p\text{'}\; =\; p*$but this is no longer the case for practical (heuristic)partitioning approaches. For partitioning-based placementalgorithms $p^*\; leq\; p\text{'}\; leq\; p$ [5] .

Region II of Rent's Rule

Landman and Russo found a deviation of Rent's rule near the"far end", i.e., for partitions with a large number of blocks, which isknown as "Region II" of Rent's Rule [1] . A similar deviation exists atfor small partitions, and has been found by Stroobandt [6] who calledit Region III.

Rentian Wirelength Estimation

Another IBM employee, Donath, discovered that Rent's rule can be usedto estimate the average wirelength and the wirelength distributionin VLSI chips [8,9] . This motivated the System Level Interconnect Predictionworkshop, founded in 1999, and an entire community workingon wirelength prediction (see a survey in [7] ). The resultingwirelength estimates have been improved significantly sincethen and are now used for "technology exploration" [10] .The use of Rent's rule allows to perform such estimates "a priori"(i.e., before actual placement) and thus predict the propertiesof future technologies (clock frequencies, number of routing layers needed,area, power) based on limited information about future circuits andtechnologies.

A comprehensive overview of work based on Rent's rule can be found in [11] and [7] .

References

1. B. S. Landman and R. L. Russo, [http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1671752 On a Pin Versus Block Relationship For Partitions of Logic Graphs] , IEEE Trans. on Comput., col. C-20, pp. 1469-1479, 1971.
2. P. Christie and D. Stroobandt, doi-inline|10.1109/92.902258|The Interpretation and Application of Rent's Rule, IEEE Trans. on VLSI Systems, Special Issue onSystem-Level Interconnect Prediction, vol. 8, no. 6, pp. 639-648, 2000.
3. L. Hagen, A. B. Kahng, F. J. Kurdahi and C. Ramachandran, doi-inline|10.1109/43.273752|On the Intrinsic Rent Parameter and Spectra-based Partitioning Methodologies, IEEE Trans. on Comput.-Aided Des., IntegratedCircuits & Syst., vol. 13, no. 1, pages 27 - 37, 1994.
4. R. L. Russo, On the Tradeoff Between Logic Performance andCircuit-to-Pin Ratio for LSI, IEEE Trans. Comput., vol. C - 21,pages 147 - 153, 1972.
5. P. Verplaetse, J. Dambre, D. Stroobandt, and J. Van Campenhout, doi-inline|10.1145/368640.368665|On Partitioning vs. Placement Rent Properties, Intl. Workshop onSystem-Level Interconnect Prediction (SLIP 2001), pp. 33 - 40, March 2001.
6. D. Stroobandt, doi-inline|10.1109/GLSV.1999.757445|On an efficient method for estimating the interconnection complexity of designs and on the existence of region III in Rent's rule, Proc. 9th Great Lakes Symposium on VLSI, pp. 330 - 331, 1999.
7. D. Stroobandt, "A Priori Wire Length Estimates for Digital Design". Kluwer Academic Publishers. ISBN 0-7923-7360-X. 2001. pp. 298.
8. W. E. Donath, [http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1084635 Placement and Average Interconnection Lengths of Computer Logic] , IEEE Trans. Circuits & Syst., vol. CAS-26, pp. 272 - 277, 1979.
9. W. E. Donath, [http://www.research.ibm.com/journal/rd/252/ibmrd2502a3H.pdf Wire Length Distribution for Placements of Computer Logic] , IBM J. of Research and Development, vol. 25, pp. 152 - 155, 1981.
10. A. E. Caldwell, Y. Cao, A. B. Kahng, F. Koushanfar, H. Lu, I. L. Markov,M. Oliver, D. Stroobandt, and D. Sylvester, doi-inline|10.1145/337292.337617|GTX: The MARCO GSRC Technology Extrapolation System, IEEE/ACM Design Automation Conf., pp. 693 - 698, June 2000.
11. D. Stroobandt, Recent Advances in System-Level InterconnectPrediction, IEEE Circuits and Systems Society Newsletter,vol. 11, no. 4, pages 1; 4-20; 48, December 2000. Invited.Available at http://www.nd.edu/~stjoseph/newscas/.

See also

*Electronic design automation
*Integrated circuit design --------Adapted from [http://www.elis.ugent.be/~dstr/ Dirk Stroobandt] 's column in the ACM [http://www.sigda.org SIGDA] [http://www.sigda.org/newsletter/index.html e-newsletter] by [http://www.eecs.umich.edu/~imarkov/ Igor Markov]
The original text can be found athttp://www.sigda.org/newsletter/2006/060401.txt