| 改进的Prim启发式算法在VLSI布线中的应用 |
| |
| 引用本文： | 邓爱姣,李强,张嘉为.改进的Prim启发式算法在VLSI布线中的应用[J].沈阳工业大学学报,2006,28(5):557-559. |
| |
| 作者姓名： | 邓爱姣 李强 张嘉为 |
| |
| 作者单位： | 1. 武汉大学,数学与统计学院,武汉,430072
2. 武汉大学,电气工程学院,武汉,430072 |
| |
| 摘 要： | 总体布线在超大规模集成电路的设计中有着举足轻重的作用.为了寻求总体布线图的最优斯坦纳树，改进了普里姆(Prim)算法，提出了一种基于改进的普里姆启发式算法寻求最小矩形斯坦纳树(RST)的方法，不同于以往的先求最小生成树(MST)然后再把树的边矩形化的方法；同时考虑到时延在深亚微米、超深亚微米阶段的重要影响，在算法中又加入了总体布线设计时的时延要求，最后通过仿真实例验证了算法的可行性.
|
| 关 键 词： | 总体布线 总体布线图 改进的普里姆启发式算法 最小矩形斯坦纳树 时延 |
| 文章编号： | 1000-1646（2006）05-0557-03 |
| 收稿时间： | 2006-03-28 |
| 修稿时间： | 2006-03-28 |
Application of improved Prim heuristic algorithm in VLSI placement |
| |
| DENG Ai-jiao,LI Qiang,ZHANG Jia-wei.Application of improved Prim heuristic algorithm in VLSI placement[J].Journal of Shenyang University of Technology,2006,28(5):557-559. |
| |
| Authors: | DENG Ai-jiao LI Qiang ZHANG Jia-wei |
| |
| Affiliation: | a. School of Mathematics and Statitics, b. School of Electrical Engineering, Wuhan University, Wuhan 430072, China |
| |
| Abstract: | Global routing plays an important part in VLSI design.To seek the optimal Steiner Tree of the Global Routing Graph(GRG),an improved Prim heuristic algorithm was proposed and applied to(determine) the optimal RST.The improved method is different from the approach of obtaining firstly MST and then performing edge rectangle.Time delay is added in global routing design because its(considerable) effect on the deep submicron and super deep submicron stage of VLSI and ULSI design.Finally,feasibility of the algorithm is testified by emulational examples. |
| |
| Keywords: | global routing global routing graph improved Prim heuristic algorithm least rectangle steiner tree time delay |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《沈阳工业大学学报》浏览原始摘要信息 |
|
点击此处可从《沈阳工业大学学报》下载全文 |
