| Crosstalk-Aware Routing Resource Assignment |
| |
| 作者姓名： | Hai-LongYao Yi-CiCai QiangZhou Xian-LongHong |
| |
| 作者单位： | Hai-Long Yao，Yi-Ci Cai，Qiang Zhou，and Xian-Long Hong Department of Computer Science and Technology，Tsinghua University，Beijing 100084，P.R. China |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China under Grant No.60176016，The National Hi-Tech Development 863 Program of China under Grant No. 2002AA1Z1460，The Specialized Research Fund for the Doctoral Program of Higher Education under Grant No.20020003008. |
| |
| 摘 要： | Crosstalk noise is one of the emerging issues in deep sub-micrometer technology which causes many undesired effects on the circuit performance. In this paper, a Crosstalk-Aware Routing Resource Assignment (CARRA) algorithm is proposed, which integrates the routing layers and tracks to address the crosstalk noise issue during the track/layer assignment stage. The CARRA problem is formulated as a weighted bipartite matching problem and solved using the linear assignment algorithm. The crosstalk risks between nets are represented by an undirected graph and the maximum number of the concurrent crosstalk risking nets is computed as the max clique of the graph. Then the nets in each max clique are assigned to disadjacent tracks. Thus the crosstalk noise can be avoided based on the clique concept. The algorithm is tested on IBM benchmarks and the experimental results show that it can improve the final routing layout a lot with little loss of the completion rate.
|
| 关 键 词： | 串扰 互连 结构设计 布线 VLSI |
| 收稿时间： | 10 March 2004 |
Crosstalk-Aware Routing Resource Assignment |
| |
| Hai-LongYao Yi-CiCai QiangZhou Xian-LongHong.Crosstalk-Aware Routing Resource Assignment[J].Journal of Computer Science and Technology,2005,20(2):0-0. |
| |
| Authors: | Email author" target="_blank">Hai-Long?YaoEmail author Yi-Ci?Cai Qiang?Zhou Xian-Long?Hong |
| |
| Affiliation: | (1) Department of Computer Science and Technology, Tsinghua University, Beijing, 100084, P.R. China |
| |
| Abstract: | Crosstalk noise is one of the emerging issues in deep sub-micrometer technology which causes many undesired effects on the circuit performance. In this paper, a Crosstalk-Aware Routing Resource Assignment (CARRA) algorithm is proposed, which integrates the routing layers and tracks to address the crosstalk noise issue during the track/layer assignment stage. The CARRA problem is formulated as a weighted bipartite matching problem and solved using the linear assignment algorithm. The crosstalk risks between nets are represented by an undirected graph and the maximum number of the concurrent crosstalk risking nets is computed as the max clique of the graph. Then the nets in each max clique are assigned to disadjacent tracks. Thus the crosstalk noise can be avoided based on the clique concept. The algorithm is tested on IBM benchmarks and the experimental results show that it can improve the final routing layout a lot with little loss of the completion rate. |
| |
| Keywords: | crosstalk interconnect physical design routing track/layer assignment VLSI |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载全文 |
