基于自由分层的通道区布线算法

本文在分析线网之间关系的基础上提出了自由分层条件下的通道区布线模型:同层限制图Gs,相交图Gi,基于这一模型,分析了二层布线条件下对线网分层和布线序的基本限制,导出了分层的基本原则,在此基础上,分析了线网可Overlap的性质和条件,从总体分析的思想出发,提出了直接以完成布线通道区所需面积最小化为目标的分层布线算法,实验结果表明,通道区布线面积和通孔的致目比基于横竖分层的布线算法有较大减少,对于Deutsch′s diffjcult example,该算法获得18个track解。

Channel Routing Algorithm by Free Layer Assignment

A new channel routing model, while allows horizontal and vertical wire seg-ments to be placed on both layers, and two wires on different layer can be overlapped, is pre-sented. Based on this model, the constraints as well as the rules to layer assignment and routing order of nets in the two-layer channel routing are obtained. Then the property of opti-mal overlapping in a zone is analysed. By means of this property, the algorithm determines layer assignment and routing order of nets acoording to global optimat analysis. The routing area and number of vias are reduced much more than the router based on traditional Gv, Gh graph model. Preliminary experimental results are very encouraging. For the famous Deutsch's difficult example, the algorithm obtains 18 tracks solution.