On partitioning vs. placement rent properties

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On partitioning vs. placement rent properties

Full text

Pdf (324 KB)

Source

International Workshop on System-Level Interconnect Prediction archive
Proceedings of the 2001 international workshop on System-level interconnect prediction table of contents

Sonoma, California, United States

Pages: 33 - 40

Year of Publication: 2001

ISBN:1-58113-315-4

Authors

P. Verplaetse	Ghent Univ., Belgium
J. Dambre	Ghent Univ., Belgium
D. Stroobandt	Ghent Univ., Belgium
J. Van Campenhout	Ghent Univ., Belgium

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 23, Citation Count: 13

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/368640.368665 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Can recursive bisection alone produce routable placements?, Proceedings of the 37th conference on Design automation, p.477-482, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337549]
	2	Philip Christie , Dirk Stroobandt, The interpretation and application of Rent's rule, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.6, p.639-648, Dec. 2000 [doi>10.1109/92.902258]
	3	J. Dambre , P. Verplaetse , D. Stroobandt , J. Van Campenhout, On rent's rule for rectangular regions, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.49-56, March 31-April 01, 2001, Sonoma, California, United States [doi>10.1145/368640.368700]
	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	Majid Sarrafzadeh , Maogang Wang, NRG: global and detailed placement, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.532-537, November 09-13, 1997, San Jose, California, United States
	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	Dirk Stroobandt, On an Efficient Method for Estimating the Interconnection Complexity of Designs and on the Existence of Region III in Rent's Rule, Proceedings of the Ninth Great Lakes Symposium on VLSI, p.330, March 04-06, 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	Maogang Wang , Xiaojian Yang , Majid Sarrafzadeh, Dragon2000: standard-cell placement tool for large industry circuits, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	16	Xiaojian Yang , Maogang Wang , Kenneth Eguro , Majid Sarrafzadeh, A snap-on placement tool, Proceedings of the 2000 international symposium on Physical design, p.153-158, May 2000, San Diego, California, United States [doi>10.1145/332357.332392]

CITED BY 13

	M. Y. Lanzerotti , G. Fiorenza , R. A. Rand, Predicting interconnect requirements in ultra-large-scale integrated control logic circuitry, Proceedings of the 2005 international workshop on System level interconnect prediction, April 02-03, 2005, San Francisco, California, USA
	J Dambre , P. Verplaetse , D. Stroobandt , J. Van Campenhout, Getting more out of Donath's hierarchical model for interconnect prediction, Proceedings of the 2002 international workshop on System-level interconnect prediction, April 06-07, 2002, San Diego, California, USA
	J. Dambre , P. Verplaetse , D. Stroobandt , J. Van Campenhout, On rent's rule for rectangular regions, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.49-56, March 31-April 01, 2001, Sonoma, California, United States
	J. Dambre , D. Stroobandt , J. Van Campenhout, Fast estimation of the partitioning rent characteristic using a recursive partitioning model, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA
	Joni Dambre , Peter Verplaetse , Dirk Stroobandt , Jan Van Campenhout, A comparison of various terminal-gate relationships for interconnect prediction in VLSI circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.1, p.24-34, February 2003
	Joachim Pistorius , Mike Hutton, Placement rent exponent calculation methods, temporal behaviour and FPGA architecture evaluation, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA
	J. Dambre , D. Stroobandt , J. Van Campenhout, A probabilistic approach to clock cycle prediction, Proceedings of the 8th ACM/IEEE international workshop on Timing issues in the specification and synthesis of digital systems, December 02-03, 2002, Monterey, California, USA
	André DeHon, Unifying mesh- and tree-based programmable interconnect, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.10, p.1051-1065, October 2004
	Joni Dambre , Dirk Stroobandt , Jan Van Campenhout, Toward the accurate prediction of placement wire length distributions in VLSI circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.4, p.339-348, April 2004
	Mary Y. Lanzerotti , Giovanni Fiorenza , R. A. Rand, Assessment of on-chip wire-length distribution models, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.10, p.1108-1112, October 2004
	Wenyi Feng , Jonathan W. Greene, Post-placement interconnect entropy: how many configuration bits does a programmable logic device need?, Proceedings of the international workshop on System-level interconnect prediction, March 04-05, 2006, Munich, Germany
	Mary Y. Lanzerotti , Giovanni Fiorenza , Rick A. Rand, Impact of interconnect length changes on effective materials properties (dielectric constant), Proceedings of the 2007 international workshop on System level interconnect prediction, March 17-18, 2007, Austin, Texas, USA
	Shuhei Amakawa , Takumi Uezono , Takashi Sato , Kenichi Okada , Kazuya Masu, Adaptable wire-length distribution with tunable occupation probability, Proceedings of the 2007 international workshop on System level interconnect prediction, March 17-18, 2007, Austin, Texas, USA