An algorithm for integrated pin assignment and buffer planning

Hua Xiang; Xiaoping Tang; D. F. Wong

doi:10.1145/513918.514067

An algorithm for integrated pin assignment and buffer planning

Hua Xiang, Xiaoping Tang, D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

6 Citations (Scopus)

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 language	English
Title of host publication	39th ACM/IEEE Design Automation Conference - Proceedings 2002
Publisher	Association for Computing Machinery (ACM)
Pages	584-589
Number of pages	6
ISBN (Print)	9781581134612, 1581134614
DOIs	https://doi.org/10.1145/513918.514067 https://doi.org/10.1109/DAC.2002.1012693
Publication status	Published - Jun 2002
Event	39th ACM/IEEE Design Automation Conference, DAC 2002 - New Orleans, United States Duration: 10 Jun 2002 → 14 Jun 2002 https://www.dac.com/About/Conference-Archive/39th-DAC-2002 (Conference website) https://www.dac.com/portals/0/documents/archive/2005-01/39thfinal.pdf (Conference program) https://dl.acm.org/doi/proceedings/10.1145/513918 (Conference proceedings) https://ieeexplore.ieee.org/xpl/conhome/7910/proceeding (Conference proceedings)

Publication series

Name	ACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)	0738-100X

Conference

Conference	39th ACM/IEEE Design Automation Conference, DAC 2002
Country/Territory	United States
City	New Orleans
Period	10/06/02 → 14/06/02
Internet address	https://www.dac.com/About/Conference-Archive/39th-DAC-2002 (Conference website) https://www.dac.com/portals/0/documents/archive/2005-01/39thfinal.pdf (Conference program) https://dl.acm.org/doi/proceedings/10.1145/513918 (Conference proceedings) https://ieeexplore.ieee.org/xpl/conhome/7910/proceeding (Conference proceedings)

Scopus Subject Areas

Control and Systems Engineering
Hardware and Architecture

User-Defined Keywords

Buffer insertion
Min-cost maximum flow
Pin assignment

Access to Document

Cite this

@inproceedings{9c953153745b4f2fb549e3ebc6dbd462,

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, {D. F.}",

note = "Funding information: This work was partially supported by the National Science Foundation under grant CCR-9912390. Publisher copyright: {\textcopyright} 2002 ACM; 39th ACM/IEEE Design Automation Conference, DAC 2002 ; Conference date: 10-06-2002 Through 14-06-2002",

year = "2002",

month = jun,

doi = "10.1145/513918.514067",

language = "English",

isbn = "9781581134612",

series = "ACM/IEEE Design Automation Conference - Proceedings",

publisher = "Association for Computing Machinery (ACM)",

pages = "584--589",

booktitle = "39th ACM/IEEE Design Automation Conference - Proceedings 2002",

address = "United States",

url = "https://www.dac.com/About/Conference-Archive/39th-DAC-2002, https://www.dac.com/portals/0/documents/archive/2005-01/39thfinal.pdf, https://dl.acm.org/doi/proceedings/10.1145/513918, https://ieeexplore.ieee.org/xpl/conhome/7910/proceeding",

}

Xiang, H, Tang, X & Wong, DF 2002, An algorithm for integrated pin assignment and buffer planning. in 39th ACM/IEEE Design Automation Conference - Proceedings 2002. ACM/IEEE Design Automation Conference - Proceedings, Association for Computing Machinery (ACM), pp. 584-589, 39th ACM/IEEE Design Automation Conference, DAC 2002, New Orleans, Louisiana, United States, 10/06/02. https://doi.org/10.1145/513918.514067, https://doi.org/10.1109/DAC.2002.1012693

An algorithm for integrated pin assignment and buffer planning. / Xiang, Hua; Tang, Xiaoping; Wong, D. F.
39th ACM/IEEE Design Automation Conference - Proceedings 2002. Association for Computing Machinery (ACM), 2002. p. 584-589 (ACM/IEEE Design Automation Conference - Proceedings).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - An algorithm for integrated pin assignment and buffer planning

AU - Xiang, Hua

AU - Tang, Xiaoping

AU - Wong, D. F.

PY - 2002/6

Y1 - 2002/6

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 - https://dl.acm.org/doi/10.1145/513918.514067

UR - https://ieeexplore.ieee.org/document/1012693

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

U2 - 10.1145/513918.514067

DO - 10.1145/513918.514067

M3 - Conference proceeding

AN - SCOPUS:0036047787

SN - 9781581134612

SN - 1581134614

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 584

EP - 589

BT - 39th ACM/IEEE Design Automation Conference - Proceedings 2002

PB - Association for Computing Machinery (ACM)

T2 - 39th ACM/IEEE Design Automation Conference, DAC 2002

Y2 - 10 June 2002 through 14 June 2002

ER -

An algorithm for integrated pin assignment and buffer planning

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this