An algorithm for simultaneous pin assignment and routing

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.