吳 倩，王小航

（華南理工大學軟件學院，廣州 510006）

1 引言

隨著計算需求的不斷增長，眾核系統(tǒng)得到廣泛應用，單個芯片上集成的處理器核多達數(shù)十到數(shù)百個。在應用執(zhí)行任務之前，資源管理器需按照特定算法為各個任務選擇執(zhí)行指令的處理器核，即分配處理器核給該應用，該過程稱為任務映射，所使用的算法稱為任務映射算法。任務映射直接影響芯片性能。

任務映射需考慮通信延時。任務映射直接決定運行任務的處理器核之間的距離，若將兩個相互間數(shù)據(jù)通信量較大的任務映射至相距較遠的處理器核，會導致通信延遲增大。所以任務映射需考慮任務間的通信距離。

任務映射需考慮系統(tǒng)功耗。處理器核功耗過高，容易降低處理器核的可靠性和壽命。此外，功耗過高，容易使得處理器核溫度過高，增加冷卻成本。

任務映射需考慮處理器核可靠性。如果在任務映射時不考慮可靠性，會導致某些處理器核的老化速度比其他處理器核快，使之成為系統(tǒng)可靠性瓶頸。

任務映射需考慮處理器核溫度。任務映射直接影響芯片熱分布，例如將高計算需求的任務映射至連續(xù)區(qū)域，在功率密度大的系統(tǒng)中，容易使得系統(tǒng)產(chǎn)生熱點（芯片局部溫度過高）。因此，在設計任務映射算法時需考慮芯片溫度。

任務映射算法可從以下角度進行分類和分析：根據(jù)是否可以在線實時為應用選擇處理器核對任務映射算法進行分類[1]；從應用軟硬實時要求角度對任務映射算法進行比較[2]；從應用映射的處理器區(qū)域連續(xù)與否討論映射區(qū)域?qū)θ蝿沼成涞挠绊慬3]；從任務是否可重映射的角度討論現(xiàn)有任務映射算法的優(yōu)劣[4]。本文從系統(tǒng)架構和任務映射算法目標兩個角度對現(xiàn)有任務映射算法進行分析。

2 任務映射算法

2.1 任務映射過程

任務映射過程如圖1所示。在任務映射算法研究中，通常采用任務圖（加權有向無環(huán)圖）來表示一個應用，如圖1(b)所示。圖1(b)所示的應用有4個任務，每個任務的權重表示該任務需執(zhí)行的指令數(shù)/執(zhí)行時間。任務之間用有向邊相連，其方向表示數(shù)據(jù)傳輸?shù)姆较?，邊的權重表示傳送的?shù)據(jù)包數(shù)量。應用開始運行前，需資源管理器按照特定算法為它的各個任務選擇執(zhí)行指令的處理器核，即分配處理器核給該應用，該過程稱為任務映射。

圖1 任務映射

2.2 任務映射算法分類

2.2.1 二維片上網(wǎng)絡

1）優(yōu)化通信的任務映射算法

應用任務間具有通信，任務映射時需考慮任務映射位置，減少處理器核間的通信距離，進而減少應用執(zhí)行時間。

FATTAH等人[1]提出一種CoNA算法，該方法首先選擇距離資源管理器最近、具有4個空閑鄰居處理器核的處理器核(文中稱為第一節(jié)點)，然后將具有最大通信量的任務映射到第一節(jié)點上，接著圍繞第一節(jié)點建立連續(xù)區(qū)域以映射應用的其余任務。在CoNA算法的基礎上，F(xiàn)ATTAH等人[2]還提出了SHiC算法，該方法使用隨機爬山算法來估計一個處理器核的空閑相鄰處理器核數(shù)，從而快速確定最佳的第一節(jié)點。ANAGNOSTOPOULOS等人[3]針對可擴展的應用提出了一種工作負載感知的分布式框架，提高了處理器核利用率，同時減少了核間通信開銷。這些方法以最小化通信距離或降低網(wǎng)絡擁塞為目標，為應用選擇連續(xù)處理器區(qū)域。

通過將任務遷移至另一個處理器核（任務重映射）可降低處理器核的通信距離。NG等人[4]提出了一個評估碎片化程度的度量指標，并基于該指標提出了一個處理器核碎片整理方案。WANG等人[5]提出了一種重新定位應用處理器區(qū)域的碎片整理算法。PATHANIZ等人[6]將碎片整理問題轉(zhuǎn)換成一個可以在多項式時間內(nèi)求解的問題。這些方法通過將任務重新映射來獲得連續(xù)空閑區(qū)域，減少了后續(xù)應用通信開銷。

優(yōu)化通信的任務映射方法可降低應用通信延時和網(wǎng)絡擁塞，但是該類方法偏向于為應用選擇一個連續(xù)處理器區(qū)域。隨著處理器核不斷分配和釋放，優(yōu)化通信的任務映射算法會導致碎片化程度加重，迫使后續(xù)應用延遲執(zhí)行或系統(tǒng)需執(zhí)行碎片化整理。同時，優(yōu)化通信的任務映射方法，考慮芯片功率預算，容易使系統(tǒng)產(chǎn)生熱點，尤其是在功率密度大的系統(tǒng)中。

2）提高可靠性的任務映射算法

提高可靠性的任務映射算法可分為老化緩解算法和故障避讓算法。

關于老化緩解算法，隨著單芯片上集成的處理器核越來越多，芯片功率密度也不斷增大、溫度也迅速提升，導致器件老化和磨損速度加快，縮短了芯片使用時間。HUANG等人[7]提出了一個估計系統(tǒng)使用時間的可靠性模型，并基于該模型，采用模擬退火技術提出了一種感知處理器核可靠性的任務映射算法。WANG等人[8]通過對系統(tǒng)生命周期定量化建模，提出了一種考慮處理器核和物理鏈路老化程度的任務映射算法。WANG等人[9]在系統(tǒng)可靠性和溫度閾值約束下，結(jié)合輕量級溫度預測模型，提出了一種混合整數(shù)線性規(guī)劃模型，確定應用調(diào)度和映射方案。上述方法可為應用選擇連續(xù)區(qū)域。

關于故障避讓算法，為提高處理器可靠性，降低處理器故障，部分學者關閉部分處理器以降低處理器功率密度，選擇性能良好的處理器進行任務映射。關閉的處理器核被稱為暗核。KAPADIA等人[10]在系統(tǒng)可靠性和功率限制的約束下，提出了一種任務映射算法，該方法通過考慮芯片熱分布變化來確定應用的映射位置和處理器核的電壓頻率，從而提高應用的性能要求。KRIEBEL等人[11]在系統(tǒng)中集成了一組具有不同可靠性級別的處理器核，在滿足功耗約束條件下，考慮應用的可靠性級別，為應用選擇具有合適的可靠性級別的處理器核，進而為系統(tǒng)提供不同級別的保護。KAPADIA等人[12]提出了一個結(jié)合動態(tài)電壓頻率調(diào)整技術的資源管理框架，該框架為應用任務選擇映射位置時優(yōu)化系統(tǒng)性能和降低功耗，同時滿足處理器核的可靠性約束。上述方法只是簡單、機械地在功率約束下關閉系統(tǒng)一部分核心，而并沒有明確指出關閉哪些處理器核。

3）降低功耗的任務映射算法

SHAFIQUE等人[13]提出了一種快速確定系統(tǒng)最佳暗核集合（關閉哪些處理器核為暗核）以及確定任務與處理器核映射的任務映射算法。HOVEIDA等人[14]提出的HCPS方法嘗試在開啟的集群中爭取最高的處理器核利用率，從而可以關閉更多的集群以節(jié)省功耗。RAGHUNATHAN等人[14]基于排隊論估計應用在異構集群的執(zhí)行時間，為到達系統(tǒng)的應用選擇最佳集群，而其他的集群保持關閉狀態(tài)。BHARATHWAJ等人[15]提出在片上網(wǎng)絡中引入加速器來加速由于處理器核關閉而不能在規(guī)定時間內(nèi)完成的應用。上述算法[12-15]結(jié)合動態(tài)電壓頻率調(diào)整技術，使得系統(tǒng)在功率預算下運行。但是功率預算是在系統(tǒng)所有處理器核開啟以及最差任務空間分布下確定的值，將系統(tǒng)限制在功率預算下運行的方法過于保守。

圖2是8個處理器核開啟并且系統(tǒng)達到溫度閾值80℃時的芯片熱分布圖，實驗配置是4×4的片上網(wǎng)絡以及溫度模擬器Hotspot，圖2（a）所示分布的功率是53.6 W，圖2（b）所示分布的功率為61.2 W。因此，任務映射時，在應用處理器區(qū)域中包含部分關閉的處理器核可以降低處理器核功率密度。MUHAMMAD等人[16]提出了一種稱為PAT的任務映射算法，為應用選擇一個包含暗核的處理器區(qū)域，工作處理器核和暗核間隔放置，使得系統(tǒng)在高于功率預算下運行。KANDURI等人[17]在PAT的基礎上又提出了Adboost方法，通過利用合理分布暗核而獲得的額外功率加速了計算密集型應用的執(zhí)行。ANIL等人[18]提出的HCRS算法在實時計算功率的約束下，提高了集群處理器核的利用率。

圖2 芯片熱分布（圖中色度單位為℃）

4）優(yōu)化溫度的任務映射算法

芯片局部或全局過熱容易影響使用壽命。因此，學者們提出了以溫度為優(yōu)化目標的任務映射算法。

ANUP等人[19]綜合考慮瞬態(tài)溫度、穩(wěn)態(tài)溫度和處理器核溫度三個因素提出了一個溫度模型，并基于該模型確定了任務與處理器核的映射關系。THIDAPAT等人[20]提出了一種用于任務分配和調(diào)度的技術框架，該技術框架基于穩(wěn)態(tài)溫度來優(yōu)化芯片的峰值溫度。JUNLONG等人[21-22]考慮應用執(zhí)行時間和功耗兩個因素的時變特征，有效地將應用映射到處理器核上，最大程度減少了應用執(zhí)行時間。

為進一步降低系統(tǒng)溫度，學者們將任務從過熱的處理器核遷移到較冷的處理器核，以減少系統(tǒng)熱點或均衡處理器核溫度。MAJED等人[23]提出了基于分析歷史溫度數(shù)據(jù)的熱感知任務遷移機制。BAGHER等人[24]提出了一種基于處理器核熱行為的任務調(diào)度和任務遷移算法。YOUNG等人[25]提出了一種異構多核處理器的遷移算法，將應用遷移到小核，以便大核可以快速冷卻。

研究學者利用工作處理器核和暗核之間的溫度梯度均衡處理器核溫度。HANWOONG等人[26]利用指令級并行和線程級并行特性，提出了一種熱約束下的資源分配策略，可有效地確定工作處理器核和暗核數(shù)目。HANWOONG等人[27]提出了將暗核放置在工作處理器核周圍的模式資源映射方法，通過暗核和工作處理器核交錯分布的方式確定暗核位置。文獻[25-26]提出的方法是針對已知應用的，具有局限性。文獻[25，27-31]是在系統(tǒng)暗核數(shù)量固定的假設下設計的，事實上，暗核數(shù)會因為工作負載而不斷發(fā)生變化。

2.2.2 三維集成片上網(wǎng)絡

1）優(yōu)化通信的任務映射算法

相比于二維片上網(wǎng)絡，在三維片上網(wǎng)絡中，位于不同層的處理器核距離底層散熱器的距離不同，這直接導致了位于不同層的處理器核散熱能力不同。在三維片上網(wǎng)絡中，應用處理器區(qū)域垂直方向?qū)訑?shù)影響應用通信延時，例如在處理器核數(shù)目相等的條件下，處理器核均在同一層的處理器區(qū)域的平均通信延時會比垂直方向多層的處理器區(qū)域的高。因此，任務映射算法應考慮架構特性。

DING等人[32]提出了考慮層間和層內(nèi)通信的任務映射算法。MANNA等人[33]提出了基于線性規(guī)劃和粒子群優(yōu)化算法的任務映射機制。JHA等人[34]提出的任務遷移算法可減少兩個任務之間的通信跳數(shù)。該類算法以最小化處理器核間的通信距離為目標；只考慮通信一個因素，將任務映射至連續(xù)處理器區(qū)域，容易使系統(tǒng)產(chǎn)生熱點。

2）降低功耗的任務映射算法

AGYEMAN等人[35]針對異構三維集成片上網(wǎng)絡，提出了降低功耗和提升系統(tǒng)性能的任務映射算法。ELMILIGI[36]實現(xiàn)了使用遺傳算法搜索任務的映射位置。王源等人[37]針對非規(guī)則的三維集成片上網(wǎng)絡，提出了考慮系統(tǒng)通信功耗的任務映射方法，并設計了基于在線學習的啟發(fā)式任務映射算法。RAPARTI等人[38]以降低系統(tǒng)功耗為目標，利用量子粒子群算法確定了任務映射位置。然而，該類算法無法避免熱點。

3）優(yōu)化溫度的任務映射算法

三維集成片上網(wǎng)絡功率密度大，為此FENG等人[39]提出基于遺傳算法的任務映射算法，優(yōu)化芯片溫度。WANG等人[40]提出了一個異構三維集成片上網(wǎng)絡架構，并針對該架構提出了考慮系統(tǒng)運行溫度的任務映射算法和路由算法。DEMIRIZ等人[41]針對異構三維集成片上網(wǎng)絡提出了一種熱管理方案。MOSAYYEBZADEH等人[42]提出了優(yōu)化系統(tǒng)溫度和功耗的任務映射算法，在為應用選擇處理器區(qū)域時，考慮了任務間的通信量以及熱點等因素。LI等人[43]提出了一種降低應用通信延時、減少應用執(zhí)行時間的任務映射算法。

4）提高可靠性的任務映射算法

三維集成網(wǎng)格片上網(wǎng)絡采用硅通孔（Through Silicon Via，TSV）技術將二維網(wǎng)格片上網(wǎng)絡連接起來，提供了更高的集成度和更短的層間連接距離，所以在三維片上網(wǎng)絡中比較關注針對TSV的可靠性優(yōu)化。

DING等人[44]提出的方法試圖在任務映射過程中通過算法優(yōu)化TSV技術的使用和降低處理器核之間的通信延時。HAGHBAYAN等人[45]提出了一個分層框架，并通過該分層框架，為應用選擇使用壓力較小的處理器核，從而為使用壓力較大的處理器核提供較長的恢復時間。HAGHBAYAN等人[46-47]在為應用選擇處理器區(qū)域時引入了處理器核壽命指標以提高系統(tǒng)可靠性。GNAD等人[48]提出了一個輕量級的處理器核老化評估技術，并基于該評估技術，將計算密集型任務映射到健康處理器核，以避免部分處理器核老化過快。RATHORE等人[49]提出了一種稱為HipMap的動態(tài)分層映射方法，該方法利用暗核來降低系統(tǒng)峰值溫度，從而延長了系統(tǒng)的使用壽命。

3 發(fā)展趨勢

3.1 暗核

考慮暗核的任務映射算法可以使得處理器核運行在高頻，但是引入暗核會增加工作處理器核間的通信距離。因此考慮暗核的任務映射算法需同時考慮功耗、溫度、通信三個因素。此外，考慮暗核的任務映射算法需考慮暗核數(shù)量。計算密集型應用需更多的暗核，通信密集型應用則應減少暗核。PARSEC測試集中的應用Facesim和Swaptions在眾核模擬器中運行時的計算需求變化如圖3所示，其中計算需求是以吞吐率（每周期指令數(shù)，Instructions Per Cycle，IPC）來衡量的。分配給應用的暗核數(shù)也應該隨時間變化。

圖3 應用計算需求變化

3.2 三維集成片上網(wǎng)絡

目前針對三維集成片上網(wǎng)絡的任務映射算法較少。三維集成片上網(wǎng)絡如圖4所示，有區(qū)別于二維片上網(wǎng)絡的特點。首先，每層處理器核距離底部散熱器的距離不同，這導致了處理器核散熱能力不同。

圖4 三維集成片上網(wǎng)絡

其次，應用處理器區(qū)域?qū)訑?shù)影響處理器核間通信距離。不同的處理器區(qū)域如圖5所示，在處理器核數(shù)相同的情況下，垂直方向只有一層的處理器區(qū)域的處理器核間最大跳數(shù)為8，垂直方向三層的處理器區(qū)域的處理器核間最大跳數(shù)為5。

圖5 不同的處理器區(qū)域

由于處理器區(qū)域?qū)訑?shù)影響處理器核間通信距離，以及處理器核散熱能力不同的特點，二維片上網(wǎng)絡任務映射算法不能直接運用至三維集成片上網(wǎng)絡。現(xiàn)有三維集成片上網(wǎng)絡的典型拓撲結(jié)構是三維集成網(wǎng)格片上網(wǎng)絡，采用TSV技術可將二維網(wǎng)格片上網(wǎng)絡連接起來，因此可將三維集成網(wǎng)格片上網(wǎng)絡所提出的任務映射算法拓展至其他拓撲結(jié)構，如Torus等。之前提出的任務映射算法多采用集中控制的方式。在未來，芯片中的處理器核數(shù)目更大，可將現(xiàn)有任務映射算法擴展為分布式任務映射算法。

4 結(jié)論

本文從二維片上網(wǎng)絡和三維集成片上網(wǎng)絡針對不同的優(yōu)化目標對現(xiàn)有任務映射算法進行了研究，分析了優(yōu)化通信的任務映射算法導致碎片化程度加重等問題的產(chǎn)生，考慮了三維集成片上網(wǎng)絡區(qū)別于二維片上網(wǎng)絡的特點，指出了如何將任務映射算法拓展到其他拓撲結(jié)構如Torus等，如何設計分布式任務映射算法將成為未來眾核任務映射算法亟待解決的關鍵問題。