摘要
提出了一种确定区域的详细布线算法，它能对不同设计模式进行布线．该算法能适用于任意多层布线情况，并且支持不同布线层具有的不同工艺参数．在构造布线树时，考虑芯片当前的走线拥挤度，使布线比较平均，并加快了算法运行速度、改善了布线质量．在连接两点线网时，构造基于二维迷宫布线结果的分层图，提出了一种对分层图的启发式染色算法来进行布线层分配，大大提高算法布线速度．采用拆线重布的方法来处理布线失败的线网．
An algorithm for the definite area detailed routing is presented. The algorithm can handle different design styles. Multiple routing layers and differing design rules of each layer are also supported. The wire congestion during construction of the routing tree is taken into consideration and measures are taken to average the wire congestion of the area, thus both the running time and the routing quality are improved. To avoid routing all nets in three dimensions, a heuristic algorithm for the graph coloring is proposed to solve the layer assignment problem. The rip up and rerouting techniques are used to link the unconnected nets.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
1999年第6期533-537,共5页
Journal of Computer-Aided Design & Computer Graphics
基金
国家"九五"攻关项目
博士点基金
国家自然科学基金
关键词
详细布线
迷宫算法
集成电路
制造工艺
detailed routing, minimum spanning tree (MST), maze routing algorithm, layer assignment, graph coloring
