智能识点法实现MD模型上的自动布线

Realize Automatic Routing in MD Model by Intelligent Discern Points Algorithm

给出了一种MD模型上的布线算法。首先,提出了MD模型上的广义线段的概念;其次,依据人工智能的思维给出绕障点的定义方法;最后,以绕障点和待布点组成布线点集合,以布线点集合中的所有点为顶点构造带边权值的完全图,将布线问题转化为在带边权值的完全图中求布线点间的最短路径,从而得到最优布线路径。实验证明算法的性能良好。

A automatic routing algorithm is presented in Manhattan-diagonal （MD） model with tracks in horizontal,vertical,and ±45 directions.First,the concept of generalized line segment is presented in MD model.Second,by means of artificial intelligence theory,the way of deciding the position of detouring points is proposed.Finally,a set of point which is made up of detouring points and pins is formed.By using the points of the set as the vertices ,a weighted complete graph is formed.The question of routing is transformed into finding shortest-path problem in the weighted complete graph. Thereby,the optimization of routing is found. It is proved by experimentation that the algorithm performance is efficient.