Min-cost flow-based algorithm for simultaneous pin assignment and routing

Hua Xiang, Xiaoping Tang, Martin D.F. Wong

Research output: Contribution to journalArticlepeer-review

Abstract

Macroblock pin assignment and routing are important tasks in physical design. 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. However, none of the existing algorithms is "exact" in the sense that they may fail to route all of the nets even though a feasible solution exists. This remains to be true even if only two-pin nets with fixed pins between two blocks are concerned. In this paper, we consider the problem of two-pin net connections from one macroblock to all of the other blocks, and present the first polynomial-time exact algorithm for simultaneous pin assignment and routing for all of the two-pin nets between one block (source block) and all of the 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 wire length and V is the total number of vias. Our algorithm has various applications. 1) It is suitable in engineering change order (ECO) situations where the existing solution is modified incrementally. 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 of the 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)870-878
Number of pages9
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume22
Issue number7
DOIs
StatePublished - Jul 2003

Keywords

  • Detail routing
  • Global routing
  • Min-cost flow
  • Physical design
  • Pin assignment
  • Routing

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Min-cost flow-based algorithm for simultaneous pin assignment and routing'. Together they form a unique fingerprint.

Cite this