面向区域布线的层次式PB角勾链版图数据结构

摘要：

无网格区域布线具有存储量小、布通率较高、易实现混合设计规则布线并可解决串扰问题等优点.无网格区域布线算法中,找到路径后对底层版图数据库的修改时间在整个算法运行时间中占很大比例.因此,操作简便、快捷的版图数据结构对于无网格区域布线算法非常重要.目前在无网格区域布线算法中应用最广泛的版图数据结构是矩形角勾链,其点查找和模块插入操作的复杂度均为O(N1/2).文中提出一种新型的结合了Bin结构与梯形角勾链结构的层次式PB角勾链版图数据结构,其点查找和模块插入操作的复杂度降低至O(N1/2/r),其中r2为Bin数.同时,针对区域布线算法的特点,文中给出了层次式PB角勾链结构的点查找、区域枚举、推移等操作的算法.

关键词：层次式PB角勾链、版图数据结构、无网格区域布线

所属期刊栏目：23

分类号：TP301(计算技术、计算机技术)

资助基金：科技部科研项目G1998030413;中国科学院资助项目69776027

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：768-773