A Game Theory-Based Heuristic for the Two-Dimensional VLSI Global Routing Problem

摘要

In this work we propose a game theory (GT)-based global router. It works in two steps: (i) Initial routing of all nets using maze routing with framing (MRF) and (ii) GT-based rip-up and reroute (R&R) process. In initial routing, the nets are divided into several small subsets which are routed concurrently using multithreading (MT). The main task of the GT-based R&R process is to eliminate congestion. Nets are considered as players and each player employs two pure strategies: (attempt to improve its spanning tree, and, do not attempt to improve its spanning tree). The nets also have mixed strategies whose values act as probabilities for them to select any particular pure strategy. The nets which select their first strategy will go through the R&R operation. We also propose an algorithm which computes the mixed strategies of nets. The advantage of using GT to select nets is that it reduces the number of nets and the number of iterations in the R&R process. The performance of the proposed global router was evaluated on ISPD'98 benchmarks and compared with two recent global routers, namely, Box Router 2.0 (configured for speed) and Side-winder. The results show that the proposed global router with MT has a shorter runtime to converge to a valid solution than that of Box Router 2.0. It also outperforms Side-winder in terms of routability. The experimental results demonstrated that GT is a valuable technique in reducing the runtime of global routers.