的选择。有数据表示，以往的 SA 主要是面向可 Slicing Structure 的布图规划这 一类问题。虽然 Slicing Structure 的布图规划在通道布线利用率上有更好的效果， 但是也都一个相当局限的地方就是会浪费芯片的面积。另一个 Non-Slicing Structure，当你完成了一开始的布局想要进行迭代算法时有些困难。由于缺乏有 效的数据表示，一些行之有效的随机优化算法难以得到应用。 

2.4 VLSI 布图规划问题和序列对模型

2.4.1 布图规划问题的描述

VLSI 布图规划可以用下面三个部分表示，它的输入如下： 

（1）一个集合 B= { M1 ，M2 ，… }是通过模块集合而成，集合中的任何模 块都有确定边长范围这一特点或者是一些形状不定的硬模块，还有的是面积确

定不变但是长和宽的比例在一定范围内可以变形的软模块。我们可以发现任何

布局的模块 M  有一个集合 P = {   p  ， p  ，… }是关于端口的，其中被放在

i i

边界上的就是端口 pij   。 

i1 i 2

（2）此外，还有一个网表 S = { L1  ， L2 ，… }，当中的Li用来表示某个端

口的集合。我们把可以分配到同一端口的网结合在一起。 

（3）各种约束范围是由用户确定的，芯片的 RA 或芯片的最大长度和宽度 等形状部分的条件，和所在路径上产生的最大的时延约束等。 

给定了输入以后，布图规划的目的是尽可能的把需要的模块放在芯片适合 的地方，不仅要满足在已经约束的范围之内，更是希望芯片的面积越小越好， 达到以上两个要求之后，更高的要求就是模块间的连线总的长度更短和性价比 更高。 文献综述

2.4.2 序列对模型

在布图规划和 BBL 布局问题中，首先就应该考虑芯片的面积优化 。序列 对模型就是针对这类问题一种很有效的数据表示。

序列就是指由所有模块的两个有顺序的排列形成的对。在布图规划中每个 布局都相应会有一个序列对。也就是说，如果给出了一个确定的序列对，任何 模块间的水平关系图和与垂直关系图也就唯一确定 。

可二划分结构的布局可以用一类特殊的序列对加以表示，即具有可二划分 结构布局对应的解空间是一般序列对解空间的子集。这同时也说明可二划分结 构的最优布图面积通常是大于一般结构的最优布图面积的。

2.4.3 软模块的布图规划设计

    通常处理软模块的布图规划相关问题，我们需要给所有模块确定数目的备 选模块，这是因为这些模块有各种各样的长宽比例。这样我们在实验中就可以 更全方面进行测试。我在查找资料中发现利用遗传算法是通过对布局好的硬模 块进行改造加入了软模块来优化结果，在调整之前先要把硬模块如何布局规划 好，这样会使软模块的布图有了一定的局限性。此外,我们在试验中发现，即使 关于硬模块的布局已经达到了很高的面积利用率，在其基础上的改进的效果还 是不能令人十分满意。产生这种情况的原因很大一部分是因为模块之间的关系

确定，在软模块加入后没有办法进行更多样化和更令人满意的调整。 面向软模块的固定边框的布图规划(FOF)问题的输入包括[14]： 来!自~优尔论-文|网www.youerw.com

（1）集合 M={ m1 ，m2 ，… mn }是 n 个模块的集合，模块 宽用 a i ， hi 和 wi 表示； 

mi 的面积、高和