一種軟硬結合的預取技術探討

唐言

（黑龍江省教育學院，黑龍江 哈爾濱 150000）

1 課題背景和研究現狀

現代處理器速度的快速發展和存儲器速度的慢速發展導致處理器要花費大量的時間等待存儲器數據的返回，這就是存儲墻問題。例如，Alpha 21264 667 MHz的工作站一次訪存失效造成的開銷就高達128個時鐘周期!

為了解決這個問題，預取技術就被提了出來，通過計算和訪存的重疊，在Cache可能會發生失效之前發出預取請求以便在該數據真正被使用到時己提前將數據塊取入Cache，從而避免Cache失效造成的處理器停頓。

2 相關工作

數據預取是用來解決或者說隱藏局部性不足的訪存模式，在數據將要使用前將其由下一級存儲器取回Cache，保證CPU可以無停頓的執行。預取必須保證及時、準確并且引入盡可能小的額外開銷。同時預取的負面效應也是必須考慮的因素，例如Cache污染和帶寬的浪費。現在有多種多樣的預取技術，但它們各有千秋，沒有哪一種預取策略己被證明是最優的。下表比較了它們各自的優缺點。

2.1 硬件預取

硬件預取是由硬件根據訪存的歷史信息，對未來可能的訪存單元預先取入Cache，從而在數據真正被用到時不會造成Cache失效。但是由于只是基于訪存的歷史信息，硬件預取會取回大量無用的Cache塊，占用訪存帶寬，還會導致嚴重的Cache污染問題。由于硬件預取是基于訪存的歷史信息來預測未來的訪存模式，從而可以在數據使用之前將其從下一級的存儲器中取回。

2.2 軟件預取

當代微處理器大都提供了預取指令來支持軟件的預取。軟件預取是指在編譯時由編譯器顯示加入預取指令，提前將下一級存儲器中的數據取回。因為加入了大量的預取指令，同時顯示的預取指令需要計算出準確的預取地址，從而導致不能及時的發出預取指令以足夠隱藏訪存延時，影響了性能的提高。并且必須使額外的預取指令開銷不能超過預取所能帶來的效益，否則得不償失。

2.3 軟硬件結合的預取

考慮到硬件預取和軟件預取的缺點，現在有不少學者提出用軟硬件結合的方法來解決這些問題。基本方法都是圍繞軟件給予硬件一些關于程序的信息，克服單純的硬件預取的盲目性，從而可以得到更高的性能，更具有吸引力。如提出的GRP技術，它是由編譯提供預取的時機、預取的步長、預取的元素數目等信息，由硬件完成預取動作。

3 對Cache失效問題的研究

Cache失效通常被分為三類，分別為強制性失效、沖突失效和容量失效。有很多技術關注的是減少沖突性失效，但是它們對于沖突失效和容量失效則不能解決。預取技術預測將會引起Cache失效的訪存，利用存儲器的空閑帶寬，提前將其取回，從而隱藏由于訪存延遲引起的處理器停頓。能夠很好的解決強制性失效和容量失效。

一般來說，CPU并不直接與存儲器交換數據，而是通過Cache間接進行。由平均訪存時間公式和程序運行時間公式可以看出，Cache失效對于系統的性能有著很大的影響。因此，為了改進系統的性能，首先必須要找出Cache失效的特點。

通過對NPB訪存行為的研究，發現在NPB測試集中線性訪存模式是造成Cache失效的最主要的原因。統計結果表明，由線性訪存模式直接引起的Cache失效占程序總的Cache失效次數的68.6%;而若考慮由此引起的Cache污染對失效率的影響該比例上升至78.2%。同時，線性訪存模式具有模式簡單，便于優化的優點。因此，在研究Cache行為、提高Cache利用率以及設計新的軟件可管理的Cache結構時應該對這類訪存模式給予考慮。

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

a.什么時候進行預取;b.預取什么樣的數據;c.預取到的數據放在什么位置。

而如果沒有解決好其中某些問題，則會導致:

a.大量無用數據塊的取回，以及由此導致的帶寬的浪費;b.預取的數據造成了將要使用數據的替換，造成Cache性能的下降;c.預取時機過早或過晚，數據在沒有使用前就被替換出去或者是要使用時還沒有取回。

4 軟硬件結合的預取技術探討

Cache對于NPB這類計算密集型的應用性能發揮不足;這是由于程序中不同代碼段的數據集具有不同的訪存模式而Cache卻對它們采用了統一的策略所造成的。

4.1 編譯指導的失效時預取

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

4.2 編譯指導的基于訪存預測表的預取技術

以上提出的編譯指導的失效時預取技術和傳統失效時預取技術相比，可以大大的提高預取的準確度，減少Cache的污染。但是，編譯指導的失效時預取只有在訪存發生Cache失效時才會啟動預取動作，預取順序的下一個Cache塊。對于數組順序遍歷的訪問模式，失效時預取(預取度為1)可以將失效率降低一半。但是可以看到，對于跨步式或是逆序的訪問模式，失效時預取會糟糕。因為跨步式或是逆序的訪問模式在訪存發生Cache失效后不會在短時間內訪問順序的下一個Cache塊，而失效時預取則不斷的取回了大量的無用塊，造成Cache污染。即使增加了編譯的指導對于這類訪問模式也只能采取不預取的策略。但線性訪存模式是最具有規律性的訪問模式，很容易預測，同時在程序總訪存量中占有很大的比例，所以應該采用更高級的策略來處理線性訪問模式。如果硬件能夠在編譯所給的提示下，在Cache還沒有發生失效時就能夠預測到將會訪問到的數據，并不斷地將其提前取回，那么預取的性能將會大大的提升。

5 性能評測

在選定模擬器和測試集后，需要確定測試方案和測試內容，以便在模擬器中實現。測試方案如上表所示。

同時需要對Cache的失效率、下一級存儲器的訪問帶寬和IPC等性能做比較，來評估設計的性能。失效率是為了確定存儲系統的性能，計算平均訪存時間;下一級存儲器的訪問帶寬是為了說明不同技術之間在存儲器帶寬代價上的差異;最后IPC是整個系統運行的性能參數，為了比較整個系統性能的。只有IPC有所提高，才能說明某項技術是有效的。

模擬器驗證采用在測試程序一級加入宏指令以實現對硬件預取的指導。我們在5impleScalar sim-outorder模擬器上修改實現了失效時預取、編譯指導的失效時預取、硬件預測表、編譯指導的硬件預測表以及帶有EM提示的編譯指導的硬件預測表模擬器。對NPB的五個核程序分別在模擬器上進行了測試。

6 實驗結果分析

編譯指導的失效時預取技術性能分析

預取塊數不同時編譯指導的失效時預取和不加編譯指導的失效預取的失效率的比較，其中橫軸代表不同的測試程序，縱軸為采用編譯指導的失效時預取后的失效率與傳統的失效時預取技術失效率的比值。從中發現，在預取1塊時編譯指導的預取和不加編譯指導的預取失效率相差不多，各有好壞。這是因為此時由于預取的錯誤所造成的對將要使用數據的替換并不會對性能造成嚴重影響，但由前面的分析知道，不加編譯的預取對帶寬的浪費較多。隨著預取塊數的增加，沒有編譯指導的失效時預取對下一級存儲器的訪問次數則迅速的攀升。當預取塊數目繼續增多時，不加編譯指導的預取失效率開始上升，而有編譯指導的預取則失效率還會下降，只是下降的速率有所減緩。

編譯指導的基于訪存預測表的預取技術性能分析

不同測試程序分別在不采用預取、采用傳統的RPT預取和采用編譯指導的RPT預取時的失效率，其中傳統的RPT和編譯指導的RPT均配置為4個表項。從中可以看出，在沒有編譯指導時，采用RPT預取和沒有任何預取相比幾乎沒有效果。而在有編譯指導的硬件預測表技術下，則Cache失效率明顯下降。和傳統的LRU相比，下降率在91%之間，平均達到了67%。

[1]張晨曦，計算機體系結構，高等教育出版社，2000年

[2]杜紅燕，田興彥，田新華，一種新穎的軟件可控Cache優化方法，計算機工程與應用，2005年