Research On VLSI Routing Based On Parallel A~* Algorithm

Integrated circuits have been widely used since the 1950 s.With the increasing scale of circuits,EDA has faced challenge in solving VLSI routing problems.In order to improve the efficiency of routing algorithms,many graph algorithms and Meta-heuristic algorithms have been widely studied.A~* algorithm,as a widely used industrial routing algorithm,has been favored by researchers because of its flexibility and ability of solving barrier problem.In this paper,we analyzed the principle of A~* algorithm and applied the parallel version of it to VLSI routing with GPU computing platform.This paper concluded two specific mathematical models of routing problems based on the basic principles and design models of VLSI routing.The routing problem of two-terminal net and multi-terminal net were concluded as shortest path problem and minimum steiner tree problem respectively.For shortest path problem,this paper proposed multi-queue parallel maze expansion method in the step of maze expansion of A~* algorithm and implemented parallel A~* algorithm with GPU platform.By the step of redundancy deduplicate,the algorithm avoided the use of atomic lock and increased the efficiency of program.In the experiment of shortest path problem,parallel A~* algorithm can obtain 2-48 times of speed up compared to serial A~* algorithm.For minimum Steiner tree problem,this paper introduced the basic principle and defects of TM algorithm and presented the improvement approximation algorithm based on parallel A~* algorithm.A new synchronization method was proposed in the implementation of algorithm.In the test of routing quality,error between the total cost of the minimum Steiner tree and the optimal solution was less than 7% in all test cases,the error of 51% test cases was within 5% and the average error was 4.2%.In the test of routing speed,A~* approximation algorithm can obtain4-51 times of speed up compared to improved maze algorithm.Those tests proved parallel A~* algorithm and its derived approximation Steiner tree algorithm can solve routing problems of large scale routing graph effectively and GPU has large potential in solving VLSI routing problems.