An evaluation of game theory for rip-up and re-routing in global routing

The global routing process in VLSI physical design is used to determine congestion-free spanning trees for all nets. Almost all global routers use some type of rip-up and re-routing (R&R) method to eliminate congestion. Game theory (GT) is an efficient decision making technique which is useful in situations where action of any one player effects the actions of the other players. The global routing problem can be modeled as a game because spanning tree of any one net effects the congestion in the spanning trees of many other players. In this work, we evaluated the performance of using GT-based R&R to successfully solve complex global routing problems. Our proposed global routing algorithm consists of two GT-based R&R processes. The first one lies in the initial routing phase and the second one lies in the re-routing of the congested nets phase. The performance of the proposed algorithm was evaluated on the ISPD'98 suite of test problems. In the experiments, the proposed algorithm has successfully solved up-to ten trials of each test problem. Therefore, the GT-based R&R method is found to be efficient and stable.