论文部分内容阅读
当今,随着片上系统(SoC)以及片上网络(NoC)的不断发展,在层次化设计中,许多学者根据芯片的性能和可靠性的需求,在布局中增加了一些与实际需求相关的约束,其中包括模块间的位置约束,比如对齐约束、边缘约束、性能约束、电性能约束等等。现代布局问题已经从简单的、传统的布局问题,向具有各种条件约束的、复杂的布局问题转变。在解决带约束的布局问题时,本文采用B*-Tree表示法进行布局。它是一种灵活高效的有序二叉树表示方法。本文针对两种约束布局进行了研究,即对齐约束布局和性能约束布局。由于模块的排布是用坐标来表示,因此对齐约束可按方向分为水平方向对齐约束和竖直方向对齐约束。本文基于B*-tree表示法进行约束布局,实现了水平方向对齐约束布局、竖直方向对齐约束布局和性能约束布局的混合约束布局。并深入地研究了B*-tree的构造及特点,提出了三个对应约束的充分条件,提出优化算法可快速筛选合法解。针对模拟退火算法,也提出了它的优化流程。即在每次降温迭代的过程中,我们要检测其布局是否合法,如果是非法的,则动态的将之合法化,完成此温度下的布局。在降温迭代产生新的解空间的过程中,加入判断步骤以减少时间的开销来提高效率。实验数据验证,本文约束的实现是成功的、优化流程是行之有效的。随着VLSI的不断大型化、复杂化,晶元的个数成指数增长,在现阶段芯片的设计过程中,布局时延成了布图规划瓶颈。所以,把布局中一些重复劳动省去,达到减少时延的目的增量式算法成为研究的热点。本文通过深入的分析研究,我们采取了一种折中的三划分的增量式约束布局。该增量式约束布局分为两个阶段,第一段是用三划分法解决增量式布局,第二个阶段是基于本文约束布局的增量式布局。由于二者的约束方法和处理非法解的方法是相同的,因此实现增量式的约束布局不再赘述。随着测试实例中的模块数量增加,增量式布局的优势逐渐增强。由此可推知,增量式约束布局对今后的VLSI布局具有一定的影响。实验结果表明该增量式约束布局已完成设计要求,很好避免了一些重复性的操作而节省布局时间。