高層綜合中面向運(yùn)算器電源門控技術(shù)的低能耗調(diào)度算法

姚蔓婷， 邱 源， 柳宜川， 袁偉娜， 汪 楠

（1. 華東理工大學(xué)信息科學(xué)與工程學(xué)院，上海 200237；2. 上海航天計(jì)算機(jī)技術(shù)研究所，上海 200233）

在摩爾定律的引領(lǐng)下，集成電路的復(fù)雜度成倍地提高，工藝節(jié)點(diǎn)快速進(jìn)步至納米級，芯片設(shè)計(jì)的復(fù)雜度大幅增加，高性能、低功耗架構(gòu)逐漸成為主流設(shè)計(jì)要求。尤其是工藝發(fā)展至65 nm 及以下時，漏電功耗開始迅速增大[1]，加之便攜及移動設(shè)備的廣泛應(yīng)用，使得漏電功耗成為集成電路中日趨重要的問題[2]。

電源門控技術(shù)是工業(yè)界常用的一項(xiàng)低功耗技術(shù)，它通過關(guān)斷模塊的電源來減少該模塊的漏電功耗。電源門控技術(shù)首先需要將設(shè)計(jì)分為不同的電壓域，基于電壓域的門控稱為粗調(diào)電源門控。當(dāng)門控模塊需要關(guān)斷時，該模塊的狀態(tài)將被保存至狀態(tài)保持寄存器（Retention registers）中以便再次喚醒該模塊。王磊磊等[3]通過求解一組線性規(guī)劃獲得最佳接入時間序列來優(yōu)化電源門控技術(shù)中的電壓噪聲問題。Sumanta[4]嘗試在模塊切換睡眠模式與活躍模式的過程中重新調(diào)度電源門控指令來減少因?yàn)殡娫撮T控帶來的電流涌入問題。Mohankumar 等[5]針對因電源門控技術(shù)帶來的芯片面積增加的問題，提出了合并觸發(fā)器來減少門控單元，進(jìn)而降低面積的增加。Sathanur 等[6]在算法中引入“簇”的概念，并在電路面積及處理速度的約束下，較大幅度地減少了漏電功耗。Kahng 等[7]設(shè)計(jì)了適用于電源門控設(shè)計(jì)的狀態(tài)保持寄存器，使得電路在工作狀態(tài)下?lián)碛休^低的漏電功耗及較小的電路面積。Sinkar 等[8]將溫度對電路造成的影響納入考慮范疇，使得電路在減少10%漏電功耗的同時，還減少了3.7%的動態(tài)功耗。Reimann等[9]將電源門控技術(shù)在工業(yè)設(shè)計(jì)生產(chǎn)中所面臨的諸多因素納入考慮范圍，并在處理速度約束下采用基于拉格朗日松弛的方法，有效地降低了電路的漏電功耗。

然而，隨著電路工藝節(jié)點(diǎn)技術(shù)的快速發(fā)展，漏電功耗在總功耗中所占的比重越來越大。因此，為了進(jìn)一步減少電路的漏電功耗，一種運(yùn)算器級別的細(xì)粒度電源門控技術(shù)成為了近期研究的熱點(diǎn)。該技術(shù)根據(jù)各個運(yùn)算器的工作時間，獨(dú)立地開關(guān)各個運(yùn)算器的電源電壓。Rele 等[10]通過分析各個運(yùn)算器可能的空閑時段來確定運(yùn)算器電源的開關(guān)時間。Hu 等[11]從電路結(jié)構(gòu)上分析了運(yùn)算器電源門控技術(shù)所能獲得的漏電功耗優(yōu)化結(jié)果。Henry 等[12]設(shè)計(jì)了NEMS 電源門控開關(guān)，并建立了采用該電源門控開關(guān)電路的能耗模型。Yeh 等[13]提出了一種有效的喚醒策略，可最小化開關(guān)運(yùn)算器電源所帶來的工作時延的增加。Kannan 等[14]通過設(shè)置運(yùn)算器漏電傳感器，設(shè)計(jì)了一種基于溫度以及處理進(jìn)程的運(yùn)算器電源門控方法。此外，諸多研究者[15-16]還嘗試通過軟件代碼分析來計(jì)算運(yùn)算器電源的開關(guān)時間，在保證系統(tǒng)性能的同時減少了硬件電路的漏電功耗。

雖然運(yùn)算器電源門控技術(shù)已經(jīng)成為近期的研究熱點(diǎn)，但許多研究者開始嘗試從多個角度來減少運(yùn)算器的漏電能耗。由于在調(diào)度過程中無法確定操作的調(diào)度及綁定結(jié)果，因此目前鮮有人在高層綜合中對運(yùn)算器電源門控技術(shù)進(jìn)行研究。由于高層綜合中存在著較多的漏電功耗優(yōu)化可能性，并且調(diào)度是高層綜合中最為重要的任務(wù)，因此通過合理的調(diào)度能夠優(yōu)化后期各個運(yùn)算器的空閑時段，從而大幅減少電路的漏電能耗。本文在高層綜合的調(diào)度中對采用運(yùn)算器電源門控技術(shù)的ASIC 電路漏電能耗進(jìn)行分析，提出了一種啟發(fā)式算法以實(shí)現(xiàn)電路在工作時延以及電路面積不變的前提下優(yōu)化漏電能耗。

1 電源門控運(yùn)算器的能耗分析與優(yōu)化問題

電源門控電路如圖1 所示。由輸入信號、組合邏輯單元、狀態(tài)保存觸發(fā)器、隔離電路、輸出信號組成。 PMU（ Power-gating Manager Unit） 單 元 產(chǎn) 生Sleep 信號給腳門控單元來控制Vssv。

圖1 電源門控電路示意圖Fig. 1 Schematic diagram of power gating circuit

1.1 電源門控運(yùn)算器的能耗分析

本文所討論的電路均采用頭門控開關(guān)（Header device），對于采用腳門控開關(guān)的電源門控電路，本文的結(jié)論同樣適用。圖2 示出了開關(guān)運(yùn)算器電源時的能耗-時間關(guān)系。

在t=t1時刻，控制電路決定將該運(yùn)算器的電源關(guān)閉，“Sleep”信號被使能并于t=t2時刻送至頭門控開關(guān)，該過程所需的額外能耗為Eoh1。當(dāng)頭門控開關(guān)接收到“Sleep”信號時，電路的虛Vdd(標(biāo)記為Vddv)開始降低，并于t=t4時刻完全放電。

圖2 開關(guān)運(yùn)算器電源時的能耗分析Fig. 2 Energy consumption analysis of power gating a functional unit

設(shè)運(yùn)算器需要在t=t5時刻開始喚醒，“Sleep”信號也將被禁能，相應(yīng)會產(chǎn)生的額外能耗為Eoh2。在t=t6時，頭門控開關(guān)已完全打開，Vddv開始充電，并在t=t7時刻完成充電。在平衡點(diǎn)(Break even point)t=t3時，通過降低Vddv減少的運(yùn)算器漏電能耗等同于開關(guān)頭門控開關(guān)時的額外功耗(Eoh=Eoh1+Eoh2)。平衡時長(Break even cycle count)tbe=t3-t1，表示從關(guān)閉電源到平衡點(diǎn)所需的時長；喚醒時長tcu=t7-t6為Vddv的充電時間。運(yùn)算器需要提前tcu周期開始對Vddv進(jìn)行充電，以便該運(yùn)算器能夠按時進(jìn)行操作的運(yùn)算。所以只有當(dāng)運(yùn)算器的空閑間隙的長度tidle＞tbe+tcu時，在該空閑時間段內(nèi)關(guān)閉該運(yùn)算器的電源電壓才能減少漏電能耗。

令運(yùn)算器的電源門控收益均衡時間為toh=tbe+tcu。當(dāng)tidle=toh時，開關(guān)該運(yùn)算器既不會減少也不會增加運(yùn)算器的能耗；當(dāng)tidle＜toh時，開關(guān)該運(yùn)算器會產(chǎn)生額外的能耗；而當(dāng)tidle＞toh時，開關(guān)該運(yùn)算器能夠減少能耗。因此能夠通過關(guān)閉電源獲得電源門控收益，收益量與tidle-toh成正比。

設(shè)IIi表示第i個空閑間隙，根據(jù)空閑間隙所處的位置，將其分為以下3 類：（1）運(yùn)算器上相鄰兩個操作之間的空閑間隙；（2）在程序開始之前及第一個操作之間的空閑間隙；（3）在最后一個操作及程序結(jié)束之間的空閑間隙。如果空閑間隙的長度為0，同樣認(rèn)為該空閑間隙是存在的，因此空閑間隙的數(shù)量等于操作的數(shù)量與運(yùn)算器數(shù)量之和。

操作類型為k的運(yùn)算器中空閑間隙內(nèi)的收益時長表示為，定義如下：

則該運(yùn)算器減少的漏電能耗為ERk，其計(jì)算方法如下：

對于所有操作類型為k的運(yùn)算器，其所有的空閑間隙的總收益時長表示為 c ycpg，因此，開關(guān)該類型運(yùn)算器所能減少的漏電能耗為ER。

1.2 電源門控運(yùn)算器的問題描述

為了直觀地展示高層綜合中的調(diào)度過程對電路漏電能耗的影響，圖3 示出了一個數(shù)據(jù)流程圖（Data Flow Graph, DFG）（圖3（a）），并針對此數(shù)據(jù)流程圖給出了2 種不同的調(diào)度及綁定結(jié)果（圖3（b），3（c））。

圖3 中所需的ALU（Arithmetic and Logic Unit）數(shù)量均為1，乘法器數(shù)量均為3，時間約束為12 個時鐘周期，其中乘法器的收益均衡時間為=8 周期，ALU 的收益均衡時間=3 周期。圖3(b)示出的是先采用List scheduling 算法進(jìn)行調(diào)度再使用Left edge 進(jìn)行綁定的高層綜合結(jié)果，其對應(yīng)的=2周期。而在圖3(c)中所示的例子中，=6 周期，因此該結(jié)果將獲得更多的漏電能耗優(yōu)化。

問題的輸入：DFG，時間約束tc，資源約束；

優(yōu)化目標(biāo)：對每個操作進(jìn)行調(diào)度，從而最大限度地優(yōu)化運(yùn)算器的漏電能耗(Energy reduction)。

目標(biāo)函數(shù)可以表述為

2 基于空閑間隙的漏電能耗優(yōu)化算法

2.1 空閑間隙分析

運(yùn)算器中空閑間隙的長度直接決定了運(yùn)算器所能優(yōu)化的能耗，因此需要首先分析運(yùn)算器中各個空閑間隙的長度。

k類運(yùn)算器中所有空閑間隙的總長度可以用如下公式表示：

根據(jù)空閑間隙的長度，將空閑間隙分為兩類：（1）長空閑間隙IIl，即IIl＞toh；（2）短空閑間隙IIs，IIs≤toh。設(shè)長空閑間隙的數(shù)量為 α ，短空閑間隙的數(shù)量為 β ，則有 α +β=+nk。式（2）顯示，最小化運(yùn)算器的漏電能耗等同于最大化，而由式（1）可得:

圖3 調(diào)度結(jié)果對電源能耗的影響Fig. 3 Influence of scheduling results on power consumption

則所有k類型運(yùn)算器上的空閑間隙的懲罰時長之和為 c ost_cyck，

因此，最小化漏電能耗問題就可以轉(zhuǎn)化為最小化所有運(yùn)算器上空閑間隙內(nèi)懲罰時長之和的問題。

2.2 基于空閑間隙的調(diào)度算法

在進(jìn)行調(diào)度前，需要對所有的操作分別進(jìn)行資源約束下的ASAP (As-Soon-As-Possible)調(diào)度以及ALAP (As-Late-As-Possible)調(diào)度以確定各個操作在可調(diào)度空間（Mobility）。操作vi的可調(diào)度空間表示為M(vi)=[Ms(vi),Me(vi)] ，其 中Ms(vi) 表 示調(diào) 度 開始 時刻；Me(vi) 表示調(diào)度結(jié)束時刻。

只有當(dāng)兩個操作能夠被綁定至同一個運(yùn)算器上，它們之間才可能存在空閑間隙。能夠被綁定至同一運(yùn)算器的兩個操作稱為操作間相互兼容，本文將根據(jù)操作的可調(diào)度空間來判斷兩個操作是否兼容。操作vi與vj兼容，則它們的操作類型相同，并且M(vi)∪M(vj)≥d(vi)+d(vj) 。操作vi的兼容集C(vi)為所有與vi兼容的操作構(gòu)成的集合。

在實(shí)際調(diào)度中，由于操作在其可調(diào)度空間中存在多個可能的調(diào)度結(jié)果，因此需要首先計(jì)算出操作之間空閑間隙的長度?，F(xiàn)有操作vi與vj，并且vj∈C(vi) ，則操作vi與vj之間的空閑間隙長度表示為IIi,j，其計(jì)算方法如下：

IIi,j中無法獲得電源門控收益的時長為IIno_pg_i,j，其計(jì)算方法為

本文算法步驟如下：

輸出：操作的調(diào)度方案

在調(diào)度過程中，每個操作的不同調(diào)度結(jié)果都會改變DFG 中其他操作的調(diào)度空間，從而直接影響著操作的調(diào)度結(jié)果以及綁定結(jié)果，因此無法在調(diào)度的過程中確定各個運(yùn)算器的工作以及休眠時間。而針對運(yùn)算器休眠時長進(jìn)行功耗優(yōu)化的電源門控技術(shù)也無法確定電源的開關(guān)時間，所以無法直接在高層綜合中對采用細(xì)粒度電源門控技術(shù)的能耗優(yōu)化結(jié)果進(jìn)行評估。針對此，本文通過將能耗優(yōu)化問題進(jìn)行規(guī)約成為求解最小懲罰時長的問題，并采用基于貪婪算法的調(diào)度算法實(shí)現(xiàn)問題的快速準(zhǔn)確求解。

本文提出的基于貪心策略的啟發(fā)式算法，每次針對未被調(diào)度的操作遍歷其所有可能的調(diào)度方法，計(jì)算懲罰時長，選取當(dāng)前狀態(tài)下最優(yōu)解，直至所有操作調(diào)度完成。本文算法的時間復(fù)雜度為O(n2)，能夠?qū)FG 實(shí)現(xiàn)快速的計(jì)算，得到近似最優(yōu)解。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)配置

為驗(yàn)證本文算法的有效性，實(shí)驗(yàn)中對6 個數(shù)據(jù)流程圖進(jìn)行了操作調(diào)度，這些流程圖有些是由已有算法抽象而得(ar, ellip, mpeg, fft), 有些則是隨機(jī)生成的(ran0，ran1)。為了簡化實(shí)驗(yàn)，只選擇了ALU 以及乘法器這兩種運(yùn)算器進(jìn)行實(shí)驗(yàn)，其單位時鐘周期內(nèi)的漏電能耗是采用Synopsys Design Compiler，并利用65 nm standard cell library 對32 bit 的ALU 以及乘法器進(jìn)行綜合仿真得到的。各類型運(yùn)算器的漏電能耗仿真結(jié)果如表1 所示。其中LEcyc表示運(yùn)算器單位時鐘周期內(nèi)的漏電能耗，LEpg_cyc表示使用電源門控后一個周期內(nèi)運(yùn)算器漏電能耗。Delay 表示運(yùn)算器的延遲周期數(shù)。

由于高層綜合中操作的調(diào)度及綁定結(jié)果無法確定，所以鮮有研究者在高層綜合中對運(yùn)算器電源門控技術(shù)進(jìn)行研究，而大多都集中在邏輯綜合及版圖綜合中。因此，為了驗(yàn)證本文算法在優(yōu)化能耗問題上的性能，選取了在高層綜合中經(jīng)典的操作調(diào)度算法-力驅(qū)動調(diào)度算法（Force-Directed Scheduling，F(xiàn)DS）進(jìn)行能耗優(yōu)化結(jié)果的對比。同時考慮到溫度對運(yùn)算器的均衡時間toh會產(chǎn)生較大影響，因此本實(shí)驗(yàn)將測試兩組不同的運(yùn)算器均衡時間：(1)=3 周期，=8 周期；(2)=5 周期，=12 周期。此外，由于不同的硬件資源約束同樣會對調(diào)度的結(jié)果產(chǎn)生影響，因此還針對每組數(shù)據(jù)流程圖測試兩組不同的資源約束。

表1 運(yùn)算器漏電能耗仿真結(jié)果Table 1 Simulation results of leakage energy consumption of functional units

3.2 實(shí)驗(yàn)結(jié)果

當(dāng)運(yùn)算器的均衡時間設(shè)置為=3 周期、=8周期時，實(shí)驗(yàn)結(jié)果如表2 所示。其中tc為電路的性能約束，本文將tc設(shè)置為數(shù)據(jù)流程圖在相應(yīng)的資源約束下所需的最小調(diào)度時長；Rc表示ALU 和乘法器兩種不同的資源約束；TLE 表示未對運(yùn)算器進(jìn)行電源門控時總的漏電能耗；ER表示使用電源門控后兩種算法降低的漏電能耗；Ratio 表示降低的漏電能耗占總漏電能耗的比率。實(shí)驗(yàn)結(jié)果顯示，采用傳統(tǒng)的力驅(qū)動調(diào)度算法所得的調(diào)度結(jié)果僅能優(yōu)化27.4%的能耗，而采用本文算法，則能夠優(yōu)化30.8%的能耗。

當(dāng)運(yùn)算器的均衡時間設(shè)置為=5 周期、=12 周期時，相應(yīng)的優(yōu)化結(jié)果如表3 所示。該結(jié)果顯示，采用FDS 算法進(jìn)行面向細(xì)粒度的電源門控技術(shù)的調(diào)度時，可以減少19.5%的漏電能耗；而采用本文算法能夠進(jìn)一步減少漏電能耗至25.6%。

表2 =3 時鐘周期，=8 時鐘周期時的能耗優(yōu)化結(jié)果Table 2 Optimation results of leakage energy reduction when=3 cycle, =8 cycle

表2 =3 時鐘周期，=8 時鐘周期時的能耗優(yōu)化結(jié)果Table 2 Optimation results of leakage energy reduction when=3 cycle, =8 cycle

DFG Rc+,* tc TLE/fJ Ours FDS ER/fJ Ratio/% ER/fJ Ratio/%ar (1,1)(2,2)34 19 1 023 1 144 16 31 1.6 2.7 0 22 0 1.9 ellip (1,1)(2,1)28 24 843 746 77 52 9.1 7.0 77 26 9.1 3.4 mpeg (1,1)(2,1)49 38 1 475 1 288 591 358 40.1 27.8 591 334 40.1 25.9 fft (1,1)(2,2)106 57 3 191 3 431 2 134 1 762 66.9 51.4 1 866 1 493 58.5 43.5 ran0 (1,1)(2,2)74 38 2 227 2 288 728 765 32.7 33.4 617 676 27.7 29.6 ran1 (1,1)(2,2)137 69 4 124 4 154 1 957 2 053 47.5 49.4 1 810 1 893 43.9 45.6 avg. 30.8 27.4

表3 =5 時鐘周期， =12 時鐘周期時的能耗優(yōu)化結(jié)果Table 3 Optimation results of leakage energy reduction when=5 cycle, =12 cycle

表3 =5 時鐘周期， =12 時鐘周期時的能耗優(yōu)化結(jié)果Table 3 Optimation results of leakage energy reduction when=5 cycle, =12 cycle

DFG Rc+,* tc TLE/fJ Ours FDS ER/fJ Ratio/% ER/fJ Ratio/%ar (1,1)(2,2)34 19 1 023 1 144 4 17 0.4 1.5 00 00 ellip (1,1)(2,1)28 24 843 746 53 15 6.3 2.0 26 0 3.1 0 mpeg (1,1)(2,1)49 38 1 475 1 288 437 248 29.6 19.3 437 231 29.6 18.0 fft (1,1)(2,2)106 57 3 191 3 431 1965 1 537 61.6 44.8 1 496 1 165 46.9 33.4 ran0 (1,1)(2,2)74 38 2 227 2 288 576 732 25.9 32.0 437 463 19.6 20.2 ran1 (1,1)(2,2)137 69 4 124 4 154 1 738 1 749 42.1 42.1 1 373 1 259 33.3 30.3 avg. 25.6 19.5

4 結(jié)束語

電源門控技術(shù)能夠有效地減少電路的漏電能耗，本文算法通過對操作進(jìn)行合理的調(diào)度來最小化運(yùn)算器開關(guān)的懲罰時長從而對電路的漏電能耗進(jìn)行優(yōu)化。首先將能耗優(yōu)化問題轉(zhuǎn)化成為調(diào)度的空閑間隙問題，隨后對不同調(diào)度結(jié)果下的懲罰間隔時長進(jìn)行評估，并選擇最小的懲罰間隔進(jìn)行調(diào)度，最后實(shí)現(xiàn)電路的能耗優(yōu)化。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的有效性，并表明該算法可較好地應(yīng)用于星載平臺的低功耗電路設(shè)備的設(shè)計(jì)。