Abstract
Abstract In this thesis, we study the problem of layer assignment for via minimization that arises during multi-layer global routing. In this problem, we take total overflow and maximum flow as the congestion constraints from an initial one-layer routing solution and we want to find a layer assignment result for each net such that the via cost is as small as possible while the given congestion constraints are satisfied. This layer assignment problem is different from the well-known constrained via minimization problem that is handled after detailed routing. To solve this problem, we propose a sequential algorithm which first generates a net order, and then according to the order, performs layer assignment one net at a time by using dynamic programming We use the benchmarks released from the ISPD’07 global routing contest to test our algorithm, and the experimental results show that our algorithm can get averagely 7.77%, 16.69%, and 2.11% improvement rates on the via cost as compared to three state-of-the-art multi-layer global routers, MaizeRouter, BoxRouter and FGR, which were known to the top three winners of the multi-layer category at the ISPD’07 global routing contest.