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

(國防科技大學 計算機學院， 湖南 長沙　410073)

?

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

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

(國防科技大學 計算機學院， 湖南 長沙410073)

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

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

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

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

1問題定式化

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

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

(1)

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

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

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

(2)

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

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

(3)

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

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

2最差噪聲分析算法

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

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

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

(4)

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

(a)交點超過邊界(a) Intersection over border

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

如果z(t)在[tj,tj+1]時間段為負，Gj(k,i,t)可以表示為類似形式。以圖2(a)所示情況為例來證明貪婪算法。假設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中的一個原點領域.假設F(0)=0是F(x)在原點領域的不動點，因此可將F(x)表示為：

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

3算法加速

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

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

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

引理1：對任何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]。然而，該不等式并不成立，也就是說無法推導出OPT的四邊形不等式。因此，選擇基于下面一條引理的Knuth-Yao加速方法來降低算法的時間復雜度。

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

證明：

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

i0=GetTransPos(j,k1,k2)

3.2加速算法偽代碼描述

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

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

3.3時間復雜度

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

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

3.4算法加速效果

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

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

4結(jié)論

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

參考文獻(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

基金項目：國家自然科學基金資助項目(61272139)

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

中圖分類號：TN47

文獻標志碼：A

文章編號：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