眾核任務(wù)映射算法研究現(xiàn)狀與發(fā)展趨勢*

吳 倩，王小航

（華南理工大學(xué)軟件學(xué)院，廣州 510006）

1 引言

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

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

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

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

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

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

2 任務(wù)映射算法

2.1 任務(wù)映射過程

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

圖1 任務(wù)映射

2.2 任務(wù)映射算法分類

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

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

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

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

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

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

2）提高可靠性的任務(wù)映射算法

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

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

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

3）降低功耗的任務(wù)映射算法

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

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

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

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

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

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

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

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

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

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

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

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

2）降低功耗的任務(wù)映射算法

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

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

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

4）提高可靠性的任務(wù)映射算法

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

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

3 發(fā)展趨勢

3.1 暗核

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

圖3 應(yīng)用計算需求變化

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

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

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

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

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

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

4 結(jié)論

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