VLSI Multilayer Obstacle-Avoiding Steiner Minimal Tree Construction Algorithms in X-Architecture

Steiner minimal tree is a fundamental model in VLSI routing. Further considering X-architecture, the presence of obstacles, and the requirements of multilayer routing, this paper presented an efficient algorithm based on particle swarm optimization for constructing the multilayer obstacle-avoiding X-architecture Steiner minimal tree. Edge transformation was designed to make the particles have the greater ability to change the topology of the routing tree and avoided the obstacles. The new operators combined with union-find set were designed to prevent the generation of the loops. In order to avoid obstacle and discourage the generation of vias, the penalty function related to obstacle-avoiding and vias was proposed. The proposed algorithm finally optimizes the total cost of routing tree which is the most important optimization target of the multilayer routing. The experimental results show that, the proposed algorithm is effective and superior to state-of-the-art multilayer routing algorithms on the total cost.