片上多核處理器共享資源分配與調(diào)度策略研究綜述（一）

摘要： 對于片上多核處理器，如何在多線程間公平有效地分配調(diào)度有限的共享資源是一個很重要的問題。隨著處理器核規(guī)模的增長，多線程對于系統(tǒng)中有限的共享資源的爭奪將愈發(fā)激烈，由此導(dǎo)致的對于系統(tǒng)性能的影響也將更加顯著。為了緩解乃至解決這一問題，除了增加可用共享資源外，一個能夠公平有效地在多線程間分配共享資源的調(diào)度算法也至關(guān)重要。在各類共享資源中，對于系統(tǒng)性能有著最大影響的是共享緩存和DRAM 系統(tǒng)。對于共享緩存，可以通過緩存分區(qū)，來降低由于線程間的爭奪所帶來的影響;對于DRAM系統(tǒng)，可以采取適當(dāng)?shù)?a class="contentlabel" href="http://www.ex-cimer.com/news/listbylabel/label/調(diào)度">調(diào)度算法來調(diào)節(jié)各個線程發(fā)出的訪存請求的服務(wù)優(yōu)先級，從而改善系統(tǒng)性能。首先分別以系統(tǒng)吞吐量和公平性為優(yōu)化目標(biāo)介紹了一系列對共享緩存的分區(qū)調(diào)度算法，并針對緩存分區(qū)粒度過大的問題給出了相關(guān)解決方案。然后從利用線程的訪存行為特征和借鑒網(wǎng)絡(luò)路由算法等多個角度介紹了DRAM 的調(diào)度算法。接下來，研究了從全局出發(fā)的聯(lián)合調(diào)度算法，以解決針對不同共享資源的調(diào)度算法間相互矛盾的問題。最后，從不同角度對于今后的研究進(jìn)行了展望。

引言

隨著集成電路工藝的發(fā)展，片上多核處理器(chip multi-processor, CMP)開始占據(jù)市場，在一個CMP 上并發(fā)地執(zhí)行多個線程成為主流趨勢。CMP上的多個核/線程通常共享最后一級緩存(lastlevel cache,LLC)、DRAM 控制器、主存總線帶寬和預(yù)取部件(prefetching hardware)等多種資源。

系統(tǒng)中的共享資源總是有限的，線程間需要爭奪共享資源的使用權(quán)。不同的線程其程序特征(在本文中主要指訪存行為)存在差異，而線程爭奪共享資源的能力通常與此相關(guān)。如果沒有特別的調(diào)度機(jī)制，某些線程可能占用大部分乃至全部的系統(tǒng)資源，導(dǎo)致其他線程的請求得不到服務(wù)，最終對系統(tǒng)的性能(吞吐量和公平性)造成影響。

如果存在一個調(diào)度策略能夠在多個并行線程間公平有效地分配共享資源，則可以緩解由于對共享資源的爭奪所帶來的負(fù)面影響，從而改善系統(tǒng)性能。

因此，在CMP 系統(tǒng)中對共享資源的分配調(diào)度成為一個值得研究的熱點問題。

在CMP 系統(tǒng)中，最為重要的共享資源是其共享存儲系統(tǒng)(主要包括共享緩存和主存帶寬)。當(dāng)線程的訪存請求得不到服務(wù)時，由于所需數(shù)據(jù)沒有及時返回，相關(guān)處理器核將會一直處于阻塞等待狀態(tài)，導(dǎo)致計算資源的浪費，對系統(tǒng)性能會造成巨大影響。

學(xué)術(shù)界當(dāng)前的研究重點也主要集中在共享緩存和主存帶寬的分配調(diào)度上，因此，本文將從這兩個方面對CMP 系統(tǒng)的共享資源調(diào)度問題進(jìn)行闡述。

當(dāng)私有緩存空間不夠用時，程序?qū)⒃L問共享緩存，線程間會爭奪有限的共享緩存空間。常用的最近最少使用替換算法(least recently used,LRU)不區(qū)分訪存請求來自哪個線程，同等對待所有訪存請求，當(dāng)需要發(fā)生緩存替換時，總是逐出最近訪問頻率最低的緩存塊。因此，多個線程實際上是在自由競爭共享緩存空間的使用權(quán)。一些能夠快速產(chǎn)生大量緩存失效的線程可能替換掉其他線程的有效數(shù)據(jù)，獨占大部分乃至全部緩存空間。緩存空間在線程間的分配方式不當(dāng)會導(dǎo)致部分線程或總的緩存失效率急劇上升，影響到系統(tǒng)的性能?，F(xiàn)有的研究大多通過緩存分區(qū)來解決這個問題。由于不同線程在不同的時刻對緩存空間的需求并不一樣，簡單地將共享緩存平均分給各個線程并不能有效解決問題。

制定相應(yīng)的分區(qū)策略，根據(jù)程序運行中的動態(tài)特征把緩存空間適當(dāng)分配給各個線程，從而盡量避免線程間對緩存的爭奪，同時滿足線程各自的緩存需求，從而改善系統(tǒng)性能。基于這種動態(tài)緩存分區(qū)的概念，學(xué)術(shù)界為改善系統(tǒng)性能，分別以提高系統(tǒng)吞吐量和改善系統(tǒng)公平性為優(yōu)化目標(biāo)提出了各類緩存分區(qū)策略。

當(dāng)發(fā)生最后一級緩存失效時，訪存請求需要讀寫主存，即動態(tài)隨機(jī)存儲器(dynamic random-accessmemory,DRAM)，而DRAM 的訪存帶寬是有限的。來自不同線程的訪存請求間存在相互依賴和制約的關(guān)系，延時情況會由于線程間的干擾(interface)加劇，進(jìn)而導(dǎo)致帶寬利用率低。任由多個線程自由爭奪有限的訪存帶寬，會降低系統(tǒng)性能。通過DRAM控制器充分利用DRAM 的結(jié)構(gòu)特點和線程的訪存行為特征對訪存請求的服務(wù)優(yōu)先級進(jìn)行合理的調(diào)度可以降低延遲，提高帶寬利用率，進(jìn)而改善系統(tǒng)性能。因此，學(xué)術(shù)界對于多線程環(huán)境中的有效訪存調(diào)度策略也進(jìn)行了大量研究。

單獨針對一類共享資源各自提出調(diào)度策略，從全局效果來看可能相互矛盾，達(dá)不到優(yōu)化目的。因此，在一些關(guān)于共享資源調(diào)度策略的研究中，需要綜合考慮各類共享資源，進(jìn)行聯(lián)合調(diào)度。

為了深入理解CMP 系統(tǒng)中共享資源的分配調(diào)度策略、存在的問題以及應(yīng)用前景，以便更好地應(yīng)對隨著CMP 系統(tǒng)規(guī)模增大而帶來的調(diào)度復(fù)雜度，對CMP 系統(tǒng)中共享資源的分配調(diào)度策略進(jìn)行綜述是具有重要意義的。本文首先介紹了基于緩存分區(qū)的共享緩存分配調(diào)度策略的基本思想和特點，然后介紹了采用不同性能優(yōu)化目標(biāo)的緩存分區(qū)方案的研究進(jìn)展，接下來我們研究了DRAM 的訪存調(diào)度算法，之后對于系統(tǒng)中多種共享資源的聯(lián)合調(diào)度算法進(jìn)行了介紹。最后，對CMP 系統(tǒng)中共享資源的分配調(diào)度策略未來可以開展的研究方向進(jìn)行了展望。