0 引言

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

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

    本文在MANDELLI M等人所提出的層次化結構以及固定分簇的基礎上，加入了核級容錯機制的設計，其中包括初始片上分簇管理方案，以及動態重分簇方案的設計。

1 NoC分簇方案設計

1.1 層次化管理方案設計

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

1.2 參數定義及選擇

    (1)相對管理開銷

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

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

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

    對于采用2D Mesh拓撲結構的網絡，對于片上坐標分別為(a，b)，(c，d)的兩個IP核t_ab和t_cd，它們的曼哈頓距離等于兩個核之間的最小跳步數為式(2)：

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

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

    (4)全局管理者的放置

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

    (5)簇尺寸的確定

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

    (6)局部管理者的放置

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

    (7)容錯問題的提出

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

則刪掉一個簇。

    (8)通信功耗模型

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

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

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

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

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

2 片上重分簇方案設計

2.1 簇區域重劃分算法設計

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

2.2 簇填充策略及遍歷順序設計

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

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

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

2.3 局部管理者的選舉

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

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

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

3 實驗結果及對比分析

3.1 與隨機分簇算法的比較

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

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

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

    將這10 000次的分簇結果取平均，結果如表2所示，區域重劃分算法比隨機分簇算法AMD_chip平均值減少3.9%，區域重劃分算法的執行結果要優于隨機分簇算法。

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

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

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

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

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

4 結論

    本文針對眾核芯片的片上資源劃分和管理問題，基于固定分簇方案加入核級容錯機制的設計，設計了區域重劃分算法，以平均曼哈頓距離為約束目標，利用MATLAB實現了該區域重劃分算法，模擬實驗結果表明，該算法的平均曼哈頓距離比隨機分簇算法和冗余核行列替換算法都要小，而且在故障注入數目較多的情況下，所得的平均曼哈頓距離相比其他兩種算法具有顯著的減少，采用此算法可以降低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.