skip to main content
10.1145/368640.368665acmconferencesArticle/Chapter ViewAbstractPublication PagesslipConference Proceedingsconference-collections
Article

On partitioning vs. placement rent properties

Published: 01 March 2001 Publication History

Abstract

Rent's rule can be derived by direct partitioning of the circuit netlist, by indirect partitioning of the placed layout, or by averaging the number of terminals for various equally large regions of the placed circuit. It is shown that all three methods may produce different results. After investigation of the fundamental reasons for these differences, three distinct effects can be identified. The boundary and the embedding effect is present with all placement approaches, though the embedding effect may be (partly) nullified by the grid effect that may occur with some partitioning-based placement algorithms.
One of the main applications of Rent's rule is the estimation of wire length distribution. Both flat and hierarchical placement models can be applied, though experiments show that for the current state-of-the-art estimation techniques the latter produces better results, even for layouts that were generated using a flat placement approach. Which Rent parameters and occupation probability function should be used depends on the placement algorithm. We discuss various possibilities and present a new occupation probability function that allows better wire length estimations of partitioning-based placements.

References

[1]
A. E. Caldwell, K. A. B., and M. I. L. Can recursive bisection produce routable placements? In Proc. Design Automation Conf., pages 477-482, June 2000.]]
[2]
P. Christie and D. Stroobandt. The interpretation and application of Rent's rule. IEEE Trans. on VLSI Systems, Special Issue on System-Level Interconnect Prediction, 8(6):639-648, December 2000.]]
[3]
J. Dambre, P. Verplaetse, D. Stroobandt, and J. Van Campenhout. On Rent's rule for rectangular regions. In Proc. of Intl. Workshop on System-Level Interconnect Prediction, March 2001.]]
[4]
J. A. Davis, V. K. De, and J. D. Meindl. A stochastic wire-length distribution for gigascale integration (GSI) - PART I: Derivation and validation. IEEE Trans. on Electron Devices, 45(3):580-589, March 1998.]]
[5]
W. E. Donath. Wire length distribution for placements of computer logic. IBM J. of Research and Development, 25:152-155, 1981.]]
[6]
G. Karypis and V. Kumar. hMetis: A Hypergraph Partitioning Package, November 1998. Available at: http://www-users.cs.umn.edu/_karypis/metis/hmetis/ main.shtml.]]
[7]
B. S. Landman and R. L. Russo. On a pin versus block relationship for partitions of logic graphs. IEEE Trans. on Comput., C-20:1469-1479, 1971.]]
[8]
M. Sarrafzadeh and M. Wang. NRG: Global and detailed placement. In Proc. IEEE Intl. Conf. on Computer-Aided Design, pages 532-537, November 1997.]]
[9]
D. Stroobandt. Analytical methods for a priori wire length estimates in computer systems, November 1998. Ph.D. thesis (translated from Dutch), University of Ghent, Faculty of Applied Sciences.]]
[10]
D. Stroobandt. On an efficient method for estimating the interconnection complexity of designs and on the existence of region III in Rent's rule. In Proc. 9th Great Lakes Symposium on VLSI, pages 330-331, March 1999.]]
[11]
D. Stroobandt, P. Verplaetse, and J. Van Campenhout. Generating synthetic benchmark circuits for evaluating CAD tools. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems., 19(9):1011-1022, September 2000.]]
[12]
P. Suarism and G. Kedem. An algorithm for quadrisection and its application to standard cell placement. IEEE Trans. on Circuits & Systems, 35(3):294-303, March 1988.]]
[13]
W. Sun and C. Sechen. Efficient and effective placement for very large circuits. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 14(3):349-359, March 1995.]]
[14]
P. Verplaetse. A stochastic model for the interconnection topology of digital circuits. Technical Report PARIS 00-07, Ghent University, Belgium, ELIS Department, December 2000. Submitted to IEEE Trans. on Very Large Scale Integration (VLSI) Systems.]]
[15]
M. Wang, X. Yang, and M. Sarrafzadeh. Dragon2000: Standard-cell placement tool for large industry circuits. In Proc. of Intl. Conf. on Computer-Aided Design, pages 260-263, November 2000.]]
[16]
X. Yang, M. Wang, K. Eguro, and M. Sarrafzadeh. A snap-on placement tool. In Proc. of Intl. Symp on Physical Design, pages 153-158, April 2000.]]

Cited By

View all
  • (2024)Improving the Area-Delay Tradeoff for Academic FPGA Architectures by Applying Rent’s Rule to Logic Block Modeling2024 XXXIII International Scientific Conference Electronics (ET)10.1109/ET63133.2024.10721534(1-6)Online publication date: 17-Sep-2024
  • (2018)Comparing two classes of biological distribution systems using network analysisPLOS Computational Biology10.1371/journal.pcbi.100642814:9(e1006428)Online publication date: 7-Sep-2018
  • (2017)A method for validating Rent’s rule for technological and biological networksScientific Reports10.1038/s41598-017-05670-w7:1Online publication date: 14-Jul-2017
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SLIP '01: Proceedings of the 2001 international workshop on System-level interconnect prediction
March 2001
178 pages
ISBN:1581133154
DOI:10.1145/368640
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2001

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Rent's rule
  2. estimation
  3. partitioning
  4. placement
  5. wire length distribution

Qualifiers

  • Article

Conference

SLIP01
Sponsor:

Acceptance Rates

Overall Acceptance Rate 6 of 8 submissions, 75%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)19
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Improving the Area-Delay Tradeoff for Academic FPGA Architectures by Applying Rent’s Rule to Logic Block Modeling2024 XXXIII International Scientific Conference Electronics (ET)10.1109/ET63133.2024.10721534(1-6)Online publication date: 17-Sep-2024
  • (2018)Comparing two classes of biological distribution systems using network analysisPLOS Computational Biology10.1371/journal.pcbi.100642814:9(e1006428)Online publication date: 7-Sep-2018
  • (2017)A method for validating Rent’s rule for technological and biological networksScientific Reports10.1038/s41598-017-05670-w7:1Online publication date: 14-Jul-2017
  • (2014)Disparate Connectivity for Structural and Functional Networks is Revealed When Physical Location of the Connected Nodes is ConsideredBrain Topography10.1007/s10548-014-0393-328:2(187-196)Online publication date: 7-Sep-2014
  • (2010)Logical Core AlgorithmProceedings of the 2010 IEEE Annual Symposium on VLSI10.1109/ISVLSI.2010.114(69-73)Online publication date: 5-Jul-2010
  • (2009)A unified gate sizing formulation for optimizing soft error rate, cross-talk noise and power under process variationsProceedings of the 2009 10th International Symposium on Quality of Electronic Design10.1109/ISQED.2009.4810326(388-393)Online publication date: 16-Mar-2009
  • (2007)Impact of interconnect length changes on effective materials properties (dielectric constant)Proceedings of the 2007 international workshop on System level interconnect prediction10.1145/1231956.1231972(73-80)Online publication date: 17-Mar-2007
  • (2007)Adaptable wire-length distribution with tunable occupation probabilityProceedings of the 2007 international workshop on System level interconnect prediction10.1145/1231956.1231958(1-8)Online publication date: 17-Mar-2007
  • (2006)Post-placement interconnect entropyProceedings of the 2006 international workshop on System-level interconnect prediction10.1145/1117278.1117289(41-48)Online publication date: 4-Mar-2006
  • (2005)Predicting interconnect requirements in ultra-large-scale integrated control logic circuitryProceedings of the 2005 international workshop on System level interconnect prediction10.1145/1053355.1053366(43-50)Online publication date: 2-Apr-2005
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media