0 引言

    在半導體行業(yè)中，多核處理器片上系統(tǒng)(Multiprocessors System-on-Chip，MPSoC)的設(shè)計是一個明顯的趨勢，根據(jù)國際半導體技術(shù)藍圖預測^[1]，在2025年MPSoC上可能達到集成1 000個處理核心的眾核的規(guī)模。日益增加的核心數(shù)目引出了一個重要的問題：系統(tǒng)的可擴展性。盡管采用片上網(wǎng)絡(luò)能夠提供一定的可擴展性，眾核芯片的片上資源還需要有效管理以提供預期的性能^[2]。傳統(tǒng)的管理方案采用集中式管理，然而這種單一管理者的模式在片上核心數(shù)目逐漸增多時會遇到瓶頸，因為該管理核心的計算任務(wù)將會變得極為龐大，而且由于其需要與片上所有其他核心進行通信，會導致其周圍形成通信的熱點(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等人提出了基于應用的實時分簇方案，當有新應用提出運行請求時，一個負責分簇的任務(wù)被激活，該任務(wù)獲取應用的需求并依次將整個網(wǎng)絡(luò)劃分為簇，此時，與應用需求匹配的簇被選中，并由該簇內(nèi)的一個區(qū)域管理者完成映射算法。MANDELLI M等人在此層次化結(jié)構(gòu)上進行了改進^[4]，提出了三級管理方案。不同于之前提出的基于應用的動態(tài)實時分簇，他們提出了一種固定的片上分簇管理模式。全局管理者從應用池中獲取待執(zhí)行應用的信息，并將其轉(zhuǎn)包給有空余計算資源的局部管理者，具體的任務(wù)映射由LMP對其從屬核心進行，其分簇方案采取固定簇尺寸的分簇，GMP作為比LMP高一級的管理者，同樣也要執(zhí)行LMP全部的工作并且還對LMP進行管理。這種管理結(jié)構(gòu)將任務(wù)映射從單一的GMP轉(zhuǎn)移到了多個LMP上，加快了任務(wù)映射的速度，也減輕了GMP的任務(wù)量，但是固定分簇管理模式并沒有考慮在片上發(fā)生核心損壞時的容錯方案。

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

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

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

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

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

    (1)相對管理開銷

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

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

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

    對于采用2D Mesh拓撲結(jié)構(gòu)的網(wǎng)絡(luò)，對于片上坐標分別為(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ū)域進行重新劃分，即重分簇。當系統(tǒng)的可用處理核心數(shù)目減少，而簇的數(shù)量并沒有減少以及簇管理者的數(shù)目沒有減少，這就導致了系統(tǒng)管理開銷的上升，而當損壞的核心數(shù)目達到一個簇的容量時，可以通過刪除一個簇來降低系統(tǒng)的管理開銷。即當前簇的數(shù)量為n，簇容量為s，當前正常工作的核心數(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é)點間的曼哈頓距離正相關(guān)。

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

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

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

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

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

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

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

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

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

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

2.3 局部管理者的選舉

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

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

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

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

3.1 與隨機分簇算法的比較

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

參考文獻

[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.