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

• 作者: 张雁 洪先龙 王葆华 蔡懿慈
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 层次式PB角勾链 版图数据结构 无网格区域布线
• 年，卷（期）: 2000,（7）
• 所属期刊栏目: 短文
• 页码范围: 768-773
• 页数: 6页
• 分类号: TP301
• 字数: 5905字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2000.07.016

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	洪先龙	清华大学计算机科学与技术系	114	410	9.0	11.0
2	蔡懿慈	清华大学计算机科学与技术系	68	273	8.0	11.0
3	张雁	清华大学计算机科学与技术系	3	24	2.0	3.0
4	王葆华	清华大学计算机科学与技术系	1	2	1.0	1.0