顓孫宗亮，李克秋＊

（大連理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，遼寧 大連 116024）

0 引 言

隨著半導(dǎo)體工藝的發(fā)展，片上系統(tǒng)（system on chip，SoC）未來可能會包含幾十個或上百個IP（intellectual property，IP）核.傳統(tǒng)的總線型拓撲結(jié)構(gòu)不能滿足未來片上系統(tǒng)對系統(tǒng)可擴展性、靈活性和能量有效性的要求［1］.采用路由和包交換技術(shù)的片上網(wǎng)絡(luò)（network on chip，NoC）已經(jīng)在多處理器片上系統(tǒng)中廣泛采用［2］.在片上網(wǎng)絡(luò)系統(tǒng)中，系統(tǒng)能耗變成NoC 研究領(lǐng)域中的熱點，為了降低系統(tǒng)能耗，Ogras等在NoC 系統(tǒng)機制中引入了電壓島的概念［3］，他們把NoC 系統(tǒng)劃分成不同的電壓頻率區(qū)域（島），使每個核能調(diào)整自己所屬的電壓，讓整個系統(tǒng)能更好地降低能耗.

Jang等在混合時鐘FIFO（mixed clock FIFO，MCFIFO）和不同電壓轉(zhuǎn)化器（voltage level converter，VLC）的路由器能量消耗基礎(chǔ)上，設(shè)計電壓島分配和靜態(tài)電壓分配方案［4］.他們在感知電壓島的情況下，設(shè)計出基于電壓島的能量消耗優(yōu)化框架，有效地減少了復(fù)雜路由器的個數(shù)，從而有效降低NoC 系統(tǒng)的能耗.文獻［5］描述在可靠性約束下的能耗NoC 映射問題，利用禁忌搜索的優(yōu)化方法來降低系統(tǒng)能耗.文獻［6］設(shè)計一種基于量子粒子群的電壓島劃分算法，降低了NoC系統(tǒng)的能耗.文獻［7］利用混線性規(guī)劃方案解決IP映射與電壓島劃分問題，提出一個基于貪婪的啟發(fā)式算法解決此類問題.

以上方案是在NoC 支持電壓島（voltagefrequency island，VFI）的體系結(jié)構(gòu)下來進行能耗的優(yōu)化.然而在NoC 系統(tǒng)中，片上網(wǎng)絡(luò)互連線上的誤碼是由于片上各種干擾源如電源干擾、電磁干擾等引起的.數(shù)據(jù)誤碼率計算公式可以由文獻［8］得到.可以看出，供應(yīng)電壓（supply voltage）對數(shù)據(jù)傳輸誤碼率有很大的影響，在其他條件同等的情況下，路由器供應(yīng)電壓越低，其數(shù)據(jù)傳輸誤碼率越高.比如在噪聲δ＝0.2的情況下，電壓為1 V 和1.6V 數(shù)據(jù)誤碼率分別為6.2×10－3和3.16×10－5，相差將近200倍.

數(shù)據(jù)接收端的處理節(jié)點發(fā)現(xiàn)數(shù)據(jù)錯誤后，要求數(shù)據(jù)發(fā)送端的處理節(jié)點必須重新發(fā)送數(shù)據(jù).在滿足IP核計算周期和通信帶寬的情況下，電壓島供應(yīng)電壓越低，系統(tǒng)能耗越低.

然而路由器供應(yīng)電壓越低，數(shù)據(jù)傳輸?shù)恼`碼率就越高，要求數(shù)據(jù)發(fā)送端重新發(fā)送的次數(shù)就越多，重新發(fā)送數(shù)據(jù)需要消耗通信能耗，特別在數(shù)據(jù)交換比較頻繁的應(yīng)用實例中，這種消耗十分明顯［9］，因而在進行IP核映射與路由算法選擇過程中應(yīng)充分考慮這個因素.

現(xiàn)有的工作利用電壓島進行能耗優(yōu)化［3－7］，但是沒有考慮供應(yīng)電壓對誤碼率的影響及數(shù)據(jù)重傳引起的能量消耗問題.另外也存在一定的局限，如文獻［3］的方案存在容易形成電壓孤島的問題，文獻［3－7］也沒有考慮可以利用IP核從低電壓島往高電壓島移動的機制，來降低NoC 整體能耗.本文針對這些問題，提出一種基于數(shù)據(jù)重傳機制的能耗模型，并定義考慮供應(yīng)電壓對數(shù)據(jù)傳輸影響情況的能耗優(yōu)化問題.在此基礎(chǔ)上設(shè)計能耗優(yōu)化方案，其中包括電壓島劃分、IP 核映射和路由路徑選擇等3個部分.

1 系統(tǒng)模型

本章首先描述支持電壓島的NoC 平臺模型，處理節(jié)點放置一個IP核和一個路由器，每個處理節(jié)點有自己固定的電壓和時鐘頻率.當相鄰的處理節(jié)點的電壓和時鐘頻率不一致時，用混合時鐘FIFOs進行時鐘頻率轉(zhuǎn)換.在考慮供應(yīng)電壓對數(shù)據(jù)傳輸可靠性影響下，重新定義NoC 系統(tǒng)能耗模型，并在此基礎(chǔ)上，提出基于電壓島分配、IP 核映射和路由算法的NoC系統(tǒng)能耗優(yōu)化設(shè)計方法.描述這個問題需要以下簡單的定義.

1.1 定 義

定 義 1 應(yīng) 用 通 信 圖 （application communication graph）ACG（T，A）是一個有向圖.頂點ti∈T表示一個IP核，邊ai，j∈A表示從ti到tj通信任務(wù).C（ai，j）表示從ti到tj通信量，B（ai，j）表示從ti到tj需要的通信帶寬.每一個IP核都有自己的供應(yīng)電壓和閾值電壓.

定義2 系統(tǒng)拓撲結(jié)構(gòu)圖（architecture topology graph）ATG（P，L）是一個有向圖.頂點pi∈P表示系統(tǒng)結(jié)構(gòu)一個節(jié)點，邊li，j∈L表示相鄰節(jié)點通信鏈路.Si，j表示pi到pj可用通信路徑 的 集 合，si，j表 示pi到pj一 條 通 信 路 徑表示pi到pj一位數(shù)據(jù)通信鏈路能耗.

定義3 映射函數(shù)MF（mapping function）：ACG→ATG映射一個IP核ti∈T到節(jié)點pi∈P上.φ（t，p）表示ACG中的IP核映射到ATG上，滿足如下性質(zhì)：

1.2 能耗模型

基于電壓島的NoC 系統(tǒng)能耗主要由處理器動態(tài)計算能耗、數(shù)據(jù)傳輸能耗和不同電壓島之間轉(zhuǎn)換能耗組成.

根據(jù)文獻［2］，動態(tài)計算能耗定義為

其中Ri是有效周期數(shù)，Ceff是有效切換電容，Vdd是IP核的供應(yīng)電壓.

其中f為時鐘頻率，Vth為閾值電壓，k和α為常數(shù).

在文獻［2］中沒有考慮電壓島概念情況下，所有鏈路傳輸一位數(shù)據(jù)能耗是相同的，定義為

其 中El，bit表 示 鏈 路 能 耗，Eb，bit表 示 緩 沖 區(qū) 能 耗，Es，bit表示交 換能耗.

在支持電壓島的NoC系統(tǒng)中，假設(shè)片上系統(tǒng)供應(yīng)電壓最大為Vmax，每一個路由器供應(yīng)電壓為Vi，則每傳輸一位數(shù)據(jù)從源節(jié)點ps到終節(jié)點pd能耗可以定義為

其中pi為定義2中從源節(jié)點ps到終節(jié)點pd通信路徑上路由器.

每一個通信任務(wù)能耗為

其中Ck為通信任務(wù)k的通信流量.

不同電壓島之間轉(zhuǎn)換能耗由MCFIFO 和VLC能耗構(gòu)成，定義為

其中EMCFIFO和EVLC分別為MCFIFO 和VLC 能耗，m為MCFIFO 個數(shù).

1.3 數(shù)據(jù)傳輸誤碼的模型

片上網(wǎng)絡(luò)的模塊化和可重用性等性質(zhì)決定可以使用ECC（error control coding，ECC）方法來解決發(fā)生在瞬時的數(shù)據(jù)傳輸錯誤.ECC 方法一般有兩種.一種是在數(shù)據(jù)鏈路層（hop－to－h(huán)op ECC），在每一個路由器配置一個ECC 編碼器／解碼器，每一個路由器能檢測出錯誤數(shù)據(jù)，當數(shù)據(jù)錯誤發(fā)生時，數(shù)據(jù)接收端可以要求數(shù)據(jù)發(fā)送端重新發(fā)送或者用冗余線路來解決數(shù)據(jù)傳輸錯誤問題［10］.這種傳輸錯誤控制機制能有效地控制錯誤的傳播，但是在每一個路由器上增加一個ECC 編碼器／解碼器就會增加系統(tǒng)能量的消耗和芯片面積的消耗.另一種可以替代的糾錯機制發(fā)生在數(shù)據(jù)網(wǎng)絡(luò)層（end－to－end ECC），這種糾錯機制不發(fā)生在數(shù)據(jù)傳輸?shù)闹虚g路由器中，數(shù)據(jù)接收終點路由器發(fā)現(xiàn)數(shù)據(jù)錯誤，要求數(shù)據(jù)發(fā)送端路由器重新發(fā)送數(shù)據(jù).這種糾錯機制和鏈路層數(shù)據(jù)糾錯相比，不會增加片上網(wǎng)絡(luò)的能耗和面積消耗.在設(shè)計NoC 系統(tǒng)過程中，對芯片面積消耗有嚴格的限制.因此，本文采用在數(shù)據(jù)網(wǎng)絡(luò)層的糾錯機制，并采用片上網(wǎng)絡(luò)數(shù)據(jù)傳輸超時重傳機制ARQ（automatic repeat request，ARQ）［11］.

片上網(wǎng)絡(luò)互連線上的誤碼是由片上各種干擾源如電源干擾、電磁干擾等引起的.一般用δ2N高斯白噪聲電壓來表示所有不同噪聲源的總和的方差，ε表示一條信號線進行一次數(shù)據(jù)傳輸時發(fā)生錯誤的概率，根據(jù)文獻［10］，ε定義為

從上面的模型可以得到一個報文在兩個相連路由器傳輸?shù)恼`碼概率模型

其中k表示數(shù)據(jù)報文（packet）的數(shù)據(jù)位長度.

在數(shù)據(jù)接收端報文誤碼概率模型為

這里pi表示數(shù)據(jù)通信路徑中的路由器，rpi是在pi路由器數(shù)據(jù)發(fā)生錯誤的概率.

在數(shù)據(jù)接收端的處理節(jié)點如果發(fā)現(xiàn)報文是不正確的，需要數(shù)據(jù)發(fā)送端重新傳輸數(shù)據(jù).根據(jù)rps，pd可以得到平均正確數(shù)據(jù)傳輸?shù)拇螖?shù)NARQ：

1.4 重新定義系統(tǒng)通信能耗模型

在基于電壓島的NoC 系統(tǒng)中，IP 核在考慮供應(yīng)電壓對數(shù)據(jù)誤碼率的影響下，采用片上網(wǎng)絡(luò)數(shù)據(jù)傳輸超時重傳機制.整個NoC系統(tǒng)數(shù)據(jù)通信的整體能耗可以重新定義為

1.5 問題定義

在基于電壓島的NoC 系統(tǒng)中，系統(tǒng)能耗問題可以形式化定義為給定應(yīng)用通信圖ACG（T，A）、NoC系統(tǒng)拓撲結(jié)構(gòu)圖ATG（P，L）和電壓島最大數(shù)，在考慮通信帶寬約束和供應(yīng)電壓對數(shù)據(jù)傳輸誤碼率的影響下，考慮電壓島劃分和尋找核集合C與資源節(jié)點集合T一一對應(yīng)的映射函數(shù)φ（C），并在此基礎(chǔ)上設(shè)計數(shù)據(jù)傳輸路由算法，使得NoC系統(tǒng)能耗最優(yōu).

其中

2 設(shè)計方法

本章描述整個設(shè)計方法和主要算法.設(shè)計方法主要包含3個部分：電壓島的劃分、IP 核的映射和路由算法.本文在電壓島劃分方面不但考慮計算能耗，同時考慮了通信能耗；IP 核的映射部分主要考慮總體通信流量最少和電壓孤島問題；在路由算法設(shè)計方面主要考慮數(shù)據(jù)通信能耗優(yōu)化問題.下面從3個方面進行描述.

2.1 電壓島劃分

電壓島劃分問題是在給定電壓等級集合和最大電壓島數(shù)的情況下，給每個IP核分派一個供應(yīng)電壓.假設(shè)給定最大電壓島數(shù)是m，電壓等級為N，那么就有M＝C（N，m）種VF＝ ｛vf1，vf2，…，vfm｝的電壓組合.用式（1）和（2）算出每個IP核所需要的最低供應(yīng)電壓Vi，對于任何vfi中最大的電壓大于或者等于最大Vi，這個就是候選的vfi.這僅是IP核的計算能耗，沒有考慮通信能耗和轉(zhuǎn)換能耗.本文的算法結(jié)合這3個方面的能耗來進行電壓島分配.本文定義IP核從低電壓島往高電壓島移動能耗函數(shù)，如果函數(shù)值大于零表示可以移動，如果小于或等于零表示不可以移動.移動能耗函數(shù)定義如下：

其中D是IP核的映射平均距離.具體算法如下：

算法1 電壓島分配算法

2.2 IP核映射

進行IP核映射時應(yīng)考慮電壓孤島的問題，因為這會帶來算法效率和通信能耗優(yōu)化方面的問題［3］.本文算法在保證整體通信流量最小的情況下，結(jié)合考慮電壓孤島問題.本文用算法2來解決這個問題，首先IP核之間按照通信流量進行降序排序，然后把電壓島候選的Tile放到CT 列表中.接下來在候選的CT 表中選擇一個Tile來進行映射，如果此Tile有最大的相鄰節(jié)點和已經(jīng)映射IP核通信流量最少，再判斷是否產(chǎn)生電壓孤島，如果不產(chǎn)生電壓孤島，則映射此候選Tile，如果產(chǎn)生電壓孤島，則再選擇其他的候選Tile，如果找不到這樣的Tile，選擇第一個Tile來進行映射.映射此IP核以后，把該Tile相鄰的節(jié)點都放到與IP 核具有相同電壓島CT 列表中，再進行剩余的IP核映射.算法描述如下：

算法2 IP核映射算法

2.3 路由算法

設(shè)計NoC系統(tǒng)中的路由算法時，路由死鎖和活鎖問題要充分考慮.本文用通信兩個節(jié)點最短路由來解決路由活鎖問題.在解決路由死鎖問題方面，本文參照文獻［12］解決路由死鎖技術(shù)，首先找到所有通信任務(wù)的兩點最短路徑的集合.判斷通信最短路徑構(gòu)成的鏈路依賴圖［12］中是否有環(huán)路.如果沒有環(huán)路，就進行路由選擇.如果鏈路依賴圖構(gòu)成環(huán)路，則必須去掉一些鏈路來消除所有的環(huán)路，否則構(gòu)成死鎖.本文用最小代價函數(shù)η去掉這些環(huán)路，具體細節(jié)參考文獻［12］.首先按通信流量進行排序，考慮供應(yīng)電壓對數(shù)據(jù)通信可靠性的影響，用式（11）和（6）計算通信能耗和轉(zhuǎn)換能耗，選擇通信能耗最少的路徑，然后依次選擇路由路徑.

算法3 路由算法

3 性能評價

為了驗證設(shè)計方案的性能，將6個具體應(yīng)用實例映射到NoC系統(tǒng)結(jié)構(gòu)上.把VOPD［13］（video object plane decoder）和MMS［14］（H263 編／解碼器、MP3編／解碼器）兩種應(yīng)用映射到4×4和5×5 NoC二維Mesh拓撲結(jié)構(gòu)上.采取同樣的方式，把E3S［15］中consumer、networking、auto－industry和telecom 等應(yīng)用實例分別映射到3×3、3×3、4×4 和5×5NoC二維Mesh拓撲結(jié)構(gòu)上.

將本文VFI－ARQ 方法與下列3種方法進行了比較：

（1）VFI－P：第一次提出電壓島設(shè)計方法［3］；

（2）VFI－R：基于電壓島感知設(shè)計方法［4］；

（3）VFI－S：基于整數(shù)線性規(guī)劃設(shè)計方法［7］.

對6個應(yīng)用實例在白噪聲δ和供應(yīng)電壓取不同值的情況下做了3組實驗.實驗結(jié)果以VFI－P算法的電壓島優(yōu)化結(jié)果為標準，進行歸一化處理.第一組實驗用比較大的供應(yīng)電壓V1＝｛1.5，1.6，1.7，1.8，1.9，2.0｝V，在白噪聲δ1＝0.1情況下比較各種方法，系統(tǒng)能耗比較如圖1所示.第二組實驗在供應(yīng)電壓V1＝｛1.5，1.6，1.7，1.8，1.9，2.0｝V 不變和δ2＝0.2情況下比較各種方法，系統(tǒng)能耗比較如圖2所示.第三組實驗在δ1＝0.1，但是供應(yīng)電壓比較小，即V2＝｛0.6，0.8，0.9，1.0，1.2，1.5｝V 的情況下比較各種設(shè)計方法，能耗比較如圖3所示.

圖1 能量消耗比較（δ1，V1）Fig.1 Energy consumption comparison for（δ1，V1）

圖2 能量消耗比較（δ2，V1）Fig.2 Energy consumption comparison for（δ2，V1）

圖3 能量消耗比較（δ1，V2）Fig.3 Energy consumption comparison for（δ1，V2）

從圖1～3可以看出，在基于電壓島NoC 系統(tǒng)中，考慮數(shù)據(jù)傳輸可靠性的情況下，供應(yīng)電壓數(shù)值越小，數(shù)據(jù)傳輸可靠性越差，要求重新傳輸?shù)拇螖?shù)就越多，本文的設(shè)計方法更有效.在其他參數(shù)相同的情況下，噪聲越大，數(shù)據(jù)傳輸可靠性越小，本文的設(shè)計方法同樣表現(xiàn)出明顯的優(yōu)勢.

本文在考慮數(shù)據(jù)重傳的基礎(chǔ)上，設(shè)計了新的降低系統(tǒng)能耗的方案VFI－ARQ.與VFI－P、VFIR、VFI－S 方案比較表明，系統(tǒng)能耗平均降低了17%、11%、7%.VFI－P方案只是考慮相鄰電壓島的合并問題，沒有考慮不相鄰的電壓島合并問題，容易形成電壓孤島的現(xiàn)象.所以在VFI－P 方案中，會造成更多系統(tǒng)能量的消耗.方案VFI－S 和VFI－R 雖然考慮了電壓孤島的現(xiàn)象，也分析了電壓孤島產(chǎn)生的原因，有進一步降低系統(tǒng)能耗的效果，但是沒有考慮IP核可以從低電壓島往高電壓島移動的問題，所以降低NoC整體能耗的效果不明顯.本文在電壓島劃分問題上不僅考慮了IP核的計算能耗，還考慮了IP核之間數(shù)據(jù)在重傳下的通信能耗問題和電壓孤島等問題，實驗結(jié)果表明該設(shè)計方案能有效地降低系統(tǒng)能耗.

4 結(jié) 語

已有的NoC映射設(shè)計方法中，沒有考慮供應(yīng)電壓對數(shù)據(jù)傳輸重傳的影響.本文將供應(yīng)電壓對通信數(shù)據(jù)誤碼率的傳輸模型引入NoC 設(shè)計方法中，改進數(shù)據(jù)傳輸能耗模型.實驗結(jié)果表明在多級電壓NoC模型中，考慮供應(yīng)電壓對數(shù)據(jù)傳輸可靠性的影響，能很好地優(yōu)化數(shù)據(jù)通信能耗.下一步的研究工作主要在數(shù)據(jù)重傳情況下電壓島分配機制中延長NoC系統(tǒng)的生存周期.

［1］ Dally W J，Towles B.Route packets，not wires：onchip interconnection networks ［C］／／ Design Automation Conference 2001，June 18－22，2001，Las Vegas，Nevada，USA.New York：ACM，2001：683－689.

［2］ Ye T T，Benini L，De Micheli G.Analysis of power consumption on switch fabrics in network routers［C］／／ The 39th Annual Design Automation Conference，June 10－14，2002，New Orleans，Louisiana，USA.New York：ACM，2002：524－529.

［3］ Ogras U Y，Marculescu R，Choudhary P，etal.Voltage－frequency island partitioning for GALSbased networks－on－chip ［C］／／The 44th Annual Design Automation Conference，June 4－8，2007，San Diego，California，USA.New York：ACM，2007：110－115.

［4］ Jang W，Ding D，Pan D Z.A voltage－frequency island aware energy optimization framework for networks－on－chip ［C］ ／／ 2008 IEEE／ACM International Conference on Computer－Aided Design.Piscataway：IEEE，2008：264－269.

［5］ 常政威，熊光澤，桑 楠，等.基于電壓島的能量和可靠性感知NoC映射［J］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，2009，21（1）：19－26.CHANG Zheng－wei，XIONG Guang－ze，SANG Nan，etal.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）

［6］ 張劍賢，周 端，楊銀堂，等.處理器可靠性約束的電壓頻率島NoC 能耗優(yōu)化［J］.電子與信息學(xué)報，2011，33（9）：2205－2211.ZHANG Jian－xian，ZHOU Duan，YANG Yin－tang，etal.Energy optimization of NoC based on voltagefrequency islands under processor reliability constraints ［J］.Journal of Electronics ＆Information Technology，2011，33（9）：2205－2211.（in Chinese）

［7］ Ghosh P，Sen A.Efficient mapping and voltage islanding technique for energy minimization in NoC under design constraints ［C］／／The 2010 ACM Symposium on Applied Computing.New York：ACM，2010：535－541.

［8］ Raghunathan V，Srivastava M B，Gupta R K.A survey of techniques for energy efficient on－chip communication ［C］／／ The 40th Annual Design Automation Conference，June 2－6，2003，Anaheim，California，USA.New York：ACM，2003：900－905.

［9］ Varatkar G，Marculescu R.Traffic analysis for onchip networks design of multimedia applications［C］／／ The 39th Annual Design Automation Conference，June 10－14，2002，New Orleans，Louisiana，USA.New York：ACM，2002：795－800.

［10］ Bertozzi D，Benini L，De Micheli G.Error control schemes for on－chip communication links：the energy－reliability tradeoff［J］.IEEE Transactions on Computer－Aided Design of Integrated Circuits and Systems，2005，24（6）：818－831.

［11］ YU Qiao－yan，Ampadu P.A flexible parallel simulator for networks－on－chip with error control［J］.IEEE Transactions on Computer－Aided Design of Integrated Circuits and Systems，2010，29（1）：103－116.

［12］ Palesi M，Holsmark R，Kumar S，etal.Application specific routing algorithms for networks on chip ［J］.IEEE Transactions on Parallel and Distributed Systems，2009，20（3）：316－330.

［13］ Moein－Darbarila F，Khademzade A，Gharooni－Fard G.CGMAP：a new approach to network－on－chip mapping problem ［J］.IEICE Electronics Express，2009，6（1）：27－34.

［14］ HU Jing－cao，Marculescu R.Energy－aware mapping for tile－based NoC architectures under performance constraints［C］／／The 2003Asia and South Pacific Design Automation Conference，January 24，2003，Kitakyushu，Japan.New York：ACM，2003：233－239.

［15］ Dick R.Embedded system synthesis benchmarks suites（E3S）［EB／OL］.［2013－01－25］.http：／／www.ece.northwestern.edu／～dickrp／e3s／.