Research On VLSI Net Routing Based On Tabu-ant Colonies System

Net routing is an important step in very large-scale integration(VLSI) physical design. As the electric circuit integration increasing day by day,traditional algorithms cannot meet the design requirements any more.So,new algorithms should be proposed continuously.In this paper,an intelligent net routing method for very large-scale integration(VLSI) physical design is provided.Two-terminal net routing is the basal problem for VLSI net routing.Therefore,the study of this problem is used as the starting point of this paper.This problem is a NP problem.Ant colonies system is a typical intelligent algorithm.In this paper, ant colonies system is studied.Ant colonies system has two disadvantages which are long search time and easy stagnation.Therefore,some improvement schemes are proposed.The initial distribution of the pheromone on the routing plane is adjusted.The moving rule used by ants in searching process is modified.Besides,tabu-search method is incorporated.So,a new intelligent algorithm called tabu-ant colonies system is proposed.A connection graph is used as the routing plane.The new algorithm has been implemented in Java language.The value of the parameter q₀ which is important to the experiment result is discussed.It shows that when the value of q₀ is mezzo,the convergence effect of experiments is good.The performances of algorithms are compared with other algorithms by using the statistical results of some examples.Computer experiments show that the new algorithm overcomes the blindness of ant colonies system in search process.It speeds up convergence rate of ant colonies system in early stage.Further more,it avoids local optimum and can find the optimal path for two-terminal net routing problem in a short time.This new algorithm can be applied to gridless net routing,multi-terminal and multi-layer net routing.The quantity of the nodes in gridless net routing is smaller than in grid net routing. Therefore,the search space and search time of the algorithm is smaller.Then,a method for multi-terminal and multi-layer net routing is provided.We take two-layer net routing for example.One layer is for horizontal lines and the other is for vertical lines.Vias are used for the connection between different layers.The typical minimum spanning tree(MST) algorithm which called Prim algorithm is used to solve it.Tabu-ant colonies system is used for search of the minimum cost path in each repeat of MST algorithm.By this way,the complicated multi-terminal net routing problem is simplified as search for the shortest path between two points repeatedly.This method is applied to an example which has six terminals and two layers.Computer experiments show that the MST algorithm with intelligent characteristics is a valid algorithm to solve multi-terminal and multi-layer routing problem.