0 引言

    在半導(dǎo)體行業(yè)中,，多核處理器片上系統(tǒng)(Multiprocessors System-on-Chip,，MPSoC)的設(shè)計是一個明顯的趨勢，根據(jù)國際半導(dǎo)體技術(shù)藍(lán)圖預(yù)測^[1],，在2025年MPSoC上可能達(dá)到集成1 000個處理核心的眾核的規(guī)模,。日益增加的核心數(shù)目引出了一個重要的問題：系統(tǒng)的可擴(kuò)展性。盡管采用片上網(wǎng)絡(luò)能夠提供一定的可擴(kuò)展性,，眾核芯片的片上資源還需要有效管理以提供預(yù)期的性能^[2],。傳統(tǒng)的管理方案采用集中式管理，然而這種單一管理者的模式在片上核心數(shù)目逐漸增多時會遇到瓶頸,，因為該管理核心的計算任務(wù)將會變得極為龐大，而且由于其需要與片上所有其他核心進(jìn)行通信,，會導(dǎo)致其周圍形成通信的熱點(diǎn)(hot-spot)區(qū)域^[3-5],。

    為了解決多核管理帶來的問題，GUANG L等人提出了一種層次化的自監(jiān)測方法^[2],，他們把監(jiān)測劃分為第三個維度,，在原有的系統(tǒng)中添加監(jiān)測層，使系統(tǒng)可以自我感知和自我管理,，然而并沒有對片上的簇具體如何劃分給出算法,，而且平臺管理者需要完成所有的任務(wù)調(diào)度，其實際的計算任務(wù)依舊很大,。Ana gnos topoulos.I等人提出了基于應(yīng)用的實時分簇方案,，當(dāng)有新應(yīng)用提出運(yùn)行請求時，一個負(fù)責(zé)分簇的任務(wù)被激活,，該任務(wù)獲取應(yīng)用的需求并依次將整個網(wǎng)絡(luò)劃分為簇,，此時，與應(yīng)用需求匹配的簇被選中,，并由該簇內(nèi)的一個區(qū)域管理者完成映射算法,。MANDELLI M等人在此層次化結(jié)構(gòu)上進(jìn)行了改進(jìn)^[4],，提出了三級管理方案。不同于之前提出的基于應(yīng)用的動態(tài)實時分簇,，他們提出了一種固定的片上分簇管理模式,。全局管理者從應(yīng)用池中獲取待執(zhí)行應(yīng)用的信息，并將其轉(zhuǎn)包給有空余計算資源的局部管理者,，具體的任務(wù)映射由LMP對其從屬核心進(jìn)行,，其分簇方案采取固定簇尺寸的分簇，GMP作為比LMP高一級的管理者,，同樣也要執(zhí)行LMP全部的工作并且還對LMP進(jìn)行管理,。這種管理結(jié)構(gòu)將任務(wù)映射從單一的GMP轉(zhuǎn)移到了多個LMP上，加快了任務(wù)映射的速度,，也減輕了GMP的任務(wù)量,，但是固定分簇管理模式并沒有考慮在片上發(fā)生核心損壞時的容錯方案。

    本文在MANDELLI M等人所提出的層次化結(jié)構(gòu)以及固定分簇的基礎(chǔ)上,，加入了核級容錯機(jī)制的設(shè)計,，其中包括初始片上分簇管理方案，以及動態(tài)重分簇方案的設(shè)計,。

1 NoC分簇方案設(shè)計

1.1 層次化管理方案設(shè)計

    為了提高眾核芯片的可擴(kuò)展性,，采用層次化管理方案，如圖1所示,。第一級核心負(fù)責(zé)整個系統(tǒng)的監(jiān)測,并且執(zhí)行簇的選擇,，將待執(zhí)行應(yīng)用轉(zhuǎn)包給第二級核心。第二級核心完成具體的任務(wù)映射,，同時逐級返回任務(wù)分配請求給GM(Global Manager),，GM完成最終的任務(wù)分配。當(dāng)有新應(yīng)用向系統(tǒng)提出執(zhí)行請求時系統(tǒng)首先通過應(yīng)用池(Application Repository)將應(yīng)用的需求提供給第一級核心GM,，GM根據(jù)第二級核心LM(Local Manager)反饋的系統(tǒng)資源占用情況,，選擇LM進(jìn)行轉(zhuǎn)包，LM完成對其下屬的第三級核心PE(Processing Element)的任務(wù)映射,?？紤]到芯片上初始簇劃分的規(guī)整性，決定將全局管理者作為一個特殊的局部管理者來使用,。

1.2 參數(shù)定義及選擇

    (1)相對管理開銷

    對于本文所采用的分簇管理方案,，片上核心中只有部分核心能夠處理用戶任務(wù)，而一部分核心需要承擔(dān)系統(tǒng)的管理任務(wù),。這里定義系統(tǒng)的相對管理開銷p為式(1)：

    其中,，M為非管理核心數(shù)目，N為片上所有可用核心數(shù)目,。

    (2)曼哈頓距離(Manhattan Distance,，MD)

    對于采用2D Mesh拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò),，對于片上坐標(biāo)分別為(a，b),，(c,，d)的兩個IP核t_ab和t_cd，它們的曼哈頓距離等于兩個核之間的最小跳步數(shù)為式(2)：

    (3)平均曼哈頓距離(Average Manhattan Distance,，AMD)

    為了表示某個簇的聚攏程度,，定義簇的平均曼哈頓距離。簇內(nèi)每個核心到其他核心的曼哈頓距離的平均值求出后,，再對這些均值求平均,，即得到簇的平均曼哈頓距離。設(shè)簇內(nèi)有n個核心t₁,，t₂,，…，t_n,，則該簇的平均曼哈頓距離為式(3)：

    (4)全局管理者的放置

    作為唯一與外部設(shè)備相連的處理核心,，通常被放置在芯片的某一角，此處選擇放在左上角,。

    (5)簇尺寸的確定

    由于簇尺寸大小直接關(guān)系到片上相對管理開銷的大小,。一般而言，相對管理開銷在15%以下,，平均曼哈頓距離在3以下都是可以接受的范圍,，這里選擇3×3的簇尺寸。

    (6)局部管理者的放置

    局部管理者的位置關(guān)系到簇內(nèi)通信的效率,對于簇內(nèi)不同位置的核心,，其距離簇內(nèi)其他核心的曼哈頓距離的平均值如表1所示,。為提高簇內(nèi)的通信效率，將局部管理者設(shè)置在簇的中間位置,。

    (7)容錯問題的提出

    在片上一些處理核心損壞之后，系統(tǒng)的每個簇也就變得不規(guī)整,，所以需要對簇區(qū)域進(jìn)行重新劃分,，即重分簇。當(dāng)系統(tǒng)的可用處理核心數(shù)目減少,，而簇的數(shù)量并沒有減少以及簇管理者的數(shù)目沒有減少,，這就導(dǎo)致了系統(tǒng)管理開銷的上升，而當(dāng)損壞的核心數(shù)目達(dá)到一個簇的容量時,，可以通過刪除一個簇來降低系統(tǒng)的管理開銷,。即當(dāng)前簇的數(shù)量為n，簇容量為s,，當(dāng)前正常工作的核心數(shù)量為Na,，若：

則刪掉一個簇,。

    (8)通信功耗模型

    通常對于NoC的通信功耗采用按位計量能量模型。對于片上任意一條有向的邊(directed edge)e_ij,，每傳輸一位數(shù)據(jù)所消耗的能量為式(5)：

    MD(e_ij)為核心v_i到v_j的曼哈頓距離,，E_Rbit代表每傳輸一位數(shù)據(jù)在路由上(包括交叉式開關(guān)和讀寫緩沖區(qū))所消耗的能量，E_link代表每傳輸一位數(shù)據(jù)在鏈路上所消耗的能量,，E_Rbit和E_link對于某個給定的芯片均為常數(shù),。由式(5)可以看出，片上通信功耗與通信節(jié)點(diǎn)間的曼哈頓距離正相關(guān),。

    (9)計算核心損壞概率模型

    對于片上的計算核心的損壞概率,，單個核心的損壞概率可以采用美國國防部發(fā)布的《電子設(shè)備可靠性預(yù)計手冊》中所定義的模型加上Arrhenius模型中引入的溫度參數(shù)對原模型進(jìn)行的修正，可得：

    其中E為過程中的激活能,，K是玻爾茲曼常數(shù),，T是絕對溫度。A為一常數(shù),，其取值應(yīng)當(dāng)使核心在正常工作溫度下每周期的損壞概率在10^-9,。

2 片上重分簇方案設(shè)計

2.1 簇區(qū)域重劃分算法設(shè)計

    整個重分簇方案分兩步進(jìn)行:對片上的簇進(jìn)行重新劃，對全局管理者和簇內(nèi)的局部管理者進(jìn)行重新選舉,。通常的解決方法是采用啟發(fā)式算法,這里采用的算法是基于現(xiàn)有的分簇結(jié)果來進(jìn)行重分簇,，單個簇的填充采用貪心算法，簇區(qū)域重劃分算法流程圖如圖2所示,。

2.2 簇填充策略及遍歷順序設(shè)計

    在2D Mesh下,，每個簇的最優(yōu)形狀應(yīng)該是正方形或逼近正方形，大小應(yīng)當(dāng)越小越好,，才能保證簇的平均曼哈頓距離為最小,，這即為貪心算法使用時的最優(yōu)量度標(biāo)準(zhǔn)。

    本文中對于某一個尚未填充滿的簇,，首先將覆蓋簇內(nèi)所有核心的最小的矩形劃分出來,，如果矩形內(nèi)有尚未分簇的處理核心，優(yōu)先將這些核心填充進(jìn)簇內(nèi),，若該矩形內(nèi)核心已全部填充完畢,，但簇仍未被填滿，此時將該矩形進(jìn)行擴(kuò)展,，此時又有兩種情況,。若矩形區(qū)域已為正方形，則將該區(qū)域向上下左右四個方向中的任意一個方向擴(kuò)展均可,；若矩形區(qū)域不是正方形,，則對于該區(qū)域較長的那一對邊所對應(yīng)的方向進(jìn)行擴(kuò)展，使得整個矩形的區(qū)域向正方形逼近經(jīng)過每一次擴(kuò)展,，矩形區(qū)域內(nèi)都有可能出現(xiàn)新的尚未分簇的處理核心,，依次將這些核心填充進(jìn)當(dāng)前簇直至填滿,這種單個簇填充策略是一種保證先填充簇的結(jié)構(gòu)最優(yōu)化的策略,。

    片上簇填充的遍歷順序依據(jù)上節(jié)提出的單個簇填充策略，對片上已有的所有簇進(jìn)行遍歷,，須遵循一定的順序,。這里采用一種以左上角為起點(diǎn)的折線形的順序來遍歷整個芯片，定義初始的橫向和縱向擴(kuò)展方向分別為向右和向下,。

2.3 局部管理者的選舉

    由于區(qū)域重新劃分后,，原有的任務(wù)映射結(jié)構(gòu)被改變，各個簇與全局管理者的通信量難以進(jìn)行采樣,，此時對于局部管理者的選舉可以忽略掉全局管理者的影響,。

    而片上的通信功耗依據(jù)按位計量能量模型^[6]，每跳步數(shù)耗能量與傳輸數(shù)據(jù)的位數(shù)成正比,。要降低簇內(nèi)通信功耗,，必須要求局部管理者到簇內(nèi)其他處理核心的跳步數(shù)最少，即距離其他核心的曼哈頓距離之和為最小,。

    由于簇內(nèi)核心數(shù)目不是很多,，這里可以采用窮舉搜索的方法，以確定簇內(nèi)距離其他核心的曼哈頓距離之和最小的核心,，將其選舉為局部管理者,。之前標(biāo)記過的簇由于含有全局管理者，所以不參與局部管理者的選舉,。

3 實驗結(jié)果及對比分析

3.1 與隨機(jī)分簇算法的比較

    隨機(jī)分簇算法采用與區(qū)域重劃分算法有相同的遍歷順序,，不同的是其在填充核心時是隨機(jī)選擇剩余可用核心進(jìn)行填充。

    由前述的核心損壞模型可知,，核心的損壞概率為常數(shù),，為了實驗的方便，本文將損壞概率設(shè)置為1/100,。分別利用區(qū)域重劃分算法與隨機(jī)分簇算法進(jìn)行分簇,，并計算每次分簇后芯片的平均曼哈頓距離。芯片的平均曼哈頓距離由式(7)給出,，其中c_i表示第i個簇,，為c_i內(nèi)可用核心數(shù)目，N為片上所有可用核心數(shù)目,。

    基于9×9的芯片與3×3的簇尺寸,，進(jìn)行了故障注入實驗,通過10 000次的分簇實驗,，區(qū)域重劃分算法的執(zhí)行結(jié)果基本都在2.2以下,，最高僅達(dá)到了2.35。而隨機(jī)分簇算法,，其平均執(zhí)行結(jié)果在2.4到2.6左右,，最高達(dá)到了3.5左右,。

    將這10 000次的分簇結(jié)果取平均，結(jié)果如表2所示,，區(qū)域重劃分算法比隨機(jī)分簇算法AMD_chip平均值減少3.9%,，區(qū)域重劃分算法的執(zhí)行結(jié)果要優(yōu)于隨機(jī)分簇算法。

    為了驗證區(qū)域重劃分算法對于較多核心損壞時是否能夠有較好的分簇結(jié)果,，本文進(jìn)行了不同數(shù)目的故障注入,。損壞概率仍然設(shè)置為1/100，對于一個眾核芯片而言,，損壞20%以上的核心認(rèn)為是比較嚴(yán)重的損壞,，注入時的數(shù)目選取1到20個故障(1.2%-24.7%)來進(jìn)行實驗，注入完成后分別利用區(qū)域重劃分算法與隨機(jī)分簇算法進(jìn)行分簇,，并計算每次分簇后芯片的平均曼哈頓距離,，分簇后所得的結(jié)果對比如圖3所示，可以看出區(qū)域重劃分算法明顯優(yōu)于隨機(jī)分簇算法,。

3.2 與冗余核行列替換策略的比較

    實際工程中,，為了保證芯片能夠?qū)崿F(xiàn)核級的容錯，片上的冗余核是必不可少的,，這里采用工程上常用的行列替換的冗余核替換策略與本文提出的區(qū)域重劃分算法進(jìn)行比較,。

    冗余核行列替換策略采用距離最近的冗余核進(jìn)行替換。本文在芯片的最右側(cè)那一列放置一列共計9個冗余核,，將損壞概率設(shè)置為1/100,，進(jìn)行10 000次隨機(jī)注入，分別利用區(qū)域重劃分算法與橫向冗余核替換策略進(jìn)行實驗,，并計算每次分簇后芯片的平均曼哈頓距離,，將10 000次的結(jié)果取平均，結(jié)果如表3所示,，區(qū)域重劃分算法比行列替換算法AMDchip平均值減少1.85%,。

    與3.1類似，進(jìn)行不同數(shù)目的故障注入,，損壞概率仍然設(shè)置為1/100,，由于只放置了9個冗余核，故注入故障數(shù)目為1到9,，每種數(shù)目的故障進(jìn)行500次隨機(jī)注入,。注入完成后分別利用區(qū)域重劃分算法與行列替換算法進(jìn)行分簇，并計算每次分簇后芯片的平均曼哈頓距離,，分簇后所得的結(jié)果對比數(shù)據(jù)如圖4所示,，可以看出區(qū)域重劃分算法優(yōu)于行列替換算法。

4 結(jié)論

    本文針對眾核芯片的片上資源劃分和管理問題，基于固定分簇方案加入核級容錯機(jī)制的設(shè)計,，設(shè)計了區(qū)域重劃分算法,，以平均曼哈頓距離為約束目標(biāo)，利用MATLAB實現(xiàn)了該區(qū)域重劃分算法,，模擬實驗結(jié)果表明,，該算法的平均曼哈頓距離比隨機(jī)分簇算法和冗余核行列替換算法都要小，而且在故障注入數(shù)目較多的情況下,，所得的平均曼哈頓距離相比其他兩種算法具有顯著的減少,，采用此算法可以降低NoC的通信功耗，具有實際應(yīng)用價值,。

參考文獻(xiàn)

[1] VAJDA A.Programming Many-Core Chips[M].Springer US,，2011.

[2] GUANG L，NIGUSSIE E,，RANTALA P,，et al.Hierarchical agent monitoring design approach towards self-aware parallel systems-on-chip[J].Acm Transactions on Embedded Computing Systems，2010,，9(3)：177-185.

[3] LIAO X,，SRIKANTHAN T.A scalable strategy for runtime resource management on NoC based manycore systems[C]//International Symposium on Integrated Circuits.IEEE，2011：297-300.

[4] MANDELLI M,，CASTILHOS G M,，MORAES F G.Enhancing performance of MPSoCs through distributed resource management[C]//IEEE International Conference on Electronics，Circuits and Systems,，2012：544-547.

[5] CHOU C L,，MARCULESCU R.FARM：Fault-aware resource management in NoC-based multiprocessor platforms[J].Design Automation & Test in Europe，2011：1-6.

[6] YE T T,，BENINI L,，DE MICHELI G.Analysis of power consumption on switch fabrics in network routers[M].2002.