多層3D芯片中硅通孔分布優(yōu)化的改進(jìn)算法

李德隆, 郝　聰, 吉村猛, 俞　暉

(1.上海交通大學(xué) 上海交通大學(xué)電子信息與電氣工程學(xué)院,上海 200240;2.早稻田大學(xué) IPS研究所,東京 169-8050)

?

多層3D芯片中硅通孔分布優(yōu)化的改進(jìn)算法

李德隆1, 郝聰2, 吉村猛2, 俞暉1

(1.上海交通大學(xué) 上海交通大學(xué)電子信息與電氣工程學(xué)院,上海 200240;2.早稻田大學(xué) IPS研究所,東京 169-8050)

摘要:3D芯片中硅通孔(TSV)的位置分布會(huì)對(duì)總線長(zhǎng)造成很大影響,所以對(duì)于TSV位置分布的優(yōu)化有許多算法,逐層進(jìn)行TSV分配只能做到局部?jī)?yōu)化.提出用逆向重分配的方法對(duì)已有算法結(jié)果進(jìn)一步優(yōu)化以達(dá)到減少總線長(zhǎng)的目的.同時(shí)提出了一種快速重分配以提高深度優(yōu)化的運(yùn)行時(shí)間.實(shí)驗(yàn)結(jié)果表明,對(duì)比逐層TSV分配方法,此逆向重分配方法可減少3.7%的總線長(zhǎng);此方法亦可對(duì)其他TSV分配算法(如逐網(wǎng)TSV分配、拉格朗日松弛算法等)所得結(jié)果作進(jìn)一步線長(zhǎng)優(yōu)化;而快速重分配可將逆向重分配的運(yùn)行時(shí)間降低為原來(lái)的10%.

關(guān)鍵詞:3D芯片; 硅通孔(TSV); 逆向重分配; 線長(zhǎng)優(yōu)化

0概述

近年來(lái),3D芯片已經(jīng)成為研究者與開(kāi)發(fā)者重點(diǎn)研究的課題.相比傳統(tǒng)2D芯片,3D芯片可以在極大提高芯片性能的同時(shí)降低信號(hào)時(shí)延.而硅通孔(Through Silicon Via,TSV)作為3D芯片層與層之間的垂直連接,也受到了相當(dāng)?shù)年P(guān)注.

全局最優(yōu)化的TSV位置分配問(wèn)題已經(jīng)被證明是NP完全問(wèn)題,而低優(yōu)化度的TSV分配方法可能會(huì)導(dǎo)致芯片內(nèi)布線總長(zhǎng)的增加進(jìn)而提高生產(chǎn)成本,針對(duì)TSV位置分配優(yōu)化的問(wèn)題已經(jīng)有了很多相關(guān)研究與算法.逐層分配方法主要使用最小消費(fèi)最大流模型逐層對(duì)所有TSV分配位置,此方法不考慮TSV所屬不同節(jié)點(diǎn)網(wǎng),使得每一層的TSV分配達(dá)到局部最優(yōu),卻會(huì)導(dǎo)致同網(wǎng)的未分配層的TSV無(wú)法選取最優(yōu)位置而引起冗余布線.逐網(wǎng)分配方法無(wú)視了TSV所屬層而依次對(duì)每一個(gè)節(jié)點(diǎn)網(wǎng)分別進(jìn)行TSV位置分配,其核心思想可等效為最短路徑問(wèn)題,此方法會(huì)使后期分配的TSV無(wú)法取到最優(yōu)位置.

本文作者提出了逆向逐層重分配的方法對(duì)已有逐層算法所得結(jié)果進(jìn)行深度優(yōu)化,盡可能使總布線線長(zhǎng)最小從而減小布線花費(fèi).實(shí)驗(yàn)仿真結(jié)果顯示此方法可對(duì)原始逐層TSV分配方法所得結(jié)果有較好改善,同時(shí)此重分配方法亦適用于其他TSV分配方法.為了減少重分配運(yùn)行時(shí)間,本文作者提出了快速重分配,通過(guò)替換最小消費(fèi)最大流模型求解而使運(yùn)算時(shí)間大幅度減少.

1系統(tǒng)模型與預(yù)操作

對(duì)于一個(gè)m層3D芯片,可將其從頂層到底層定義為layer0,layer1,…,layerm-1.如果一個(gè)節(jié)點(diǎn)網(wǎng)覆蓋多于1層:layeri～layerj(i

1.1節(jié)點(diǎn)網(wǎng)分解

逐層TSV分配是對(duì)每一層上所有TSV同時(shí)分配位置,不考慮TSV所屬節(jié)點(diǎn)網(wǎng),這就要對(duì)所有節(jié)點(diǎn)網(wǎng)進(jìn)行分解,使每一節(jié)點(diǎn)網(wǎng)上的節(jié)點(diǎn)根據(jù)所在層數(shù)分解為數(shù)個(gè)子網(wǎng)進(jìn)而服務(wù)于TSV的分配.

如圖1,節(jié)點(diǎn)網(wǎng)nt1={p1,…,p7}的7個(gè)節(jié)點(diǎn)分布在4層,若要連通此節(jié)點(diǎn)需插入3個(gè)硅通孔(TSV)pvia1、pvia2、pvia3,進(jìn)而可以將nt1與插入的TSV節(jié)點(diǎn)根據(jù)所在不同層分解為4個(gè)子網(wǎng):{p1,pvia1}、{p2,p3,pvia1,pvia2}、{p4,p5,p6,pvia2,pvia3}、{p7,pvia3}.若使布線長(zhǎng)最短,則只需令4個(gè)子網(wǎng)的線長(zhǎng)達(dá)到最優(yōu),研究中采用矩形半周長(zhǎng)預(yù)測(cè)(HPWL)評(píng)估線長(zhǎng).

圖1　節(jié)點(diǎn)網(wǎng)分解

1.2設(shè)定備選位置

為了計(jì)算方便,可將每一層都建立P*Q方格結(jié)構(gòu),定義每格面積為ws(g),這樣對(duì)于可插入TSV的方格,其容量即可定義為ws(g)/A(v),其中A(v)為TSV所占面積.對(duì)于TSV,該層所有容量大于等于1的方格皆可成為其備選位置,為了降低時(shí)間復(fù)雜度,設(shè)定一個(gè)備選范圍,其初始范圍為子節(jié)點(diǎn)網(wǎng)(不含TSV節(jié)點(diǎn))所有節(jié)點(diǎn)圈定的矩形,若其內(nèi)方格總?cè)萘坎淮笥?,則擴(kuò)展此范圍直到容量大于等于1.

2逆向重分配算法

2.1逐層TSV分配

逐層TSV分配是基于最小消費(fèi)最大流模型的TSV位置分配算法,此算法不考慮TSV所隸屬的節(jié)點(diǎn)網(wǎng)而只關(guān)注當(dāng)前層所有待插入TSV的分配問(wèn)題,使當(dāng)前層上所有子節(jié)點(diǎn)網(wǎng)線長(zhǎng)達(dá)到最優(yōu).原始的逐層分配算法是局部最優(yōu)算法,當(dāng)前所分配TSV的位置可能會(huì)造成未分配層的布線冗余.圖2為原始逐層分配所引起冗余布線的說(shuō)明.從頂層layer 0開(kāi)始逐層布線,分配pvia2時(shí),并沒(méi)有考慮layer 2上子節(jié)點(diǎn)網(wǎng)的信息,而在選擇pvia2時(shí),所有在pvia1與p3所構(gòu)成的備選范圍內(nèi)的方格都被判斷為最優(yōu)位置而隨機(jī)選擇其中之一.然而此位置可能導(dǎo)致layer 2上子節(jié)點(diǎn)網(wǎng)的線長(zhǎng)增加,如圖2中所示,虛線為插入pvia2時(shí)的更佳位置,若可以將pvia2重新分配到虛線位置,則可以達(dá)到優(yōu)化布線總長(zhǎng)的目的.

圖2　原始逐層TSV分配算法缺點(diǎn)

2.2最小消費(fèi)最大流模型

逐層分配與逆向重分配的核心就是利用最小消費(fèi)最大流模型解決當(dāng)前層的TSV分布.利用最小消費(fèi)最大流算法解決TSV分配問(wèn)題,首先要建立流圖.

定義1二分圖G(V,E)代表該層所有待分配TSV與所有方格.

(1)V(G)=Vv∪Vg,其中Vv={vi|i=1,…,kv}表示所有該層待分配TSV,Vg={wj|j=1,…,kg}為方格集合;

(2)E(G)={(vi,wj)|vi∈Vv,wj∈Vg},其中wj為vi的備選位置,(vi,wj)為從TSV指向其備選位置的邊.

逐層分配算法即對(duì)每一層采用最小消費(fèi)最大流模型對(duì)該層所有TSV同時(shí)分配位置,設(shè)Nv為該層TSV數(shù)目,Ng為該層方格數(shù)目,則可建立S-T網(wǎng)絡(luò)流來(lái)解決最小消費(fèi)最大流問(wèn)題.

定義2S-T網(wǎng)絡(luò)流N(V,E,fcap,fcost),其中V為點(diǎn)集,E為邊集,fcap邊的容量約束,fcost為邊的費(fèi)用.

(1)V(N)=V(G)∪{S,T};

(2)E(N)=E(G)∪ESv∪EgT,其中ESv={(S,v)|v∈Vv},EgT={(g,T)|g∈Vg};

(3)fcap為整數(shù)方程,用以表示流圖中所有邊的容量,

(1)

4)fcost為實(shí)數(shù)方程,用以表示流圖中所有邊的費(fèi)用,

(2)

其中wl(*)表示子節(jié)點(diǎn)網(wǎng)的半周長(zhǎng)預(yù)測(cè)(HPWL).圖3為某一包含n個(gè)帶插入TSV與m個(gè)方格芯片層所對(duì)應(yīng)的S-T網(wǎng)絡(luò)流.

圖3　最小消費(fèi)最大流針對(duì)的某一層的S-T網(wǎng)絡(luò)流

2.3逆向重分配算法

原始逐層TSV分配會(huì)導(dǎo)致布線冗余,本文作者提出了逆向重分配的算法對(duì)原始逐層分配得到的結(jié)果進(jìn)一步優(yōu)化.經(jīng)過(guò)第一次的正向逐層TSV分配,各層TSV的位置信息已經(jīng)得到,利用當(dāng)前TSV位置可以對(duì)各層TSV重新分配位置.

原始TSV解決最小消費(fèi)最大流問(wèn)題中費(fèi)用約束條件只計(jì)算了針對(duì)某一TSV其連接的兩層子節(jié)點(diǎn)網(wǎng)的半周長(zhǎng)預(yù)測(cè)(HPWL),然而wl(snt1)子節(jié)點(diǎn)網(wǎng)并不包含下一層所插入的TSV,若將當(dāng)前已有的原始逐層分配位置結(jié)果考慮進(jìn)去,則已分配位置此時(shí)可能不是最優(yōu)解.利用原始分配結(jié)果可以對(duì)這部分TSV重新分配位置,使其達(dá)到基于當(dāng)前其他層TSV位置的最優(yōu)解.

在進(jìn)行逆向重分配時(shí),按照從底層到頂層的逆向順序,對(duì)每一層所有TSV重新分配位置,這里依然采用最小消費(fèi)最大流算法來(lái)解決問(wèn)題,但是因?yàn)榭紤]所有TSV的位置信息,可以將S-T網(wǎng)絡(luò)流中的約束條件加以更新:

(3)

其中n為芯片層數(shù).此費(fèi)用方程計(jì)算了該TSV所在節(jié)點(diǎn)網(wǎng)的所有子節(jié)點(diǎn)網(wǎng)總線長(zhǎng),這樣最小消費(fèi)問(wèn)題就可以得到基于當(dāng)前條件的最優(yōu)線長(zhǎng)TSV位置.而通過(guò)逆向或循環(huán)重分配,可以使節(jié)點(diǎn)網(wǎng)布線總長(zhǎng)不斷得到優(yōu)化,實(shí)驗(yàn)顯示,10次循環(huán)之后所得結(jié)果不會(huì)再有明顯改善,而循環(huán)重分配平均可以將原始逐層TSV算法線長(zhǎng)降低3.7%.同時(shí)此逆向重分配算法亦可用于優(yōu)化其他TSV位置分配算法所得結(jié)果,仿真實(shí)驗(yàn)已驗(yàn)證其有效性.

2.4快速重分配算法

在逆向重分配算法中,解決最小消費(fèi)最大流模型問(wèn)題所消耗的時(shí)間占總運(yùn)行時(shí)間60%以上,如果能夠用一種快速算法代替最小消費(fèi)最大流問(wèn)題進(jìn)行TSV分配,則可極大地降低運(yùn)行時(shí)間.快速重分配算法省去了最小消費(fèi)最大流中同時(shí)給該層所有TSV分配位置的步驟,改為按照一定順序依次對(duì)TSV分配位置.理論分析可以發(fā)現(xiàn),如果TSV所在節(jié)點(diǎn)網(wǎng)總線長(zhǎng)越短,說(shuō)明其所聯(lián)通層數(shù)越少,而這些TSV的位置對(duì)其他節(jié)點(diǎn)網(wǎng)插入TSV的影響就越小,所以可以優(yōu)先分配.這里定義了一個(gè)代價(jià)函數(shù)用來(lái)代表某一TSV的影響能力:

(4)

快速重分配算法按照該層所有TSV的I(v)遞增順序?qū)SV進(jìn)行依次插入,在減少運(yùn)行時(shí)間的同時(shí),又不會(huì)犧牲太大的線長(zhǎng)優(yōu)化能力.

3仿真實(shí)驗(yàn)結(jié)果

仿真實(shí)驗(yàn)是基于64-bit 的IBM Linux平臺(tái),利用c++語(yǔ)言對(duì)MCNC(ami33,ami49)及GSRC(n50,n100,n200,n300)6種檢驗(yàn)標(biāo)準(zhǔn)進(jìn)行仿真.利用已有的3D芯片布局(包括層上空白位置信息),定義TSV大小為5 μm×5 μm,3D芯片布局層數(shù)為4層.本仿真所得數(shù)據(jù)為循環(huán)10次重分配所得結(jié)果,數(shù)據(jù)為10次運(yùn)行平均值.表1為各檢驗(yàn)標(biāo)準(zhǔn)電路參數(shù),包含平均子節(jié)點(diǎn)網(wǎng)數(shù)、總節(jié)點(diǎn)數(shù)以及需插入的TSV數(shù).

表1　檢驗(yàn)標(biāo)準(zhǔn)參數(shù)

圖4為循環(huán)重分配1至5周所得總線長(zhǎng)趨勢(shì),循環(huán)次數(shù)越多,線長(zhǎng)優(yōu)化度越高,但優(yōu)化趨勢(shì)逐漸趨于平緩,循環(huán)運(yùn)行時(shí)間越長(zhǎng).

圖4　1～5次循環(huán)重分配所得線長(zhǎng)

表2為仿真實(shí)驗(yàn)結(jié)果,基于最小消費(fèi)最大流的逆向TSV重分配算法經(jīng)過(guò)10周循環(huán)重分配對(duì)總布線長(zhǎng)度進(jìn)行優(yōu)化.10次運(yùn)行平均結(jié)果為:對(duì)比原始逐層TSV分配,總線長(zhǎng)減少了3.7%,運(yùn)行時(shí)間為原始逐層分配的12.93倍.此實(shí)驗(yàn)結(jié)果說(shuō)明逆向重分配方法通過(guò)循環(huán)對(duì)TSV已分配位置進(jìn)一步優(yōu)化減少了總布線長(zhǎng)度,降低了生產(chǎn)成本,代價(jià)為增加了運(yùn)算時(shí)間.快速重分配方法經(jīng)過(guò)10次10周循環(huán)所得運(yùn)行結(jié)果為:對(duì)比原始逐層分配方法,總線長(zhǎng)降低2.2%,運(yùn)行時(shí)間為原始方法的1.84倍.可以發(fā)現(xiàn)快速重分配方法雖然無(wú)法達(dá)到基于最小消費(fèi)最大流的逆向重分配方法的高優(yōu)化程度,但是可以顯著減少逆向重分配的運(yùn)行時(shí)間,10周重分配所占時(shí)間小于原始逐層分配所消耗時(shí)間.

表2　逆向重分配算法

`

4結(jié)論

本文作者提出了逆向重分配的方法對(duì)原始逐層TSV分配方法進(jìn)一步優(yōu)化,實(shí)驗(yàn)結(jié)果表明,在原始方法基礎(chǔ)上可以減少平均3.7%的總線長(zhǎng)以達(dá)到降低生產(chǎn)成本的目的.此方法運(yùn)行時(shí)間為原始逐層分配方法的12.93倍.而快速重分配方法則可以顯著降低重分配所需時(shí)間,代價(jià)為無(wú)法達(dá)到基于最小消費(fèi)最大流算法的重分配優(yōu)化度.

參考文獻(xiàn):

[1]Banerjee K,Souri S J,Kapur P,et al.3-D ICs:A novel chip design for improving deep-submicrometer interconnect performance and systems-on-chip integration [J].Proceedings of the IEEE,2001,89(5):602-633.

[2]Joyner J W,Zarkesh-Ha P 0,Meindl J D.A global interconnect design window for a three-dimensional system-on-a-chip [C]//IEEE:Interconnect Technology Conference 2001 Proceedings of the IEEE 2001 International.Burlingame:IEEE,2001.

[3]Goplen B,Spatnekar S.Placement of 3D ICs with thermal and interlayer via considerations [C]//ACM.Proceedings of the 44th annual Design Automation Conference.San Diego:ACM,2007.

[4]Cong B J,Zhang Y.Thermal-driven multilevel routing for 3-D ICs [C]//ACM.Proceedings of the 2005 Asia and South Pacific Design Automation Conference.New York:ACM,2005.

[5]Zhou L,Wakayama C,Shi C J R.Cascade:A standard supercell design methodology with congestion-driven placement for three-dimensional interconnect-heavy very large-scale integrated circuits [J].Computer-Aided Design of Integrated Circuits and Systems IEEE Transactions on,2007,26(7):1270-1282.

[6]Chen S,Ge L W,Chiang M F,et al.Lagrangian Relaxation Based Inter-Layer Signal Via Assignment for 3-D ICs [J].IEICE TRANSACTIONS on Fundamentals of Electronics Communications and Computer Sciences,2009,E92-A(4):1080-1087.

(責(zé)任編輯：顧浩然)

An improved layer by layer TSV assignmentoptimization for multi-layer 3-D ICs

LI Delong1, HAO Cong2, YOSHIMURA Takesi2, YU Hui1

(1.School of Electronic Information and Electrical Engineering,Shanghai Jiao Tong University,Shanghai 200240 China;2.Graduate School of Information,Production and Systems LSI,WASEDA University,Tokyo 169-8050,Japan)

Abstract:Poor TSV assignment algorithm leads to a large detour of wire-length.Some of the previous works deal with TSV assignment problem using layer-by-layer methods(LBL) only gets local optimal results.In this research work,a backward layer-by-layer reassignment(BRLBL) is developed to do further optimization.This reassignment algorithm takes global information into consideration and optimizes the outcome of layer-by-layer TSV assignment methods.Also a fast layer-by-layer reassignment(FLBL) method is proposed to shorten the runtime.Experimental results show that BRLBL achieves an average reduction over 3.7% of wire-length,while the FLBL improves the execution time of BRLBL by 10 times.

Key words:3-D IC; Through-silicon via(TSV);wire-length optimization; backward reassignment

中圖分類號(hào):TN 47

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1000-5137(2016)02-0180-06

通信作者:俞輝,中國(guó)上海市閔行區(qū)東川路800號(hào),上海交通大學(xué)電子信息與電氣工程學(xué)院,郵編:200240,E-mail:yuhui@sjtu.edu.cn.

基金項(xiàng)目:國(guó)家科技重大專項(xiàng)“TD-LTE/FDD-LTE/TD-SCDMA/WCDMA/GSM多模型基帶商用芯片研發(fā)”(2013 ZX03001007-004)

收稿日期:2015-12-15