期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

改进的Prim启发式算法在VLSI布线中的应用 被引量：1

Application of improved Prim heuristic algorithm in VLSI placement
下载PDF
导出
摘要 总体布线在超大规模集成电路的设计中有着举足轻重的作用.为了寻求总体布线图的最优斯坦纳树,改进了普里姆(Prim)算法,提出了一种基于改进的普里姆启发式算法寻求最小矩形斯坦纳树(RST)的方法,不同于以往的先求最小生成树(MST)然后再把树的边矩形化的方法;同时考虑到时延在深亚微米、超深亚微米阶段的重要影响,在算法中又加入了总体布线设计时的时延要求,最后通过仿真实例验证了算法的可行性. 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 deer, submicron and super deep submicron stage of VLSI and ULSI design. Finally, feasibility of the algorithm is testified by emulational examples.
作者 邓爱姣 李强 张嘉为
机构地区 武汉大学数学与统计学院 武汉大学电气工程学院
出处 《沈阳工业大学学报》 EI CAS 2006年第5期557-559,567,共4页 Journal of Shenyang University of Technology
关键词 总体布线 总体布线图 改进的普里姆启发式算法 最小矩形斯坦纳树 时延 global routing global routing graph improved Prim heuristic algorithm least rectangle steiner tree time delay
分类号 TN43 [电子电信—微电子学与固体电子学]
  • 相关文献

参考文献7

  • 1Hashimoto A,Stevens J.Wire routing by optimizing channel assignment within large apertures[ A].Proc.8th IEEE/ACM Design Automation Workshop[C].New York:Acm Press,1971.155-169.
  • 2Srinivasan A.An algorithm for performance-driven initial placement of Small-Cell ICs[A].Proc.28th DAC[C].New York:Acm Press,1991.636-639.
  • 3Forcrand P,Zimmermann H.Timing-driving auto placement[A].Proc.ICCD[C].Washington:IEEE Computer Ssociety Press,1987.518-521.
  • 4Prastijutrakul S,Kubitz W J.A timing-driven global router for custom chip design[A].Proc.IEEE ICCAD[C].Washington:IEEE Com-puter Society Press,1990.48-51.
  • 5Carter D L,Guise D F.Analysis of signal propagation delays and chip level performance due to on chip interconnections[A].Proc.ICCD[ C].Washington:IEEE Com-puter Society Press,1983.218-221.
  • 6Horneber E H,Mathis W.A closed-form expression for signal delay in CMOS-Driven branched transmission lines[ A].Proc.VLSI[ C ].Amsterdam:North Holland,1987.353-362.
  • 7Sakurai T.Approximation of wiring delay in MOSFET LSI[J].IEEE JSSC,1983(4):418-426.

同被引文献14

  • 1张会生,翁史烈,张小兵,袁亚雄.基于内弹道改进型零维模型的装药优化仿真[J].弹道学报,2000,12(3):32-36. 被引量：10
  • 2Hashimoto A, et al. Wire Routing by Optimizing Channal Assignment Within Large Appertures[C] //Proc. of 8th IEEE/ ACM Design Automation Workshop. 1971.
  • 3Wey Chin-Long. Efficient Rectilinear Steiner Tree Construction with Rectangular Obstacles[C]//Prcc. 5th WSEAS International Conference on Circuits System Selectronics Control & Signal Processign. Dallas, USA, 2006 : 204-208.
  • 4Rita M H, Bryant A J. A Spanning-Tree-based Genetic Algorithm for Some Instances of the Rectilinear Steiner Problem with Obstacles[C]//Proceedings of the 2003 ACM Symposium on Applied Computing. 2003 : 725-729.
  • 5Eberhart R C, Kennedy J. A New Optimizer Using Particles Swarm Theory[C]//Proc. 6th International Symposium on Micro Machine and Human Science. Nagoya,Japan, 1995:39-43.
  • 6Clerc 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.
  • 7Hanan M. On steiner's problem with rectilinear distance[J]. SIAM Journal of Applied Mathematics,1996,14(2) :255-265.
  • 8Kennedy J,Eberhart R C. A Discrete Binary Version of the Particle Swarm Optimization Algorithm[C]//Proc. of the IEEE International Conference on Systems Man and Cybernetics. Orlando,USA, 1997,V: 4104-4109.
  • 9Clerc M. Discrete Particle Swarm Optimzation illustrated by the Traveling Salesman Problem [EB/OL]. http://www. mauriceclerc. net, 2000-02-29.
  • 10Shi Y H, Eberhart R C. A Modified Particle Swarm Optimizer [C]//IEEE International Conference of Evolutionary Computation. Piscataway, NJ: IEEE, 1998 : 69-73.

引证文献1

二级引证文献5

沈阳工业大学学报
2006年 第5期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部