基于图论的VLSI中最小斯坦纳树问题及其改进算法

The Rectilinear Steiner Minimal Tree Problem in VLSI Based on Graph Theory and Its Improved Algorithm

超大规模集成电路(VLSI)中,对于多端线网的最佳布线结果是构造最小直角斯坦纳树,该问题是典型的NP组合优化问题.利用图论中直角斯坦纳树的性质,在采用斯坦纳点编码方案寻找优化点位置的基础上,增加粒子趋同性判定及惯性权重系数调整策略,提出改进的粒子群优化算法,对一些实例模型进行了仿真测试,表明该算法的效果良好.

In the very large scale integration （VLSI） circuit, the creation of rectilinear Steiner minimal tree （RSMT）is the key to the routing of multi-end nets. RSMT problem is a classical NP-complete problem. We propose an optimization algorithm based on properties of rectilinear Steiner tree in graph theory. In this improved algorithm, Steiner coding approach is adopted to find optimized locations and to reduce the length of rectilinear Steiner tree. We also determine the consistency of particle and adjust the strategy for inertance weighting coefficient. Couples of simulation testing results on routing benchmarks show that the proposed algorithm is effective.