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. Put simply, it states that there is a simple power law relationship between these two values (pins and gates).
E. F. Rent's discovery and first publications
In the 1960s, E. F. Rent, an
IBM
International Business Machines Corporation (using the trademark IBM), nicknamed Big Blue, is an American Multinational corporation, multinational technology company headquartered in Armonk, New York, and present in over 175 countries. It is ...
employee, found a remarkable trend between the number of pins (terminals, ''T'') at the boundaries of
integrated circuit
An integrated circuit (IC), also known as a microchip or simply chip, is a set of electronic circuits, consisting of various electronic components (such as transistors, resistors, and capacitors) and their interconnections. These components a ...
designs at
IBM
International Business Machines Corporation (using the trademark IBM), nicknamed Big Blue, is an American Multinational corporation, multinational technology company headquartered in Armonk, New York, and present in over 175 countries. It is ...
and the number of internal components (''g''), such as logic gates or standard cells. On a
log–log plot
In science and engineering, a log–log graph or log–log plot is a two-dimensional graph of numerical data that uses logarithmic scales on both the horizontal and vertical axes. Exponentiation#Power_functions, Power functions – relationshi ...
, these datapoints were on a straight line, implying a power-law relation
, where ''t'' and ''p'' are constants (''p'' < 1.0, and generally 0.5 < ''p'' < 0.8).
Rent's findings in
IBM
International Business Machines Corporation (using the trademark IBM), nicknamed Big Blue, is an American Multinational corporation, multinational technology company headquartered in Armonk, New York, and present in over 175 countries. It is ...
-internal memoranda were published in the IBM Journal of Research and Development in 2005, but the relation was described in 1971 by Landman and Russo.
They performed a hierarchical circuit partitioning in such a way that at each hierarchical level (top-down) the fewest interconnections 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 the number 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".
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. However, it provides a useful framework with which to compare similar architectures.
Theoretical basis
Christie and Stroobandt later derived Rent's rule theoretically for homogeneous systems and pointed out that the amount of optimization achieved in
placement
Placement may refer to:
* Placement (EDA), an essential step in E-design automation
* Placement exam, determines which class a student should take
* Favored placement, the practice of preferentially listing search engine results for given sites
...
is reflected by the parameter
, the "Rent exponent", which also depends on the circuit topology. In particular, values
correspond to a greater fraction of short interconnects. The constant
in Rent's rule can be viewed as the average number of terminals required by a single logic block, since
when
.
Special cases and applications
Random arrangement of logic blocks typically have
. Larger values are impossible, since the maximal number of terminals for any region containing ''g'' logic components in a homogeneous system is given by
. Lower bounds on ''p'' depend on the interconnection topology, since it is generally impossible to make all wires short. This lower bound
is often called the "intrinsic Rent exponent", a notion first introduced by Hagen et al. It can be used to characterize optimal placements and also measure the interconnection complexity of a circuit. Higher (intrinsic) Rent exponent values correspond to a higher topological complexity. One extreme example (
) is a long chain of logic blocks, while a
clique has
. In realistic 2D circuits,
ranges from 0.5 for highly-regular circuits (such as
SRAM) to 0.75 for random logic.
System performance analysis tools such as
BACPAC typically use Rent's rule to calculate expected wiring lengths and wiring demands.
Rent's rule has been shown to apply among the regions of the brain of
''Drosophila'' fruit fly, using synapses instead of gates, and neurons which extend both inside and outside the region as pins.
Estimating Rent's exponent
To estimate Rent's exponent, one can use top-down partitioning, as used in min-cut placement. For every partition, count the number of terminals connected to the partition and compare it to the number of logic blocks in the partition. Rent's exponent can then be found by fitting these datapoints on a log–log plot, resulting in an exponent ''p. For optimally partitioned circuits,
but this is no longer the case for practical (heuristic) partitioning approaches. For partitioning-based placement algorithms
.
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 is known as "Region II" of Rent's Rule.
A similar deviation also exists for small partitions and has been found by Stroobandt, who called it "Region III".
Rentian wirelength estimation
Another
IBM
International Business Machines Corporation (using the trademark IBM), nicknamed Big Blue, is an American Multinational corporation, multinational technology company headquartered in Armonk, New York, and present in over 175 countries. It is ...
employee, Donath, discovered that Rent's rule can be used to estimate the average wirelength and the wirelength distribution in
VLSI chips.
This motivated the System Level Interconnect Prediction workshop, founded in 1999, and an entire community working on wirelength prediction (see a survey by Stroobandt
). The resulting wirelength estimates have been improved significantly since then and are now used for "technology exploration".
The use of Rent's rule allows to perform such estimates ''a priori'' (i.e., before actual placement) and thus predict the properties of future technologies (clock frequencies, number of routing layers needed, area, power) based on limited information about future circuits and technologies.
A comprehensive overview of work based on Rent's rule has been published by Stroobandt.
[{{cite magazine, last=Stroobandt, first=D., title=Recent Advances in System-Level Interconnect Prediction, magazine=IEEE Circuits and Systems Society Newsletter, volume=11, issue=4, pages=1; 4–20; 48, date=December 2000, citeseerx=10.1.1.32.6011]
See also
* Electronic design automation
Electronic design automation (EDA), also referred to as electronic computer-aided design (ECAD), is a category of software tools for designing Electronics, electronic systems such as integrated circuits and printed circuit boards. The tools wo ...
* Integrated circuit design
Integrated circuit design, semiconductor design, chip design or IC design, is a sub-field of electronics engineering, encompassing the particular Boolean logic, logic and circuit design techniques required to design integrated circuits (ICs). A ...
*Network architecture
Network architecture is the design of a computer network. It is a framework for the specification of a network's physical components and their functional organization and configuration, its operational principles and procedures, as well as commun ...
**Network on a chip
A network on a chip or network-on-chip (NoC or )This article uses the convention that "NoC" is pronounced . Therefore, it uses the convention "a" for the indefinite article corresponding to NoC ("a NoC"). Other sources may pronounce it as an ...
References
Gate arrays
Electronic design automation
Computer architecture statements