一種多重約束下的NoC 電壓頻率島劃分方法

周 芳 吳 寧 葉云飛 葛 芬

(南京航空航天大學電子信息工程學院，南京210016)

隨著集成電路技術(shù)的發(fā)展，MPSoC 系統(tǒng)逐漸成為下一代單芯片處理器的主要設(shè)計形式，其規(guī)模將會擴展至數(shù)百個處理核.相對于飛速增長的計算性能，傳統(tǒng)的總線片內(nèi)通信方式已經(jīng)無法適應MPSoC 中日益復雜的互聯(lián)結(jié)構(gòu)、通信效率以及可擴展性需求.因此，作為一種復雜MPSoC 系統(tǒng)互聯(lián)的有效解決方案，片上網(wǎng)絡日漸受到學術(shù)界的關(guān)注.

能耗問題一直是NoC 研究的熱點之一.近年來，研究人員根據(jù)不同的NoC 能耗模型，提出了動態(tài)電壓調(diào)整(DVS)、動態(tài)電壓頻率調(diào)整(DVFS)和電壓頻率島(VFI)等低功耗技術(shù)［1-12］.其中，VFI 技術(shù)是依據(jù)NoC 所具有的全局異步局部同步(globally asynchronous locally synchronous，GALS)固有機制，綜合考慮電壓與性能間的折中關(guān)系，將NoC系統(tǒng)在邏輯上劃分為多個VFI，為它們分配不同的電壓和頻率值，使同一個VFI 上的PE 都工作于相同的電壓和頻率.在已有的關(guān)于VFI 的研究中［4-12］，有些致力于將已知的NoC 網(wǎng)格結(jié)構(gòu)劃分為VFI，有些為給定的島嶼選擇最佳的電壓與頻率.如文獻［4］首先為每個PE 分配不同的VFI，然后反復合并相鄰的島嶼，以最小化系統(tǒng)的總能耗.但該方法在合并VFI 時只考慮相鄰島，對于不相鄰的相同電壓頻率島則無法合并，容易形成孤島.文獻［6］提出了一種基于改進的遺傳模擬退火算法的NoC 電壓島劃分方法，該方法以犧牲求解時間為代價，來獲得更低的系統(tǒng)能耗.文獻［7］則采用了禁忌搜索優(yōu)化算法來最小化NoC 能耗，該方法只針對基于VFI 的NoC 進行電壓分配，而未解決VFI 的劃分問題.

由于系統(tǒng)芯片電源電壓的降低和特征尺寸的縮小，導致芯片中瞬時故障數(shù)目的增加［13］，因此MPSoC 可靠性已成為NoC 設(shè)計中需要考慮的一個重要問題［14］.電壓和頻率值的改變會同時影響NoC 系統(tǒng)的能耗和可靠性，但現(xiàn)有的VFI 研究主要以優(yōu)化能耗為目標，沒有過多關(guān)注可靠性問題［4-9］，或者僅考慮了可靠性約束，而未考慮傳輸延時等其他約束條件［11-12］.因此在VFI 劃分過程中，綜合考慮傳輸延時、能耗和可靠性等性能指標，提出多重約束條件才更加合理.

基于上述分析，本文以NoC 系統(tǒng)總能耗為優(yōu)化目標，綜合考慮數(shù)據(jù)包傳輸延時、VFI 數(shù)量及PE可靠性等多重約束條件，提出了一種基于整數(shù)線性規(guī)劃(integer linear program，ILP)的VFI 劃分方法.該方法首先研究適用于ILP 的數(shù)學模型，并使用LPSolve 求解該模型，以完成NoC 電壓頻率島的劃分，達到能耗優(yōu)化目標.

1 VFI 劃分問題分析

NoC 的VFI 劃分方案對NoC 系統(tǒng)復雜度、總能耗、延時和可靠性等性能指標都有著重要的影響.其基本的劃分原則是系統(tǒng)中對可靠性和延時要求高的PE 劃分到高電壓頻率域，要求相對低的PE則劃分到低電壓頻率域，以控制系統(tǒng)的整體能耗;同時，從物理設(shè)計的角度考慮，過多的VFI 碎片會增加版圖電源布線和時鐘樹的復雜性［7］，且不同VFI 之間的電平轉(zhuǎn)換器也會帶來額外的能耗成本.因此，VFI 的劃分數(shù)目不宜過多，復雜度不能過高.圖1所示為VFI 的劃分對NoC 的影響.

圖1中3 ×3 二維Mesh 結(jié)構(gòu)的片上網(wǎng)絡中包含9 個PE 節(jié)點，均可分別工作在高電壓頻率域或低電壓頻率域中.如果不考慮VFI 的數(shù)目限制，在完成任務圖到NoC 的映射后，僅為了滿足各PE 的性能和它們之間的通信關(guān)系來設(shè)置電壓頻率，相鄰的PE 可能工作于不同的VFI 中，它們之間通信都要通過電平轉(zhuǎn)換器，這樣就會帶來額外的通信能耗成本，可能導致NoC 的通信能耗和延時很大，系統(tǒng)復雜度過高(碎片多).可能出現(xiàn)的最壞情況如圖1(a)所示，整個片上網(wǎng)絡被劃分為9 個島;如果要求降低NoC 通信能耗、延時和系統(tǒng)復雜度，VFI 數(shù)目不能高于2 個，則部分PE 需要調(diào)整電壓頻率域.一種可能的劃分結(jié)果如圖1(b)所示，將PE1劃分于高電壓頻率域中，剩余的PE 劃分于低電壓頻率域中.這樣可降低系統(tǒng)的復雜度和能耗，但由于大部分PE 工作于低電壓頻率域，系統(tǒng)可靠性會較差.因此，需要研究一種合理的VFI 劃分方法，綜合考慮系統(tǒng)復雜度、能耗和可靠性等性能指標，達到它們之間的均衡，如圖1(c)所示的劃分結(jié)果較為合理.

當系統(tǒng)規(guī)模擴大，NoC 中PE 節(jié)點達到上百個，電壓頻率島的劃分問題變得非常復雜，這就需要結(jié)合多性能指標優(yōu)化算法來實現(xiàn)電壓頻率島的劃分.ILP 是一種適合用于多重約束條件的優(yōu)化算法.基于ILP 算法來解決多重約束條件下的NoC電壓頻率島劃分問題時，首先需要根據(jù)已知的NoC 體系結(jié)構(gòu)圖和各PE 節(jié)點的工作電壓集，分析VFI 劃分問題中多重約束條件、優(yōu)化目標與其之間的關(guān)系，然后構(gòu)建適用于ILP 算法的數(shù)學模型.下面給出VFI 劃分問題的數(shù)學描述.給定條件如下:①有向圖NAG(NoC architecture graph)(VP，EP)，是已完成任務映射的NoC 體系結(jié)構(gòu)圖，圖中每個頂點pi∈VP表示NoC 中的一個處理核PE;每條邊ei，j∈EP表示從頂點pi到pj的通信路徑，其權(quán)重ci，j表示PE 節(jié)點pi和pj之間的通信量.②每個PE節(jié)點pi∈VP的工作電壓集其中表示PE 節(jié)點pi的工作電壓.約束條件為VFI最大數(shù)目n，最大通信延時Tmax和PE 最小可靠性要求Pmin.優(yōu)化目標是最小化NoC 系統(tǒng)總能耗E，即minE.

2 VFI 模型建立

2.1 能耗模型

片上網(wǎng)絡VFI 劃分問題的能耗優(yōu)化目標由3部分組成:NoC 中所有PE 節(jié)點的計算能耗E1，NoC 各路由節(jié)點之間的通信能耗E2以及各VFI之間的轉(zhuǎn)換器能耗E3.文獻［11］只考慮了前2 個能耗.

2.1.1 PE 節(jié)點的計算能耗E1

PE 節(jié)點的計算能耗是指在不同的工作電壓和工作頻率下，PE 節(jié)點所消耗的能耗，可表示為

式中，Ri為PE 節(jié)點的活動周期數(shù);Ceff為每個周期的翻轉(zhuǎn)電容;Ti為PE 節(jié)點的空閑周期數(shù);ki為設(shè)計參數(shù);St為工藝參數(shù);Vti為閾值電壓.

根據(jù)式(1)可計算出在不同工作電壓vki 下，所對應的PE 節(jié)點計算能耗值E1.

2.1.2 NoC 各路由節(jié)點之間的通信能耗E2

對于NoC 中所有通信鏈路，其通信能耗可表示為

式中，dij表示PE 節(jié)點pi和pj之間的跳數(shù);φl(i，j)表示從PE 節(jié)點pi傳輸1 bit 數(shù)據(jù)到節(jié)點pj時的鏈路能耗，其值和鏈路電壓的平方成正比.當VFI 的電壓降低時，其頻率也隨之降低，如果相鄰的2 個路由節(jié)點位于不同的VFI 中，則它們之間的數(shù)據(jù)傳輸速率應滿足兩者中較低的頻率值，它們之間的鏈路電壓應是兩者中較低的電壓值，因此φl(i，j)可用下式計算:

式中，lpq為相鄰2 個路由節(jié)點pp和pq之間的鏈路，它位于路由節(jié)點pi到pj的鏈路lij中;Elij為NoC 中所有PE 節(jié)點均為最高電壓Vmax時，節(jié)點pi到pj之間傳輸1 bit 數(shù)據(jù)的能耗;vp和vq分別為路由節(jié)點pp和pq的工作電壓值.

由以上分析可看出通信能耗E2與各節(jié)點PE之間的電壓關(guān)系，從而可計算出在不同電壓值下所對應的通信能耗值.

2.1.3 各VFI 之間的轉(zhuǎn)換能耗E3

NoC 系統(tǒng)中每增加一個電壓島都會帶來額外的能耗開銷，主要是島間頻率轉(zhuǎn)換器的能耗和電平轉(zhuǎn)換器能耗.當相鄰的2 個PE 工作在不同的電壓和時，所需要的轉(zhuǎn)換能耗可根據(jù)下式計算:

式中，η 為電壓轉(zhuǎn)換器的效率，這里可設(shè)置η=0.9;C 為電源的濾波電容值，可取100 μF.因此，只要知道NoC 中各PE 節(jié)點之間的電壓轉(zhuǎn)換關(guān)系，就可計算出總轉(zhuǎn)換能耗E3.

2.2 可靠性模型

片上網(wǎng)絡VFI 劃分問題中，各PE 節(jié)點的可靠性是指所有處理任務在PE 上正確執(zhí)行的概率，其值Pi可用下式計算［15］:

式中，τi為任務在PE 節(jié)點pi上的執(zhí)行時間;μi為每秒鐘的平均故障數(shù)，與PE 的工作電壓vki 有關(guān)，其計算公式為

其中，Vmax和Vmin分別為PE 的最高和最低工作電壓;d 為一個由芯片參數(shù)等決定的常數(shù)，這里可設(shè)置d=1;μ0為PE 對應于最高電壓Vmax的故障率，這里可設(shè)置μ0=10－6.

由式(5)、(6)可看出，各PE 節(jié)點的可靠性Pi與PE 的工作電壓vki 之間為指數(shù)關(guān)系.當Vmax和Vmin分別被設(shè)置為1.5 和1.0 V 時，可發(fā)現(xiàn)可靠性Pi的值無限趨近于1，因此可設(shè)置 Pmin=0.999 999 99［12］.

3 基于ILP 的片上網(wǎng)絡VFI 劃分方法

基于ILP 算法構(gòu)建片上網(wǎng)絡VFI 劃分問題的數(shù)學模型，一般包括3 個步驟:決策變量定義、確定約束條件和確定目標函數(shù).

3.1 決策變量

首先根據(jù)所要優(yōu)化目標的影響因素找到?jīng)Q策變量.根據(jù)NoC 的能耗模型，發(fā)現(xiàn)影響能耗大小的主要因素是各PE 的工作電壓、PE 節(jié)點之間的電壓轉(zhuǎn)換關(guān)系以及VFI 的個數(shù).因此，該模型中所用到的變量可定義如下.

定義變量xik表示PE 節(jié)點pi的工作電壓是否為，

定義變量ri，k，j，l表示PE 節(jié)點pi和pj之間的電壓轉(zhuǎn)換關(guān)系，

在極端情況下，VFI 最大數(shù)目n 即為片上網(wǎng)絡中PE 的個數(shù).將所有NoC 中的VFI 按序排列編號，則?pi∈VP，1≤m≤n.定義變量yim表示PE 節(jié)點pi是否分配到編號為m 的VFI 中，

定義變量tm表示編號為m 的VFI 中是否分配了PE 節(jié)點，

3.2 約束條件

針對NoC 的VFI 劃分問題，需要綜合考慮傳輸延時、VFI 最大個數(shù)和PE 最小可靠性等約束條件.此外，還需要由決策變量所受的限制條件確定決策變量本身所要滿足的約束條件.約束條件設(shè)定如下:

式中，tlatency(i，j)為路由節(jié)點pi和pj之間的延時，

其中，μk為數(shù)據(jù)包通過傳輸路徑上路由節(jié)點k 時的周期數(shù);fk為該節(jié)點所屬電壓頻率島的頻率;tFIFO為數(shù)據(jù)包在異步FIFO 上的延遲;W 為通道帶寬.

式(7)是為了限制每個PE 節(jié)點只能配置唯一一個電壓值;式(8)是為了限制每個PE 節(jié)點只能劃分到唯一一個電壓島上;式(9)是為了限制電壓島的個數(shù)不超過n;式(10)保證了當tm=0 時，電壓島m 上PE 節(jié)點的個數(shù)為0;同樣，式(11)保證了當電壓島m 上PE 節(jié)點個數(shù)為0 時，tm也為0;式(12)保證了只有當pi的工作電壓為vki 且pj的工作電壓為時，ri，k，j，l才為1;式(13)是為了滿足系統(tǒng)的通信延時要求;式(14)是為了保證各PE 節(jié)點的可靠性Pi滿足要求.

通過設(shè)置上述一系列約束條件，完成了VFI劃分過程中，傳輸延時、VFI 最大個數(shù)和PE 最小可靠性等多重約束條件的設(shè)置.

3.3 目標函數(shù)

目標函數(shù)由決策變量和優(yōu)化目標之間的函數(shù)關(guān)系確定.片上網(wǎng)絡VFI 劃分問題的能耗優(yōu)化目標由3 部分組成:NoC 中所有PE 節(jié)點的計算能耗E1，NoC 各路由節(jié)點之間的通信能耗E2以及各VFI 之間的轉(zhuǎn)換器能耗E3.

PE 的計算能耗E1可表示為

式中，ηki為PE 節(jié)點pi的工作電壓為vki時的能耗，可由式(1)計算得到.

NoC 各路由節(jié)點之間的通信能耗E2可表示為

各VFI 之間的轉(zhuǎn)換能耗E3可表示為

式中，αkl表示當相鄰的2 個PE 工作在不同的電壓和時，它們之間的電平轉(zhuǎn)換器所消耗的能耗，可由式(4)計算得到.

因此，基于ILP 的NoC 電壓頻率島劃分問題的目標函數(shù)可表示如下:

4 實驗結(jié)果及分析

對建立的適用于ILP 優(yōu)化算法的VFI 數(shù)學模型，使用LPSolve 求解器來求解該模型.本文從嵌入式系統(tǒng)綜合評測E3S(embedded systems synthesis benchmarks suite)測試基準［16］中選取了多組應用實例和一個多媒體系統(tǒng)(MMS)進行仿真實驗，驗證了所提出的VFI 劃分方法的有效性，并給出了實驗結(jié)果.所有實驗均運行在配置為Intel Ceon 2.4 GHz CPU，3.48 GB RAM，Windows XP 操作系統(tǒng)的HP 工作站上.

4.1 E3S 實驗結(jié)果

本文所用的E3S 測試基準涵蓋了自動化、消費電子、網(wǎng)絡、辦公處理和通信5 個應用領(lǐng)域，收集了17 種來自工業(yè)界的嵌入式處理器單元作為PE庫，每個測試用例中都包含一組完整的任務圖信息.實驗中所用到的測試用例，其網(wǎng)絡規(guī)模分別為5 ×5，4 ×4，4 ×4，3 ×3 和4 ×4.所選用的PE 均為AMD K6-2E 處理器.實驗中的主要參數(shù)設(shè)置如下:每個PE 選取了6 個電壓等級V= {1.0，1.1，1.2，1.3，1.4，1.5 V}，最小可靠性要求Pmin=0.999 999 99［12］.

在實驗中，VFI 數(shù)量的上限n 分別設(shè)置為3 和7［5］，延時約束Tmax也選取較高和較低2 個不同的數(shù)值，這樣約束條件Tmax和n 就有4 種可能的組合((low，low)，(low，high)，(high，low)，(high，high)).在每種組合下，應用本文方法對每組測試用例進行VFI 劃分，實驗結(jié)果如圖2所示.

圖2 4 種不同約束條件下的能耗開銷

從圖2中可看出，隨著Tmax和n 的改變，5 種測試用例的變化趨勢相同.當(Tmax，n)為(low，low)時，由于約束條件變得最為嚴格，電壓調(diào)節(jié)空間較小，各PE 都工作在較高的電壓下，因此能耗開銷最大.當(Tmax，n)為(low，high)或(high，low)時，只放寬其中一個約束條件，能耗開銷比前一種情況要小些.當(Tmax，n)為(high，high)時，約束條件變得最寬松，電壓可調(diào)空間較大，從而使能耗開銷最小.

此外，本文對于每組測試用例分別與隨機劃分方法和文獻［6］所用劃分方法進行能耗比較，以隨機方法的能耗值為標準，作歸一化處理.比較結(jié)果如圖3所示.

圖3 4 種不同約束條件下能耗結(jié)果比較

由圖3可看出，對于所有的測試用例，本文方法的能耗值優(yōu)于其他2 種方法.相比于隨機方法，可降低能耗9.1% ～33.6%;而相比于文獻［6］所用方法，最高可降低能耗16.7%.

4.2 MMS 實驗結(jié)果

以一個由H.263 視頻編/解碼器以及MP3 音頻編/解碼器組成的多媒體系統(tǒng)為例，采用本文方法對該系統(tǒng)進行VFI 劃分.該多媒體系統(tǒng)包含25個任務，并可分配至若干個PE 節(jié)點，PE 節(jié)點可以是DSP、通用處理器、嵌入式DRAM 及專用ASIC等.該系統(tǒng)的通信任務圖及各任務所屬PE 節(jié)點類型如圖4所示.

圖4 MMS 系統(tǒng)通信任務圖

首先采用文獻［17］所提出的映射算法將MMS 系統(tǒng)中的各任務分配至16 個PE 節(jié)點，并映射至一個4 ×4 的二維Mesh NoC 中，再用本文所提出的方法對其進行VFI 劃分，最小可靠性要求Pmin=0.999 999 99，VFI 最大數(shù)目限制為3.最終劃分結(jié)果如圖5所示.

圖5 MMS 的VFI 劃分結(jié)果

圖5中，每個PE 節(jié)點中的括號里面標識了該PE 核上分配的任務，如ASIC1(1，3，5)表示任務1，3，5 分配至PE 節(jié)點ASIC1上.其中，VFI1的電壓值為1.5 V，VFI2的電壓值為1.2 V，VFI3的電壓值為1.0 V.該結(jié)果相比于所有PE 節(jié)點均工作于最高電壓1.5 V 下，可節(jié)約能耗37.9%，相比于文獻［6］，可節(jié)約能耗10.1%.進一步驗證了多重約束條件下的VFI 劃分方法的有效性.

5 結(jié)語

為了解決NoC 的VFI 劃分問題，本文提出了一種多約束條件下的VFI 劃分方法，綜合考慮數(shù)據(jù)包傳輸延時、VFI 數(shù)量及PE 可靠性等多重約束條件，采用ILP 算法優(yōu)化NoC 系統(tǒng)總能耗.選取嵌入式系統(tǒng)綜合評測E3S 測試基準中的多組應用實例和一個多媒體系統(tǒng)實例進行仿真實驗，驗證了所提出的VFI 劃分方法的有效性，并給出了精確的評估結(jié)果.實驗結(jié)果表明:在滿足多重約束條件的同時，所提出的劃分方法可有效降低NoC 總能耗，系統(tǒng)性能得到了提高.此外，該方法還可推廣解決三維NoC 的VFI 劃分問題，下一步的研究工作主要是三維NoC 中IP 核映射與VFI 劃分問題的協(xié)同設(shè)計.

References)

［1］ Arjomand M，Sarbazi-Azad H.Voltage-frequency planning for thermal-aware，low-power design of regular 3-D NoCs［C］//23rd International Conference on VLSI Design.Bangalore，India，2010:57-62.

［2］ Jung H，Pedram M.Supervised learning based power management for multicore processors［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2010，29(9):1395-1408.

［3］ Sharifi S，Coskun A K，Rosing T S.Hybrid dynamic energy and thermal management in heterogeneous embedded multiprocessor SoCs ［C］//Proceedings of the 2010 Asia and South Pacific Design Automation Conference.Taipei，China，2010:873-878.

［4］ Ogras U Y，Marculescu R，Choudhary P，et al.Voltage frequency island partitioning for GALS-based networks-on-chip ［C］//Proceedings of the 44th Annual Conference on Design Automation.New York，2007:110-115.

［5］ Ogras U Y，Marculescu R，Marculescu D，et al.Design and management of voltage-frequency island partitioned networks-on-chip ［J］.IEEE Transactions on Very Large Scale Integration Systems，2009，17(3):330-341.

［6］ 劉斌，常振超，張興明，等.一種基于遺傳算法的片上網(wǎng)絡電壓島劃分方法［J］.計算機應用研究，2012，29(10):3740-3743.Liu Bin，Chang Zhenchao，Zhang Xingming，et al.Genetic algorithm based NoC voltage-frequency island partition method［J］.Application Research of Computers，2012，29(10):3740-3743.(in Chinese)

［7］ Lee W，Liu H Y，Chan Y W.Voltage island aware floorplanning for power and timing optimization［C］//IEEE/ACM International Conference on Computer-Aided Design.San Jose，CA，USA，2006:389-394.

［8］ Sengupta D，Saleh R A.Application-driven voltage-island partitioning for low-power system-on-chip design［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2009，28(3):316-326.

［9］ Ghosh P，Sen A.Energy efficient mapping and voltage islanding for regular NoC under design constraints［J］.International Journal of High Performance Systems Architecture，2010，2(3/4):132-144.

［10］ Popovich M，F(xiàn)riedman E G，Sotman M，et al.Onchip power distribution grids with multiple supply voltages for high performance integrated circuits ［C］//Proceedings of the 15th ACM Great Lakes symposium on VLSI.Chicago，IL，USA，2005:2-7.

［11］ 常政威，熊光澤，桑楠，等.基于電壓島的能量和可靠性感知NoC 映射［J］.計算機輔助設(shè)計與圖形學學報，2009，21(1):19-26.Chang Zhengwei，Xiong Guangze，Sang Nan，et al.Energy-and reliability-aware mapping for NoC implemented with voltage islands［J］.Journal of Computer-Aided Design ＆ Computer Graphics，2009，21(1):19-26.(in Chinese)

［12］ 張劍賢，周端，楊銀堂，等.處理器可靠性約束的電壓頻率島NoC 能耗優(yōu)化［J］.電子與信息學報，2011，33(9):2205-2211.Zhang Jianxian，Zhou Duan，Yang Yintang，et al.Energy optimization of NoC based on voltage-frequency islands under processor reliability constraints［J］.Journal of Electronics ＆Information Technology，2011，33(9):2205-2211.(in Chinese)

［13］ Zhao B X，Aydin H，Zhu D.Reliability-aware dynamic voltage scaling for energy-constrained real-time embedded systems ［C］//2008 IEEE International Conference on Computer Design.Lake Tahoe，CA，USA，2008:633-639.

［14］ Yamamoto A Y，Ababei C.Unified system level reliability evaluation methodology for multiprocessor systems-on-chip［C］//2012 International Green Computing Conference.San Jose，CA，USA，2012:1-6.

［15］ Zhu D K，Melhem R，Mosse D.The effects of energy management on reliability in real-time embedded systems ［C］//Proceedings of the International Conference on Computer Aided Design.San Jose，CA，USA，2004:35-40.

［16］ Dick R.Embedded system synthesis benchmarks suite(E3S)［EB/OL］.(2013-06-20)［2014-6］.http://ziyang.eecs.umich.edu/ ～dickrp/e3s/.

［17］ Ge F，Wu N.Genetic algorithm based mapping and routing approach for network on chip architectures［J］.Chinese Journal of Electronics，2010，19(1):91-96.