Research progress of VLSI detailed routing algorithm

Detailed routing in very-large-scale integration (VLSI) is one of the most important and challenging stages in physical design. The path of all wires will be determined at this stage, the quality of routing is directly related to the area and performance of the chip.The path search is one of the most time-consuming steps in routing. First, the grid-based routing model is described in this paper, which models the routing problem into a graph search problem or a multi-commodity flow problem. Then it summarizes the application of maze search algorithm, A* algorithm, integer linear programming (ILP) algorithm, and parallel acceleration algorithm in path search and optimization for design constraints, and analyzes its pros and cons in the application of routers. Finally, it summarized and reviewed the research progress of algorithms based on machine learning, analyzed the existing problems, and looked forward to the development trend of detailed routing algorithms. Analysis shows that the comprehensive performance of the A* algorithm in terms of routing quality, stability, and speed is over performed than other algorithms. The difficulty lies in designing a reasonable routing strategy and graph model. Reinforcement learning has great research potential, the current research is only tested in a small-scale design, and further improvement and exploration are still needed.