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 language | English |
---|---|
Title of host publication | Proceedings of The IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2001 |
Place of Publication | United States |
Publisher | IEEE |
Pages | 232-238 |
Number of pages | 7 |
DOIs | |
Publication status | Published - Nov 2001 |
Event | 2001 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2001 - DoubleTree Hotel, San Jose, United States Duration: 4 Nov 2001 → 8 Nov 2001 https://ieeexplore.ieee.org/xpl/conhome/7652/proceeding (Conference proceedings) |
Publication series
Name | Proceedings of the IEEE/ACM international conference on Computer-aided design, ICCAD |
---|---|
Publisher | IEEE |
ISSN (Print) | 1092-3152 |
Conference
Conference | 2001 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2001 |
---|---|
Country/Territory | United States |
City | San Jose |
Period | 4/11/01 → 8/11/01 |
Internet address |
|