|Table of Contents|

The Rectilinear Steiner Minimal Tree Problem in VLSI Based onGraph Theory and Its Improved Algorithm(PDF)

南京师范大学学报（工程技术版）[ISSN:1006-6977/CN:61-1281/TN]

Issue:
2015年04期
Page:
47-
Research Field:
计算机工程
Publishing date:

Info

Title:
The Rectilinear Steiner Minimal Tree Problem in VLSI Based onGraph Theory and Its Improved Algorithm
Author(s):
Chen Xiuhua
Department of Basic Courses，Fujian Chuanzheng Communications College，Fuzhou 350007，China
Keywords:
graph theory; very large scale integration（VLSI）; rectilinear Steiner minimal tree
PACS:
O157.6
DOI:
-
Abstract:
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.

References:

［1］ FRANK K HWANG，DANA S，RICHARDS P W. The Steiner tree problem［M］. Netherlands：North-Holland，1992.
［2］ 金慧敏，马良，王周缅，等. 欧氏Steiner最小树问题的智能优化算法［J］. 计算机工程，2006，32（10）：201-203.
JIN H M，MA L，WANG Z M，et al. Intelligent optimization algorithms for euclidean Steiner minimum tree problem［J］. Computer Engineering，2006，32（10）：201-203.（in Chinese）
［3］ 杨文国，郭田德. 求解最小Steiner树的蚁群优化算法及其收敛性［J］. 应用数学学报，2006，29（2）：352-361.
YANG W G，GUO T D. An ant colony optimization algorithm for the minimum Steiner tree problem and its convergence proof［J］. Acta mathematicae applicatae sinica，2006，29（2）：352-361.（in Chinese）
［4］ 刘耿耿，王小溪，陈国龙，等. 求解VLSI布线问题的离散粒子群优化算法［J］. 计算机科学，2010，37（10）：197-201.
LIU G G，WANG X X，CHEN G L，et al. Discrete particle swarm optimization algorithm for the routing of VLSI circuit［J］. Computer science，2010，37（10）：197-201.（in Chinese）
［5］ ZHANG Y H，CHU C. GDRouter：Interleaved global routing and detailed routing for ultimate routability［C］//Design Automation Conference（DAC），2012 49th ACM/EDAC/IEEE. San Francisco：IEEE Press，2012：597-602.
［6］ HUANG T W，HO T Y. A two-stage ILP-based droplet routing algorithm for pin-constrained digital microfluidic biochips［J］. IEEE transactions on computer-aided design of integrated circuits and systems，2011，30（2）：215-228.
［7］ ZHANG Y，CHU C. Regular route：an efficient detailed router with regular routing patterns［C］//International Symp on Physical Design，March 27-30，2011. California，2011：146-151.
［8］ CLERC M，KENNEDY J. The particle swarm-explosion，stability and convergence in a multidimensional complex space［J］. IEEE transactions on evolutionary computation，2002，6（1）：58-73.
［9］ KHAN A，LAHA S，SARKAR S K. A novel particle swarm optimization approach for VLSI routing［C］//Advance Computing Conference（IACC），2013 IEEE 3rd International. Ghaziabad：IEEE Press，2013：258-262.
［10］ 姜长元，赵曙光，沈士根，等. 惯性权重正弦的粒子群算法［J］. 计算机工程与应用，2012，48（8）：40-42.
JIANG C Y，ZHAO S G，SHEN S G，et al. Particle swarm optimization algorithm with sinusoidal changing inertia weight［J］. Computer engineering and applications，2012，48（8）：40-42.（in Chinese）
［11］ KENNEDY J S. Improving particle swarm performance with cluster analysis［C］//Proceedings of the Congress on Evolutionary Computing. Piscatawat，NJ，2000：1 507-1 5l2.
［12］ 陈秀华，朱自然. 一种求解RSMT布线问题的PSO算法［J］. 闽江学院学报，2014，35（5）：39-44.
CHEN X H，ZHU Z R. A PSO algorithm for RSMT routing problem［J］. Journal of Minjiang university，2014，35（5）：39-44.（in Chinese）
［13］ 徐宁，洪先龙. 超大规模集成电路物理设计理论与算法［M］. 北京：清华大学出版社，2009：167-177.
XU N，HONG X L. Physics design theory and algorithm for VLSI［M］. Beijing：Tsinghua University Press，2009：167-177.（in Chinese）
［14］ HANAN M. On steiner’s problem with rectilinear distance［J］. SIAM journal of applied mathematics，1996，14（2）：255-265.
［15］ HUANG T，LI L，YOUNG E F. On the construction of optimal obstacle-avoiding rectilinear Steiner minimum trees［J］. IEEE transactions on computer-aided design of integrated circuits and systems，2011，30（5）：718-731.
［16］ 郑莹，王建新，陈建二. Steiner Tree问题的研究进展［J］. 计算机科学，2011，38（10）：17-22.
ZHENG Y，WANG J X，CHEN J E. Survey of Steiner Tree problem［J］. Computer science，2011，38（10）：17-22.（in Chinese）
［17］ 张烈平，张云生，杨桂华. 基于粒子群算法的流程工业生产调度研究［J］. 计算机工程与应用，2012，48（6）：225-228.
ZHANG L P，ZHANG Y S，YANG G H. Research on production scheduling problems in process industry based on particle swarm optimization algorithm［J］. Computer engineering and applications，2012，48（6）：225-228.（in Chinese）
［18］ 柳寅，马良，黄钰. 模糊粒子群算法构造Steiner最优树问题研究［J］. 计算机工程与应用，2014，50（14）：54-57.
LIU Y，MA L，HUANG Y. Studies on construction of Steiner minimum tree problem based on fuzzy particle swarm optimization［J］. Computer engineering and applications，2014，50（14）：54-57.（in Chinese）
［19］ GRIFFITH J. Closing the gap：near-optimal Steiner trees in polynomial time［J］. IEEE Trans on CAD，1994，13（11）：1 351-1 365.
［20］ 邢焕革，卫一熳. 跟随变异粒子扰动变化的惯性权重PSO算法［J］. 四川兵工学报，2015，36（1）：106-110.
XING H G，WEI Y M. Inertia weight particle swarm optimization algorithm with mutation particle disturbance changes［J］. Journal of Sichuan ordnance，2015，36（1）：106-110.（in Chinese）
［21］ 邵洪涛，秦亮曦，何莹. 带变异算子的非线性惯性权重PSO算法［J］. 计算机技术与发展，2012，22（8）：30-34.
SHAO H T，QIN L X，HE Y. A nonlinear inertia weight particle swarm optimization algorithm with mutation operator［J］. Computer technology and development，2012，22（8）：30-34.（in Chinese）
［22］ 史哲文，白雪石，郭禾，等. 基于改进小生境粒子群算法的多模函数优化［J］. 计算机应用研究，2012，29（2）：465-468.
SHI Z W，BAI X S，GUO H，et al. Multimodal function optimization based on modified niching particle swarm optimization［J］. Application research of computers，2012，29（2）：465-468.（in Chinese）

Memo

Memo:
-
Last Update: 2015-12-20