A Game Theory Based Post-Processing Method to Enhance VLSI Global Routers

Abstract

The increase in problem size and complexity of the global routing problems has made it harder for the global routers to produce good results. The global routers employ many different techniques to reach good solutions. However, the results on the recent benchmarks (ISPD 2008) reveal that existing global routers need more enhancements in their designs in-order to improve their solution quality. This work proposes a game theory based algorithm that can enhance the solutions of existing global routers. The proposed algorithm models the rip-up and re-route process as a sequential game in which nets act as players. The set of pure strategies of a net consists of different methods to rip-up and re-route its spanning tree. The nets use mixed strategies in which the probability of any pure strategy is based on the estimation of its likelihood to improve the solution. The performance of the proposed method has been evaluated by using it to enhance the solutions of two excellent global routers namely NCTU-GR 2.0 [1] & BFG-R [2]. The proposed method has been experimented using the ISPD 2008benchmarks and found to be successful in enhancing the total-overflow/wire-length of the existing global routers. On four hard-to-route problems, it has improved the total-overflow of three problems when used with NCTU-GR 2.0 and all four problems when used with BFG-R. It has improved the wire-lengths of all sixteen problems for both NCTU-GR 2.0 and BFG-R. The wire-length of NCTU-GR 2.0 was improved by a value ranging from 35-754 edges and that of BFG-R by a value ranging from 6462-15587 edges. While we demonstrated the potential of GT to enhance results of other heuristics, embedding the discussed technique can help produce better global routers as it will help better traversal of search space, and intelligent decision making.

Keywords

• Global routing
• game theory
• VLSI physical design
• rip-up and re-routing