基于角模块布图表示的增量式布图规划算法

• 作者: 周强 杨柳 洪先龙 董社勤 马昱春
• 来源期刊: 半导体学报
• 学科: 工学
• 关键词: 增量式布图规划 角模块布图表示 连接图 平衡点
• 年，卷（期）: 2005,（12）
• 所属期刊栏目: 研究论文
• 页码范围: 2335-2343
• 页数: 9页
• 分类号: TN47
• 字数: 1177字
• 语种: 中文
• DOI: 10.3321/j.issn:0253-4177.2005.12.014

摘要

提出了一种基于CBL布图表示的新的增量式布图规划算法.该算法能很好地解决包括不可二划分结构在内的布图规划问题.针对现有增量式的一些需求,算法给出了相应的高速解决方案.在已有的初始布局的基础上,基于CBL表示方法建立水平约束和垂直约束图,利用图中关键路径和各模块之间的累加的距离松弛量进行增量式操作.对于新模块的插入,在力求面积最小,线长最短和移动模块数目最少的目标指引下能快速地找到最佳位置作为插入点,高效地完成相关操作,算法的时间复杂性仅为O(n).通过对一组来自工业界的设计实例的测试结果表明,该算法在保证芯片的面积、线长等性能不降低甚至有所改善的情况下,运行速度相当快,仅在μs量级,满足了工业界对增量式布图规划算法在速度上的首要要求,同时保证了基本性能的稳定.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	董社勤	清华大学计算机科学与技术系	22	99	6.0	8.0
2	洪先龙	清华大学计算机科学与技术系	114	410	9.0	11.0
3	周强	清华大学计算机科学与技术系	73	599	13.0	22.0
4	马昱春	清华大学计算机科学与技术系	15	48	4.0	6.0
5	杨柳	清华大学计算机科学与技术系	24	244	8.0	15.0