第九 布局.ppt

门阵列布图模式改善布局的目标是可布性好, 即希望线网匀分布,其目标函数为: MIN(MAX ) 式中: 是水平切割或垂直切割的割线数。 2)基于对交换的迭代改善 基于对交换的迭代该善是一种简单而实用的 迭代改善算法。它通过芯片上一对单元的位置 互换而产生一个新的布局，与不同目标函数结 合就形成了不同的迭代改善方法。 a、成对交换法 b、力矢量成对交换松弛法 c、力矢量指向交换法 a、成对交换法: b 、力矢量成对交换松弛法 受的拉力由虎克定律确定。 目标函数选为式(9.35)的型式,算法步骤如下: c、力矢量指向交换法 3)基于最小割(值)的交换算法 a) 割值最小化的目标函数 b)割值最小化的算法: (i)面向切割线的最小割算法 (ii)面向模块的最小割算法 面 向模块的最小割算法以块或块的一个子集为基础。这种方式对于指定的块或块的子集用一条(或一个序列的)割线来进行切割。此切割对非指定的块不起分割作用。如下图所示,割线C2只划分A1而对A2不起作用.这种划分对块的选择和划分都比较灵活，较适用于BBL模式的布局改善。 (iii) 块和切割线顺序的选择: 最小割算法的处理效率与切割线选择的顺序有关.选择模块与割线可采用深度优先或广度优先策略.在深度优先处理方式中,每次处理的是那些允许继续分割的块中具有当前最高级别的块;而在广度优先处理方式中,只有所有j级的块都已分划、处理完毕后,才开始处理j+1级的块。我们以割线的处理顺序为例看条状切割和正交切割中的两种选择策略: (1) 条状切割: 在条状切割中,选择割线的处理顺序为 C1,C2,C3….,每次分划时,应注意使割线两側具 有大致相同的模块数。如下图所示: 图(a)为深度优先 图(b)为广度优先 图中给出了两种不同策略下的割线的位置 及分割过程的树状结构示意图。 C1 C2 C9 C3 C6 C4 C5 C7 C8 (a) 深度优先 C1 C2 C3 C4 C5 C6 C7 C8 C9 C1 C4 C2 C7 C3 C5 C6 C1 C2 C3 C4 C5 C6 C7 (b) 广度优先 (2) 正交切割: 按照”水平—垂直—水平”交替的顺序选择割线，也可以采用深度优先或广度优先的策略对区域近行划分.如下图: C1 C2 C3 C4 C5 C6 C1 C2 C4 C6 C3 C5 (a) 广度优先 (b) 深度优先 4) BBL模式下的布局改善 5) 基于数学规划方法的布局迭代改善 6) 基于模拟退火算法的布局方法 7) 基于神经网络算法的布局方法 8) 基于遗传算法的布局方法 结 束 * 复合目标函数2: 这个目标函数用于标准单元，其中, (9.11) 复合目标函数3: 9.4 初始布局 布局设计由于其复杂性,一般分为初始布局和迭代改善布局两个子过程。由于初始布局一般采用快速的构造性算法,所以也称为构造性布局。初始布局的目的是求得一个比较好的布局初始构形,以减少迭代改善的次数,从而提高整个布局设计的质量和处理效率。 初始布局需要确定所采用的选择函数和安置规则，所以其算法由选择和安置两部分组成,而这些选择函数和安置规则往往是启发性的和易于度量的。选择就是从未布单元集中 选择一个(或一组)准备安置;而安置就是把选则的单元放置在芯片的合适位置上。初始布局应使两者策略(目标函数)一致。 9.4.1 单元的安置 介绍单元的安置算法和安置策略: 1) 安置的最佳位置—”重心”的概念 2) 一维最佳安置算法 3) 二维最佳安置算法 4) 两种安置的策略 1) 安置的最佳位置 假设模块M可以放置在芯片上的mXn个不同位置上,有n个线网与模块M相连,一般希望把M安置在使连线总长度最小的位置。该最佳位置称为”重心” 。 但对不同的布局模式又可以有一维和两维两种安置算法。 2) 一维安置 标准单元或门阵列行内单元的安置是一种 一维安置。一维安置可采用等分接点法或重 心法求解重心位置。 (1) 等分接点法 若在X轴上有序