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

摘要

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