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.