并转(2)继续执行;若不满足 件,则转(4)。
(4)检查A=ɸ
若不满足条件,i=i+1,转(1)产生新的划分集;否则结束划 分过程,输出划分结果。
14
简单连接度划分示例
解:设有待划分集合A={a,b,c,d} Con(a,A-a)=3 Con(b,A-b)=6 Con(c,A-c)=2 Con(d,A-d)=3 (1)∵Con(c,A-c)最小,将其选出,则Ai={c}, A={a,b,d}; (2)虽然d与b与Ai的连接度相同,但Dis(Ai,d)﹤Dis(Ai,b),选中d; (3)检查,测定满足条件,即S、E均满足条件(面积和边界连线端子的约束)。Ai={c,
7
§1.逻辑划分
• 布图规划过程与所用的算法和求解策略有关。一个典 型的布图规划过程一般包括:Bottom up结群并产生结 群树、Top down软模块布局、调整模块形状和确定模 块的引线位置,目标是使芯片面积、总连线长度最小 和优化输出结果。
• 布规划分为物理分级构造、分级布图规划和详细布图 构造三大部分,每个部分又分成若干过程。物理分级 构造是一个Bottom up结群和估计模块面积的过程;分 级布图规划则是个Top down软模块布局、布线区面积 估计和分配、模块形状调整以及布局修正的过程;随 后在详细布图构造中完成整个布局和布线。
(2)在A中取出一个单元a2,使Con(Ai,a2)为最大,即最相关。 如果存在两个以上连接度相同的单元,则选Dis(Ai,a2)最小 的单元,即a2与其它单元有弱的连接关系。
(3)检查
S( E(
Ai Ai
) )
S max E max
,是否符合给出的面积和出线端的限 制条件。
如满足条件则
AAi