《電子技術應用》
您所在的位置:首頁 > 嵌入式技術 > 設計應用 > 眾核片上資源動態劃分與管理研究
眾核片上資源動態劃分與管理研究
2018年電子技術應用第1期
賈民政1,付方發2
1.北京工業職業技術學院 電氣與信息工程學院,北京100042;2.哈爾濱工業大學 微電子中心,黑龍江 哈爾濱150001
摘要: 為了提高芯片的可擴展性多采用基于NoC的分簇管理方案,現有的基于應用的動態實時分簇管理方案已有較深入的研究,然而關于固定分簇方案的研究較為缺乏,包括在該方案下的核級容錯策略。在此背景下設計了一種基于固定分簇方案的核級容錯策略,提出了片上區域重劃分算法,并完成了芯片的MATLAB建模及實現。進行了故障注入實驗,將區域重劃分算法與隨機分簇算法就分簇后的片上平均曼哈頓距離進行比較,得到了比較好的結果,加入側邊冗余核之后,將區域重劃分算法與工程常用的行列替換策略進行比較,結果也表明該算法優于行列替換策略。
中圖分類號: TN47
文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.172089
中文引用格式: 賈民政,付方發. 眾核片上資源動態劃分與管理研究[J].電子技術應用,2018,44(1):24-27.
英文引用格式: Jia Minzheng,Fu Fangfa. Research on the dynamic division and management of resources on multiprocessor system-on-chip[J]. Application of Electronic Technique,2018,44(1):24-27.

Research on the dynamic division and management of resources on multiprocessor system-on-chip
Jia Minzheng1,Fu Fangfa2
1.Department of Information Engineering,Beijing Polytechnic College,Beijing 100042,China; 2.Microelectronics Center,Harbin Institute of Technology,Harbin 150001,China
Abstract: To increase the scalability of cores, many methods are used, including Network on Chip(NoC) and cluster-based distributed management scheme. The application-based re-clustering algorithm has been delved deeply, while fixed-sized cluster is less developed, including the core-level fault tolerant scheme under such method. Under such environment, a re-clustering scheme based on fixed-sized cluster was proposed in order to achieve fault tolerance, including dynamic re-clustering algorithm. This modeling of chip was finished on MATLAB, and the proposed dynamic re-clustering algorithm was compared with several other algorithms. Core error injections were did and the Average Manhattan Distance(AMD) of the dynamic re-clustering algorithm was compared with random re-clustering algorithm. The results show that the dynamic re-clustering algorithm is far better than random re-clustering algorithm. Then backup cores to the side of the chip were added, and the dynamic re-clustering algorithm was compared with the same-row-replacing algorithm what was commonly used in industry. The dynamic re-clustering algorithm still shows advantages.
Key words : MPSoC;Network on Chip(NoC);re-clustering algorithm;core-level fault tolerance; redundancy cores

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)的任務映射。考慮到芯片上初始簇劃分的規整性,決定將全局管理者作為一個特殊的局部管理者來使用。

wdz5-t1.gif

1.2 參數定義及選擇

    (1)相對管理開銷

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

    wdz5-gs1.gif

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

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

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

    wdz5-gs2.gif

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

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

    wdz5-gs3.gif

    (4)全局管理者的放置

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

    (5)簇尺寸的確定

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

    (6)局部管理者的放置

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

wdz5-b1.gif

    (7)容錯問題的提出

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

    wdz5-gs4.gif

則刪掉一個簇。

    (8)通信功耗模型

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

    wdz5-gs5.gif

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

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

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

    wdz5-gs6.gif

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

2 片上重分簇方案設計

2.1 簇區域重劃分算法設計

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

wdz5-t2.gif

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

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

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

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

2.3 局部管理者的選舉

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

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

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

3 實驗結果及對比分析

3.1 與隨機分簇算法的比較

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

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

    wdz5-gs7.gif    

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

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

wdz5-b2.gif

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

wdz5-t3.gif

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

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

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

wdz5-b3.gif

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

wdz5-t4.gif

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.

此內容為AET網站原創,未經授權禁止轉載。
主站蜘蛛池模板: 欧美 日本 亚洲 | 日韩高清免费观看 | 欧美大胆性生话 | 日日干狠狠| 无遮挡h黄漫画免费观看 | 欧美亚洲国产精品久久 | 亚洲三级a | 日本欧美在线观看 | 欧美香蕉 | 欧美1区2区3区 | 19国产精品麻豆免费观看 | 成人免费高清视频 | 久99久爱精品免费观看视频 | 欧美亚洲激情 | 国产女女互摸互慰在线观看 | 欧美日韩一区二区中文字幕视频 | 一级特黄录像免费播放中文版 | 热99在线视频 | 天堂资源网 | 亚洲h片| 国产欧美日韩不卡一区二区三区 | 国产a久久精品一区二区三区 | 欧美人善交vides0 | 国产伦精品一区二区三区 | 曰本三级香港三级三级人 | 日韩一区二区三区精品 | 中国毛片基地 | 国产 另类 在线 欧美日韩 | 欧美成人看片一区二区三区尤物 | 日韩三级伦理 | 甜性涩爱免费看 | 欧美福利在线 | 欧美性群另类大交人妖 | 免费国产成人手机在线观看 | 91短视频版在线观看免费大全 | 91福利国产在线观看一区二区 | 91欧洲在线视精品在亚洲 | 亚洲乱人伦精品图片 | 国产精品久久久久久久 | 1级黄色录像 | 美女视频很黄很暴黄是免费的 |