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

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

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

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

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

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

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

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

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