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 fruit fly, 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 telecommunications technologies. The microprocessor and memory chips are VLSI devices.

An adder, or summer, is a digital circuit that performs addition of numbers. In many computers and other kinds of processors, adders are used in the arithmetic logic units (ALUs). They are also used in other parts of the processor, where they are used to calculate addresses, table indices, increment and decrement operators and similar operations.

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

<span class="mw-page-title-main">Integrated circuit design</span> Engineering process for electronic hardware

Integrated circuit design, semiconductor design, chip design or IC design, is a sub-field of electronics engineering, encompassing the particular logic and circuit design techniques required to design integrated circuits, or ICs. ICs consist of miniaturized electronic components built into an electrical network on a monolithic semiconductor substrate by photolithography.

In electronic design, wire routing, commonly called simply routing, is a step in the design of printed circuit boards (PCBs) and integrated circuits (ICs). It builds on a preceding step, called placement, which determines the location of each active element of an IC or component on a PCB. After placement, the routing step adds wires needed to properly connect the placed components while obeying all design rules for the IC. Together, the placement and routing steps of IC design are known as place and route.

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 a 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. The bisection bandwidth accounts for the bottleneck bandwidth of the entire network. Therefore, the 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.

Jingsheng Jason Cong is a Chinese-born American computer scientist, educator, and serial entrepreneur. He received his B.S. degree in computer science from Peking University in 1985, his M.S. and Ph. D. degrees in computer science from the University of Illinois at Urbana-Champaign in 1987 and 1990, respectively. He has been on the faculty in the Computer Science Department at the University of California, Los Angeles (UCLA) since 1990. Currently, he is a Distinguished Chancellor’s Professor and the director of Center for Domain-Specific Computing (CDSC).

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.

<span class="mw-page-title-main">Transistor computer</span> Computer built using discrete transistors

A transistor computer, now often called a second-generation computer, is a computer which uses discrete transistors instead of vacuum tubes. The first generation of electronic computers used vacuum tubes, which generated large amounts of heat, were bulky and unreliable. A second-generation computer, through the late 1950s and 1960s featured circuit boards filled with individual transistors and magnetic-core memory. These machines remained the mainstream design into the late 1960s, when integrated circuits started appearing and led to the third-generation computer.

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

<span class="mw-page-title-main">Floorplan (microelectronics)</span> Layout of major electronic circuit blocks

In electronic design automation, a floorplan of an integrated circuit is a schematic representation of tentative placement of its major functional blocks.

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.

Charles Albert Zukowski is a professor and former chair of the Department of Electrical Engineering at Columbia University. Zukowski was born in Buffalo, New York. While still a student at MIT, from 1979 to 1982, Zukowski worked at the Thomas J. Watson Research Center. He received his BS in electrical engineering from the Massachusetts Institute of Technology in 1982. He received the IBM PhD Fellowship from 1982 to 1985; in 1985 he earned his PhD in electrical engineering with a thesis entitled "Design and measurement of a reconfigurable multi-microprocessor machine". The same year, he joined the faculty of Columbia University as assistant professor, and was awarded tenure in 1993. Zukowski is an active member of IEEE and was made an IEEE Fellow in 2000. Zukowski's present research focuses on VLSI circuits and integrated circuit (IC) optimization, though in the past he has published in the fields of systems biology and computer architecture.

<span class="mw-page-title-main">Igor L. Markov</span> American computer scientist and engineer

Igor Leonidovich Markov is an American professor, computer scientist and engineer. Markov is known for 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 an American non-profit executive responsible for aid to Ukraine worth over a hundred million 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. S2CID   42581168.
  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. S2CID   9253458.
  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. S2CID   11305439.
  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. S2CID   17506981.
  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.