趙振宇，孫　浩，鄧　全，蔣劍鋒

(國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院， 湖南 長(zhǎng)沙　410073)

?

引入電流變化率的電源分布網(wǎng)絡(luò)最差噪聲分析算法*

趙振宇，孫浩，鄧全，蔣劍鋒

(國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院， 湖南 長(zhǎng)沙410073)

摘要：隨著時(shí)鐘頻率的增加以及電源電壓的降低，電源完整性問(wèn)題日益凸顯。將電流變化率加入到最差噪聲算法的電流約束中，能夠在任意電流變化率的情況下分析電源分布網(wǎng)絡(luò)的最差噪聲，從而獲得更加真實(shí)的最差噪聲。另外，利用改進(jìn)的Knuth-Yao四邊形不等式法對(duì)基于動(dòng)態(tài)規(guī)劃的最差噪聲算法進(jìn)行加速，加速后算法的時(shí)間復(fù)雜度從O(n2m)降為O(mnlogn)。

關(guān)鍵詞：動(dòng)態(tài)規(guī)劃；最差噪聲；變化率；電源分布網(wǎng)絡(luò)；時(shí)域分析

最差噪聲估計(jì)的目標(biāo)是在不清楚芯片準(zhǔn)確負(fù)載電流的情況下，為封裝以及印刷電路板(Printed Circuit Board, PCB)設(shè)計(jì)者提供驗(yàn)證電源分布網(wǎng)絡(luò)的可靠方法[1-2]。這是因?yàn)?，在芯片設(shè)計(jì)完成之前，很難得到芯片上負(fù)載電流的詳細(xì)信息。即使在芯片設(shè)計(jì)完成之后，也很難確定所有的輸入情況能獲得所有可能的輸出電流。此外，為了保證系統(tǒng)的魯棒性，模擬時(shí)必須遍歷所有的輸入電流，這樣的代價(jià)是昂貴的。

為了描述不確定負(fù)載電流，Kouroussis和Najm[3]提出了“電流約束”這個(gè)概念。這個(gè)概念是合理的，因?yàn)椋谛酒O(shè)計(jì)完成之前，芯片設(shè)計(jì)者即使不能夠完整地掌握負(fù)載電流的信息，但還是對(duì)負(fù)載電流有一定程度的了解。這些了解可能基于前面的設(shè)計(jì)者，也可能基于設(shè)計(jì)初期的系統(tǒng)級(jí)模擬[4-5]。封裝以及PCB設(shè)計(jì)者就可以利用這些信息對(duì)電源分布網(wǎng)絡(luò)進(jìn)行初期的驗(yàn)證[6]。然而，之前的一些工作僅考慮了電流幅值這個(gè)約束，卻沒(méi)有考慮電流的變化率，這會(huì)導(dǎo)致所估計(jì)的最差噪聲過(guò)分悲觀。因此，本文所構(gòu)建的電流約束將考慮電流的最小變化率。

1問(wèn)題定式化

最差噪聲算法的目的是在電流約束下確定芯片的最差噪聲[7-8]。如上一小節(jié)所述，負(fù)載電流的一個(gè)約束條件就是電流幅值，約束條件可以通過(guò)下面的式(1)表示：

0≤i(t)≤b, ?t≥0

(1)

其中，b代表瞬態(tài)電流i(t)的上邊界。在此約束條件下，電流變化率tr代表電流從0變化到b所需要的時(shí)間或者從b變化到0所需要的時(shí)間。此外，再增加一個(gè)電流約束條件，變化率的下邊界tb，即tr≥tb。最小變化率的約束條件可以通過(guò)最大電流斜率的形式來(lái)表示：

其中b/tb為電流的最大斜率。

將電源傳輸系統(tǒng)噪聲表示為v(t)。為了簡(jiǎn)化分析過(guò)程，假設(shè)電壓源Vdd為零。這樣，噪聲v(t)可以表示為輸入電流和系統(tǒng)單位脈沖響應(yīng)的卷積為：

(2)

其中z(τ)代表系統(tǒng)單位脈沖響應(yīng)。由于卷積過(guò)程會(huì)對(duì)v(t)產(chǎn)生累加效果，我們將積分時(shí)間t設(shè)置為脈沖響應(yīng)衰減到可以忽略的時(shí)候。通過(guò)將式(2)中i(t-τ)替換為一般函數(shù)f(τ)，將積分變量由τ變換為t，可以將最差噪聲定式化為：

s.t.0≤f(t)≤b,?t≥0

(3)

其中C=b/tb表示f(t)斜率的上邊界。一旦確定了f(t)，相應(yīng)的最差負(fù)載電流可以通過(guò)i(t)=f(T-t)得到。

值得注意的是，式(3)通過(guò)電流方向計(jì)算得到的是最大壓降。電源傳輸系統(tǒng)的電感效應(yīng)會(huì)引起Ldi/dt噪聲，包括壓降和偏差。對(duì)于最大偏差，僅需要在同樣約束條件下，將式(3)中原函數(shù)進(jìn)行最小化。因此，本文后面的內(nèi)容主要是針對(duì)最大壓降進(jìn)行分析。

2最差噪聲分析算法

首先，將卷積時(shí)間[0,T]分為m個(gè)時(shí)間段[t0=0,t1], [t1,t2],…,[tm-1,tm=T]，以保證系統(tǒng)單位脈沖響應(yīng)在每一個(gè)時(shí)間段不發(fā)生正負(fù)變化，如圖1所示。同時(shí)，在電流約束范圍[0,b]選擇n+1個(gè)采樣點(diǎn)u0=0,u1,…,un-1,un=b，n的取值由計(jì)算精度要求決定。

圖1　卷積時(shí)間分段方法Fig.1　Division of convoluting time

選擇一個(gè)時(shí)間段[tj,tj+1]，將Gj(k,i,t)定義為從tj時(shí)刻的uk到tj+1時(shí)刻的ui所產(chǎn)生的最差f(t)。將Vj(k,i)定義為對(duì)應(yīng)的最差噪聲。我們就可以得到：

(4)

利用貪婪算法很容易地計(jì)算Gj(k,i，t)。如圖2(a)和圖2(b)所示，如果z(t)在[tj,tj+1]時(shí)間段為正，則從uk畫(huà)一條斜率為C的直線，另外畫(huà)一條到ui結(jié)束的直線，斜率為-C。如果兩條直線在低于電流上邊界b的地方相交，則Gj(k,i,t)為uk→P→ui，如圖2(b)所示。如果直線交點(diǎn)高于上邊界b，則將邊界與兩條直線的交點(diǎn)分別用P1和P2表示，Gj(k,i,t)為uk→P1→P2→ui，如圖2(a)所示。

(a)交點(diǎn)超過(guò)邊界(a) Intersection over border

(b)交點(diǎn)未超過(guò)邊界(b) Intersection under border圖2　貪婪算法Fig.2　Greedy algorithm

如果z(t)在[tj,tj+1]時(shí)間段為負(fù)，Gj(k,i,t)可以表示為類(lèi)似形式。以圖2(a)所示情況為例來(lái)證明貪婪算法。假設(shè)G′j(k,i,t)為未經(jīng)貪婪算法處理的f(t)，如圖2(a)中虛線所示，可得在[tj,tj+1]上G′j(k,i,t)≤Gj(k,i,t)。由于z(t)在[tj,tj+1]為正，可得：

(5)

這就表示Gj(k,i)是在上述約束下的最差f(t)。

考慮Cr+1(r≥2)映射F:Ω?Cn→Cn，其中Ω是Cn中的一個(gè)原點(diǎn)領(lǐng)域.假設(shè)F(0)=0是F(x)在原點(diǎn)領(lǐng)域的不動(dòng)點(diǎn)，因此可將F(x)表示為：

將OPT(j,i)(j∈[0,m],i∈[0,n])定義為電流停留在tj時(shí)刻電流值為ui時(shí)的最差噪聲。OPT的一些基本特性如下：

3算法加速

如果利用迭代方法計(jì)算OPT的所有值，時(shí)間復(fù)雜度為O(n2m)[9-10]。本小節(jié)，將通過(guò)一些方法對(duì)動(dòng)態(tài)規(guī)劃算法進(jìn)行提速，經(jīng)過(guò)算法加速，時(shí)間復(fù)雜度降低為O(mnlogn)。

3.1優(yōu)化問(wèn)題的性質(zhì)分析

假設(shè)z(t)在[tj,tj+1]時(shí)間段為負(fù)，將Wj(k,i)定義為Gj(k,i,t)的絕對(duì)值，而Fj(k,i)為對(duì)應(yīng)于k的OPT(j+1,i)候選值，即Fj(k,i)=OPT(j,k)-Wj(k,i)。關(guān)于W和F有以下幾條有用的性質(zhì)：

引理1：對(duì)任何0≤k1

Wj(k2,i2)-Wj(k1,i2)≤Wj(k2,i1)-Wj(k1,i1)

圖3　函數(shù)W的四邊形不等式Fig.3　Quadrangle inequality for the function W

值得注意的是，引理1就是W的四邊形不等式[11]。然而，該不等式并不成立，也就是說(shuō)無(wú)法推導(dǎo)出OPT的四邊形不等式。因此，選擇基于下面一條引理的Knuth-Yao加速方法來(lái)降低算法的時(shí)間復(fù)雜度。

引理2：假設(shè)k1i1，可以得到Fj(k1,i2)≤Fj(k2,i2)。

證明：

根據(jù)引理2，假設(shè)k1

i0=GetTransPos(j,k1,k2)

3.2加速算法偽代碼描述

將S定義為OPT(j+1,i)的候選值k從小到大排列的隊(duì)列。將Q定義為數(shù)據(jù)越小優(yōu)先級(jí)越高的優(yōu)先隊(duì)列，隊(duì)列可進(jìn)行GetMin，DeleteMin和Add三種操作。GetMin和DeleteMin分別能夠獲取和刪除優(yōu)先隊(duì)列中的最小元素，而Add(e)操作則可以將元素e插入到隊(duì)列中。上述三種操作均可在時(shí)間復(fù)雜度O(logn)內(nèi)完成。隊(duì)列中每一個(gè)元素都包括三個(gè)分量：第一個(gè)分量是優(yōu)先隊(duì)列的關(guān)鍵碼(key)，它表明了i0的位置。后面兩個(gè)分量k1和k2對(duì)應(yīng)于i0。加速動(dòng)態(tài)規(guī)劃算法可以通過(guò)偽代碼“算法1”表示，該算法的時(shí)間復(fù)雜度為O(nlogn)。

算法1　加速優(yōu)化

3.3時(shí)間復(fù)雜度

S隊(duì)列可以通過(guò)雙向鏈接表實(shí)現(xiàn)，同時(shí)還需要一個(gè)指針給出每一個(gè)k在S中的位置。這樣，算法中第8步和第9步可在瞬間完成。更進(jìn)一步，算法1中每一個(gè)候選值k僅能被刪除n次，因此，第6步到第12步整個(gè)過(guò)程中最多運(yùn)行n次。GetMin，DeleteMin和Add三種操作的時(shí)間復(fù)雜度為O(logn)，GetTransPos()的時(shí)間復(fù)雜度也為O(logn)。因此算法1的時(shí)間復(fù)雜度為O(nlogn)。

對(duì)于OPT，僅需對(duì)每一個(gè)i初始化OPT(0,i)=0，調(diào)用GetOPT算法m次，因此，OPT的時(shí)間復(fù)雜度為O(mnlogn)。

3.4算法加速效果

分別利用加速前算法和加速算法進(jìn)行最差噪聲估計(jì)，并對(duì)兩種算法的運(yùn)行時(shí)間進(jìn)行對(duì)比，以檢驗(yàn)算法的加速效果。算法通過(guò)C++語(yǔ)言實(shí)現(xiàn)，并運(yùn)行于配置為2 GB內(nèi)存，CORE i5的計(jì)算機(jī)。單位脈沖響應(yīng)分為12段，即m=12。加速前算法與加速算法運(yùn)行時(shí)間與電流采樣點(diǎn)個(gè)數(shù)n的關(guān)系如圖4所示。由圖可知，加速算法的運(yùn)行時(shí)間要遠(yuǎn)遠(yuǎn)小于加速前算法的運(yùn)行時(shí)間，尤其當(dāng)n足夠大的時(shí)候。

圖4　算法加速前后運(yùn)行時(shí)間對(duì)比Fig.4　Run time comparison between the of O(n2m) algorithm and the O(mnlogn) algorithm

4結(jié)論

對(duì)最差噪聲算法進(jìn)行優(yōu)化，引入電流變化率，反映了更真實(shí)的最差噪聲，避免只考慮電流幅度所估計(jì)的較為悲觀的最差噪聲。同時(shí)利用Kunth Yao四邊形不等式法對(duì)動(dòng)態(tài)規(guī)劃算法進(jìn)行加速，有效地降低了運(yùn)算的復(fù)雜度，從O(n2m)降為O(mnlogn)。在大規(guī)模集成電路設(shè)計(jì)中仿真時(shí)間收益明顯，為后續(xù)電源的網(wǎng)絡(luò)問(wèn)題打下基礎(chǔ)。

參考文獻(xiàn)(References)

[1]Hu X, Zhao W B, Du P, et al. On the bound of time-domain power supply noise based on frequency-domain target impedance[C]//Proceedings of the 11th International Workshop on System Level Interconnect Prediction, ACM, 2009: 69-76.

[2]Wang Y Z, Hu X, Cheng C K, et al. A realistic early-stage power grid verification algorithm based on hierarchical constraints[J]. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 2012, 31(1): 109-120.

[3]Kouroussis D, Najm F N. A static pattern-independent technique for power grid voltage integrity verification[C]//Proceedings of the 40th Annual Design Automation Conference, ACM, 2003: 99-104.

[4]Abdul Ghani N H, Najm F N. Fast vectorless power grid verification using an approximate inverse technique[C]//Proceedings of the 46th Annual Design Automation Conference, ACM, 2009: 184-189.

[5]Ferzli I A, Najm F N, Kruse L. A geometric approach for early power grid verification using current constraints[C]//Proceedings of the IEEE/ACM International Conference on Computer-aided design, 2007: 40-47.

[6]Xiong X, Wang J. Verifying RLC power grids with transient current constraints[J]. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 2013, 32(7): 1059-1071.

[7]Zhu H, Wang Y, Liu F, et al. Efficient transient analysis of power delivery network with clock/power gating by sparse approximation[J]. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 2015, 34(3): 409-421.

[8]Ferzli I A, Chiprout E, Najm F N. Verification and codesign of the package and die power delivery system using wavelets[J]. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 2010, 29(1): 92-102.

[9]Zhao W, Cai Y, Yang J L. A multilevel 64-matrix-based approximate matrix inversion algorithm for vectorless power grid verification[C]//Proceedings of the 18th Asia and South Pacific Design Automation Conference (ASP-DAC), IEEE, 2013: 163-168.

[10]Zhao W, Cai Y, Yang J L. Fast vectorless power grid verification using maximum voltage drop location estimation[C]//Proceedings of the 19th Asia and South Pacific Design Automation Conference (ASP-DAC), IEEE, 2014: 861-866.[11]Yao F F. Efficient dynamic programming using quadrangle inequalities[C]//Proceedings of the 12th Annual ACM Symposium on Theory of Computing, ACM, 1980: 429-435.

doi:10.11887/j.cn.201602014

*收稿日期：2015-03-09

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61272139)

作者簡(jiǎn)介：趙振宇(1973—)，男，遼寧朝陽(yáng)人，研究員，博士，E-mail：zyzhao@nudt.edu.cn

中圖分類(lèi)號(hào)：TN47

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

文章編號(hào)：1001-2486(2016)02-082-05

A time-domain worst-case noise algorithm for power delivery network with non-zero current transition times

ZHAO Zhenyu, SUN Hao, DENG Quan, JIANG Jianfeng

(College of Computer, National University of Defense Technology, Changsha 410073, China)

Abstract：With the increasing of clock frequency and the decreasing of supply voltage, power integrity becomes a critical issue. The effect of the transition time of load currents was taken into account, and a more realistic worst-case noise prediction was obtained. In addition, a dynamic programming algorithm is introduced for the time-domain impulse response of the power distribution system, and a modified Knuth-Yao quadrangle inequality speedup method is developed which reduces the time complexity of the algorithm from O(n2m) to O(mnlogn).

Key words：dynamic programming; worst-case noise; transition time; power delivery network; time-domain analysis

http://journal.nudt.edu.cn