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

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

面向BBL布局的遗传算法研究

BBL布局问题是VLSI物理设计中的一个重要问题，其质量的好坏直接影响物理设计的其它阶段。本文基于角模块序列（CBL）的布图结构表示方法．采用遗传算法进行求解，实验结果表明，遗传算法在求解该问题上是有效的。

芯片级布图规划中的缓冲器规划算法

文中对纳米技术下, 互连驱动的芯片级布图规划问题中的缓冲器规划问题进行了研究, 提出了基于空白区重分布(redistribution)的缓冲器规划算法; 布局中的空白区是指在布局中不被任何电路模块占用的闲置区域; 该算法充分利用布局中的空白区插入缓冲器. 在基于拓扑的布图规划表示中, 可以把电路模块和空白区相关联, 在相应区域内移动一些电路模块就可以达到重分布空白区的目的. 在进行空白区重分布的过程中, 给定布局的总面积和拓扑结构将维持不变. 通过重分布布局中的空白区, 可以增加满足时延约束的线网数目; 实验证实, 满足时延约束的线网数的增长率平均达到9%.