片上多核處理器共享資源分配與調(diào)度策略研究綜述(三)
接上文
本文引用地址:http://m.butianyuan.cn/article/148026.htm片上多核處理器共享資源分配與調(diào)度策略研究綜述(二)
3 聯(lián)合調(diào)度
前面兩章分別對于共享緩存和DRAM 提出了相應的調(diào)度算法,但這只是系統(tǒng)中眾多共享資源里最為重要的兩種。實際上在多線程環(huán)境下,線程還會對于其他包括系列總線和I/O 設(shè)備等共享資源進行爭奪,線程間互相干擾,對系統(tǒng)性能造成影響。
一方面,針對不同的共享資源獨立提出的調(diào)度算法間從效果上可能互相矛盾。例如,同一個線程在共享緩存和主存處分別表現(xiàn)出的訪存行為特征未必一致,再根據(jù)各自的調(diào)度策略,分別設(shè)定的優(yōu)先級可能相反,使得調(diào)度失效。另一方面,從不同層面提出的調(diào)度策略之間也可能存在矛盾。例如,底層硬件層面的調(diào)度對線程的優(yōu)化可能使得操作系統(tǒng)層面對于線程優(yōu)先級的設(shè)定反轉(zhuǎn)。因此,從全局出發(fā),綜合考慮所有共享資源,進行聯(lián)合調(diào)度是極有研究價值的。
Ebrahimi 等在文獻中為了解決線程的公平性問題,提出一個可以協(xié)調(diào)所有共享存儲資源的機制稱為公平性資源節(jié)源( fairness via sourcethrottling,FST),從而避免了需要為系統(tǒng)中每個共享存儲資源提出單獨的公平性機制。該機制使用前面在STFM中提到的線程減速比Mi=Tshd_i/Tsolo_i信息 , 用一組失效狀態(tài)信息寄存器(miss statusholding/informatiON registers,MSHRs)記錄各線程發(fā)向共享存儲系統(tǒng)的請求,請求得到服務后相應寄存器清空,當沒有可用的MSHRs 時,則禁止該線程向共享存儲系統(tǒng)發(fā)送請求。系統(tǒng)的不公平性通過下式衡量:
當unfairness 超過某個設(shè)定閾值時,表示有線程的性能降低程度已經(jīng)嚴重影響到系統(tǒng)的公平性。可以通過調(diào)節(jié)可用MSHRs 數(shù)目來限制侵略性最強(或受影響最小)的線程向共享存儲系統(tǒng)發(fā)送訪存請求的速率,直到各線程的減速比基本保持一致水平,即unfairness 小于設(shè)定閾值,恢復受限制線程發(fā)送訪存請求的能力。這個方法從源頭上限制對共享存儲資源的不公平性使用,從而無需從單個共享存儲資源特別提出公平性的調(diào)度策略。
由于對DRAM 進行訪存的速度提升遠不及處理器速度的提升,訪存DRAM 所帶來的延遲常常是影響性能的一個關(guān)鍵因素。一個解決方案是,預測線程可能需要的數(shù)據(jù),在處理器實際用到該數(shù)據(jù)之前就發(fā)送訪存請求從DRAM 取回數(shù)據(jù)。該技術(shù)稱之為預取(prefetching),已被證明確實能夠有效改善系統(tǒng)性能,并被用于大多數(shù)商業(yè)處理器中。
然而,各個線程發(fā)向DRAM 的預取請求,同樣存在對于系統(tǒng)資源的爭奪和線程間的干擾,從而抵消由于預取部件所帶來的性能改善。Ebrahimi 等人在文獻中提出了分層預取侵略性控制( hierarchical prefetcher aggressiveness control ,HPAC),類似于文獻[24]中的FST,HPAC 通過從源頭上限制預取請求的發(fā)送來改善系統(tǒng)的預取性能。
為了降低問題的復雜性,之前提出的調(diào)度策略都是針對沒有采用預取技術(shù)的情況。為了更好地改善系統(tǒng)性能,我們總是希望調(diào)度策略和預取技術(shù)能夠同時生效。然而,實驗發(fā)現(xiàn),即使采用已被證明有效的調(diào)度策略,在加入預取技術(shù)之后,調(diào)度策略仍然可能失效,使系統(tǒng)的性能受到影響。因此,Ebrahimi 等人在文獻中的研究,解決了預取技術(shù)與調(diào)度策略的共存問題,并將文獻中提出的FST 和HPAC 相結(jié)合。該項研究的基本思想包括如下幾點:首先,預取請求涉及的通常只是處理器未來可能用到的數(shù)據(jù),而非當前急需的數(shù)據(jù),因此,除非某些預取請求有著和普通訪存請求同樣的重要性,預取請求的優(yōu)先級應該低于普通的訪存請求;其次,在所有訪存請求中優(yōu)先來自延遲敏感型線程的訪存請求;并且,對預取請求按重要性分配不同的優(yōu)先級;最后,F(xiàn)ST 中對于處理器發(fā)送請求的調(diào)節(jié)可能與HPAC 對于預取請求的調(diào)節(jié)存在矛盾,通過協(xié)同考慮處理器和預取部件,可以有效降低對系統(tǒng)性能的影響。
Ebrahimi 等人在文獻中的探索對于解決系統(tǒng)共享資源的聯(lián)合調(diào)度是很好的啟發(fā)。這些調(diào)度策略將所有共享資源抽象為一個整體,從源頭上解決系統(tǒng)的公平性問題,但是并沒有充分利用具體共享資源的訪存特點。若能夠?qū)⒉煌瑢哟蔚恼{(diào)度策略有效結(jié)合起來,將會對對系統(tǒng)的性能有進一步的改善。
4. 研究展望
隨著處理器核規(guī)模的增長,多線程對于有限的共享資源的爭奪將愈發(fā)激烈,由此導致的對于系統(tǒng)性能的影響也將更加顯著。為了緩解乃至解決這一問題,除了增加可用共享資源外,一個能夠公平有效地在多線程間分配共享資源的調(diào)度算法也至關(guān)重要。學術(shù)界對此投入了大量的精力與時間。在各類共享資源中,對于系統(tǒng)性能有著最大影響的是共享緩存和DRAM 帶寬。已有的研究也大多基于此,并已經(jīng)取得了大量研究成果。
在第1 節(jié)中,我們分別以系統(tǒng)吞吐量和公平性為優(yōu)化目標介紹了一系列對共享緩存的分區(qū)調(diào)度算法,并針對緩存分區(qū)粒度過大的問題給出了相關(guān)解決方案;在第2 節(jié)中,從利用線程的訪存行為特征和借鑒網(wǎng)絡路由算法等多個角度介紹了DRAM 的調(diào)度算法,并研究了基于機器學習的自我強化的調(diào)度算法;在隨后的第3 節(jié)中,研究了從全局出發(fā)的聯(lián)合調(diào)度算法,以解決針對不同共享資源的調(diào)度算法間相互矛盾的問題。上述研究都在一定程度上解決了我們?nèi)缃袼媾R的問題,但是隨著眾核時代的來臨,一些調(diào)度算法的復雜度和相應的硬件開銷都可能大幅增長,導致這類調(diào)度算法失去實用性。針對調(diào)度算法在未來的系統(tǒng)中對共享資源的合理分配中所存在的應用潛力和面臨的問題,我們認為仍然有問題可以展開進一步的研究:
1)如前所述,制定有效的緩存分區(qū)策略需要知道各線程的緩存需求,以及各線程從分配的單位粒度的緩存空間取得的收益。為了獲取上述信息,Suh等人在文獻中提出了的MON,隨后,Qureshi等在此基礎(chǔ)上提出了改進的UMON[4].基于UMON的系列研究分別針對共享緩存的吞吐量和公平性做出了有效改進。在文獻中提出的zcache又解決了緩存分區(qū)粒度過大的問題,可以以較小的粒度將共享緩存分為數(shù)十個分區(qū),使得緩存分區(qū)策略的可擴展性增強,能夠應用于更大規(guī)模的CMP系統(tǒng)中。但是由于利用UMON 獲取信息需要在每個核保留一份標簽目錄備份ATD.當核數(shù)較多且共享緩存較大時,會產(chǎn)生比很大的硬件開銷。另外,如圖1 所示,各個核將UMON 收集的信息送至一個緩存分區(qū)模塊,集中進行緩存分區(qū)策略的制定。這種全局式的做法在眾核時代會導致緩存分區(qū)模塊面臨過高的計算復雜度。
下一步研究,可以采用分布式的緩存分區(qū)策略:
由于共享數(shù)據(jù)的存在,先按照線程來源將共享緩存劃分為幾個子區(qū),每個子區(qū)內(nèi)的線程應該來自同一應用,共享某些數(shù)據(jù);然后在各個子區(qū)內(nèi),根據(jù)不同線程的需求制定適當?shù)木彺娣謪^(qū)策略,每個子區(qū)還應該保留一部分緩存空間來存儲共享數(shù)據(jù)。分布式的緩存分區(qū)策略一方面可以大大降低計算復雜度,同時又充分利用了緩存分區(qū)以及共享數(shù)據(jù)的優(yōu)點,將會更好地提高系統(tǒng)性能。
另外,設(shè)計一類新的緩存替換算法,使其能夠區(qū)分對待來自不用線程的不同請求,并執(zhí)行適當?shù)奶鎿Q操作,也能夠有效緩解共享緩存的爭奪,并且避免了緩存分區(qū)所帶來的開銷。由于這種新的緩存替換算法需要更多的信息,可能需要在緩存的Tag中加入一些新的域,替換算法的復雜度也會增加。
2)對于DRAM 的調(diào)度策略,現(xiàn)有的研究方向可以主要分為兩類。一類研究大多從組成訪存請求的底層操作出發(fā),充分利用DRAM 結(jié)構(gòu)特點和線程的訪存行為特征,例如行緩存相關(guān)性,塊級并行性以及訪存密集度等;這類研究能夠有效利用DRAM帶寬,有助于提高系統(tǒng)吞吐量。另一類研究則從網(wǎng)絡公平調(diào)度算法得到啟發(fā),以DRAM 系統(tǒng)的公平性為優(yōu)化目標,其中以FQM和STFM等為代表;這類研究存在的問題是將訪存請求抽象為一個整體看待,沒有充分利用DRAM 的結(jié)構(gòu)特點和線程的訪存行為,系統(tǒng)吞吐量往往不高。一個將這兩類研究的優(yōu)點有機結(jié)合起來的算法,能夠同時做到改善系統(tǒng)公平性并保證吞吐量。
從另一角度看,如果能夠從源頭上減少訪存請求的行沖突,提高塊級并行性,將更有利于提高系統(tǒng)性能。因此,還可以從如下兩個思路進行研究:
DRAM 訪存由于不同線程訪存請求的交互執(zhí)行帶來的行沖突是影響系統(tǒng)性能的一個重要因素,借鑒緩存分區(qū)的思想,通過操作系統(tǒng)地址映射使得不同線程的訪存請求訪問不同的DRAM 塊,可以降低行沖突,提高行命中率。
另外,改變DRAM 的邏輯結(jié)構(gòu)(通過增加channel,rank 等概念),使得一個線程的不同訪存請求被映射到更多的塊,提高其塊級并行性,也可以有效提高性能。
3)系統(tǒng)中包括大量共享資源,之前的研究為了更有針對性以及降低研究的復雜度,通常只涉及其中一種共享資源的調(diào)度。但是實際上系統(tǒng)中的各類共享資源并非彼此獨立的,調(diào)度算法之間可能相互矛盾,使得調(diào)度失效。因此,從全局出發(fā),綜合考慮所有共享資源提出調(diào)度算法是有必要的。在文獻中給出的調(diào)度算法,利用MSHRs 從源頭上控制各線程向共享存儲系統(tǒng)的發(fā)出訪存請求的頻率和數(shù)量,從而實現(xiàn)系統(tǒng)的公平性。這對于全局統(tǒng)一調(diào)度是很好的啟發(fā)。
隨著工藝發(fā)展,功耗管理已經(jīng)成為一個不得不面對的問題。功耗管理需要要保證多核系統(tǒng)的總功耗不超過功耗預算(power budget),所以,功耗也是另一種重要的共享資源。調(diào)節(jié)功耗的主要手段之一是降低處理器核的頻率,則其產(chǎn)生訪存請求的頻率也將降低,實際上起到與MSHRs 類似的效果,同時還不需要帶來硬件開銷。通過調(diào)節(jié)頻率,使得多個訪存密集型線程訪問共享存儲系統(tǒng)的時間段錯開,可以有效減緩共享存儲系統(tǒng)的壓力。一個好的策略可以做到同時兼顧功耗管理和訪存調(diào)度兩方面的需求,實現(xiàn)全局的統(tǒng)一調(diào)度。
5 結(jié)束語
本文首先介紹了在CMP 系統(tǒng)中,由于線程間對于有限共享資源的爭奪,調(diào)度算法的必要性和重要性,然后根據(jù)不同的優(yōu)化目的介紹了對于共享緩存的一系列緩存分區(qū)算法,同時從不同角度出發(fā)介紹了一些DRAM 訪存調(diào)度算法,接下來研究了綜合考慮共享資源的聯(lián)合調(diào)度算法,并對于未來的共享資源調(diào)度算法的研究進行了展望。
考慮到隨著將來CMP 系統(tǒng)中處理器數(shù)目規(guī)模會越來越大,對于共享資源的爭奪將更加激烈,設(shè)計調(diào)度算法的難度也將顯著增加,這項工作也將更具挑戰(zhàn)性。因此,設(shè)計公平有效的調(diào)度算法將更有必要。
評論