湯戰(zhàn)勇, 郝 杰, 郭 軍, 劉寶英

(西北大學(xué) 信息科學(xué)與技術(shù)學(xué)院, 西安 710127)

隨著集成電路(IC)規(guī)模的擴(kuò)大, 芯片設(shè)計(jì)精度也越來越高, 使電路中晶體管數(shù)目及所對(duì)應(yīng)的電路方程規(guī)模不斷增加. 傳統(tǒng)LU分解法求解大規(guī)模模擬電路的時(shí)間較長(zhǎng), 因此很難高效滿足現(xiàn)代芯片的發(fā)展需求. 為設(shè)計(jì)更穩(wěn)定有效的集成電路, 文獻(xiàn)[1]提出了相應(yīng)的解決算法, 即模型縮減法、 時(shí)域頻域變換法和近似算法. 其中模型縮減法和時(shí)域頻域變換法面對(duì)大規(guī)模電路求解, 其分析矩陣的運(yùn)算量較大, 且計(jì)算時(shí)間較長(zhǎng). 近似算法是指用近似的方法解決優(yōu)化問題的算法, 其在可證明的解決方法和運(yùn)行時(shí)間范圍內(nèi)能得到保證質(zhì)量的解. 文獻(xiàn)[2]研究了隨機(jī)行走方法在電路網(wǎng)絡(luò)分析中的應(yīng)用. 隨機(jī)行走算法對(duì)無窮大或相對(duì)無窮大解空間問題能求得符合要求的近似解, 在許多領(lǐng)域應(yīng)用廣泛[3-6]. 為滿足大規(guī)模電路設(shè)計(jì)需求, 文獻(xiàn)[7]采用隨機(jī)行走算法對(duì)不同規(guī)模及特點(diǎn)的電源電路進(jìn)行分析, 并研究了其在電源網(wǎng)絡(luò)上的加速技術(shù)及改進(jìn)措施.

傳統(tǒng)隨機(jī)行走算法加速技術(shù)具有局限性, 即在電路電壓幅值變化較小的情形下不能有效縮短運(yùn)行時(shí)間. 針對(duì)此問題, 本文在滿足精度要求的前提下提出變步長(zhǎng)加速策略, 其基本原理是在信息重用加速策略的基礎(chǔ)上, 根據(jù)動(dòng)態(tài)檢測(cè)出的電路電壓幅值大小靈活地改變時(shí)間步長(zhǎng), 從而有效縮短運(yùn)行時(shí)間.

1 隨機(jī)行走算法

圖1 隨機(jī)行走問題示意圖

對(duì)解決空間無窮大或接近無窮大的問題, 隨機(jī)行走是一種有效的方法[8]. 圖1為隨機(jī)行走問題描述模型, 其中x點(diǎn)為一位醉酒行走者的起始點(diǎn), home節(jié)點(diǎn)可被認(rèn)為是旅店或其家, 其他交叉點(diǎn)則表示岔道路口, 交點(diǎn)間的線段可被認(rèn)為是街道. 行走者要從x點(diǎn)回到home點(diǎn), 則有3條路可選擇, 但由于其醉酒, 他會(huì)隨機(jī)挑選一條路走, 則走這3條路的概率分別可設(shè)為Px,1,Px,2,Px,3. 從3條路中他任選一條路都會(huì)先到達(dá)一個(gè)岔道路口, 而過該路口所交費(fèi)用為mx, 繼續(xù)走至home節(jié)點(diǎn)時(shí)獲得獎(jiǎng)勵(lì)并停止此次行走. 此時(shí), 其最終所獲獎(jiǎng)勵(lì)值或行走多次后的平均獎(jiǎng)勵(lì)值為醉漢從x節(jié)點(diǎn)出發(fā)到home點(diǎn)獎(jiǎng)勵(lì)的期望值, 用公式表示為

(1)

其中:E(x)表示期望獎(jiǎng)勵(lì)值；Px,i為醉漢從x節(jié)點(diǎn)出發(fā)去第i個(gè)相鄰道路的概率值；mx為通過岔道路口的路費(fèi). 醉漢從x點(diǎn)去各相鄰道路的總概率表達(dá)式為

(2)

解決隨機(jī)行走問題的基本理論是大數(shù)定律, 即當(dāng)某實(shí)驗(yàn)重復(fù)發(fā)生次數(shù)達(dá)到足夠數(shù)量時(shí), 事件A發(fā)生次數(shù)與總實(shí)驗(yàn)次數(shù)之比會(huì)接近于其真實(shí)概率值. 在理想狀態(tài)下, 實(shí)驗(yàn)次數(shù)越多, 最終觀測(cè)事件的發(fā)生概率會(huì)越接近真實(shí)值. 例如： 在擲骰子實(shí)驗(yàn)中, 所拋骰子次數(shù)足夠多時(shí), 任意一面向上出現(xiàn)的概率會(huì)接近其真實(shí)值1/6. 因此, 可在大數(shù)定律的基礎(chǔ)上根據(jù)中心極限定理進(jìn)行求解. 中心極限定理是指在全部樣本中隨機(jī)抽取一定容量n的部分樣本, 當(dāng)容量達(dá)到一定規(guī)模時(shí), 其樣本分布與高斯正態(tài)概率密度分布趨于相似, 即實(shí)驗(yàn)次數(shù)越多, 實(shí)驗(yàn)值與真實(shí)值相近的概率越高. 假設(shè)滿足正態(tài)分布隨機(jī)抽樣實(shí)驗(yàn)結(jié)果為X1,X2,…,Xn, 可求得樣本均值為

(3)

樣本方差為

(4)

最少實(shí)驗(yàn)次數(shù)為

(5)

式(5)是根據(jù)文獻(xiàn)[9-10]得到的隨機(jī)行走的結(jié)束判斷式. 設(shè)在誤差允許范圍內(nèi),M為最少實(shí)驗(yàn)次數(shù), 允許誤差為Δ, 絕對(duì)誤差區(qū)間為[-Δ,+Δ], 置信概率為P, 置信概率所得系數(shù)為β. 在該次數(shù)下得到的實(shí)驗(yàn)統(tǒng)計(jì)平均值可表示為實(shí)驗(yàn)期望值μ的近似值.

2 隨機(jī)行走算法在電路分析中的應(yīng)用

圖2為典型的IC芯片電源網(wǎng)絡(luò)等效電路模型, 實(shí)際上是一個(gè)電阻-電容(RC)電路網(wǎng)絡(luò), 為避免問題過于復(fù)雜, 該電路圖僅含有電阻、 電容和電源, 其中任意一個(gè)電路節(jié)點(diǎn)結(jié)構(gòu)示意圖如圖3所示.

圖2 RC電路網(wǎng)絡(luò)

由Kirchhoff電流電壓定律和歐姆定律可得：

簡(jiǎn)化式(6)可得節(jié)點(diǎn)x的電壓表達(dá)式為

(7)

其中：Vi為相鄰節(jié)點(diǎn)電壓;gi為電導(dǎo)參數(shù)； degree(x)為電路節(jié)點(diǎn)x的度. 對(duì)比式(1)與式(7)可見, 公式結(jié)構(gòu)相似, 即對(duì)電路節(jié)點(diǎn)分析與經(jīng)典隨機(jī)行走算法分析一致, 因此可推得節(jié)點(diǎn)x到其相鄰節(jié)點(diǎn)i的概率值表達(dá)式為

(8)

相對(duì)應(yīng)的路費(fèi)表達(dá)式為

(9)

由上述結(jié)論可將電路節(jié)點(diǎn)類比為隨機(jī)行走算法分析中的岔道路口, 電路元件與道路相對(duì)應(yīng), 電壓源和接地節(jié)點(diǎn)都與home節(jié)點(diǎn)相對(duì)應(yīng), 電路節(jié)點(diǎn)x到其相鄰節(jié)點(diǎn)i概率分析與每條道路概率分析相同, 電網(wǎng)節(jié)點(diǎn)的路費(fèi)求解與每個(gè)岔道路口所交費(fèi)用相同. 對(duì)于含電容電路的瞬態(tài)分析, 可利用Norton等效方法處理電容等動(dòng)態(tài)元件, 即令電容C等效成電導(dǎo)為C/Δt的電壓源, Δt是時(shí)間步長(zhǎng), 被等效的電壓源電壓V是上一時(shí)刻相鄰節(jié)點(diǎn)的電壓值. 在電路分析領(lǐng)域, 由于隨機(jī)行走算法在電源網(wǎng)絡(luò)分析上的等價(jià)性, 可進(jìn)一步擴(kuò)展應(yīng)用到RC動(dòng)態(tài)分析上, 因而簡(jiǎn)化的電阻電源網(wǎng)絡(luò)既能按照隨機(jī)行走算法進(jìn)行分析, 也能對(duì)一般的電容電阻網(wǎng)絡(luò)進(jìn)行瞬態(tài)分析, 即可將一個(gè)RC電路網(wǎng)絡(luò)表示成一個(gè)一般的電阻電源網(wǎng)絡(luò), 并利用隨機(jī)行走算法進(jìn)行分析.

3 改進(jìn)的隨機(jī)行走算法

3.1 隨機(jī)行走算法在電路網(wǎng)絡(luò)中的加速分析

圖4 某步長(zhǎng)隨機(jī)行走結(jié)果

隨機(jī)行走算法在分析動(dòng)態(tài)電路網(wǎng)絡(luò)時(shí), 可采用信息重用的策略加速算法. 首先, 假設(shè)在某一時(shí)刻, 從節(jié)點(diǎn)Ns,0出發(fā), 進(jìn)行M次隨機(jī)行走實(shí)驗(yàn), 結(jié)果分析如圖4所示, 其中: 節(jié)點(diǎn)Ns,0,Ns,1,Ns,2,…,Ns,k是隨機(jī)行走過程訪問的節(jié)點(diǎn); 訪問次數(shù)為V1,V2,…,Vk;Ws,k為Ns,k節(jié)點(diǎn)路費(fèi). 此時(shí)從節(jié)點(diǎn)Ns,0出發(fā)所獲總報(bào)酬平均值表達(dá)式為

(10)

由于行走經(jīng)過各路徑概率和電路拓?fù)浣Y(jié)構(gòu)不變, 因而下個(gè)時(shí)間步從節(jié)點(diǎn)Ns,0出發(fā), 仍會(huì)訪問相同的節(jié)點(diǎn), 且次數(shù)Vi保持不變. 因此, 只需將新的參數(shù)Ws,i代入便可求出下個(gè)時(shí)間步長(zhǎng)下節(jié)點(diǎn)的電壓值. 可見, 從任一節(jié)點(diǎn)出發(fā), 只需在第一個(gè)時(shí)間步長(zhǎng)上進(jìn)行M次隨機(jī)行走實(shí)驗(yàn), 并記錄下必要的行走信息, 后續(xù)工作便不用再進(jìn)行實(shí)際行走, 只需更新數(shù)據(jù), 從而節(jié)省了大量時(shí)間. 該加速策略記錄行走信息雖會(huì)占用內(nèi)存空間, 但達(dá)到了用空間換時(shí)間的目的.

針對(duì)穩(wěn)態(tài)RC電路采用隨機(jī)行走算法, 若要關(guān)注所有電路節(jié)點(diǎn)的電壓, 獲得更高的電壓測(cè)算精確度, 則需隨機(jī)行走次數(shù)M足夠大. 對(duì)規(guī)模越大的電源電路, 算法的耗時(shí)越多, 隨機(jī)行走算法可通過并行行走減少運(yùn)算時(shí)間. 對(duì)隨機(jī)行走, 由于其具有先天可并行性, 所以從每個(gè)節(jié)點(diǎn)出發(fā)行走的實(shí)驗(yàn)可并行運(yùn)行.

區(qū)別于傳統(tǒng)并行方法, 文獻(xiàn)[11-12]采用了一種偽并行方法. 假設(shè)某次隨機(jī)行走軌跡如圖5所示. 對(duì)于節(jié)點(diǎn)Ns, 從出發(fā)開始, 依次通過節(jié)點(diǎn)N1,N2,…,Nm-1, 至home節(jié)點(diǎn)結(jié)束, 最終完成一次從節(jié)點(diǎn)Ns出發(fā)的行走實(shí)驗(yàn), 所獲總報(bào)酬為rews. 此時(shí), 在該隨機(jī)行走過程中實(shí)際也完成了一次以節(jié)點(diǎn)N1出發(fā)的行走實(shí)驗(yàn), 如圖6所示.

圖5 從Ns出發(fā)的隨機(jī)行走軌跡

圖6 從N1出發(fā)的隨機(jī)行走軌跡

由圖6可見, 從N1出發(fā)的總報(bào)酬為rews-fs(fs為圖5中經(jīng)過節(jié)點(diǎn)Ns的路費(fèi)). 對(duì)于圖6中從Ns出發(fā)軌跡上的其他節(jié)點(diǎn)情形相同, 因此可推得行走軌跡上的節(jié)點(diǎn)都并行完成了一次行走實(shí)驗(yàn). 區(qū)別于一般意義的真并行, 這種并行行走稱為偽并行. 此外, 結(jié)合行走重用技術(shù), 記錄所有非home節(jié)點(diǎn)的隨機(jī)行走結(jié)果, 所需總時(shí)間為

Tr=tr+2tr+…+mtr,

(11)

其中tr為記錄數(shù)據(jù)的平均時(shí)間. 按相同軌跡完成隨機(jī)行走實(shí)驗(yàn), 所需時(shí)間為

Ts=ts+2ts+…+mts,

(12)

其中ts是每行走一步所用的平均時(shí)間, 通常隨機(jī)行走一步的時(shí)間多于記錄時(shí)間, 即ts>tr. 因此, 對(duì)于大規(guī)模RC電路又節(jié)省了一部分時(shí)間.

3.2 變步長(zhǎng)加速算法

圖7 SPICE測(cè)試下節(jié)點(diǎn)電壓變化曲線

本文提出的變步長(zhǎng)加速方法是對(duì)傳統(tǒng)信息重用方法的延伸. 信息重用方法是將瞬態(tài)電路各節(jié)點(diǎn)到達(dá)穩(wěn)態(tài)后的總時(shí)長(zhǎng)劃為若干個(gè)步長(zhǎng)h, 在記錄隨機(jī)行走結(jié)果的基礎(chǔ)上, 通過逐步迭代使其達(dá)到穩(wěn)態(tài). 對(duì)一般RC電路, 各電路節(jié)點(diǎn)電壓是變化的. 圖7為在真實(shí)電路數(shù)據(jù)的RC電源電路中被SPICE電路模擬器測(cè)試的一個(gè)節(jié)點(diǎn)電壓變化曲線. 由圖7可見, 在達(dá)到穩(wěn)定點(diǎn)過程中, 節(jié)點(diǎn)電壓的變化幅度越來越小, 如果按照固定步長(zhǎng)h進(jìn)行動(dòng)態(tài)電路分析, 則需較多的迭代次數(shù), 會(huì)消耗較多的計(jì)算時(shí)間. 因此, 可根據(jù)電壓變化幅度調(diào)整步長(zhǎng)大小, 實(shí)現(xiàn)變步長(zhǎng)隨機(jī)行走, 在滿足精度要求的前提下, 減少迭代次數(shù), 從而縮短運(yùn)行時(shí)間.

變步長(zhǎng)策略為： 基于上述電源電路加速分析可獲得任意一個(gè)節(jié)點(diǎn)在隨機(jī)行走過程中的總報(bào)酬平均值, 其下一步的總報(bào)酬平均值可采用變步長(zhǎng)信息重用技術(shù)求得. 按預(yù)先設(shè)定的精度要求設(shè)置閾值區(qū)間檢測(cè)電壓的幅值變化, 用當(dāng)前時(shí)刻的總報(bào)酬值減去該節(jié)點(diǎn)上一時(shí)刻的總報(bào)酬值為X, 如果設(shè)閾值區(qū)間為Y, 則與信息復(fù)用的關(guān)系如下：

1) 若X>Y, 則繼續(xù)按當(dāng)前步長(zhǎng)進(jìn)行信息復(fù)用；

2) 若X≤Y, 則采用變換后的步長(zhǎng)進(jìn)行信息復(fù)用.

若上一時(shí)刻為t=0, 則節(jié)點(diǎn)的總報(bào)酬值為隨機(jī)行走過程中得到的總報(bào)酬值.

3.3 變步長(zhǎng)隨機(jī)行走算法的時(shí)間復(fù)雜度

隨機(jī)行走算法的最差時(shí)間復(fù)雜度為O(LMN), 其中:L為行走的步數(shù)；M為行走次數(shù);N為電路節(jié)點(diǎn)數(shù). 傳統(tǒng)加速技術(shù)第一次是基于隨機(jī)行走的運(yùn)算, 其余時(shí)間步的電壓均采用信息重用技術(shù)運(yùn)算. 采用信息重用技術(shù)運(yùn)算過程中, 假設(shè)從任意節(jié)點(diǎn)出發(fā)訪問過的節(jié)點(diǎn)有P個(gè), 則需更新的數(shù)據(jù)有NP個(gè). 設(shè)每個(gè)節(jié)點(diǎn)數(shù)據(jù)的平均更新時(shí)間為γ, 則每個(gè)時(shí)間步更新數(shù)據(jù)的時(shí)間為NPγ. 因此, 在信息重用過程中, 設(shè)有k個(gè)時(shí)間步, 則總迭代時(shí)間為kNPγ. 傳統(tǒng)加速技術(shù)的總計(jì)算時(shí)間為t=0時(shí)電路隨機(jī)行走運(yùn)行時(shí)間與該電路的信息復(fù)用時(shí)間之和. 在考慮給定的誤差范圍、 置信概率及時(shí)間步長(zhǎng)后, 上述參數(shù)M和k也變?yōu)楣潭ㄖ? 而L和P是只與電路拓?fù)浣Y(jié)構(gòu)相關(guān), 與電路規(guī)模大小無關(guān)的值, 即它們是有限值. 因而可推得傳統(tǒng)隨機(jī)行走加速算法的執(zhí)行時(shí)間是關(guān)于節(jié)點(diǎn)數(shù)N的一次多項(xiàng)式, 其時(shí)間復(fù)雜度為O(N).

變步長(zhǎng)隨機(jī)行走加速算法總時(shí)間為第一時(shí)刻隨機(jī)行走計(jì)算時(shí)間(t=0)、 既定步長(zhǎng)迭代時(shí)間(節(jié)點(diǎn)電壓幅值變化大的時(shí)間段)與加大步長(zhǎng)迭代時(shí)間(節(jié)點(diǎn)電壓幅值變化微小的時(shí)間段)之和. 上述傳統(tǒng)加速算法有k個(gè)時(shí)間步長(zhǎng), 假設(shè)在變步長(zhǎng)中有U個(gè)原始時(shí)間步長(zhǎng), (k-U)/α個(gè)加大的時(shí)間步長(zhǎng)(α是滿足精度要求下關(guān)于增大步長(zhǎng)的系數(shù),α>1), 則變步長(zhǎng)信息重用運(yùn)算時(shí)間為

(13)

加速比R為

(14)

在設(shè)置的電路電壓精度范圍內(nèi), 隨著E的減小或α的增大, 算法的運(yùn)行效率逐步提高； 其時(shí)間復(fù)雜度也為O(N), 遠(yuǎn)優(yōu)于傳統(tǒng)SPICE電路模擬器中LU分解法的時(shí)間復(fù)雜度O(N3), 雖與傳統(tǒng)隨機(jī)行走加速算法相同, 也是線性增長(zhǎng)的, 但變步長(zhǎng)加速算法的斜率卻遠(yuǎn)小于傳統(tǒng)加速算法的斜率. 隨著電路規(guī)模的擴(kuò)大, 節(jié)省時(shí)間越來越多.

3.4 實(shí)驗(yàn)分析

為驗(yàn)證本文提出的加速算法的有效性, 采用規(guī)模為256節(jié)點(diǎn)的RC電路網(wǎng)絡(luò)進(jìn)行精度對(duì)比實(shí)驗(yàn), 設(shè)α=2, 閾值大小為0.5, 實(shí)驗(yàn)結(jié)果列于表1. 由表1可見, 當(dāng)RC電源電路達(dá)到穩(wěn)態(tài)時(shí), 利用本文算法進(jìn)行實(shí)驗(yàn)得到的4個(gè)節(jié)點(diǎn)數(shù)據(jù)與采用標(biāo)準(zhǔn)SPICE電路模擬器計(jì)算所得的實(shí)驗(yàn)數(shù)據(jù)相比, 誤差均在預(yù)先設(shè)置的范圍(約0.5)內(nèi), 證明了該算法對(duì)電源電路電壓求解滿足精度要求.

表1 精度實(shí)驗(yàn)對(duì)比

圖8 SPICE與變步長(zhǎng)數(shù)據(jù)變化精度比較

圖8為將表1中N017節(jié)點(diǎn)在其變步長(zhǎng)加速算法實(shí)驗(yàn)中得到的數(shù)據(jù)變化曲線與其SPICE電路模擬器下得到的數(shù)據(jù)變化曲線對(duì)比結(jié)果. 由圖8可見, 該節(jié)點(diǎn)電壓在達(dá)到穩(wěn)定的動(dòng)態(tài)變化過程中, 兩條數(shù)據(jù)曲線的誤差在任何時(shí)刻都不超過0.1, 完全滿足預(yù)先設(shè)置的誤差范圍和精度要求.

圖9 基于節(jié)點(diǎn)的傳統(tǒng)加速與變步長(zhǎng)加速時(shí)間效率對(duì)比

圖10 基于閾值的傳統(tǒng)加速與變步長(zhǎng)加速時(shí)間效率對(duì)比

4 變步長(zhǎng)隨機(jī)行走算法的運(yùn)行空間優(yōu)化

4.1 隨機(jī)行走算法空間復(fù)雜度

對(duì)隨機(jī)行走加速策略進(jìn)行分析可知, 需在每一時(shí)間步各節(jié)點(diǎn)數(shù)值已知的情形下才能得到目標(biāo)節(jié)點(diǎn)的電壓波形圖. 因此需對(duì)整個(gè)電源網(wǎng)絡(luò)的節(jié)點(diǎn)進(jìn)行隨機(jī)行走實(shí)驗(yàn), 故算法加速策略的研究都基于整個(gè)電源網(wǎng)絡(luò)進(jìn)行分析, 程序的運(yùn)行空間復(fù)雜度較大. 因此需盡量在運(yùn)行期間減少使用存儲(chǔ)空間, 實(shí)現(xiàn)算法的運(yùn)行空間優(yōu)化. 為解決該問題, 本文將基于隨機(jī)行走算法具有局部特征的前提下對(duì)是否需對(duì)整個(gè)電源網(wǎng)絡(luò)使用隨機(jī)行走策略進(jìn)行分析. 若能在對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行求解時(shí)不存儲(chǔ)與目標(biāo)節(jié)點(diǎn)關(guān)聯(lián)性低或無關(guān)聯(lián)性的節(jié)點(diǎn), 使程序在運(yùn)行前不存儲(chǔ)無關(guān)節(jié)點(diǎn)數(shù)據(jù), 在運(yùn)行期間不記錄其路徑, 便可達(dá)到算法運(yùn)行空間優(yōu)化的目的.

4.2 隨機(jī)行走算法空間局部性特征分析

為描繪節(jié)點(diǎn)電壓隨時(shí)間的變化曲線, 結(jié)合隨機(jī)行走問題描述, 需將時(shí)間步長(zhǎng)調(diào)整到節(jié)點(diǎn)去往電容的概率與去往電阻的概率大致相同, 否則當(dāng)去往電阻的概率大于去往電容的概率情形發(fā)生時(shí), 節(jié)點(diǎn)只會(huì)在電源網(wǎng)絡(luò)中做無休止的隨機(jī)行走運(yùn)動(dòng). 當(dāng)去往電阻的概率小于去往電容的概率時(shí), 節(jié)點(diǎn)會(huì)大概率僅行走到home節(jié)點(diǎn)便直接結(jié)束. 同理, 對(duì)電阻也存在類似問題, 因此設(shè)定相同的電阻值. 否則將導(dǎo)致路徑太短無法滿足對(duì)目標(biāo)節(jié)點(diǎn)電壓求解的要求, 或者路徑太長(zhǎng)超過設(shè)定行走路徑步數(shù)限制而不被記錄, 都會(huì)使節(jié)點(diǎn)做無意義的行走, 進(jìn)而降低效率. 故在電路節(jié)點(diǎn)去往相鄰電阻和電容的概率值基本相同的條件下, 觀察離目標(biāo)節(jié)點(diǎn)遠(yuǎn)的節(jié)點(diǎn)對(duì)目標(biāo)節(jié)點(diǎn)值的影響.

圖11 RC電路的節(jié)點(diǎn)

以如圖11所示的RC電路節(jié)點(diǎn)為例, 若電路節(jié)點(diǎn)Vx通過相鄰的電阻去往周圍節(jié)點(diǎn)的概率與該節(jié)點(diǎn)去往電容C3的概率大致相同, 與隨機(jī)行走問題模型對(duì)應(yīng)后, 則可得節(jié)點(diǎn)x到第i個(gè)相鄰節(jié)點(diǎn)的概率為

(15)

由于概率都大致相同, 因此可推得：p=1/i. 結(jié)合圖4, 若在此隨機(jī)行走路徑上各節(jié)點(diǎn)相鄰節(jié)點(diǎn)數(shù)均為i個(gè), 且該路徑不存在重復(fù)的節(jié)點(diǎn), 則節(jié)點(diǎn)V0沿該行走路徑走到節(jié)點(diǎn)V3的概率是(1/i)3, 依次類推, 當(dāng)行走到節(jié)點(diǎn)Vk時(shí), 發(fā)生的概率是(1/i)k. 真實(shí)電源網(wǎng)絡(luò)中節(jié)點(diǎn)所連接的相鄰節(jié)點(diǎn)與電容等元件的數(shù)量都大于2個(gè), 假設(shè)k為最小值2的情形, 則當(dāng)電路節(jié)點(diǎn)V0經(jīng)過10個(gè)節(jié)點(diǎn)(不包括路過折返的重復(fù)電路節(jié)點(diǎn))到達(dá)V10時(shí)發(fā)生的概率僅為1/1 024. 因此僅在節(jié)點(diǎn)所連接的電阻與其他元件最少的情形下, 電路節(jié)點(diǎn)V10的每一時(shí)間步長(zhǎng)下所更新的電壓數(shù)值對(duì)實(shí)驗(yàn)中想測(cè)算的目標(biāo)節(jié)點(diǎn)V0的電壓幾乎沒有影響, 通過上述分析可知, 節(jié)點(diǎn)隨機(jī)行走的運(yùn)行軌跡具有局部性特征. 因此對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行求解時(shí)不存儲(chǔ)與目標(biāo)節(jié)點(diǎn)關(guān)聯(lián)性低或無關(guān)聯(lián)性的電路節(jié)點(diǎn), 使程序在運(yùn)行過程中空間得到優(yōu)化可行.

4.3 實(shí) 驗(yàn)

隨機(jī)行走算法在IC電源網(wǎng)絡(luò)上進(jìn)行分析具有局部性特征, 因此可通過僅存儲(chǔ)與目標(biāo)節(jié)點(diǎn)相關(guān)的電源網(wǎng)絡(luò)部分節(jié)點(diǎn)達(dá)到運(yùn)行空間優(yōu)化的目的. 下面通過對(duì)比實(shí)驗(yàn), 并結(jié)合實(shí)驗(yàn)結(jié)果進(jìn)行分析, 證明結(jié)論的合理性和正確性. 為保證實(shí)驗(yàn)順利運(yùn)行, 實(shí)驗(yàn)中設(shè)定電路節(jié)點(diǎn)間的電阻值基本相同.

圖12為電阻電容基本相同且電路節(jié)點(diǎn)數(shù)為100時(shí)的RC電路， 對(duì)目標(biāo)節(jié)點(diǎn)為N044進(jìn)行測(cè)算(行走次數(shù)為500). 由圖12可見, 在時(shí)間步長(zhǎng)設(shè)定合理的情形下, 該電路節(jié)點(diǎn)的運(yùn)行軌跡基本在橫坐標(biāo)為2～8、 縱坐標(biāo)為3～8的區(qū)域內(nèi)行走. 圖13為電阻電容基本相同且電路節(jié)點(diǎn)數(shù)為10 000的RC電路， 對(duì)目標(biāo)節(jié)點(diǎn)為N4949進(jìn)行測(cè)算(行走次數(shù)為500). 由圖13可見, 在時(shí)間步長(zhǎng)設(shè)定合理的情形下, 該電路節(jié)點(diǎn)的運(yùn)行軌跡基本在橫坐標(biāo)為46～54、 縱坐標(biāo)為46～54的區(qū)域內(nèi)行走.

圖12 電阻電容基本相同且電路節(jié)點(diǎn)數(shù)為100時(shí)的等效電路

圖13 電阻電容基本相同且電路節(jié)點(diǎn)數(shù)為10 000的等效電路

圖14為電阻大于電容且電路節(jié)點(diǎn)數(shù)為10 000的電源電路， 對(duì)目標(biāo)節(jié)點(diǎn)為N4949進(jìn)行測(cè)算(行走次數(shù)為500). 由圖14可見, 在時(shí)間步長(zhǎng)設(shè)定不變的情形下, 利用隨機(jī)行走算法得到電路節(jié)點(diǎn)的運(yùn)行軌跡略擴(kuò)大了其在電路網(wǎng)絡(luò)中的行走范圍, 該電路節(jié)點(diǎn)的運(yùn)行范圍在橫坐標(biāo)為43～58、 縱坐標(biāo)43～57的區(qū)域內(nèi)行走. 圖15為電容大于電阻且電路節(jié)點(diǎn)數(shù)為10 000的電源電路， 對(duì)目標(biāo)節(jié)點(diǎn)為N4949進(jìn)行測(cè)算(行走次數(shù)為500). 由圖15可見, 在時(shí)間步長(zhǎng)設(shè)定不變的情形下, 利用隨機(jī)行走算法得到電路節(jié)點(diǎn)的運(yùn)行軌跡略小于其在電路網(wǎng)絡(luò)中的行走范圍, 該電路節(jié)點(diǎn)的運(yùn)行范圍在橫坐標(biāo)為47～53、 縱坐標(biāo)為48～52的區(qū)域內(nèi)行走.

圖14 電阻大于電容且電路節(jié)點(diǎn)數(shù)為10 000的電源電路

圖15 電容大于電阻且電路節(jié)點(diǎn)數(shù)為10 000的電源電路

通過上述實(shí)驗(yàn)結(jié)果對(duì)比分析可知, 在僅對(duì)單個(gè)目標(biāo)節(jié)點(diǎn)進(jìn)行測(cè)算的情形下, 電源網(wǎng)絡(luò)規(guī)模的增大和電路節(jié)點(diǎn)數(shù)目的增多， 并未使測(cè)算電路節(jié)點(diǎn)的運(yùn)行軌跡發(fā)生明顯改變. 因此, 電路規(guī)模的大小對(duì)目標(biāo)電路節(jié)點(diǎn)的運(yùn)行軌跡所在區(qū)域無影響, 而影響目標(biāo)節(jié)點(diǎn)運(yùn)行軌跡的因素是電路的拓?fù)浣Y(jié)構(gòu). 所以, 在保證電路拓?fù)浣Y(jié)構(gòu)不變的情形下， 對(duì)確定目標(biāo)節(jié)點(diǎn)進(jìn)行測(cè)算可通過減少讀入與目標(biāo)節(jié)點(diǎn)無關(guān)的電源網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)達(dá)到優(yōu)化隨機(jī)行走算法運(yùn)行空間的目的.

綜上所述, 本文在分析隨機(jī)行走算法的基礎(chǔ)上, 提出了一種變步長(zhǎng)隨機(jī)行走加速算法, 使隨機(jī)行走的效率和性能都有了較大提高. 在算法時(shí)間效率提升的前提下, 證明了隨機(jī)行走算法具有空間局部性特征, 在此基礎(chǔ)上提出了運(yùn)行空間優(yōu)化策略, 使隨機(jī)行走算法運(yùn)行空間得到釋放.