An algorithm for simultaneous pin assignment and routing

Hua Xiang, Xiaoping Tang, D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

7 Citations (Scopus)

Abstract

Macro-block pin assignment and routing are important tasks in physical design planning. Existing algorithms for these problems can be classified into two categories: 1) a two-step approach where pin assignment is followed by routing, and 2) a net-by-net approach where pin assignment and routing for a single net are performed simultaneously. None of the existing algorithms is "exact" in the sense that the algorithm may fail to route all nets even though a feasible solution exists. This remains to be true even if only 2-pin nets between two blocks are concerned. In this paper, we present the first polynomial-time exact algorithm for simultaneous pin assignment and routing for 2-pin nets from one block (source block) to all other blocks. In addition to finding a feasible solution whenever one exists, it guarantees to find a pin-assignment/routing solution with minimum cost /spl alpha//spl middot/W + /spl beta//spl middot/V, where W is the total wirelength and V is the total number of vias. Our algorithm has various applications and is applicable to both global and detailed routing with arbitrary routing obstacles on multiple layers. Experimental results demonstrate its efficiency and effectiveness.
Original languageEnglish
Title of host publicationProceedings of The IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2001
Place of PublicationUnited States
PublisherIEEE
Pages232-238
Number of pages7
DOIs
Publication statusPublished - Nov 2001
Event2001 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2001 - DoubleTree Hotel, San Jose, United States
Duration: 4 Nov 20018 Nov 2001
https://ieeexplore.ieee.org/xpl/conhome/7652/proceeding (Conference proceedings)

Publication series

NameProceedings of the IEEE/ACM international conference on Computer-aided design, ICCAD
PublisherIEEE
ISSN (Print)1092-3152

Conference

Conference2001 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2001
Country/TerritoryUnited States
CitySan Jose
Period4/11/018/11/01
Internet address

Fingerprint

Dive into the research topics of 'An algorithm for simultaneous pin assignment and routing'. Together they form a unique fingerprint.

Cite this