Rent's rule

Last updated

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).

Contents

E. F. Rent's discovery and first publications

In the 1960s, E. F. Rent, an IBM employee, found a remarkable trend between 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 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-internal memoranda were published in the IBM Journal of Research and Development in 2005, [1] but the relation was described in 1971 by Landman and Russo. [2] 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 [3] later derived Rent's rule theoretically for homogeneous systems and pointed out that the amount of optimization achieved in placement 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. [4] 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. [5]

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, using synapses instead of gates, and neurons which extend both inside and outside the region as pins. [6]

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 . [7]

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. [2] A similar deviation also exists for small partitions and has been found by Stroobandt, [8] who called it "Region III".

Rentian wirelength estimation

Another IBM employee, Donath, discovered that Rent's rule can be used to estimate the average wirelength and the wirelength distribution in VLSI chips. [9] [10] This motivated the System Level Interconnect Prediction workshop, founded in 1999, and an entire community working on wirelength prediction (see a survey by Stroobandt [11] ). The resulting wirelength estimates have been improved significantly since then and are now used for "technology exploration". [12] 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. [11] [13]

See also

Related Research Articles

<span class="mw-page-title-main">Very Large Scale Integration</span> Creating an integrated circuit by combining many transistors into a single chip

Very-large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining millions or billions of MOS transistors onto a single chip. VLSI began in the 1970s when MOS integrated circuit chips were developed and then widely adopted, enabling complex semiconductor and telecommunication technologies. The microprocessor and memory chips are VLSI devices.

<span class="mw-page-title-main">Electromigration</span> Movement of ions in an electrical field

Electromigration is the transport of material caused by the gradual movement of the ions in a conductor due to the momentum transfer between conducting electrons and diffusing metal atoms. The effect is important in applications where high direct current densities are used, such as in microelectronics and related structures. As the structure size in electronics such as integrated circuits (ICs) decreases, the practical significance of this effect increases.

<span class="mw-page-title-main">Boundary scan</span>

Boundary scan is a method for testing interconnects on printed circuit boards or sub-blocks inside an integrated circuit. Boundary scan is also widely used as a debugging method to watch integrated circuit pin states, measure voltage, or analyze sub-blocks inside an integrated circuit.

Placement is an essential step in electronic design automation — the portion of the physical design flow that assigns exact locations for various circuit components within the chip's core area. An inferior placement assignment will not only affect the chip's performance but might also make it non-manufacturable by producing excessive wire-length, which is beyond available routing resources. Consequently, a placer must perform the assignment while optimizing a number of objectives to ensure that a circuit meets its performance demands. Together, the placement and routing steps of IC design are known as place and route.

<span class="mw-page-title-main">Network on a chip</span> Electronic communication subsystem on an integrated circuit

A network on a chip or network-on-chip is a network-based communications subsystem on an integrated circuit ("microchip"), most typically between modules in a system on a chip (SoC). The modules on the IC are typically semiconductor IP cores schematizing various functions of the computer system, and are designed to be modular in the sense of network science. The network on chip is a router-based packet switching network between SoC modules.

In computer networking, if the network is bisected into two equal-sized partitions, the bisection bandwidth of a network topology is the bandwidth available between the two partitions. Bisection should be done in such a way that the bandwidth between two partitions is minimum. Bisection bandwidth gives the true bandwidth available in the entire system. Bisection bandwidth accounts for the bottleneck bandwidth of the entire network. Therefore bisection bandwidth represents bandwidth characteristics of the network better than any other metric.

A field-programmable analog array (FPAA) is an integrated circuit device containing computational analog blocks (CAB) and interconnects between these blocks offering field-programmability. Unlike their digital cousin, the FPGA, the devices tend to be more application driven than general purpose as they may be current mode or voltage mode devices. For voltage mode devices, each block usually contains an operational amplifier in combination with programmable configuration of passive components. The blocks can, for example, act as summers or integrators.

Franco P. Preparata is a computer scientist, the An Wang Professor, Emeritus, of Computer Science at Brown University.

<span class="mw-page-title-main">Cactus graph</span> Mathematical tree of cycles

In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or in which every block is an edge or a cycle.

The ESPRESSO logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital logic gate circuits. ESPRESSO-I was originally developed at IBM by Robert K. Brayton et al. in 1982. and improved as ESPRESSO-II in 1984. Richard L. Rudell later published the variant ESPRESSO-MV in 1986 and ESPRESSO-EXACT in 1987. Espresso has inspired many derivatives.

Maurice Karnaugh was an American physicist, mathematician, computer scientist, and inventor known for the Karnaugh map used in Boolean algebra.

<span class="mw-page-title-main">Physical design (electronics)</span>

In integrated circuit design, physical design is a step in the standard design cycle which follows after the circuit design. At this step, circuit representations of the components of the design are converted into geometric representations of shapes which, when manufactured in the corresponding layers of materials, will ensure the required functioning of the components. This geometric representation is called integrated circuit layout. This step is usually split into several sub-steps, which include both design and verification and validation of the layout.

A three-dimensional integrated circuit is a MOS integrated circuit (IC) manufactured by stacking as many as 16 or more ICs and interconnecting them vertically using, for instance, through-silicon vias (TSVs) or Cu-Cu connections, so that they behave as a single device to achieve performance improvements at reduced power and smaller footprint than conventional two dimensional processes. The 3D IC is one of several 3D integration schemes that exploit the z-direction to achieve electrical performance benefits in microelectronics and nanoelectronics.

BACPAC, or the Berkeley Advanced Chip Performance Calculator, is a software program to explore the effect of changes in IC technology. The use enters a set of fairly fundamental properties of the technology and the program estimates the system level performance of an IC built with these assumptions. Previous work in this area can be found in and, but these do not consider many of the effects of deep-sub-micrometre interconnect. BACPAC is based on the work in.

John Patrick Hayes is an Irish-American computer scientist and electrical engineer, the Claude E. Shannon Chair of Engineering Science at the University of Michigan. He supervised over 35 doctoral students, coauthored seven books and over 340 peer-reviewed publications. His Erdös number is 2.

<span class="mw-page-title-main">Ian A. Young</span> American electrical engineer

Ian A. Young is an Intel engineer. Young is a co-author of 50 research papers, and has 71 patents in switched capacitor circuits, DRAM, SRAM, BiCMOS, x86 clocking, Photonics and spintronics.

Rajiv V. Joshi is an Indian-American prolific inventor and research staff member at IBM's Thomas J. Watson Research Center. His work focuses on the development of integrated circuits and memory chips. He is an IEEE Fellow and received the Industrial Pioneer Award from the IEEE Circuits and Systems Society in 2013 and the IEEE Daniel E. Noble Award in 2018. He holds 271 U.S. patents.

Finite state machines (FSMs) are widely used to implement control logic in various applications such as microprocessors, digital transmission, digital filters and digital signal processing. Even for designs containing a good number of datapath elements, the controller occupies a sizeable portion. As the devices are mostly portable and hand-held, reducing power dissipation has emerged as the primary concern of today's VLSI designers. While the datapath elements can be shut down when they are not being used, controllers are always active. As a result, the controller consumes a good amount of system power. Thus, power-efficient synthesis of FSM has come up as a very important problem domain, attracting a lot of research. The synthesis method must be able to reduce both dynamic power and leakage power consumed by the circuit.

Verilog-to-Routing (VTR) is an open source CAD flow for FPGA devices. VTR's main purpose is to map a given circuit described in Verilog, a Hardware Description Language, on a given FPGA architecture for research and development purposes; the FPGA architecture targeted could be a novel architecture that a researcher wishes to explore, or it could be an existing commercial FPGA whose architecture has been captured in the VTR input format. The VTR project has many contributors, with lead collaborating universities being the University of Toronto, the University of New Brunswick, and the University of California, Berkeley. Additional contributors include Google, The University of Utah, Princeton University, Altera, Intel, Texas Instruments, and MIT Lincoln Lab.

Igor Leonidovich Markov is an American professor, computer scientist and engineer. Markov is known for mathematical and algorithmic results in quantum computation, work on limits of computation, research on algorithms for optimizing integrated circuits and on electronic design automation, as well as artificial intelligence. Additionally, Markov is a California non-profit executive responsible for aid to Ukraine worth tens of millions dollars.

References

  1. ↑ Lanzerotti, M. Y.; Fiorenza, G.; Rand, R. A. (July 2005). "Microminiature packaging and integrated circuitry: The work of {E. F. Rent}, with an application to on-chip interconnection requirements". IBM J. Res. & Dev. 49 (4, 5): 777–803. doi:10.1147/rd.494.0777.
  2. 1 2 Landman, B. S.; Russo, R. L. (1971). "On a Pin Versus Block Relationship For Partitions of Logic Graphs". IEEE Transactions on Computers. C-20 (12): 1469–1479. doi:10.1109/T-C.1971.223159.
  3. ↑ Christie, P.; Stroobandt, D. (2000). "The interpretation and application of Rent's rule". IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 8 (6): 639–648. doi:10.1109/92.902258.
  4. ↑ Hagen, L.; Kahng, A.B.; Kurdahi, F.J.; Ramachandran, C. (1994). "On the intrinsic Rent parameter and spectra-based partitioning methodologies". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 13: 27–37. doi:10.1109/43.273752.
  5. ↑ Russo, Roy L. (1972). "On the Tradeoff Between Logic Performance and Circuit-to-Pin Ratio for LSI". IEEE Transactions on Computers. C-21 (2): 147–153. doi:10.1109/tc.1972.5008919.
  6. ↑ Scheffer, Louis K; Xu, C Shan; Januszewski, Michal; Lu, Zhiyuan; Takemura, Shin-ya; Hayworth, Kenneth J; Huang, Gary B; Shinomiya, Kazunori; Maitlin-Shepard, Jeremy; Berg, Stuart; Clements, Jody (2020-09-03). Marder, Eve; Eisen, Michael B; Pipkin, Jason; Doe, Chris Q (eds.). "A connectome and analysis of the adult Drosophila central brain". eLife. 9: e57443. doi: 10.7554/eLife.57443 . ISSN   2050-084X. PMC   7546738 . PMID   32880371.
  7. ↑ Verplaetse, P.; Dambre, J.; Stroobandt, D.; Van Campenhout, J. (2001). "On Partitioning vs. Placement Rent Properties". Proceedings of the 2001 International Workshop on System-Level Interconnect Prediction - SLIP '01. pp. 33–40. doi:10.1145/368640.368665. ISBN   1581133154.
  8. ↑ Stroobandt, D. (1999). "On an efficient method for estimating the interconnection complexity of designs and on the existence of region III in Rent's rule". Proceedings Ninth Great Lakes Symposium on VLSI. pp. 330–331. doi:10.1109/GLSV.1999.757445. ISBN   0-7695-0104-4.
  9. ↑ Donath, W. (1979). "Placement and average interconnection lengths of computer logic". IEEE Transactions on Circuits and Systems. 26 (4): 272–277. doi:10.1109/tcs.1979.1084635.
  10. ↑ Donath, W. E. (1981). "Wire Length Distribution for Placements of Computer Logic". IBM Journal of Research and Development. 25 (3): 152–155. doi:10.1147/rd.252.0152.
  11. 1 2 Stroobandt, D. (2001). A Priori Wire Length Estimates for Digital Design. Kluwer Academic Publishers. p. 298. ISBN   0-7923-7360-X.
  12. ↑ Caldwell, Andrew E.; Cao, Yu; Kahng, Andrew B.; Koushanfar, Farinaz; Lu, Hua; Markov, Igor L.; Oliver, Michael; Stroobandt, Dirk; Sylvester, Dennis (2000). "GTX". Proceedings of the 37th Conference on Design Automation - DAC '00. pp. 693–698. doi:10.1145/337292.337617. ISBN   1581131879.
  13. ↑ Stroobandt, D. (December 2000). "Recent Advances in System-Level Interconnect Prediction". IEEE Circuits and Systems Society Newsletter. Vol. 11, no. 4. pp. 1, 4–20, 48. CiteSeerX   10.1.1.32.6011 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.