基于最小生成树的动态通道布线算法

Dynamic Channel Routing Algorithm Based on Minimum Spanning Tree

针对电子设计自动化中低的通道布线布通率,对影响布通率的因素进行了研究,分析了线网布线次序对通道布线结果的影响,比较了静态排序和动态排序的优缺点,基于最小生成树,提出了一种动态通道布线算法.在布线过程中,根据通道已布线状态,计算剩余线网加权后各自的最小生成树,优先选择受已布线线网影响最大的线网进行连接,避免连接点距离较远的线网对连接点距离较近的线网的约束.实验结果表明,对同一个布局,采用相同的布线规则,算法占有空间资源少,比商用软件在通道布线方面具有更高的布通率.

Aiming at the low connection ratio of the channel routing in electronic design automation （EDA）, the influence factors are studied in detail. The routing order of the channel routing is analyzed and the characteristics of static and dynamic ordering are compared. On these bases, a minimum spanning tree （MST） based dynamic channel routing algorithm is proposed. In the routing process, the individual MST of the remaining wire nets is calculated according to the channel state. The wire net suffered most from the wire net that is routed recently is selected first to be connected to avoid the fact that the wire net with near nodes is restricted by the one with far nodes. The experiment shows that for the same layout, the MST based dynamic channel routing algorithm occupies less memory and possesses higher connection ratio than the commercial software in the channel routing under the same routing rules.