带有引线端预处理的区域布线算法  

A Detailed Routing Algorithm with Optimized Pin Mapping Strategy

作　　者：杨柳[1] 洪先龙[1] 蔡懿慈[1] 周强[1] 

机构地区：[1]清华大学计算机科学与技术系EDA实验室,北京100084

出　　处：《计算机辅助设计与图形学学报》2006年第1期69-74,共6页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(60176016);国家"八六三"高技术研究发展计划(2002AAIZ1460);高等教育博士培养计划专用基金(SRFDP)(200200030008)

摘　　要：提出一种带有引线端优化处理的多层区域布线算法,能处理端点障碍在区域内任意分布的大量布线问题.首先将多端线网划分为二端子线网,并在此基础上根据二端子线网之间的相对位置关系进行分类;然后对每个类型的二端子线网,采用双向迷宫和朝向目标的深度优先搜索策略依次布线;最后通过拆线-重布策略来解决布线冲突.在进行布线搜索之前,对引线端映射到网格点上这一过程引入了一种有效的优化预处理机制,采用二分图中多目标约束寻找最佳匹配的思想和策略来解决引线端优化映射问题.测试并比较了有/无这种优化处理的2种情况,实验结果表明,该算法有效地改善了网格映射的精度和准确性,可缩短线长和提高布通率.A new multi-layer area routing algorithm with optimized pin mapping strategy is presented. The algorithm can handle large routing problems, in which terminals and obstacles arbitrarily located in the routing area. Firstly, it divides each net into two-pin subnets according to their relative positions. Then, every subnet is routed in turn by an improved Maze algorithm. The routing conflicts are solved by rip-up and rerouting approach. An optimized pin mapping strategy is proposed as a pre-process before routing. The best matching of a bipartite graph is used to solve the pin-mapping problem. We tested our algorithm on a set of benchmark examples and compared our routing results with the results without pin-optimized mapping. Experimental results show that, the algorithm efficiently shortens the total wire length greatly and increases the routing completion rate.

关 键 词：区域布线 引线端(pin)映射 二端于线网 迷宫算法 

分 类 号：TN47[电子电信—微电子学与固体电子学]