用角轮廓结构实现基于O-Tree表示法的模块快速放置算法

• 作者: 于永斌 李康 虞厥邦
• 来源期刊: 计算机辅助设计与图形学学报
• 学科: 工学
• 关键词: VLSI物理设计 布局 O-Tree表示法 角轮廓 放置算法
• 年，卷（期）: 2008,（10）
• 所属期刊栏目: VLSI设计与测试及电子设计自动化
• 页码范围: 1297-1302
• 页数: 6页
• 分类号: TP391.7
• 字数: 4485字
• 语种: 中文

摘要

在VLSI物理设计中,O-Tree是一种高效简洁的布局表示法,但其对应的模块放置算法因为基于水平和垂直约束图及其操作而复杂且费时(算法时间复杂度为O(n2)).文中算法利用模块放置过程中右上端边沿形成的角轮廓结构的阶梯下降性,结合O-Tree编码结点间的父子关系,快速确定模块的放置位置.在模块的放置过程中不需要约束图,只保持一个角轮廓,使模块的放置更加简单高效,算法时间复杂度降低为O(nlogn). 在MCNC Benchmark上的实验结果验证了该算法的有效性.