An algorithm for integrated pin assignment and buffer planning

Hua Xiang, Xiaoping Tang, Martin 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
Pages584-589
Number of pages6
StatePublished - 2002
Externally publishedYes
Event39th Annual Design Automation Conference, DAC'02 - New Orleans, LA, United States
Duration: Jun 10 2002Jun 14 2002

Other

Other39th Annual Design Automation Conference, DAC'02
CountryUnited States
CityNew Orleans, LA
Period6/10/026/14/02

Fingerprint

Planning
Macros
Polynomials
Wire
Costs

Keywords

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

ASJC Scopus subject areas

  • Hardware and Architecture
  • Control and Systems Engineering

Cite this

Xiang, H., Tang, X., & Wong, M. 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)

An algorithm for integrated pin assignment and buffer planning. / Xiang, Hua; Tang, Xiaoping; Wong, Martin D F.

Proceedings of the 39th Annual Design Automation Conference, DAC'02. 2002. p. 584-589.

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

Xiang, H, Tang, X & Wong, MDF 2002, An algorithm for integrated pin assignment and buffer planning. in Proceedings of the 39th Annual Design Automation Conference, DAC'02. pp. 584-589, 39th Annual Design Automation Conference, DAC'02, New Orleans, LA, United States, 6/10/02.
Xiang H, Tang X, Wong MDF. An algorithm for integrated pin assignment and buffer planning. In Proceedings of the 39th Annual Design Automation Conference, DAC'02. 2002. p. 584-589
Xiang, Hua ; Tang, Xiaoping ; Wong, Martin D F. / An algorithm for integrated pin assignment and buffer planning. Proceedings of the 39th Annual Design Automation Conference, DAC'02. 2002. pp. 584-589
@inproceedings{8d3c87645b5e49c3aef4912eca41e20d,
title = "An algorithm for integrated pin assignment and buffer planning",
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.",
keywords = "Buffer insertion, Min-cost maximum flow, Pin assignment",
author = "Hua Xiang and Xiaoping Tang and Wong, {Martin D F}",
year = "2002",
language = "English (US)",
isbn = "1581134614",
pages = "584--589",
booktitle = "Proceedings of the 39th Annual Design Automation Conference, DAC'02",

}

TY - GEN

T1 - An algorithm for integrated pin assignment and buffer planning

AU - Xiang, Hua

AU - Tang, Xiaoping

AU - Wong, Martin D F

PY - 2002

Y1 - 2002

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

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

KW - Buffer insertion

KW - Min-cost maximum flow

KW - Pin assignment

UR - http://www.scopus.com/inward/record.url?scp=0036047787&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036047787&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0036047787

SN - 1581134614

SP - 584

EP - 589

BT - Proceedings of the 39th Annual Design Automation Conference, DAC'02

ER -