English

应用科学学报 ›› 2009, Vol. 27 ›› Issue (4): 387-391.

• 电子技术 • 上一篇    下一篇

一种有约束的多层布线通孔优化算法

程心 解光军 杨依忠   

  1. 合肥工业大学电子科学与应用物理学院，合肥230009
  • 收稿日期:2009-01-13 修回日期:2009-05-11 出版日期:2009-07-30 发布日期:2009-07-30
  • 通信作者: 解光军，博士，教授，研究方向：集成电路设计、智能信息处理,E-mail:gjxie8005@hfut.edu.cn
  • 基金资助:
    安徽省优秀青年科技基金(No.06042086)；安徽省人才开发基金(No.2007Z028)资助项目

Optimization of Constrained Multi-layer Routing Algorithm

  1. School of Electronic Science and Applied Physics, Hefei University of Technology, Hefei 230009, China
  • Received:2009-01-13 Revised:2009-05-11 Online:2009-07-30 Published:2009-07-30

PDF

1516

被引次数

5

摘要：

提出一种以多层布线的通孔优化为目标、同时满足相交约束的算法. 当群体收敛到一定程度时，根据惩罚项选择个体，直到产生完全满足约束条件的可行解. 让群体在可行解的范围内进行精确搜索，得到全局最优解. 采用稳态繁殖和最佳个体保存法提高算法的效率. 该算法可避免产生不可行解，解决收敛速度和全局搜索性之间的矛盾，得到满意的通孔优化效果.

关键词: 有约束通孔优化, 多层布线, 遗传算法

Abstract:

The constrained via minimization (CVM) is a problem of determining which layers can be used for routing wire segments in interconnections of nets such that the number of vias is minimized. Based on a segment-crossing graph, a constrained via minimization algorithm for multi-layer routing is proposed. The algorithm uses tournament selection, selects individuals according to their penalty until feasible solutions are found, and searches for the best solution among feasible solutions. In addition, steady state reproduction and elitist model further improve efficiency of the algorithm. Experimental results show that the proposed algorithm is efficient and provides satisfactory solutions.

Key words: constrained via minimization, multi-layer routing, genetic algorithm

中图分类号: