A Survey on Steiner Tree Construction and Global Routing for VLSI Design

Abstract

Global Routing (GR) is a crucial and complex stage in the Very Large-Scale Integration (VLSI) design, which minimizes interconnect wirelength and delay to optimize the overall chip performance. Steiner tree construction is one of the basic models of VLSI physical design, which is usually used in the initial topology creation for noncritical nets in physical design. In a GR process, a Steiner Minimum Tree (SMT) algorithm can be invoked millions of times, which means that SMT algorithm has great significance for the final quality of GR. Some of the research works are surveyed in this paper to understand GR and SMT problems and to learn the available solutions. Firstly, we systematically dissect three types of subproblems in Steiner tree construction and three types of GR methods. Then, we investigate the recent progress under two new technology models. Finally, the survey concludes with a summary of possible future research directions.

Keywords

• Steiner tree construction
• particle swarm optimization
• routing
• very large scale integration
• global routing