基于程序段的可重構ｃａｃｈｅ與處理器低能耗算法

摘 要：運用可重構cache和動態電壓縮放技術，為處理器及其cache提出了一種基于程序段的自適應低能耗算法PBLEA（phasebased low energy algorithm）。該算法使用建立在指令工作集簽名基礎上的程序段監測狀態機來判斷程序段是否發生變化，并作出cache容量及CPU電壓和頻率的調整決定。在程序段內，使用容量調整狀態機和通過計算頻率縮放因子β來先后對cache容量及CPU電壓和頻率進行調整。在Simpanalyzer模擬器上完成了該算法的實現。通過對MiBench測試程序集的測試表明：與傳統的cache和CPU相比較，該算法使系統能耗平均節省了49.1%，而平均性能損失為8.7%。

關鍵詞：可重構高速緩沖存儲器；動態電壓縮放；自適應算法；運行程序段；低能耗

中圖分類號：TP303 文獻標志碼：A

文章編號：1001-3695(2008)09-2692-05

Phasebased lowenergy algorithm for reconfigurable cache and processor

PENG Manman，LI Renfa，PENG Fang，WANG Yuming

(School of Computer Communication， Hunan University， Changsha 410082， China)

Abstract:Utilizing the technology of reconfigurable cache and dynamic voltage scaling (DVS)， this paper proposed a phasebased lowenergy algorithm (PBLEA) for cache and processor. The algorithm used a state machine based on instruction working set signature for identifying the change in program and making a decision to adjust cache’s size and processor’s supply voltage and clock frequency. In every runningprogram phase， the algorithm used a state machine for governing cache and determining cache’s size， and setting processor’s voltage and clock frequency by calculating the ratio of the total offchip access time to the total onchip computation time (β). The algorithm has been realized in the Simpanalyzer. By simulating numerous MiBench benchmarks， the results show that the algorithm saves on average 49.1% of total system energy compared with a conventional cache and CPU， then the average performance loss is close to 8.7%.

Key words:reconfigurable cache; dynamic voltage scaling(DVS); selftuning algorithm; runningprogram phase; low energy

在系統結構設計中，能耗是與性能同等重要的首要設計約束。處理器及其cache（高速緩沖存儲器）是計算機系統能耗的主要來源，降低兩者的能耗是低能耗系統設計關注的焦點。動態電壓縮放（DVS）技術，允許CPU在工作時動態地改變其時鐘頻率和供電電壓，能有效地減少處理器的能耗。可重構cache^[1]具有可變的配置參數集，可以在自適應算法的指導下根據運行程序的需求，通過關閉cache閑置未用的部分來調整容量，較大地提高能量效率。既然可重構cache與DVS都能分別有效地降低cache和處理器的能耗，那么，能否結合兩者的特點使系統能耗進一步減少是值得研究的問題。

本文針對可重構cache和處理器電壓提出了一種基于程序段的自適應算法PBLEA。該算法通過監測指令工作集來判定程序段的變化，采用自適應的方法動態準確地配置cache容量以及處理器電壓和頻率，以滿足不同程序段的資源需求。該算法能有效地降低cache和CPU的能耗。

1 PBLEA算法方案

PBLEA必須解決兩個問題：a）如何監測程序運行過程中的行為和性能信息，判斷運行程序段是否變化；b）在程序段內如何對cache容量及處理器電壓和頻率進行動態配置。

1.1 PBLEA算法的程序段監測策略

運行程序可以分為多個程序段，每個段內指令工作集基本保持不變；而不同的程序段具有不同的指令工作集特征。若能準確地判斷指令工作集的變化，則能準確地推斷出運行程序段的變化，有效地減少不必要的重構及其帶來的性能損失^[2]。

工作集簽名最早由Dhodapkar等人^[3]提出。每個簽名包含了在100k指令間隔內的指令工作集信息，其形成過程如圖1所示。指令工作集簽名是一個n位向量，向量每一位的值由程序計數器PC的值右移b位（b＝log2m，m＝ICache塊大小）得到。隨機哈希函數用來選擇向量位地址。若S1和S2代表相鄰間隔的兩個指令工作集簽名，則定義相對簽名距離為

Δ=|S1S2|/|S1+S2|（1）

其中：分子部分為兩個簽名的異或運算；分母部分為兩個簽名的同或運算。若Δ=1，則表明兩個簽名完全不同；而Δ=0，則表明兩個簽名完全相同。為了準確地判斷運行程序段的變化，定義了一個相對簽名距離閾值Δth。如果Δ≥Δth，則表明程序的運行段發生了變化；否則表明程序段沒有改變。但一個合適的閾值可能隨著運行程序段的不同而變化，因此，該閾值將隨程序運行而自調整。由于cache的資源需求和處理器的工作負荷在同一程序段內均不作明顯變化^[3，4]，PBLEA算法以程序段為單位對cache容量和處理器電壓進行動態調整。

PBLEA算法使用程序段監測狀態機來判斷運行程序段是否發生轉變。如圖2所示，該狀態機有工作集穩定、工作集不穩定、配置調整和閾值調整四種狀態。在工作集穩定態下，程序的指令工作集特征保持不變。工作集不穩定態由一系列指令工作集特征不相似的間隔組成。在該狀態機中，判定程序段是否發生變化的操作是在每一固定間隔末進行的，所以不可避免在程序段的自然邊界與間隔邊界之間存在不匹配情況，工作集不穩態正是這種不匹配情況的集中表現。在配置調整態下，該狀態機先后對cache容量及CPU的電壓和頻率進行調整。由于不同程序的差別閾值是不同的，在閾值調整態下，程序段監測狀態機對判定程序段是否變化的差別閾值進行調整。

1.2 PBLEA算法的動態配置策略

進入程序段后，PBLEA算法首先使用容量調整狀態機對cache容量進行調整。在找到最優cache容量后，再統計cache容量固定后的CPU性能信息，從而對CPU的電壓和頻率進行調整。

條件A：如果Δ＜Δth，則表明運行程序段未作改變，PBLEA保持在工作集穩定態，并監測指令工作集的變化。

條件B：如果Δ＜Δth，且cache的缺失數量持續大于一定的閾值，則表明Δth過大。PBLEA進入閾值調整態，對Δth進行調整。

條件C：如果Δth被改變，則PBLEA進入工作集穩定態 。 

條件D：如果Δ≥Δth，則表明運行程序段開始發生改變，PBLEA進入工作集不穩定態，并監測指令工作集的變化。

條件E：如果Δ≥Δth，且PBLEA保持在工作集不穩態的持續間隔數小于5，則PBLEA算法繼續保持在工作集不穩定態，并監測指令工作集的變化。

條件F：如果Δ≥Δth，且PBLEA保持在工作集不穩態的持續間隔等于5，則表明Δth值過小，PBLEA進入閾值調整態，對Δth進行調整。

條件G：如果Δ＜Δth，則表明程序已經進入另一運行程序段。PBLEA進入配置調整態，對目前的cache容量和CPU頻率進行調整。

條件H：如果Δ≥Δth，則表明程序段可能發生變化，PBLEA進入工作集不穩定態。

條件I：如果Δ＜Δth，且未找到該程序段的cache和CPU優化配置，則PBLEA繼續尋找優化配置。

條件J：如果Δ＜Δth，且已找到該程序段的cache和CPU優化配置，則PBLEA進入工作集穩定態。

1.2.1 Cache容量調整策略

為了在程序段變化后，根據程序段的動態需求找到更優的cache配置，PBLEA使用了如圖3所示的容量調整狀態機。

該狀態機有正常、小容量、大容量和容量重構四種狀態。正常態下，cache容量保持不變；小容量態下，PBLEA將對目前容量的cache與更小容量的cache進行性能比較(若目前cache的容量不為最小，則定義更小cache的容量為當前容量的一半；否則轉到正常態)，并決定是否對容量進行調整。大容量態下，PBLEA將對目前容量的cache與更大容量的cache進行性能比較(若目前cache的容量不為最大，則定義更大cache具有比目前相聯度多1的容量；否則轉到正常態)，并決定是否對容量進行調整。容量重構態下，PBLEA算法將通過路關閉寄存器對目前的cache容量進行調整。其參數配置如下：

a）訪問計數器accessnum(AN)。分為IAN和DAN兩個計數器，分別用來統計ICache和DCache在不同狀態下的訪問次數。

b）訪問邊界寄存器accessbound(AB)。分為IAB和DAB兩個寄存器，分別用來決定ICache和DCache在不同狀態下的最大訪問次數；如果超出，則PBLEA進入另一狀態。

c）連續失效計數器consecutivemissnum (CMN)。分為ICMN和DCMN，分別用來統計ICache和DCache在正常態下的連續失效次數。

d）連續失效邊界寄存器consecutivemissbound (CMB)。分為ICMB和DCMB，分別用來決定ICache和DCache在正常態下的最大連續失效次數。一定量的連續失效表明目前容量的cache不能滿足運行程序段的需求，需要對容量進行調整。

e）最近最少cache路命中計數器LRUwayhitnum (LWHN)。分ILWHN和DLWHN，分別用來統計ICache和DCache在小容量態下，最近最少兩路的命中次數。

f）最近最少cache路命中邊界寄存器LRUwayhit bound(LWHB)。分為ILWHB和DLWHB，分別用來決定ICache和DCache在小容量態下，最近最少訪問的兩路的最大命中次數。一定量的LRU路命中，表明如果關閉這兩路，將會造成cache失效率的明顯增加和性能的下降。

條件A：如果 IAN＜IAB且ICMN

條件B：如果 IAN≥IAB且ICMN

條件C：如果IAN＜IAB且ILWHN

條件D：如果ILWHN≥ILWHB，表明減少容量后會造成ICache性能的明顯下降。PBSTA清空IAN和ILWHN，返回正常態。

條件E：如果 IAN≥IAB且ILWHN < ILWHB，則表明目前的ICache容量超出程序的需求。PBSTA清空IAN和ILWHN后，進入容量重構態，減小ICache的容量。

條件F：如果cache容量發生變化，則PBSTA進入正常態。

條件G：如果ICMN≥ICMB，則表明目前容量的ICache可能不能夠滿足程序的需求。PBSTA清空IAN和ICMN，進入大容量態。

條件H：如果IAN＜IAB且IEWHN＜IEWHB，則PBSTA保持在大容量態。

條件I：如果IEWHN≥IEWHB，則表明目前的ICache容量不能滿足程序的需求。PBSTA清空IAN和IEWHN后，進入容量重構態，增大ICache的容量。

條件J：如果 IAN≥IAB且IEWHN＜IEWHB，則表明增大ICache的容量不會帶來性能的明顯提升。PBSTA清空IAN和IEWHN，返回正常態。

g）額外cache路命中計數器extrawayhitnum (EWHN)。分為IEWHN和DEWHN，分別統計ICache和DCache在大容量態下，將要打開的那一路的命中次數。

h）額外cache路命中邊界寄存器extrawayhitbound(EWHB)。分為IEWHB和DEWHB，分別用來決定ICache或DCache在大容量態下，額外cache路的最大命中次數。一定量的額外cache路命中，表明增加那一路容量后會帶來cache性能的提升；否則只會帶來不必要的能耗。

1.2.2 CPU電壓和頻率調整策略

文獻[4，5]的DVS算法使用了cache缺失事件來觸發處理器的電壓縮放，即在片外空轉周期內通過降低CPU電壓和頻率來節省能耗。文獻[6]通過實驗驗證了CPU的占用需求在程序的運行過程中具有階段性變化的特征。如果有一算法能以運行程序段為單位對CPU電壓和頻率進行變換，那么它就能在更準確的時間區域里使CPU運行在低能耗狀態。

程序運行時會經歷多個程序段，每個程序段的任務量以周期(cycles)為基準可分為三個不同區域：

四個要素決定^[7]：

a）程序段所需執行的指令數量n（在PBLEA中，n=100k）。

b）程序段所需的內存訪問數量m。

c）程序段中每條指令所需執行的周期數CPIionchip（0≤i≤n）。

d）程序段中每次內存訪問所占用的內存訪問周期數CAPjoffchip（0≤j

對于不同的程序段，TonchipR和ToffchipR的比例關系往往也不同。如果降低CPU電壓和頻率使系統性能損失很大，則表明該程序段具有

為了計算進入程序段后前兩個間隔的m、CPIavgonchip和CPAavgoffchip，需要采取如下監測策略：

a）監測前兩個間隔內CPU執行過程的時鐘周期數。PBLEA使用CPU周期計數器CCN，統計執行過程中的CPU周期數。當程序進入該程序段的第三個間隔，PBLEA清空CCN。b）監測前兩個間隔內的內存訪問周期數。PBLEA使用內存周期計數器MCN，統計執行過程中的內存訪問周期數。當進入該程序段的第三個間隔，PBLEA算法清空MCN。

c）監測前兩個間隔內的L2Cache缺失數。由于每次L2Cache缺失都觸發了內存訪問事件，PBLEA使用L2Cache缺失計數器LMN，統計執行過程中的內存訪問數量。當進入該程序段的第三個間隔，PBLEA清空LMN。

有了上述監測策略，當程序段第二個固定間隔結束時，LMN中的值為前兩個間隔的內存訪問數m；CCN中的值為前兩個間隔CPU執行過程的周期數，它與200k相除即可得到前兩個間隔的CPIavgonchip；MCN中的值為前兩個間隔的內存周期數，它與m相除即可得到前兩個間隔的CPAavgoffchip。然后，根據式(7)(10)，即可求得不同程序段前兩個間隔的TonchipR、ToffchipR值和它們之間的比例關系。根據程序段內不同間隔的特征相似性，可以設定前兩個間隔TonchipR與ToffchipR的比例關系即為該程序段的CPU頻率變化因子βR。

下面將解決在程序段內如何改變CPU電壓和頻率的問題。由式(11)可知，CPU的理論優化頻率foptimalR不僅取決于頻率變化因子βR，而且與程序段允許的最大性能損失PFlossR和CPU初始頻率fcpu有很大關系。

首先要確定PFlossR和fcpu。本文采用預先設定的方法，在程序運行前設定PBLEA的PFlossR（該值可隨程序的運行而變化，但需增加額外的監測措施，還需作進一步的研究）。而程序段前兩個間隔內，CPU的頻率不作變化，因此很容易求得fcpu。

接著需要確定CPU電壓和頻率的變化范圍。理想中的支持DVS技術的處理器能夠在線性條件下變換頻率。但目前支持DVS技術的處理器通常只支持離散頻率模式，因此，本文將處理器頻率和電壓分為五個離散級別：F1(333 MHz，0.91 V)、F2(400 MHz，0.99 V)、F3(466 MHz，1.05 V)、F4(533 MHz，1.12 V)和F5(600 MHz，1.19 V)。內存訪問時鐘頻率不隨CPU頻率變化，固定為100 MHz。

理想的DVS技術能夠瞬間改變CPU的電壓和頻率。但在實際應用中，CPU電壓和頻率的改變往往需要一定的系統負擔。文獻[8]中指出，當處理器的頻率處于1 GHz時，頻率和電壓切換操作可以在12 ns以內完成。因此本文假設切換電壓和頻率帶來的系統延遲為20個CPU時鐘周期。

最后，PBLEA使用下列步驟確定程序段的CPU優化頻率foperR，并完成電壓和頻率的變化操作：

a）當程序段運行到第二個間隔的末尾(第200k條指令)，停止預取新的指令。

d）將CPU的電壓和頻率切換為foperR所處的電壓和頻率級別，并等待固定的時間間隔。這段間隔包括計算優化頻率帶來的延遲和電壓切換帶來的延遲，本文假定它為200個CPU時鐘周期。

e）開始預取指令，并以新的CPU電壓和頻率進入下個固定間隔。

2 實驗與結果

本文使用Simpanalyzer^[9]模擬器和Mibench^[10]測試程序集來仿真和模型化通用處理器及其cache的性能。處理器采用Simoutorder結構，并在此基礎上加入了PBLEA算法和DVS功能，修改了其cache結構，使之具有可重構能力。表1為PBLEA算法的處理器和存儲器參數，表2為PBLEA算法參數。

表1 處理器及存儲器參數

參數取值處理器工藝0.18 μm

處理器頻率F1:333 MHz、F2:400 MHz、F3:466 MHz、F4:533 MHz、F5:600 MHz

處理器電壓F1:0.91 V，F2:0.99 V，F3:1.05 V，F4:1.12 V，F5:1.19 V

預取和提交寬度 4條指令

發射和解碼寬度 4條指令

L1Cache容量8k 1路、16k 2路、24k 3路、32k 4路

L1Cache塊大小32 Byte

L1Cache延遲 1個時鐘周期

L2Cache容量128 k 1路、256k 2路、384k 3路、512k 4路

L2Cache塊大小64 Byte

L2Cache延遲 6個時鐘周期

內存總線頻率100 MHz

內存訪問延遲100內存周期

表2 PBLEA算法參數

參數取值

工作集簽名向量1 024位

工作集簽名取樣間隔100k指令周期

相對簽名距離閾值范圍 0.1~0.4

連續缺失邊界范圍 ICache、DCache: 1~6

最近最少路命中邊界范圍ICache、DCache:1~4

額外路命中邊界范圍ICache、DCache:1~4

訪問邊界范圍 ICache， DCache: 31 072~131 072

為了驗證PBLEA算法的能耗優化效果，本文將PBLEA算法與只采用動態cache重構（phasebased cache reconfiguration algorithm，PBCRA）和只采用DVS技術（phasebased DVS algorithm，PBDVSA）的兩種算法進行了能耗比較。

如圖4所示，以未采用重構技術的cache（L1Cache：32K4Way、L2Cache：512K4Way）能耗為基準，采用PBCRA算法的可重構cache平均節省了34.2%的能耗，范圍從28%到43%；以未采用DVS技術的CPU（600MHz、1.19V）能耗為基準，采用PBDVSA算法的處理器平均節省了27.1%的能耗，范圍從17.3%到48.1%；而以未采用可重構cache和DVS技術的處理器為基準，采用PBLEA算法的cache與處理器平均節省了49.1%的能耗，范圍從38.1%到61.2%。實驗結果表明，PBLEA算法能夠合理結合PBCRA算法與PBDVSA算法的特點，做到兩種低能耗技術協同工作。

評價性能的主要指標是由配置重構所帶來的額外時鐘延遲的數量。如圖5所示，以未采用可重構cache和動態電壓縮放技術的處理器為基準，采用PBCRA算法的cache平均性能損失為3.9%，范圍從3.1%到5.6%；采用PBDVSA算法的處理器平均性能損失為6.1%，范圍從4.1%到7.2%；而采用PBLEA算法的cache與處理器的平均性能損失為8.7%，范圍從7%到11.9%。實驗結果表明，由于PBLEA算法是PBCRA算法與PBDVSA算法的線性疊加，需要同時指導cache容量和處理器電壓的動態變化，有更高的性能損失。但PBLEA算法更有效地降低了系統的能耗，具有更高的性能能耗比。

3 結束語

本文為可重構cache和處理器電壓提出了一種基于程序段的自適應算法PBLEA。該算法結合動態cache重構和DVS技術的優勢，使用程序段監測狀態機來判斷運行程序段是否發生變化，以程序段為基礎對cache容量與CPU電壓和頻率進行動態調整。實驗表明，PBLEA算法在保證性能的前提下，有效地節省了cache和CPU的能耗。

參考文獻：

［1］ZHANG Chuanjun，VALID F，LUSECKY R.A selftuning cache architecture for embedded systems[J].ACM Trans on Embedded Computing System，2004，3(2): 407-425.

[2]BALASUBRAMONIAN R， ALBONESI D.Memory hierarchy reconfiguration for energy and performance in general purpose architecture[C]//Proc of the 33rd International Symposium on Microarchitecture.New York:ACM Press，2000:245-257.

[3]DHODAPKAR A S， SMITH J E. Managing multiconfiguration hardware via dynamic working set analysis[C]//Proc of the 29th Annual International Symposium on Computer Architecture.New York:ACM Press，2002:233-244.

[4]LI Hai，CHER C Y，VIJAYKUMAR T M，et al.VSV:L2MissDriven variable supplyvoltage scaling for low power[C]//Proc of the 36th International Symposium on Microarchitecture.New York:ACM Press，2003:19-29.

[5]MARCULESCU D.On the use of mircroarchitecturedriven dynamic voltage scaling[C]//Proc of Workshop on ComplexityEffective Design.2000.

[6]RUSU C，ABOUGHAZALEH N，FERREIRA A，et al.Intergrated CPU and L2 cache fequency/voltage saling using spervised learning[C]//Proc of HiPEAC Workshop on Satistical and Machine Learning Approaches Applied to Architectures and Compilation.2007:41-50.

[7]GOVIL K，CHAN E，WASSERMAN H.Comparing algorithms for dynamic speedsetting of a lowpower CPU[C]//Proc of the 1st ACM International Conference on Mobile Computing and Networking.New York:ACM Press，1995:13-25.

[8]HENNESSY J，PATTERSON D.Computer architecture a quantitative approach[M].San Francisco: Morgan Kaufmann Publishers，1996.

[9]KIN N，AUSTIN T，MUDGE T.Challenges for architectural level power modeling[M].Boston:Kluwer Academic Publishers，2001.

[10]GUTHAUS M R， RINGENBERG J S. Mibench:a free commercially representative embedded benchmark suite[C]//Proc of the 4th IEEE International Workshop on Workload Characterization.2001:314.