0 引言

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

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

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

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

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

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

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

    (1)相對(duì)管理開(kāi)銷(xiāo)

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

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

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

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

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

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

    (4)全局管理者的放置

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

    (5)簇尺寸的確定

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

    (6)局部管理者的放置

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

    (7)容錯(cuò)問(wèn)題的提出

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

則刪掉一個(gè)簇。

    (8)通信功耗模型

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

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

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

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

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

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

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

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

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

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

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

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

2.3 局部管理者的選舉

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

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

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

3 實(shí)驗(yàn)結(jié)果及對(duì)比分析

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

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

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

    基于9×9的芯片與3×3的簇尺寸，進(jìn)行了故障注入實(shí)驗(yàn),通過(guò)10 000次的分簇實(shí)驗(yàn)，區(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ī)分簇算法。

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

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

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

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

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

4 結(jié)論

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

參考文獻(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.