基于V型框架的多层无网格布线算法

为了提高大规模布线的布通率，加快布线速度，提出了一个基于“V”字型框架的总体布线与详细
布线交替进行的多层无网格布线算法.算法分粗化和细化两个阶段：粗化阶段，在每一层次对局部线网进
行总体和详细布线，先期得到布线结果，从而逐层次降低布线规模，同时也增加了总体和详细布线间的
交互性和布线资源估计的准确性；细化阶段,对布线解进行优化，并对粗化阶段布线失败的线网进行重布
线.总体布线采用速度很快的模式布线方法，并针对无网格布线的特点，引入了一种扫描布线障碍的布线
资源估计方法，无网格详细布线中则引入了通孔优化策略.实验证明，该算法在布通率、运行时间等方面
都得到了提高.

Multi-layer gridless routing algorithm with V-shaped framework

In order to improve the routing ratio and routing speed in large scale routing problem, a multilayer gridless routing algorithm with V-shaped framework was presented, in which global and detailed router ran alternately. The algorithm is comprised coarsening step and fine step. In coarsening step, global routing and detailed routing were done to local nets in each level and routing results could be obtained in advance. Consequently, the scale of routing was reduced level by level and at the same time, the interaction of global routing and detailed routing and the accuracy of routing-resource-estimation were increased. In the fine step, routing solution was optimized and the failed nets in coarsening step were rerouted. The global routing used pattern routing method, which had a fast speed, and according to the feature of gridless routing, a resource estimation method was introduced, which estimated resource by sweeping obstacles. Via optimization strategy was introduced in the detailed routing. The experiments showed great improvement in routing ratio and running time.