Generalizations of the Rent Rule

1. Introduction

As System-on-Chip (SoC) architectures incorporate billions of transistors, the ability to accurately predict design properties has become paramount ${}^5$. Early-stage architectural design and physical synthesis rely heavily on robust models that quantify the relationship between logic complexity and the communication requirements between disparate system blocks.

The foundational model in this domain is Rent's Rule ${}^1$. Discovered empirically by E. F. Rent at IBM and later formalized by Landman and Russo ${}^2$, the rule establishes a power-law relationship between the number of external signal connections (terminals) to a logic block and the number of internal components (gates or standard cells) it contains:Where:
• $T$: Number of external terminals (pins) of the block.
• $g$: Number of internal logic components (gates/cells).
• $K$: Rent's empirical constant (average pins per block).
• $p$: Rent exponent ($0<p<1$).

While Rent's Rule is an indispensable tool for wire length ${}^3{,}^4$ and placement optimization, its empirical origins lead to inherent limitations—especially when applied to modern, heterogeneous architectures. This paper discusses New Law ${}^5$ and a new generalization, which addresses these shortcomings by incorporating explicit structural constraints, extending its utility to the next generation of complex computing systems.
________________________________________
2. Overview of Rent's Rule and Current Drawbacks
2.1. Applications and Interpretation

Rent's Rule describes a statistical self-similarity in digital systems. The Rent exponent ($p$) provides insight into a design's topological complexity:
• $p\approx 0.4$: Highly regular structures.
• $p\approx 0.5$: Structured designs with high locality (e.g., SRAM).
• $p\approx 0.75$: "Random logic" or complex, unstructured designs.

2.2. Limitations

The power-law form suffers from two primary drawbacks ${}^6{,}^8$:
1. Terminal Constraint Deviation (Region II) ${}^7$: The power law breaks down as partitions approach the total system size ($>25\%$ of the chip). Physical I/O pins are finite; thus, the log-log plot flattens as $g$ approaches $N$.
2. Undefined Constants: There is an absence of methodology relating design metrics to the empirical constants $K$ and $p$.

________________________________________
3. The New Rule: Generalization for Autonomic Systems

We utilized a graph-mathematical model to generalize Rent’s Rule, specifically addressing its limitations when applied to autonomic systems. We demonstrated that the classical power-law form of Rent’s Rule is valid only under the restrictive conditions where the system contains a large number of blocks, and the number $g$ of internal components in a block is much smaller than the total number of components ($N$) in the entire system ${}^9$.

The generalized formulation, referred to as the New Graph-based Rule, extends the applicability of the scaling law across the entire range of partition sizes, including the problematic Rent's Region II. The New Rule is expressed as ${}^9{,}^{10}{,}^{11}$:Where:
• $T$ is the number of external terminals for the block partition.
• $N$ is the total number of components in the system.
• $g$ is the number of components in the block partition.
• $t$ represents the average number of pins of a component in the system.
• $P_g$ is the generalized Rent exponent, derived by the described graph-partitioning method.

The rule was derived by modeling the system as a graph, where each component is represented as a vertex, and each net is represented as a tree connecting its components.

Figure 1. "All Net Components Are in the Block" illustrates the case when a net connects three components ($A$, $B$, and $C$) and is represented as a net tree. In this example, all net components are in the same block; thus, there is no need for a block external terminal—none of the net edges exit the block.

Figure 2. "An external terminal" illustrates the same case, but only components $A$ and $B$ are in the same block, while component $C$ is located in another block. In this scenario, an edge exits the block to connect to component $C$, necessitating a block external terminal for the net under consideration.

3.1. Derivation Logic

Initially, we assumed that each block has randomly assigned components. Under this assumption, the probability $Q^{\prime }$ that a given pin of a given component has an edge to another component outside of the block is:If the net has only two components to connect (the net tree is a single edge), the above formula is straightforward. In this case, the edge goes outside the block, creating one block terminal. If the net has $m>2$ pins to connect, we still have only one outside terminal—all components of the net within the block are connected by an internal net-tree, requiring only one tree edge to exit the block.

Because the component under consideration has $t$ pins on average, the probability $Q$ that the component will have $t$ edges (block terminals) to components in other blocks is:With $g$ components in the block, the number of expected block terminals is:The drawback of formula $[2]$ is the assumption of random component assignment. In reality, blocks are not designed randomly; highly connected components are partitioned into the same block to minimize communication overhead. Therefore, formula $[2]$ produces conservative results. To account for the effect of optimized partitioning that minimizes terminals, we introduce a correction constant $P_g<1$ (analogous to the Rent exponent), which reduces the estimated number of terminals:

By substituting the variables from $[2]$ into $[3]$, we arrive at the generalized New Rule $[1]$.

3.2. Behavioral Cases

• Case 1 ($g=1$): Simplifies to $T=t$, matching classical expectations.
• Case 2 ($g=N/2$): Yields the maximum terminal count, reflecting the peak communication requirement when a system is halved.
• Case 3 ($g=N$): $T=0$. This accurately models Region II, as a closed system has no external signals.

________________________________________
4. A Hypergraph Model

Above, we utilized a graph-mathematical model to generalize Rent’s Rule. We will show that if we use a hypergraph model of the system, we can further improve the accuracy of the generalized Rent’s Rule by taking into account an additional and known design property: the average number of components, $m$, that a net connects.

Let’s represent a net that connects $m$ pins as a hyperedge, instead of a tree as used in the previous graph-based model. Note that $m$ is a known design property and is the average value that can be obtained for any real design.

Figure 3. "All three components and the hyperedge are within the Block" illustrates the case when a net connects three components ($A$, $B$, and $C$) and is represented as a hyperedge (an oval encompassing all components). In this example, all net components are in the same block, and there is no need for a block external terminal—the hyperedge does not cross the block boundary.

4.1. Hypergraph Derivation

Again, let’s initially assume that each block has randomly assigned components. Then, the probability $V^{\prime \prime }$ that a given pin of a given component within the block is connected to another component within that same block is:The probability $V^{\prime }$ that the remaining $m-1$ vertices (components) within the hyperedge are all located in the block (resulting in no block terminal for this net) is:This implies that the probability $Q^{\prime }$ that the hyperedge will exit the block (necessitating a block terminal) is:Because the component under consideration has $t$ pins on average, the probability $Q$ that the component will have $t$ hyperedges (block terminals) connecting to components in other blocks is:The above formula reflects the physical reality that the more components of a net are located within the block, the lower the probability that the net will exit the block. If all $m$ components of a net are in the block, the net requires no block terminal.
With $g$ components in the block, the number of expected block terminals is:Again, the drawback of formula $[3]$ is the assumption of random component assignment. In reality, highly connected components are partitioned together to minimize external terminals. Thus, formula $[3]$ produces conservative results. To account for optimized partitioning, we introduce a correction constant $P_h<1$ (similar to $P_g$) to reduce the estimated number of terminals:After substituting the variables into $[4]$, we arrive at the New Hypergraph-based Rule:It is easy to see that if each net connects only two components ($m=2$), the New Hypergraph-based Rule becomes equivalent to the New Graph-based Rule.

Our comparative study of graph-based versus hypergraph-based rules showed that the hypergraph model is approximately 1.2% more accurate.

Figure 4. "Comparison of the Rules" illustrates a comparison of Rent’s Rule against the new generalizations.

Properties used: $N=10,000$; $K=4$; $P_{rent}=0.6$; $t=4$; $P_g=0.6$; $m=3.2$; $P_h=0.23$.

4.2 Justification Summary

The following final points support the justification of the new rules:
• Experimental Alignment: They provide a superior match to experimental data across all regions.
• Convergence: Terminal counts are close to Rent’s predictions when $g$ is small.
• Structural Commonality: There is a fundamental commonality in the rule structures; they can be effectively approximated by Rent’s Rule for very small $g$.

________________________________________
5. Conclusion

The proposed New Rules resolve long-standing issues in VLSI modeling by explicitly incorporating $N$ (system size), $t$ (average pins), and $m$ (net fan-out). By naturally constraining terminal counts at $g=N$, these rules provide a mathematically sound bridge across both Region I and Region II of Rent's curve.
________________________________________
References

1. Rent, E.F. (1960): Original discovery (often an internal IBM memorandum).

2. Landman, L.A. and Russo, R.L. (1971): "On Pin Versus Block Relationship for Partitions of Logic Graphs," IEEE Transactions on Computers, vol. C-20, no. 12, pp. 1469-1479.

3. Donath, W.E. (1981): "Wire Length Distribution for Computer Logic," IBM Technical Disclosure Bulletin, vol. 23, no. 11, pp. 5865-5868.

4. Heller, W.R., Hsi, C. and Mikhail, W.F. (1978): "Chip-Level Physical Design: An Overview," IEEE Transactions on Electron Devices, vol. 25, no. 2, pp. 163-176.

5. Natalie Heroux (2025): “Tetelbaum’s Law of Computer Systems, ourbigbook.com/nheroux/tetelbaum%E2%80%99s-law-of-computer-systems

6. Sutherland, I.E. and Oosterhout, W.J. (2001): "The Futures of Design: Interconnections," ACM/IEEE Design Automation Conference (DAC), pp. 15-20.

7. Davis, J. A. and Meindl, J. D. (2000): "A Hierarchical Interconnect Model for Deep Submicron Integrated Circuits," IEEE Transactions on Electron Devices, vol. 47, no. 11, pp. 2068-2073.

8. Stroobandt, D. A. and Van Campenhout, J. (2000): "The Geometry of VLSI Interconnect," Proceedings of the IEEE, vol. 88, no. 4, pp. 535-546.

9. TETELBAUM, A. (1995). "Generalizations of Rent's Rule", in Proc. of 27th IEEE Southeastern Symposium on System Theory, Starkville, Mississippi, USA, March 1995, pp. 011-016.

10. TETELBAUM, A. (1995). "Estimations of Layout Parameters of Hierarchical Systems", in Proc. of 27th IEEE Southeastern Symposium on System Theory, Starkville, Mississippi, USA, March 1995, pp. 123-128.

11. TETELBAUM, A. (1995). "Estimation of the Graph Partitioning for a Hierarchical System", in Proc. of the Seventh SIAM Conference on Parallel Processing for Scientific Computing, San Francisco, California, USA, February 1995, pp. 500-502.
________________________________________