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

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

引言

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

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

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

因此，在CMP 系統中對共享資源的分配調度成為一個(gè)值得研究的熱點(diǎn)問(wèn)題。

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

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

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

制定相應的分區策略，根據程序運行中的動(dòng)態(tài)特征把緩存空間適當分配給各個(gè)線(xiàn)程，從而盡量避免線(xiàn)程間對緩存的爭奪，同時(shí)滿(mǎn)足線(xiàn)程各自的緩存需求，從而改善系統性能?；谶@種動(dòng)態(tài)緩存分區的概念，學(xué)術(shù)界為改善系統性能，分別以提高系統吞吐量和改善系統公平性為優(yōu)化目標提出了各類(lèi)緩存分區策略。

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

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

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