A Gridless Router Based on Hierarchical PB Corner Stitching Structure  

一个基于层次式PB角钩链结构的区域布线器(英文)

作　　者：张轶谦[1] 蔡懿慈[1] 洪先龙[1] 张雁[1] 谢民[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《Journal of Semiconductors》2003年第2期141-147,共7页半导体学报（英文版）

基　　金：国家自然科学基金 (批准号 :60 1670 16);国家重点基础研究发展规划 (No.G19980 3 0 40 3 )资助项目~~

摘　　要：A multi layer gridless area router is reported.Based on corner stitching,this router adopts tile expansion to explore path for each net.A heuristic method that penalizes nodes deviating from the destination is devised to accelerate the algorithm.Besides,an enhanced interval tree is used to manage the intermediate data structure.In order to improve the completion rate of routing,a new gridless rip up and rerouting algorithm is proposed.The experimental results indicate that the completion rate is improved after the rip up and reroute process and the speed of this algorithm is satisfactory.提出一个新的基于层次式 PB角钩链结构的多层无网格布线器 .该布线器基于 PB层次式角勾链数据结构和网块扩展算法 ,使用朝向目标的加速策略提高算法的运行速度 ,并使用改进的二叉区间树管理算法的中间数据 .还提出了基于拥挤度的无网格拆线重布算法 .通过显式记录每个线网段周边的拥挤状况 ,并将其结合到网块扩展的费用当中 ,使拆除线网的选择和待布线网的路径搜索统一起来 .实验结果表明 ,该布线器能有效地提高布通率 。

关 键 词：gridless area routing rip  up and reroute corner stitching structure VLSI 

分 类 号：TN402[电子电信—微电子学与固体电子学]