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

接上文

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

3 聯(lián)合調(diào)度

前面兩章分別對(duì)于共享緩存和DRAM 提出了相應(yīng)的調(diào)度算法，但這只是系統(tǒng)中眾多共享資源里最為重要的兩種。實(shí)際上在多線程環(huán)境下，線程還會(huì)對(duì)于其他包括系列總線和I/O 設(shè)備等共享資源進(jìn)行爭(zhēng)奪，線程間互相干擾，對(duì)系統(tǒng)性能造成影響。

一方面，針對(duì)不同的共享資源獨(dú)立提出的調(diào)度算法間從效果上可能互相矛盾。例如，同一個(gè)線程在共享緩存和主存處分別表現(xiàn)出的訪存行為特征未必一致，再根據(jù)各自的調(diào)度策略，分別設(shè)定的優(yōu)先級(jí)可能相反，使得調(diào)度失效。另一方面，從不同層面提出的調(diào)度策略之間也可能存在矛盾。例如，底層硬件層面的調(diào)度對(duì)線程的優(yōu)化可能使得操作系統(tǒng)層面對(duì)于線程優(yōu)先級(jí)的設(shè)定反轉(zhuǎn)。因此，從全局出發(fā)，綜合考慮所有共享資源，進(jìn)行聯(lián)合調(diào)度是極有研究價(jià)值的。

Ebrahimi 等在文獻(xiàn)中為了解決線程的公平性問題，提出一個(gè)可以協(xié)調(diào)所有共享存儲(chǔ)資源的機(jī)制稱為公平性資源節(jié)源( fairness via sourcethrottling,FST)，從而避免了需要為系統(tǒng)中每個(gè)共享存儲(chǔ)資源提出單獨(dú)的公平性機(jī)制。該機(jī)制使用前面在STFM中提到的線程減速比Mi=Tshd_i/Tsolo_i信息 , 用一組失效狀態(tài)信息寄存器(miss statusholding/informatiON registers,MSHRs)記錄各線程發(fā)向共享存儲(chǔ)系統(tǒng)的請(qǐng)求，請(qǐng)求得到服務(wù)后相應(yīng)寄存器清空，當(dāng)沒有可用的MSHRs 時(shí)，則禁止該線程向共享存儲(chǔ)系統(tǒng)發(fā)送請(qǐng)求。系統(tǒng)的不公平性通過下式衡量：

當(dāng)unfairness 超過某個(gè)設(shè)定閾值時(shí)，表示有線程的性能降低程度已經(jīng)嚴(yán)重影響到系統(tǒng)的公平性。可以通過調(diào)節(jié)可用MSHRs 數(shù)目來(lái)限制侵略性最強(qiáng)(或受影響最小)的線程向共享存儲(chǔ)系統(tǒng)發(fā)送訪存請(qǐng)求的速率，直到各線程的減速比基本保持一致水平，即unfairness 小于設(shè)定閾值，恢復(fù)受限制線程發(fā)送訪存請(qǐng)求的能力。這個(gè)方法從源頭上限制對(duì)共享存儲(chǔ)資源的不公平性使用，從而無(wú)需從單個(gè)共享存儲(chǔ)資源特別提出公平性的調(diào)度策略。

由于對(duì)DRAM 進(jìn)行訪存的速度提升遠(yuǎn)不及處理器速度的提升，訪存DRAM 所帶來(lái)的延遲常常是影響性能的一個(gè)關(guān)鍵因素。一個(gè)解決方案是，預(yù)測(cè)線程可能需要的數(shù)據(jù)，在處理器實(shí)際用到該數(shù)據(jù)之前就發(fā)送訪存請(qǐng)求從DRAM 取回?cái)?shù)據(jù)。該技術(shù)稱之為預(yù)取(prefetching)，已被證明確實(shí)能夠有效改善系統(tǒng)性能，并被用于大多數(shù)商業(yè)處理器中。

然而，各個(gè)線程發(fā)向DRAM 的預(yù)取請(qǐng)求，同樣存在對(duì)于系統(tǒng)資源的爭(zhēng)奪和線程間的干擾，從而抵消由于預(yù)取部件所帶來(lái)的性能改善。Ebrahimi 等人在文獻(xiàn)中提出了分層預(yù)取侵略性控制( hierarchical prefetcher aggressiveness control ,HPAC)，類似于文獻(xiàn)[24]中的FST,HPAC 通過從源頭上限制預(yù)取請(qǐng)求的發(fā)送來(lái)改善系統(tǒng)的預(yù)取性能。

為了降低問題的復(fù)雜性，之前提出的調(diào)度策略都是針對(duì)沒有采用預(yù)取技術(shù)的情況。為了更好地改善系統(tǒng)性能，我們總是希望調(diào)度策略和預(yù)取技術(shù)能夠同時(shí)生效。然而，實(shí)驗(yàn)發(fā)現(xiàn)，即使采用已被證明有效的調(diào)度策略，在加入預(yù)取技術(shù)之后，調(diào)度策略仍然可能失效，使系統(tǒng)的性能受到影響。因此，Ebrahimi 等人在文獻(xiàn)中的研究，解決了預(yù)取技術(shù)與調(diào)度策略的共存問題，并將文獻(xiàn)中提出的FST 和HPAC 相結(jié)合。該項(xiàng)研究的基本思想包括如下幾點(diǎn)：首先，預(yù)取請(qǐng)求涉及的通常只是處理器未來(lái)可能用到的數(shù)據(jù)，而非當(dāng)前急需的數(shù)據(jù)，因此，除非某些預(yù)取請(qǐng)求有著和普通訪存請(qǐng)求同樣的重要性，預(yù)取請(qǐng)求的優(yōu)先級(jí)應(yīng)該低于普通的訪存請(qǐng)求;其次，在所有訪存請(qǐng)求中優(yōu)先來(lái)自延遲敏感型線程的訪存請(qǐng)求;并且，對(duì)預(yù)取請(qǐng)求按重要性分配不同的優(yōu)先級(jí);最后，F(xiàn)ST 中對(duì)于處理器發(fā)送請(qǐng)求的調(diào)節(jié)可能與HPAC 對(duì)于預(yù)取請(qǐng)求的調(diào)節(jié)存在矛盾，通過協(xié)同考慮處理器和預(yù)取部件，可以有效降低對(duì)系統(tǒng)性能的影響。

Ebrahimi 等人在文獻(xiàn)中的探索對(duì)于解決系統(tǒng)共享資源的聯(lián)合調(diào)度是很好的啟發(fā)。這些調(diào)度策略將所有共享資源抽象為一個(gè)整體，從源頭上解決系統(tǒng)的公平性問題，但是并沒有充分利用具體共享資源的訪存特點(diǎn)。若能夠?qū)⒉煌瑢哟蔚恼{(diào)度策略有效結(jié)合起來(lái)，將會(huì)對(duì)對(duì)系統(tǒng)的性能有進(jìn)一步的改善。

4. 研究展望

隨著處理器核規(guī)模的增長(zhǎng)，多線程對(duì)于有限的共享資源的爭(zhēng)奪將愈發(fā)激烈，由此導(dǎo)致的對(duì)于系統(tǒng)性能的影響也將更加顯著。為了緩解乃至解決這一問題，除了增加可用共享資源外，一個(gè)能夠公平有效地在多線程間分配共享資源的調(diào)度算法也至關(guān)重要。學(xué)術(shù)界對(duì)此投入了大量的精力與時(shí)間。在各類共享資源中，對(duì)于系統(tǒng)性能有著最大影響的是共享緩存和DRAM 帶寬。已有的研究也大多基于此，并已經(jīng)取得了大量研究成果。

在第1 節(jié)中，我們分別以系統(tǒng)吞吐量和公平性為優(yōu)化目標(biāo)介紹了一系列對(duì)共享緩存的分區(qū)調(diào)度算法，并針對(duì)緩存分區(qū)粒度過大的問題給出了相關(guān)解決方案;在第2 節(jié)中，從利用線程的訪存行為特征和借鑒網(wǎng)絡(luò)路由算法等多個(gè)角度介紹了DRAM 的調(diào)度算法，并研究了基于機(jī)器學(xué)習(xí)的自我強(qiáng)化的調(diào)度算法;在隨后的第3 節(jié)中，研究了從全局出發(fā)的聯(lián)合調(diào)度算法，以解決針對(duì)不同共享資源的調(diào)度算法間相互矛盾的問題。上述研究都在一定程度上解決了我們?nèi)缃袼媾R的問題，但是隨著眾核時(shí)代的來(lái)臨，一些調(diào)度算法的復(fù)雜度和相應(yīng)的硬件開銷都可能大幅增長(zhǎng)，導(dǎo)致這類調(diào)度算法失去實(shí)用性。針對(duì)調(diào)度算法在未來(lái)的系統(tǒng)中對(duì)共享資源的合理分配中所存在的應(yīng)用潛力和面臨的問題，我們認(rèn)為仍然有問題可以展開進(jìn)一步的研究：

1)如前所述，制定有效的緩存分區(qū)策略需要知道各線程的緩存需求，以及各線程從分配的單位粒度的緩存空間取得的收益。為了獲取上述信息，Suh等人在文獻(xiàn)中提出了的MON,隨后，Qureshi等在此基礎(chǔ)上提出了改進(jìn)的UMON[4].基于UMON的系列研究分別針對(duì)共享緩存的吞吐量和公平性做出了有效改進(jìn)。在文獻(xiàn)中提出的zcache又解決了緩存分區(qū)粒度過大的問題，可以以較小的粒度將共享緩存分為數(shù)十個(gè)分區(qū)，使得緩存分區(qū)策略的可擴(kuò)展性增強(qiáng)，能夠應(yīng)用于更大規(guī)模的CMP系統(tǒng)中。但是由于利用UMON 獲取信息需要在每個(gè)核保留一份標(biāo)簽?zāi)夸泜浞軦TD.當(dāng)核數(shù)較多且共享緩存較大時(shí)，會(huì)產(chǎn)生比很大的硬件開銷。另外，如圖1 所示，各個(gè)核將UMON 收集的信息送至一個(gè)緩存分區(qū)模塊，集中進(jìn)行緩存分區(qū)策略的制定。這種全局式的做法在眾核時(shí)代會(huì)導(dǎo)致緩存分區(qū)模塊面臨過高的計(jì)算復(fù)雜度。

下一步研究，可以采用分布式的緩存分區(qū)策略：

由于共享數(shù)據(jù)的存在，先按照線程來(lái)源將共享緩存劃分為幾個(gè)子區(qū)，每個(gè)子區(qū)內(nèi)的線程應(yīng)該來(lái)自同一應(yīng)用，共享某些數(shù)據(jù);然后在各個(gè)子區(qū)內(nèi)，根據(jù)不同線程的需求制定適當(dāng)?shù)木彺娣謪^(qū)策略，每個(gè)子區(qū)還應(yīng)該保留一部分緩存空間來(lái)存儲(chǔ)共享數(shù)據(jù)。分布式的緩存分區(qū)策略一方面可以大大降低計(jì)算復(fù)雜度，同時(shí)又充分利用了緩存分區(qū)以及共享數(shù)據(jù)的優(yōu)點(diǎn)，將會(huì)更好地提高系統(tǒng)性能。

另外，設(shè)計(jì)一類新的緩存替換算法，使其能夠區(qū)分對(duì)待來(lái)自不用線程的不同請(qǐng)求，并執(zhí)行適當(dāng)?shù)奶鎿Q操作，也能夠有效緩解共享緩存的爭(zhēng)奪，并且避免了緩存分區(qū)所帶來(lái)的開銷。由于這種新的緩存替換算法需要更多的信息，可能需要在緩存的Tag中加入一些新的域，替換算法的復(fù)雜度也會(huì)增加。

2)對(duì)于DRAM 的調(diào)度策略，現(xiàn)有的研究方向可以主要分為兩類。一類研究大多從組成訪存請(qǐng)求的底層操作出發(fā)，充分利用DRAM 結(jié)構(gòu)特點(diǎn)和線程的訪存行為特征，例如行緩存相關(guān)性，塊級(jí)并行性以及訪存密集度等;這類研究能夠有效利用DRAM帶寬，有助于提高系統(tǒng)吞吐量。另一類研究則從網(wǎng)絡(luò)公平調(diào)度算法得到啟發(fā)，以DRAM 系統(tǒng)的公平性為優(yōu)化目標(biāo)，其中以FQM和STFM等為代表;這類研究存在的問題是將訪存請(qǐng)求抽象為一個(gè)整體看待，沒有充分利用DRAM 的結(jié)構(gòu)特點(diǎn)和線程的訪存行為，系統(tǒng)吞吐量往往不高。一個(gè)將這兩類研究的優(yōu)點(diǎn)有機(jī)結(jié)合起來(lái)的算法，能夠同時(shí)做到改善系統(tǒng)公平性并保證吞吐量。

從另一角度看，如果能夠從源頭上減少訪存請(qǐng)求的行沖突，提高塊級(jí)并行性，將更有利于提高系統(tǒng)性能。因此，還可以從如下兩個(gè)思路進(jìn)行研究：

DRAM 訪存由于不同線程訪存請(qǐng)求的交互執(zhí)行帶來(lái)的行沖突是影響系統(tǒng)性能的一個(gè)重要因素，借鑒緩存分區(qū)的思想，通過操作系統(tǒng)地址映射使得不同線程的訪存請(qǐng)求訪問不同的DRAM 塊，可以降低行沖突，提高行命中率。

另外，改變DRAM 的邏輯結(jié)構(gòu)(通過增加channel,rank 等概念)，使得一個(gè)線程的不同訪存請(qǐng)求被映射到更多的塊，提高其塊級(jí)并行性，也可以有效提高性能。

3)系統(tǒng)中包括大量共享資源，之前的研究為了更有針對(duì)性以及降低研究的復(fù)雜度，通常只涉及其中一種共享資源的調(diào)度。但是實(shí)際上系統(tǒng)中的各類共享資源并非彼此獨(dú)立的，調(diào)度算法之間可能相互矛盾，使得調(diào)度失效。因此，從全局出發(fā)，綜合考慮所有共享資源提出調(diào)度算法是有必要的。在文獻(xiàn)中給出的調(diào)度算法，利用MSHRs 從源頭上控制各線程向共享存儲(chǔ)系統(tǒng)的發(fā)出訪存請(qǐng)求的頻率和數(shù)量，從而實(shí)現(xiàn)系統(tǒng)的公平性。這對(duì)于全局統(tǒng)一調(diào)度是很好的啟發(fā)。

隨著工藝發(fā)展，功耗管理已經(jīng)成為一個(gè)不得不面對(duì)的問題。功耗管理需要要保證多核系統(tǒng)的總功耗不超過功耗預(yù)算(power budget)，所以，功耗也是另一種重要的共享資源。調(diào)節(jié)功耗的主要手段之一是降低處理器核的頻率，則其產(chǎn)生訪存請(qǐng)求的頻率也將降低，實(shí)際上起到與MSHRs 類似的效果，同時(shí)還不需要帶來(lái)硬件開銷。通過調(diào)節(jié)頻率，使得多個(gè)訪存密集型線程訪問共享存儲(chǔ)系統(tǒng)的時(shí)間段錯(cuò)開，可以有效減緩共享存儲(chǔ)系統(tǒng)的壓力。一個(gè)好的策略可以做到同時(shí)兼顧功耗管理和訪存調(diào)度兩方面的需求，實(shí)現(xiàn)全局的統(tǒng)一調(diào)度。

5 結(jié)束語(yǔ)

本文首先介紹了在CMP 系統(tǒng)中，由于線程間對(duì)于有限共享資源的爭(zhēng)奪，調(diào)度算法的必要性和重要性，然后根據(jù)不同的優(yōu)化目的介紹了對(duì)于共享緩存的一系列緩存分區(qū)算法，同時(shí)從不同角度出發(fā)介紹了一些DRAM 訪存調(diào)度算法，接下來(lái)研究了綜合考慮共享資源的聯(lián)合調(diào)度算法，并對(duì)于未來(lái)的共享資源調(diào)度算法的研究進(jìn)行了展望。

考慮到隨著將來(lái)CMP 系統(tǒng)中處理器數(shù)目規(guī)模會(huì)越來(lái)越大，對(duì)于共享資源的爭(zhēng)奪將更加激烈，設(shè)計(jì)調(diào)度算法的難度也將顯著增加，這項(xiàng)工作也將更具挑戰(zhàn)性。因此，設(shè)計(jì)公平有效的調(diào)度算法將更有必要。