A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> c: SCOUT BEE PHASE <s> We present in this paper a fast and stable global router called NTHU-Route 2.0 that improves the solution quality and runtime of a state-of-the-art router, NTHU-Route, by the following enhancements: (1) a new history based cost function, (2) new ordering methods for congested region identification and rip-up and reroute, and (3) two implementation techniques. The experimental results show that NTHU-Router 2.0 solves all ISPD98 benchmarks with very good quality. Moreover, it routes 7 of 8 ISPD07 benchmarks without any overflow. In particular, for one of the ISPD07 benchmarks which are thought to be difficult cases previously, NTHU-Route 2.0 can completely eliminate its total overflow. NTHU-Route 2.0 also successfully solves 12 of 16 ISPD08 benchmarks without causing any overflow. <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> c: SCOUT BEE PHASE <s> This paper presents an approach that applies the Artificial Bee Colony algorithm to the Two-Terminals-Net-Routing(TTNR) problem in VLSI physical design and compares its performance with the maze algorithm variant known as the state-of-the-art global routing algorithm. An effectively encoding method is described in this paper to solve the TTNR problem. In order to improve the convergence speed of the algorithm, some guiding solutions are employed as the initial solutions. The experimental results demonstrate that Artificial Bee Colony algorithm can find the less cost routing paths for TTNR problems than the maze algorithm. <s> BIB002 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> c: SCOUT BEE PHASE <s> Artificial Bee Colony (ABC) algorithm is a very efficient optimization algorithm that uses the foraging behavior of honeybees. ABC has been quite extensively studied upon and applied to solve many real world engineering problems. Routing is one of the crucial stages in physical design, on which the performance of the entire chip depends. Global routing is the first step of routing where the nets in different blocks of the chip are loosely interconnected. Detailed routing which follows after global routing determines the particular points through which actual routing is to be done. So global routing is the most important part of routing and the proper interconnection between nets with the most optimum wire length depends on the performance of this stage. This paper presents an algorithm based on ABC for calculating the wire length in global routing and the optimized results are compared against the standard router NTHU 2.0. NTHU-Route 2.0 is a quick and robust global router which solves all ISPD benchmarks maintaining very good quality. <s> BIB003
For any food source (matrix), the solution is discarded and the algorithm will enter the scout bee phase if the solution is not improved within the set threshold range. And the new solutions are generated by randomly selecting points in the original matrix. Repeat the above steps until the termination condition is satisfied. Then the best solution is determined according to the fitness value and the optimal wirelength is obtained. In this paper, ABC can work efficiently because the candidate solutions are obtained from the parents by means of a simple and elementary operation method. This method is implemented based on finding the difference between randomly chosen parts of parent solution and a random solution from the population. So that the convergence of the algorithm is hastened. Compared with a quick and robust global router NTHU 2.0 BIB001 , which solves all International Symposium on Physical Design (ISPD) benchmarks, BIB003 can generate better results and more optimum routing configurations. Zhang and Ye BIB002 applied the ABC algorithm to the routing for two-terminal nets and compared its performance with the maze algorithm. In order to adapt the ABC algorithm for solving the routing problem of two-terminal nets, several parts of ABC are altered as follows: (1) The algorithm adopts a sequence encoding method, which divides the solutions of the problem into two parts: the row-based solutions and the column-based solutions; (2) Half of the initial solution is generated by pattern routing, and the other half is randomly generated to speed up the algorithm convergence; (3) A local search operation is designed to exchange the front part sequences or behind part sequences of the auxiliary solution and the current solution to generate two new solutions, and then select the best solution from the new solutions and the current solutions as the updated current solution; (4) A dynamic attractiveness probability is designed for adjusting the positive feedback of this algorithm during the different stages. The experimental results demonstrate that ABC algorithm can find the less cost routing paths for the routing problem of two-terminal nets than the maze algorithm.