隨機(jī)過(guò)程論文

1、隨機(jī)過(guò)程在專業(yè)中的應(yīng)用摘要：馬爾科夫鏈作為隨機(jī)過(guò)程學(xué)科中的一項(xiàng)重要內(nèi)容，在實(shí)際的科研中有著廣 泛的應(yīng)用。本文介紹了馬爾科夫鏈在集成電路設(shè)計(jì)領(lǐng)域中的一些應(yīng)用，在大規(guī)模 集成電路中，功耗的估算是一個(gè)重要的研究?jī)?nèi)容，一款芯片的功耗大小決定了其 應(yīng)用方向甚至能否投入使用，因此在流片之前準(zhǔn)確的估算芯片的功耗對(duì)設(shè)計(jì)者來(lái) 說(shuō)是很有必要的。而集成電路中的最基本單位門電路的功耗除了和自身的一些屬 性相關(guān)外，還和每個(gè)周期其狀態(tài)轉(zhuǎn)換概率相關(guān)，這個(gè)概率便可以用馬爾科夫鏈來(lái) 求取。關(guān)鍵詞：馬爾科夫鏈、集成電路、轉(zhuǎn)換概率.集成電路功耗組成集成電路的功耗可以用以下公式表示Ptotal = Pdyn + P$c + Plea

2、k（1）其中，P$c為短路電流導(dǎo)致的功耗，短路電流是NMOS和PMOS同時(shí)導(dǎo)通的 時(shí)候產(chǎn)生的電流，由于在CMOS電路中，這部分電路很小并且NMOS和PMOS 同時(shí)導(dǎo)通的時(shí)間很短，所以一般由此帶來(lái)的功耗可以忽略不計(jì)囚。Pleak是電路的 漏電流，漏電流在MOS管截止的時(shí)候也依然存在，因此這部分功耗是難以改變 的。這樣，對(duì)電路功耗影響最大的就是Pdyn，稱為動(dòng)態(tài)功耗，這是電路邏輯狀態(tài) 切換時(shí)由于負(fù)載電容充放電導(dǎo)致的能量損耗。它由負(fù)載電容大小和電流通路共同 決定。可以用一個(gè)靜態(tài)反相器來(lái)研究馬爾科夫鏈在功耗計(jì)算中的應(yīng)用。圖1靜態(tài)反相器中的動(dòng)態(tài)功耗如上圖所示，當(dāng)輸出節(jié)點(diǎn)由。變?yōu)?的時(shí)侯，開(kāi)關(guān)1導(dǎo)通、開(kāi)關(guān)

3、2截止，此 時(shí)電源將對(duì)負(fù)載電容充電，假設(shè)負(fù)載電容為C,那么電源的輸出功率為CVX， 其中一半能量存儲(chǔ)在電容中，另一半消耗在了電路上。當(dāng)下一次狀態(tài)轉(zhuǎn)化，輸出 由1變?yōu)?時(shí)，開(kāi)關(guān)1閉合開(kāi)關(guān)2開(kāi)啟，電容對(duì)地放電，因此之前存儲(chǔ)的能量全 部消耗了，因此在一個(gè)輸出狀態(tài)變化周期內(nèi)，反相器的總功耗為必。.功耗計(jì)算模型由前面對(duì)反相器的動(dòng)態(tài)功耗分析可知，在一個(gè)時(shí)鐘周期內(nèi)，一個(gè)CMOS邏輯 電路輸出狀態(tài)變化時(shí)產(chǎn)生的動(dòng)態(tài)功耗等于負(fù)載電容充放電時(shí)電路中所消耗的電 能。如果這個(gè)門是同步邏輯電路的一部分，并且由全局時(shí)鐘控制，那么這個(gè)門 所消耗的平均功率公式即可以表示為Pavg=0.5xCxVddXE/T (2)其中Pavg

4、表示平均功率，C代表負(fù)載電容，丫時(shí)是電源電壓，T為全局時(shí)鐘周 期，而E則是每個(gè)時(shí)鐘周期內(nèi)門的輸出狀態(tài)轉(zhuǎn)換的概率。除了 E之外，其他兒 個(gè)參數(shù)都是由甩路本身的性質(zhì)決定的，而E除了受電路自身性質(zhì)影響之外還與 電路輸入信號(hào)的統(tǒng)計(jì)特性有密切關(guān)聯(lián)。因此對(duì)電路功率的估算就轉(zhuǎn)化成了求取 參數(shù)E。.馬爾科夫鏈的應(yīng)用參數(shù)E因?yàn)榕c電路的統(tǒng)計(jì)特性有關(guān)，因此對(duì)其求取可以應(yīng)用馬爾科夫鏈的一 些性質(zhì)。馬爾科夫鏈?zhǔn)且粋€(gè)隨機(jī)過(guò)程，設(shè)X(t),tT為定義在概率空間(C , F, P)上并且所有可能取指的集合為E的隨機(jī)過(guò)程，如果對(duì)于任意的n和2Vtn, tkeT, k=12,3,4.n,任給E的一個(gè)子集A,有PX(tn)eA|X

5、(t1)=x1,不購(gòu))f i = PX(X A|X(MFi (3)則此隨機(jī)過(guò)程成為馬爾科夫過(guò)程，簡(jiǎn)稱為馬氏過(guò)程，此性質(zhì)稱為馬氏性。馬氏過(guò)程的狀態(tài)空間E可以是連續(xù)的，也可以是離散的；馬氏過(guò)程的參數(shù)空 間既可以是連續(xù)的也可以是離散的。狀態(tài)空間和參數(shù)空間都是離散的馬氏過(guò)程通 常稱為馬氏鏈。馬氏鏈的一個(gè)重要特性是無(wú)后效性，可以用下式來(lái)表達(dá)PX(Q e A|X(t1)=x1, X(t3)=t2,.x(%)f 1 = PX(tn) e Apc&if (4)其中ii，i2, i3in，j均都屬于Eo其意義是,在已知“現(xiàn)在”的條件下，“將 來(lái)，與，過(guò)去，是統(tǒng)計(jì)獨(dú)立的，也就是說(shuō)，己知“現(xiàn)在”，“將來(lái)”與“歷史“

6、無(wú) 關(guān)。上式為一條件概率。當(dāng)1 =n】，令ii=i ,則此式可以記為：Pij (m)=Px(m + l)=j | x(m) = i)(5) 這就是馬氏鏈的一步轉(zhuǎn)移概率，它表示系統(tǒng)在時(shí)刻m處于狀態(tài)i的條件下，下一步轉(zhuǎn)移到狀態(tài) j的條件概率。一步轉(zhuǎn)移概率PMm)件概率。一步轉(zhuǎn)移概率具有下列性質(zhì)：PltJ(m) 2 0 i,j e EZ PM(m) = 1 i e E把元素具有上面和Q)兩條性質(zhì)的矩陣，稱為隨機(jī)矩陣。由此可見(jiàn)，一步轉(zhuǎn)移矩陣是一個(gè)隨機(jī)矩陣。圖2組合電路現(xiàn)在來(lái)討論如何用馬氏鏈來(lái)對(duì)組合邏輯電路的功率進(jìn)行估算。對(duì)于如圖2所 示的組合電路，當(dāng)輸入向量V1 ,v3，,Vn加在原始輸入端時(shí)在時(shí)刻1

7、,2 n電 路內(nèi)部的任何一個(gè)輸出節(jié)點(diǎn)的邏輯值可能為0也可能為1。這樣，在。延遲 模型條件下，節(jié)點(diǎn)X的值在一個(gè)時(shí)鐘周期內(nèi)最多只變換一次。假設(shè)Xn為一個(gè)隨機(jī)變量，用它來(lái)描述節(jié)點(diǎn)X在任意時(shí)刻n的狀態(tài)。那么 Xn 11 X)的數(shù)學(xué)模型便可以用一步馬氏鏈來(lái)刻畫，它的狀態(tài)空間為0,1,其 行為可以用下面的狀態(tài)矩陣來(lái)描述為Q= |%0 PQ.l IPto PL1Q是一個(gè)隨機(jī)矩陣，矩陣中的每一項(xiàng)HjX表示節(jié)點(diǎn)X從狀態(tài)i到狀態(tài)j的 一步轉(zhuǎn)移概率，它是一個(gè)條件概率，根據(jù)條件概率的定義，節(jié)點(diǎn)的X狀態(tài)轉(zhuǎn)移 概率可以用下式表示px = Pa-=J)nanT=j)() P(xn-l-i) ()在式(6)中，分子的值即p(

8、Xn = j) I(Xn-1 =i)表示節(jié)點(diǎn)X在n時(shí)刻等于j,并 且在時(shí)刻nl等于i的概率。在電路中，如果節(jié)點(diǎn)x在相鄰兩個(gè)時(shí)刻的狀態(tài)不一 樣，在該節(jié)點(diǎn)就會(huì)產(chǎn)生動(dòng)態(tài)功耗。因此，在式(6)中p(Xn = j)|(X_i=i)是我 們所要得到的。在這里將概率p(xn = j)|(Xn-i = i)稱作節(jié)點(diǎn)X的狀態(tài)轉(zhuǎn)換概率 記為R- j o從上面的討論中可以看到，當(dāng)狀態(tài)從0 - 1 ,或者從1 - 0變 化時(shí)電路中便產(chǎn)生動(dòng)態(tài)功耗，這樣節(jié)點(diǎn)X的開(kāi)關(guān)轉(zhuǎn)換概率可以簡(jiǎn)化為(7)E(sw) = 2p(x = 1)(1 -p (x = 1)由上式可以看到，當(dāng)已知節(jié)點(diǎn)的信號(hào)概率之后，就可以計(jì)算該節(jié)點(diǎn)的狀態(tài)轉(zhuǎn) 換概率

9、了。因此，對(duì)于功耗計(jì)算的問(wèn)題轉(zhuǎn)化為求電路中節(jié)點(diǎn)的信號(hào)概率的問(wèn)題。現(xiàn)在研究一個(gè)二輸入與門的例子。圖3所示為一個(gè)二輸入與門及其真值表。圖3二輸入與門及其真值表假設(shè)輸入xl和x2是統(tǒng)計(jì)獨(dú)立的，x為輸出節(jié)點(diǎn)。根據(jù)真值表，我們可以畫出輸出節(jié)點(diǎn)x的狀態(tài)轉(zhuǎn)移圖如圖4所示。圖4二輸入與門狀態(tài)轉(zhuǎn)換圖如果xl = 1的概率為PA , x2 = l的概率為PB ,由于xl和X2統(tǒng)計(jì)獨(dú) 立，因此有：P(x = 1) = P(Xi = 1) n (x3 = 1) = P(X1= l)P(X2 = 1) = PaPb (8) 將上式代入式(7),便可以得到：E (sw) =2p(x=l)(l-p(x=l) = 2PaPb

10、1-PaPb (9 )從式(9)可以看到，如果己知輸入信號(hào)的統(tǒng)計(jì)特性，根據(jù)電路的邏輯功能，便 可以知道該組合電路中輸出節(jié)點(diǎn)的開(kāi)關(guān)轉(zhuǎn)換的統(tǒng)計(jì)特性了，將得到的節(jié)點(diǎn)的狀態(tài) 轉(zhuǎn)換概率代入(2)就可以計(jì)算電路的功耗了。從上面的分析可以看到，在使用馬氏鏈對(duì)功率進(jìn)行分析時(shí)，主要分3步：第 1步，首先確定輸入信號(hào)的統(tǒng)計(jì)特性，以及電路的邏輯功能；第2步就是利用式 (7)計(jì)算電路中輸出節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)換概率：第3步，根據(jù)在第1部分中提到的 功率模型對(duì)功耗進(jìn)行計(jì)算。與基于仿真的動(dòng)態(tài)方法相比，這種方法的計(jì)算速度較 快，不需要利用仿真模塊，可單獨(dú)作為一個(gè)模塊使用。參考文獻(xiàn)：1卜愛(ài)國(guó).基于Markov模型的動(dòng)態(tài)電壓調(diào)節(jié)策略J.計(jì)算機(jī)應(yīng)用研究，2011, 28(10):3750-3752.liii C Y Pedram M. Accurate and efficient power simulation strategy by compacting the input vector setJ. Integration the VIsi Joumal, 1