一种基于通孔数最小化的多层通道布线算法

该文提出了一种基于通孔数量小化的多层通道布线算法，算法采用非预留层模，首先根据线网之间的位置关系利用模拟退火算法将各线网合理地分配到对应的布线层中去，然后利用遗传算法得到相关布线层中线网的最佳布线顺序向量，最的根据得到的顺序向量利用“沉积法”将各线网布于合理的通道上，该算法克服了传统通孔优化算法中原始布线对优化结果的不利影响，使通孔的优化达到很好的效果。

A Multi-Layer Channel Routing Algorithm Based on Via Minimization

In most current technologies, two or more layers are available for routing. Most of the existing routing algorithms use a large number of vias to complete the routing. This is due to the fact that most routers use a reserved layer model. However vias are undesirable from fabrication as well as circuit performance point of view and therefore, the number of vias should be kept as small as possible. Significant volume of research exists on techniques for reducing the number of vias in a completed detailed routing by re-assigning the wire segments to different layers. This kind of via minimization is called constrained via minimization (CVM). Via minimization has also been considered without the restriction of complete routing. In this approach, the actual layout of wire can be changed and thus offers more flexibility as compared to the CVM approach. This via minimization approach is called unconstrained via minimization (UVM) or topological via minimization (TVM). In UVM problem, the placement and the layer assignment of segments are not given. The problem is to both place the segments and also assign the layers so as to minimize the total number of vias. In other words, UVM is an integrated approach to routing and via minimization. A UVM via minimization model, consisting of two graphs called net constraint graph and net position graph respectively, is presented in this paper. Based on the model, a via minimization algorithm for multi-layer channel routing is proposed in this paper, too. The algorithm firstly assign all nets to proper layers according to the positional relation between each net in the net constraint graph, using simulated annealing algorithm, then using net position graph to get a best order vector of the concerned layers' nets based on genetic algorithm, and finally assign each net to proper tracks with deposit algorithm. It overcomes the disadvantage of original assignment affecting to the final result in traditional via minimization algorithms. Compared to existing UVM and CVM algorithms, experiment results show this algorithm have a better result on via minimization.