An algorithm for simultaneous pin assignment and routing

H. Xiang, X. Tang, D. F. Wong

Research output: Contribution to journalConference article

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 α · W + β · V, where W is the total wirelength and V is the total number of vias. Our algorithm has various applications: 1) It is suitable in ECO (Engineering Change Order) situations where a designer wants to incrementally modify the existing solution instead of redoing everything after a design change. 2) Given any pin assignment and routing solution obtained by any existing method, our algorithm can be used to increase the number of routed nets and reduce the routing cost. Furthermore, it provides an efficient algorithm for the pin assignment and routing problem of all blocks. The method is applicable to both global and detailed routing with arbitrary routing obstacles on multiple layers. Experimental results demonstrate its efficiency and effectiveness.

Original languageEnglish (US)
Pages (from-to)232-238
Number of pages7
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
StatePublished - Jan 1 2001
Externally publishedYes
EventInternational Conference on Computer-Aided Design 2001 - San Jose, CA, United States
Duration: Nov 4 2001Nov 8 2001

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

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

  • Cite this