一種軟硬結(jié)合的預(yù)取技術(shù)探討

唐言

（黑龍江省教育學(xué)院，黑龍江 哈爾濱 150000）

1 課題背景和研究現(xiàn)狀

現(xiàn)代處理器速度的快速發(fā)展和存儲(chǔ)器速度的慢速發(fā)展導(dǎo)致處理器要花費(fèi)大量的時(shí)間等待存儲(chǔ)器數(shù)據(jù)的返回，這就是存儲(chǔ)墻問(wèn)題。例如，Alpha 21264 667 MHz的工作站一次訪存失效造成的開(kāi)銷就高達(dá)128個(gè)時(shí)鐘周期!

為了解決這個(gè)問(wèn)題，預(yù)取技術(shù)就被提了出來(lái)，通過(guò)計(jì)算和訪存的重疊，在Cache可能會(huì)發(fā)生失效之前發(fā)出預(yù)取請(qǐng)求以便在該數(shù)據(jù)真正被使用到時(shí)己提前將數(shù)據(jù)塊取入Cache，從而避免Cache失效造成的處理器停頓。

2 相關(guān)工作

數(shù)據(jù)預(yù)取是用來(lái)解決或者說(shuō)隱藏局部性不足的訪存模式，在數(shù)據(jù)將要使用前將其由下一級(jí)存儲(chǔ)器取回Cache，保證CPU可以無(wú)停頓的執(zhí)行。預(yù)取必須保證及時(shí)、準(zhǔn)確并且引入盡可能小的額外開(kāi)銷。同時(shí)預(yù)取的負(fù)面效應(yīng)也是必須考慮的因素，例如Cache污染和帶寬的浪費(fèi)?，F(xiàn)在有多種多樣的預(yù)取技術(shù)，但它們各有千秋，沒(méi)有哪一種預(yù)取策略己被證明是最優(yōu)的。下表比較了它們各自的優(yōu)缺點(diǎn)。

2.1 硬件預(yù)取

硬件預(yù)取是由硬件根據(jù)訪存的歷史信息，對(duì)未來(lái)可能的訪存單元預(yù)先取入Cache，從而在數(shù)據(jù)真正被用到時(shí)不會(huì)造成Cache失效。但是由于只是基于訪存的歷史信息，硬件預(yù)取會(huì)取回大量無(wú)用的Cache塊，占用訪存帶寬，還會(huì)導(dǎo)致嚴(yán)重的Cache污染問(wèn)題。由于硬件預(yù)取是基于訪存的歷史信息來(lái)預(yù)測(cè)未來(lái)的訪存模式，從而可以在數(shù)據(jù)使用之前將其從下一級(jí)的存儲(chǔ)器中取回。

2.2 軟件預(yù)取

當(dāng)代微處理器大都提供了預(yù)取指令來(lái)支持軟件的預(yù)取。軟件預(yù)取是指在編譯時(shí)由編譯器顯示加入預(yù)取指令，提前將下一級(jí)存儲(chǔ)器中的數(shù)據(jù)取回。因?yàn)榧尤肓舜罅康念A(yù)取指令，同時(shí)顯示的預(yù)取指令需要計(jì)算出準(zhǔn)確的預(yù)取地址，從而導(dǎo)致不能及時(shí)的發(fā)出預(yù)取指令以足夠隱藏訪存延時(shí)，影響了性能的提高。并且必須使額外的預(yù)取指令開(kāi)銷不能超過(guò)預(yù)取所能帶來(lái)的效益，否則得不償失。

2.3 軟硬件結(jié)合的預(yù)取

考慮到硬件預(yù)取和軟件預(yù)取的缺點(diǎn)，現(xiàn)在有不少學(xué)者提出用軟硬件結(jié)合的方法來(lái)解決這些問(wèn)題。基本方法都是圍繞軟件給予硬件一些關(guān)于程序的信息，克服單純的硬件預(yù)取的盲目性，從而可以得到更高的性能，更具有吸引力。如提出的GRP技術(shù)，它是由編譯提供預(yù)取的時(shí)機(jī)、預(yù)取的步長(zhǎng)、預(yù)取的元素?cái)?shù)目等信息，由硬件完成預(yù)取動(dòng)作。

3 對(duì)Cache失效問(wèn)題的研究

Cache失效通常被分為三類，分別為強(qiáng)制性失效、沖突失效和容量失效。有很多技術(shù)關(guān)注的是減少?zèng)_突性失效，但是它們對(duì)于沖突失效和容量失效則不能解決。預(yù)取技術(shù)預(yù)測(cè)將會(huì)引起Cache失效的訪存，利用存儲(chǔ)器的空閑帶寬，提前將其取回，從而隱藏由于訪存延遲引起的處理器停頓。能夠很好的解決強(qiáng)制性失效和容量失效。

一般來(lái)說(shuō)，CPU并不直接與存儲(chǔ)器交換數(shù)據(jù)，而是通過(guò)Cache間接進(jìn)行。由平均訪存時(shí)間公式和程序運(yùn)行時(shí)間公式可以看出，Cache失效對(duì)于系統(tǒng)的性能有著很大的影響。因此，為了改進(jìn)系統(tǒng)的性能，首先必須要找出Cache失效的特點(diǎn)。

通過(guò)對(duì)NPB訪存行為的研究，發(fā)現(xiàn)在NPB測(cè)試集中線性訪存模式是造成Cache失效的最主要的原因。統(tǒng)計(jì)結(jié)果表明，由線性訪存模式直接引起的Cache失效占程序總的Cache失效次數(shù)的68.6%;而若考慮由此引起的Cache污染對(duì)失效率的影響該比例上升至78.2%。同時(shí)，線性訪存模式具有模式簡(jiǎn)單，便于優(yōu)化的優(yōu)點(diǎn)。因此，在研究Cache行為、提高Cache利用率以及設(shè)計(jì)新的軟件可管理的Cache結(jié)構(gòu)時(shí)應(yīng)該對(duì)這類訪存模式給予考慮。

對(duì)于線性訪存模式所引起的大量失效，預(yù)取是個(gè)很好的選擇。使用預(yù)取技術(shù)，能使數(shù)據(jù)和指令可在CPU使用之前到達(dá)與CPU更近的存儲(chǔ)層次，因此在真正需要它們時(shí)能及時(shí)的拿到或者可以減少延時(shí)和阻塞的時(shí)間。但是預(yù)取面臨著下面幾個(gè)問(wèn)題:

a.什么時(shí)候進(jìn)行預(yù)取;b.預(yù)取什么樣的數(shù)據(jù);c.預(yù)取到的數(shù)據(jù)放在什么位置。

而如果沒(méi)有解決好其中某些問(wèn)題，則會(huì)導(dǎo)致:

a.大量無(wú)用數(shù)據(jù)塊的取回，以及由此導(dǎo)致的帶寬的浪費(fèi);b.預(yù)取的數(shù)據(jù)造成了將要使用數(shù)據(jù)的替換，造成Cache性能的下降;c.預(yù)取時(shí)機(jī)過(guò)早或過(guò)晚，數(shù)據(jù)在沒(méi)有使用前就被替換出去或者是要使用時(shí)還沒(méi)有取回。

4 軟硬件結(jié)合的預(yù)取技術(shù)探討

Cache對(duì)于NPB這類計(jì)算密集型的應(yīng)用性能發(fā)揮不足;這是由于程序中不同代碼段的數(shù)據(jù)集具有不同的訪存模式而Cache卻對(duì)它們采用了統(tǒng)一的策略所造成的。

4.1 編譯指導(dǎo)的失效時(shí)預(yù)取

一個(gè)好的預(yù)取技術(shù)的基礎(chǔ)是能夠準(zhǔn)確的預(yù)測(cè)程序未來(lái)的訪存行為。而線性訪存模式對(duì)應(yīng)為程序中訪問(wèn)的地址隨時(shí)間按照線性規(guī)律變化，并且這類訪存模式在科學(xué)計(jì)算、數(shù)據(jù)庫(kù)、多媒體等應(yīng)用中占有很大的比例。恰恰也正是線性訪存模式造成了程序中相當(dāng)一部分的Cache失效。如果能夠很好的解決線性訪存模式的訪存失效引起的大量CPU停頓，則可能會(huì)大大改善系統(tǒng)的性能。根據(jù)局部性原理，程序即將用到的數(shù)據(jù)塊多數(shù)情況下與當(dāng)前訪問(wèn)的數(shù)據(jù)塊在空間上是相鄰的或者是臨近的。失效時(shí)預(yù)取技術(shù)(Prefetch On Miss)就是利用這個(gè)基本原理，具體做法是在訪存引起Cache失效時(shí)取回兩個(gè)Cache塊:請(qǐng)求的數(shù)據(jù)塊和順序的一下個(gè)數(shù)據(jù)塊。

4.2 編譯指導(dǎo)的基于訪存預(yù)測(cè)表的預(yù)取技術(shù)

以上提出的編譯指導(dǎo)的失效時(shí)預(yù)取技術(shù)和傳統(tǒng)失效時(shí)預(yù)取技術(shù)相比，可以大大的提高預(yù)取的準(zhǔn)確度，減少Cache的污染。但是，編譯指導(dǎo)的失效時(shí)預(yù)取只有在訪存發(fā)生Cache失效時(shí)才會(huì)啟動(dòng)預(yù)取動(dòng)作，預(yù)取順序的下一個(gè)Cache塊。對(duì)于數(shù)組順序遍歷的訪問(wèn)模式，失效時(shí)預(yù)取(預(yù)取度為1)可以將失效率降低一半。但是可以看到，對(duì)于跨步式或是逆序的訪問(wèn)模式，失效時(shí)預(yù)取會(huì)糟糕。因?yàn)榭绮绞交蚴悄嫘虻脑L問(wèn)模式在訪存發(fā)生Cache失效后不會(huì)在短時(shí)間內(nèi)訪問(wèn)順序的下一個(gè)Cache塊，而失效時(shí)預(yù)取則不斷的取回了大量的無(wú)用塊，造成Cache污染。即使增加了編譯的指導(dǎo)對(duì)于這類訪問(wèn)模式也只能采取不預(yù)取的策略。但線性訪存模式是最具有規(guī)律性的訪問(wèn)模式，很容易預(yù)測(cè)，同時(shí)在程序總訪存量中占有很大的比例，所以應(yīng)該采用更高級(jí)的策略來(lái)處理線性訪問(wèn)模式。如果硬件能夠在編譯所給的提示下，在Cache還沒(méi)有發(fā)生失效時(shí)就能夠預(yù)測(cè)到將會(huì)訪問(wèn)到的數(shù)據(jù)，并不斷地將其提前取回，那么預(yù)取的性能將會(huì)大大的提升。

5 性能評(píng)測(cè)

在選定模擬器和測(cè)試集后，需要確定測(cè)試方案和測(cè)試內(nèi)容，以便在模擬器中實(shí)現(xiàn)。測(cè)試方案如上表所示。

同時(shí)需要對(duì)Cache的失效率、下一級(jí)存儲(chǔ)器的訪問(wèn)帶寬和IPC等性能做比較，來(lái)評(píng)估設(shè)計(jì)的性能。失效率是為了確定存儲(chǔ)系統(tǒng)的性能，計(jì)算平均訪存時(shí)間;下一級(jí)存儲(chǔ)器的訪問(wèn)帶寬是為了說(shuō)明不同技術(shù)之間在存儲(chǔ)器帶寬代價(jià)上的差異;最后IPC是整個(gè)系統(tǒng)運(yùn)行的性能參數(shù)，為了比較整個(gè)系統(tǒng)性能的。只有IPC有所提高，才能說(shuō)明某項(xiàng)技術(shù)是有效的。

模擬器驗(yàn)證采用在測(cè)試程序一級(jí)加入宏指令以實(shí)現(xiàn)對(duì)硬件預(yù)取的指導(dǎo)。我們?cè)?impleScalar sim-outorder模擬器上修改實(shí)現(xiàn)了失效時(shí)預(yù)取、編譯指導(dǎo)的失效時(shí)預(yù)取、硬件預(yù)測(cè)表、編譯指導(dǎo)的硬件預(yù)測(cè)表以及帶有EM提示的編譯指導(dǎo)的硬件預(yù)測(cè)表模擬器。對(duì)NPB的五個(gè)核程序分別在模擬器上進(jìn)行了測(cè)試。

6 實(shí)驗(yàn)結(jié)果分析

編譯指導(dǎo)的失效時(shí)預(yù)取技術(shù)性能分析

預(yù)取塊數(shù)不同時(shí)編譯指導(dǎo)的失效時(shí)預(yù)取和不加編譯指導(dǎo)的失效預(yù)取的失效率的比較，其中橫軸代表不同的測(cè)試程序，縱軸為采用編譯指導(dǎo)的失效時(shí)預(yù)取后的失效率與傳統(tǒng)的失效時(shí)預(yù)取技術(shù)失效率的比值。從中發(fā)現(xiàn)，在預(yù)取1塊時(shí)編譯指導(dǎo)的預(yù)取和不加編譯指導(dǎo)的預(yù)取失效率相差不多，各有好壞。這是因?yàn)榇藭r(shí)由于預(yù)取的錯(cuò)誤所造成的對(duì)將要使用數(shù)據(jù)的替換并不會(huì)對(duì)性能造成嚴(yán)重影響，但由前面的分析知道，不加編譯的預(yù)取對(duì)帶寬的浪費(fèi)較多。隨著預(yù)取塊數(shù)的增加，沒(méi)有編譯指導(dǎo)的失效時(shí)預(yù)取對(duì)下一級(jí)存儲(chǔ)器的訪問(wèn)次數(shù)則迅速的攀升。當(dāng)預(yù)取塊數(shù)目繼續(xù)增多時(shí)，不加編譯指導(dǎo)的預(yù)取失效率開(kāi)始上升，而有編譯指導(dǎo)的預(yù)取則失效率還會(huì)下降，只是下降的速率有所減緩。

編譯指導(dǎo)的基于訪存預(yù)測(cè)表的預(yù)取技術(shù)性能分析

不同測(cè)試程序分別在不采用預(yù)取、采用傳統(tǒng)的RPT預(yù)取和采用編譯指導(dǎo)的RPT預(yù)取時(shí)的失效率，其中傳統(tǒng)的RPT和編譯指導(dǎo)的RPT均配置為4個(gè)表項(xiàng)。從中可以看出，在沒(méi)有編譯指導(dǎo)時(shí)，采用RPT預(yù)取和沒(méi)有任何預(yù)取相比幾乎沒(méi)有效果。而在有編譯指導(dǎo)的硬件預(yù)測(cè)表技術(shù)下，則Cache失效率明顯下降。和傳統(tǒng)的LRU相比，下降率在91%之間，平均達(dá)到了67%。

[1]張晨曦，計(jì)算機(jī)體系結(jié)構(gòu)，高等教育出版社，2000年

[2]杜紅燕，田興彥，田新華，一種新穎的軟件可控Cache優(yōu)化方法，計(jì)算機(jī)工程與應(yīng)用，2005年