Dynamic Channel Routing Algorithm Based on Minimum Spanning Tree

魏建军; 康继昌; 雷艳静; 陈付龙

您当前的位置：

首页 >

文章列表页 >

Dynamic Channel Routing Algorithm Based on Minimum Spanning Tree

更新时间：2026-09-14

- Dynamic Channel Routing Algorithm Based on Minimum Spanning Tree
- 基于最小生成树的动态通道布线算法
- Issue 2, Pages: 120-124(2008)
- 作者机构：
  
  西北工业大学计算机学院
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：2008
- 稿件说明：
移动端阅览
魏建军, 康继昌, 雷艳静, et al. Dynamic Channel Routing Algorithm Based on Minimum Spanning Tree[J]. 2008, (2): 120-124.
DOI：

魏建军, 康继昌, 雷艳静, et al. Dynamic Channel Routing Algorithm Based on Minimum Spanning Tree[J]. 2008, (2): 120-124. DOI：

摘要

针对电子设计自动化中低的通道布线布通率

对影响布通率的因素进行了研究

分析了线网布线次序对通道布线结果的影响

比较了静态排序和动态排序的优缺点

基于最小生成树

提出了一种动态通道布线算法.在布线过程中

根据通道已布线状态

计算剩余线网加权后各自的最小生成树

优先选择受已布线线网影响最大的线网进行连接

避免连接点距离较远的线网对连接点距离较近的线网的约束.实验结果表明

对同一个布局

采用相同的布线规则

算法占有空间资源少

比商用软件在通道布线方面具有更高的布通率.

Abstract

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.

关键词

Keywords

references

Chang Yaowen,Lin Shiping.A new framework for multilevel full-chip routing[J].IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems,2004,23(5):793-800.

Masakazu Ando,Tatsushi Nishi,Masami Konishi,et al.Autonomous decentralized route planning method and itsapplication to a dynamic route planning[J].Proceedings 2003 IEEE International Symposium on ComputationalIntelligence in Robotics and Automation,2003,8(16):492-503.

Li Yilang,Li Jinyi,Chen Wenbin.An efficient tile-based ECO router using routing graph reduction and enhancedglobal routing flow[J].IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems,2007,26(2):345-357.

原军,王世英.一类互联网络模型[J].华北工学院学报,2003,24(5):363-365.Yuan Jun,Wang Shiying.A class of interconnection network models[J].Journal of North China Institute ofTehcnology,2003,24(5):363-365(in Chinese).

冯文丽.树的顶点扩张图的最小直径定向[J].中北大学学报(自然科学版),2006,27(2):132-134.Feng Wenli.Minimum diameter orientations for tree vertex-multiplication graphs[J].Journal of North University ofChina(Natural Science Edition),2006,27(2):132-134.(in Chinese)

杨柳,洪先龙,蔡懿慈,等.带有引线端预处理的区域布线算法[J].计算机辅助设计与图形学学报,2006,18(1):69-75.Yang Liu,Hong Xianlong,Cai Yici,et al.A detailed routing algorithm with optimized pin mapping strategy[J].Journal of Computer2aided Design&Computer Graphics,2006,18(1):69-75(in Chinese)

Views

345

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Design of Parallel Robot Experimental Platform Based on Reconfigurable Innovative Components

《中北大学学报(自然科学版》》征稿简则

A Shock Wave Testing System for High⁃Altitude Explosion Experiments

Study on the Removal of CO2 in Confined Space by High⁃Gravity Enhanced Potassium Hydroxide Coupled Potassium Glycinate Solution

Hopkinson Bar Pulse Width Extension Test Method Based on Polyurethane Wave Shaper

Related Author

No data

Related Institution

No data

⁰