角模块序列布图表示及基于角模块序列表示的边界约束布图规划算法

• 作者: C.K.Cheng 洪先龙 董社勤 蔡懿慈 顾钧 马昱春
• 来源期刊: 中国科学E辑
• 学科: 工学
• 关键词: VLSI布图规划 角模块序列(corner block list) 模拟退火算法 边界约束
• 年，卷（期）: 2002,（3）
• 页码范围: 409-418
• 页数: 10页
• 分类号: TN4
• 字数: 7166字
• 语种: 中文
• DOI: 10.3321/j.issn:1006-9275.2002.03.017

摘要

布图规划是VLSI布图设计中的关键环节, 通常采用随机优化算法, 而布图结构的编码表示(或称布图表示)是基于随机优化方法的布局算法的关键. 提出一种新的布图表示-角模块序列(CBL), 并从理论上证明它具有O(n)的布局评估算法计算复杂性和较小的解空间. 在布图设计中, 部分模块的位置需要满足一定的约束条件, 边界约束就是其中常见的一种. 通过边界约束可以将特定模块的位置限制在指定的边界上, 从而有利于模块与I/O端口的互连. 基于角模块表示, 推导出满足边界约束布局的充分必要条件, 并结合模拟退火过程, 通过修正中间解使受约束模块满足约束条件, 从而实现了基于CBL模型的边界约束布图规划算法. 将代价函数惩罚方法和启发式方法相结合, 设计了边界约束的惩罚项, 能够合理准确地衡量约束满足的情况, 从而有效地控制模拟退火的进度, 以保证最终布局满足所有约束. 对MCNC的标准例子的测试结果表明算法是十分有效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	董社勤	清华大学计算机科学与技术系	22	99	6.0	8.0
2	洪先龙	清华大学计算机科学与技术系	114	410	9.0	11.0
3	蔡懿慈	清华大学计算机科学与技术系	68	273	8.0	11.0
4	顾钧	香港科技大学计算机科学与技术系	19	289	7.0	17.0
5	马昱春	清华大学计算机科学与技术系	15	48	4.0	6.0