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

Optimization of Constrained Multi-layer Routing Algorithm

作　　者：程心[1] 解光军[1] 杨依忠[1] 

机构地区：[1]合肥工业大学电子科学与应用物理学院,合肥230009

出　　处：《应用科学学报》2009年第4期387-391,共5页Journal of Applied Sciences

基　　金：安徽省优秀青年科技基金(No.06042086);安徽省人才开发基金(No.2007Z028)资助项目

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]