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

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