An algorithm for integrated pin assignment and buffer planning

Hua Xiang, Xiaoping Tang, D. F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 paper, 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 as well as minimizing the total cost α· W + β· R for any positive α and β where W is the total wire length 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 39th Annual Design Automation Conference, DAC'02
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages584-589
Number of pages6
ISBN (Print)1581134614
DOIs
StatePublished - Jan 1 2002
Externally publishedYes
Event39th Design Automation Conference - New Orleans, LA, United States
Duration: Jun 10 2002Jun 14 2002

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X

Conference

Conference39th Design Automation Conference
CountryUnited States
CityNew Orleans, LA
Period6/10/026/14/02

Keywords

  • Buffer insertion
  • Min-cost maximum flow
  • Pin assignment

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'An algorithm for integrated pin assignment and buffer planning'. Together they form a unique fingerprint.

  • Cite this

    Xiang, H., Tang, X., & Wong, D. F. (2002). An algorithm for integrated pin assignment and buffer planning. In Proceedings of the 39th Annual Design Automation Conference, DAC'02 (pp. 584-589). (Proceedings - Design Automation Conference). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1145/513918.514067