摘 要： 对模拟集成电路自动布局方法进行研究，提出基于直流通路划分的布局算法，结合直流通路顺序约束和电源方向上的位置约束，采用空间搜索布局算法提供初始布局，并用模拟退火算法进行迭代优化。使用工业界常用的电路做测试，实验结果表明，该方法可以在满足对称和邻近等约束的基础上产生紧凑的布局结果，并且最小化直流通路和信号流路径的寄生效应。
0 引言
与数字集成电路相比，模拟集成电路具有性能指标复杂、对干扰十分敏感等特点，所以模拟集成电路版图设计中需要满足匹配、对称、临近等约束。这些约束在过去几十年中已经得到了广泛的研究[1-3]，但主要集中于解决部分约束而很少考虑电路性能，效率不高且不易达到版图设计要求。
本文在模拟集成电路布局过程中按照直流通路划分电路，在布局阶段采用空间搜索算法提供一个很好的初始布局，然后采用模拟退火算法进行迭代优化，并且同时解决对称、临近等约束。
1 约束的描述
图1是工业界常用的一种带共模反馈的全差分运算放大器电路原理图。下面将结合该电路介绍本文处理的各种约束。
1.1 直流通路顺序约束
通常，电路可以分解为信号流电路和偏置电路，它们分别由不同的直流通路组成。模拟集成电路版图中如果直流通路相邻放置，可以大大减小两个直流通路间的互连线长度，从而减小连线的寄生效应，改善电路性能。直流通路顺序约束指布局结果遵从直流通路的顺序。图1共有以下4个直流通路：G1(PM0,PM1,PM2,NM1,NM2),G2(PM3,NM3,C1,R3,R4),G3(PM4,NM4,C2,R1,R2),G4(PM5,
PM6,PM7,NM5,NM6)。
1.2 对称约束
在高性能电路，尤其是全差分电路中，通常要求器件对称放置以减小寄生及其引起的失配。关于y轴方向对称的器件的坐标需要满足以下条件：
关于x轴方向对称与y方向类似。
1.3 临近约束
在模拟集成电路版图中，有时需要对特殊器件作临近处理。例如有些器件放在同一衬底/阱内可以大大减小失配，例如图1中PM0和PM5；有时多个器件的参数成比例关系,例如图1的R1和R2，此时将它们作临近处理可以减小工艺带来的失配。
1.4 电流方向上的约束
在一个电路设计中，VDD和GND可以为上下位置关系或者左右位置关系。所以定义了直流通路内部的位置约束：靠近电源、靠近地、上下位置关系。
2 序列对的描述
序列对(Sequence Pair)[4]是一对表示版图器件相对位置关系的序列。例如，一个序列对(α，β)=(ABC，BAC)，其中A、B、C是器件名称。αi表示序列α中的第i个位置的元素，α表示 A在序列α中的位置。序列对表示两个器件相对位置关系的方式为：
实验表明，任何一个版图都可以由一个序列对表示其器件的相对位置关系。
本文采用层次化的序列对表示版图中单元的相对位置信息。采用的序列对共有两层，以图2为例介绍。第一层是器件组序列对(称为Cluster SP)。例如图2中，Cluster1有以下约束：a1在a2左侧，a3在a1和a2上方，则cls1=((a1,a2,a3),(a3,a1,a2))；第二层是整体序列对(称为Whole SP)。图2中cls1,cls2和cls3 3个器件组满足以下相对位置关系：cls2在cls1下侧，cls3在cls1和cls2右侧，则可以得到WholeSP=((cls1,cls2,cls3)，(cls2,cls1,cls3))=((a1,a2,a3,b1,b2,b3,c1,c2),(b2,b3,b1,a3,a1,a2,c2,c1))。
3 空间搜索布局算法
本文采用空间搜索布局算法为后面的模拟退火算法提供一个好的初始解，空间搜索布局(Space Search Place，
SSP)过程分为3步：
(1)由器件组序列对构造各器件组布局；
(2)依次放置各器件组，器件组边界为矩形；
(3)对所有器件组进行非矩形化调整。
3.1 构造器件组
由ClusterSP可以构造出每一个器件组布局。假设器件组A包含a1,a2,a3,a4。A的序列对(α, β)=((a1,a2,a3,a4)，(a4,a2,a3,a1))，则可构造出A的布局结果，如图3(a)左侧所示。图3(a)右侧是序列对B(α, β)=((b1,b2,b3,b4,b5),(b4,b5,b3,b1,b2))的布局结果。
3.2 矩形器件组构造基础版图
由于器件组序列对已经确定组内单元的相对位置关系，所以放置器件组时，先确定该组的边界，然后整体放置该组即可。以图3(b)为例，最先放置cls1(包含a1,a2,a3,a4)后，cls2在cls1右侧。由此形成的布局结果如图3(b)所示。
3.3 器件组的非矩形化调整
将所有器件组按矩形边界放置后还需要调整器件组边界为不规则图形(jagged boundary)[5]。
对器件组内各单元的调整分为两步：(1)做边界扫描，找到该单元可以放置的空间；(2)确定最合适的空间放置该单元。边界扫描算法的流程如下：
Algorithm PlaceToLeft (BoxVec ,mj)
begin
p=0;//放置成功的标志位
for iter=BoxVec.begin() to BoxVec.end()
if iter->top – iter->bottom >= mj.height;then{
PToLeft(mj);return 1;}//置于所有器件左侧
comb= bCombine(bdBoxVec_sort);
//检查是否有空间可以与*iter合并
if comb==0 //没有可合并空间
then{ if *iter ==BoxVec.back()
PToLeft(mj);
else continue; }
else
for iter2=BoxVec.begin() to iter-1
if iter2->bm == iter->top
then{iter->top=iter2->top;
BoxVec.erase(iter2);
PlaceToLeft (mj); ++p;}
else if iter->bm== iter2->top
then{iter->bm=iter2->bm;
BoxVec.erase(iter2);
PlaceToLeft (mj);++p; }
if p==1 break;
endfor
endelse
if p==1 break;
endfor
end
4 模拟退火优化
本文采用模拟退火算法进行迭代优化。采用的扰动方式及其对约束的处理如下：
(1)M1：无约束器件在其器件组内移动(在α或β或两者中)。
(2)M2：有约束器件在其器件组内移动(在α或β或两者中)。该扰动需满足以下条件：有对称约束的器件不能产生上下位置关系；若器件有相邻约束，其相邻器件一起作相同移动；有电流方向约束的器件相对位置关系不能改变。
(3)M3：器件在其相邻器件组内移动。为满足信号流约束，器件可以在相邻期间组内小范围移动，不能跨多组移动。
(4)M4：两个属于相邻器件组的器件交换位置；有对称约束的器件，其对称器件作相应交换。
(5)M5：旋转器件组内任一器件。若器件有对称约束，则其对称器件作相同扰动。
以上5种扰动只限于一个直流通路内部或两个相邻直流通路，可以保证直流通路顺序约束。而且与传统的模拟退火算法相比，局部化的模拟退火大大减少无效扰动次数，更加高效。设总器件数为n，有m个直流通路。对传统的模拟退火算法，选取两个器件的种类数N1(M4)=C；本文算法选取两个器件的种类数N2(M4)≈m×C≈N1/m。可见直流通路越多，扰动种类会越少，算法时间消耗越少。
结合以上带约束的扰动，退火算法目标函数为：
Cost(p)=area(p)/AREA+λ×wire(p)/WIRE(3)
其中area(p)和wire(p)分别是布局p的面积和线长(用半周长表示)，AREA=area(Di)，即器件总面积，WIRE=(Wi+Li)，即器件半周长之和，Wi和Li分别为宽度和长度；λ是area和wire权重的调节因子。
5 实验结果
本文算法由C++语言编程实现，在一台RedHat-Linux服务器上测试。选取了4个实际应用较多的电路：缓冲运算放大器(Buffer-amp)[6]、二级折叠式共源共栅运放(Two stage-opa)、带隙基准电路(Bandgap)和带共模反馈的全差分运放(Cmfb-opa)。对模拟集成电路，关键路径上的寄生效应对电路性能影响很大。本文选交流信号路径作为关键路径，选用关键路径线长和版图面积作为对比标准，与参考文献[7]、[8]中算法的对比结果见表1。结果显示，本文的算法与参考文献[7]、[8]相比，关键路径线长平均减小28%，面积平均减小16%。参考文献[8]主要解决对称问题，与它相比，本文算法得到的关键路径线长减小40%。算法很好地确保了直流通路上和信号流路径上的寄生效应对电路性能影响最小。
6 结束语
本文提出了针对多约束条件的基于直流通路划分的模拟集成电路布局算法，采用层次化的序列对表示相对位置关系，在满足对称、临近等约束的基础上，采用空间搜索布局算法产生一个比较好的初始布局，再用模拟退火算法迭代优化。实验结果表明，本文算法可以产生按照直流通路顺序放置的理想版图，达到很好的布局效果。
参考文献
[1] BALASA F，LAMPAERT K.Symmetry within the sequence-pair representation in the context of placement for analog design[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2000，19(7)：721-731.
[2] YUEN W S，YOUNG E F Y.Slicing floorplan with cluste-ring constrain[J].IEEE TCAD.2003，22(5)：652-658.
[3] NOJIMA T，ZHU X，TAKASHIMA Y，et al.Multi-level
placement with circuit schema based clustering in analog IC layouts[C].Proc.ASPDAC，2004：406-411.
[4] MURATA H，FUJIYOSHI K，NAKATAKE S，et al.Rectanglepacking based module placement[C].Proceedings of IEEE International Conference on Computer Aided Design，1995：472-479.
[5] NOJIMA T，ZHU X，TAKASHIMA Y，et al.Multi-level placement with circuit schema based clustering in analog IClayouts[C].Proceedings of ASPDAC，2004：406-411.
[6] FISHER J，KOCH R.A highly linear CMOS buffer amplifier[J].IEEE Journal of Solid-State Circuits SC，1987(22)：330-334.
[7] Zhang Lingyi，Dong Sheqin，Ma Yuchun，et al.Multi-stage analog placement with various constraints[C].ICCCAS，2010：881-885.
[8] Zhang Lihong，RAUT R，Jiang Yingtao，et al.Placement algorithm in analog-layout designs[J].IEEE Trans CADICS，2006，25(10)：1889-1903.