skip to main content
article

An algorithm for integrated pin assignment and buffer planning

Published: 01 July 2005 Publication History

Abstract

The buffer block methodology has become increasingly popular as more and more buffers are needed in deep-submicron design, and it leads to many challenging problems in physical design. In this article, we present a polynomial-time exact algorithm for integrated pin assignment and buffer planning for all two-pin nets from one macro block (source block) to all other blocks of a given buffer block plan, while minimizing the total cost α ˙ W + β ˙ R for any positive α and β where W is the total wirelength, and R is the number of buffers. By applying this algorithm iteratively (each time, pick one block as the source block), it provides a polynomial-time algorithm for pin assignment and buffer planning for nets among multiple macro blocks. Experimental results demonstrate its efficiency and effectiveness.

References

[1]
Ahuja, R. K., Goldberg, A. V., Orlin, J. B., and Tarjan, R. E. 1992. Finding minimum-cost flows by double scaling. Mathemati. Program. 53, 243--266.
[2]
Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. 1993. Network Flows. Prentice Hall. Upper Saddle River, NJ.
[3]
Bakoglu, H. B. 1990. Circuits, Interconnections, and Packaging for VLSI. Addison-Wesley.
[4]
Cong, J. 1997. Challenges and opportunities for design innovations in nanometer technologies. SRC Working Papers. Available at http://www.src.org/prg_mgmt/frontier.dgw.
[5]
Cong, J., Kong, T., and Pan, D. Z. 1999. Buffer block planning for interconnect driven floorplanning. In Proceedings of the International Conference on Computer-Aided Design (ICCAD). 358--363.
[6]
Cormen, T. H., Leiserson, C. E., and Rivest, R. L. 1992. Introduction to Algorithms. The MIT Press, Cambridge, MA.
[7]
Dragan, F. F., Kahng, A. B., Mandoiu, I. I., Muddu, S., and Zelikovsky, A. 2000. Provably good global buffering using an available buffer block plan. In Proceedings of the International Conference on Computer-Aided Design (ICCAD'00). 104--109.
[8]
Dragan, F. F., Kahng, A. B., Mandoiu, I. I., Muddu, S., and Zelikovsky, A. 2001. Provably good global buffering by multiterminal multicommodity flow approximation. In Proceedings of the Asian and South Pacific Design Automation Conference (DAC). Yokohama, Japan. 120--125.
[9]
Otten, R. 1998. Global wires harmful. In Proceedings of the International Symposium on Physical Design (ISPD'98). 104---109.
[10]
Preas, B. and Lorenzetti, M. 1988. Physical Design Automation of VLSI Systems. Benjamin/Cummings, Menlo Park, CA.
[11]
Sarkar, P., Sundararaman, V., and Koh, C. K. 2000. Routability-driven repeater block planning for interconnect-centric floorplanning. In Proceedings of the International Symposium on Physical Design (ISPD'00).
[12]
Tang, X. and Wong, D. F. 2000. Planning buffer locations by network flows. In Proceedings of the International Symposium on Physical Design (ISPD'00). 180--185.

Recommendations

Reviews

Parthasarathi Dasgupta

With a drastic reduction in minimum feature sizes, interconnects are dominating deep sub-micron very large-scale integration (VLSI) physical design. As such, several techniques have evolved to reduce the interconnect delay. One effective and often-used method for reducing the interconnect delay is the use of buffers. It is estimated that the number of inserted buffers for an on-chip interconnect may be up to 800,000 in 50-nanometer (nm) technology. The use of buffers yields many challenging problems in physical design. Buffers are often grouped together as buffer blocks for convenience in floorplanning and routing. A related problem is the assignment of the locations of pins on macro blocks. For an initial placement of macro and buffer blocks, this paper considers the simultaneous assignment of pins and planning buffer insertions for a given set of nets, such that the distance between two buffers, or two pins, or a pin and a buffer, is within a range. Buffer planning determines buffer usage along net connections to maintain required delay constraints. A composite cost function, α ? W + β ? R, is considered for any positive constants α and β, where W is the total wire length, and R is the number of buffers. The problem is mapped into a minimum cost network flow problem, and a polynomial-time algorithm is proposed for simultaneous pin assignment and buffer planning for all two-pin nets. One macro block is considered as the source block, and all other blocks are considered as sink blocks. This basic algorithm is then iteratively applied, each time considering one block as the source block, and the remaining blocks as the sink blocks. This yields a polynomial-time algorithm for pin assignment and buffer planning for nets among multiple macro blocks. For larger circuits, in order to keep the problem within a manageable size and to speed up the computation, node clustering-based preprocessing is used. The algorithms were implemented in C++ on a PC, and compared with a two-step procedure where pin assignment was followed by buffer planning, using some randomly generated test cases. Results demonstrate the effectiveness of the proposed algorithm. For node clustering, the running time of the algorithm was reduced to a large extent, with minor degradation of the solution quality in terms of increased wire length, and larger numbers of buffers used. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems
ACM Transactions on Design Automation of Electronic Systems  Volume 10, Issue 3
July 2005
156 pages
ISSN:1084-4309
EISSN:1557-7309
DOI:10.1145/1080334
Issue’s Table of Contents
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]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

Publication History

Published: 01 July 2005
Published in TODAES Volume 10, Issue 3

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Buffer insertion
  2. min-cost maximum flow
  3. pin assignment

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 362
    Total Downloads
  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 09 Feb 2025

Other Metrics

Citations

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media