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

Channel Routing Algorithm By Free Layer Assignment

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

A new channel routing model,which allows horizontal and vertical wire segments to be placed on both layers,and two wires on different layer can be overlapped,is presented.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 optimal overlapping in a zone is analysed.By means of this property,our algorithm determines layer assignment as well as routing order of nets according to global optimal analysis.The routing area and number of vias are reduced much more than the router based on tra- ditional Gv,Gh graph model.Preliminary experimental results are very encou- raging.For the famous Deutsch's difficult example,our algorithm obtains 18 tracks solution.