預取技術

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

基本介紹

• 中文名：預取技術
• 外文名：Prefetching technology

隨著計算機硬體的發展，CPU 主頻已由過去 MHz 發展到了現在的 GHz，而常用硬碟的存取速率還不到100M/S。並且根據摩爾定律，微處理器的速度以及單片集成度每18 個月就會翻一番，但像磁碟這樣的機械電子設備，存取速率每年僅增加約8%。由此看來，磁碟 I/O 無疑是整個性能提升的瓶頸，而且磁碟的訪問速率與 CPU 的速度差距還在持續擴大。 常用的存儲介質從光碟、磁碟、記憶體到高速快取，存取速度越來越快，但是成本也越來越高。為了在成本和性能之間進行平衡，現代計算機體系架構往往選擇使用少量性能高但成本也高的存儲器作為速度慢而成本也低的存儲器的快取。 所以整個存儲層次如同一個金字塔結構，如圖所示。

存儲器層次結構圖

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

. 為了解決這些問題，已提出多種技術方案， 其中最主要的有快取和預取技術兩種。快取技術是利用局部性原理， 使速度更快的上層存儲器成為下層存儲器的緩衝。基於技術的限制及成 本的考慮，上層存儲器的容量要比下層存儲器小得多。數據如果存在於上層存儲器中，就可以直接對其進行讀寫， 這種情形叫做命中，命中的統計機率叫做命中率；如果未命中就必須涉及到訪問下層存儲器，這種情形也叫失效。按照產生失效的原因不同，快取失效可分為：強制性失效、容量失效和衝突失效。 快取技術能否通過較快的存儲器禁止對較慢的存儲器的訪問， 完全取決於上層存儲器的命中率。 提高相聯度、Victim Cache、偽相聯 Cache 等技術以及好的快取替換算法都可降低快取衝突失效，從而提高快取命中率。 隨著套用規模的不斷擴大和上述技術的不斷成熟， 容量失效和強制性失效在總的快取失效次數當中所占的比例越來越大，成為影響快取性能的主要因素。 預取技術可以通過計算和訪存的重疊，隱藏因為快取延時而引起的快取失效，被認為是解決容量失效和強制性失效的有效手段。 隨著快取技術的廣泛套用，預取技術也在存儲控制器、作業系統、資料庫、網路、檔案系統等套用中起到了重要作用。

硬體預取

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

軟體預取

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

軟硬體結合

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

相關問題研究

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. 預取時機過早或過晚，數據在沒有使用前就被替換出去或者是要使用時還沒有取回。

技術探討

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

編譯指導的失效時預取

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

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

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

預取算法發展

固定預取算法

OBL（One-Block Look-ahead）是一種簡單的預取算法，它認為當數據塊 i 被訪問後，數據塊 i 之後的塊應該很快就會被訪問。 除了在開始的時候不進行預取外，在每個數據塊 i 被訪問後，第 i+1 塊都會被預取到快取里。OBL 由於每次預取只取一個數據塊，會導致頻繁地使用 I/O 讀磁碟， 從而浪費大量的尋道時間。 IBL （Infinite-Block Look-ahead）對OBL進行了簡單的擴展，每次預取數據塊 i 後的 n（預取度）個頁面，相比 OBL 增大了預取的 I/O 塊大小。 這兩種算法都是固定進行預取，具有盲目性，可能會造成快取污染和預取浪費， 特別是 IBL 的預取度比較大的時候。

順序預取算法

基於空間局限性原理，對順序序列來說，如果數據塊被訪問就意味著該數據塊之後的數據很快就會被訪問，這與固定預取算法的思想是一致的。 由此提出了基於順序預取的算法，其實現可按功能分為三部分：

①順序檢測模組：對順序序列的檢測通常是基於訪問歷史來確定的。 對具有大容量快取的存儲可直接根據存在於快取中數據進行分析，而對快取容量較小的存儲來說這些數據將不足以進行檢測，於是提出了一種基於表格的算法；

②預取模組：此模組用來決定預取的時機和預取度，是順序預取算法的核心部分。 通過預取數據命中率及預取浪費率等信息進行分析，從而自適應地改變預取行為；

③快取管理模組：該模組用來管理頁面的換出，希望把最為有用的數據留在快取裡面。 利用不同的 LRU 鏈管理順序和隨機的序列，通過邊際效應的大小來決定淘汰頁面，從而讓淘汰的損失最小化。

基於套用暗示的預取算法

像視頻、音頻、數據備份和恢復等很多套用其 I/O 基本是順序的，而 Web 套用其訪問是基於連結的分枝訪問，資料庫套用經常需要進行隨機訪問。 順序預取算法將不再適用於非順序序列的套用，於是文獻提出了由用戶暗示的透明信息預取方法（TIP）。TIP 可以根據用戶提供的訪問方式在適當的時候發出異步的預取指令，指令內容由用戶的暗示確定。 這類算法也可以有順序檢測模組，主要是增加了一個能夠提供給上層套用接口的模組， 套用通過此模組告知預取模組相應的信息。 由於預取信息由相應的套用自己提供，基於用戶對套用的了解，針對性強，預取也會更加準確。 通過以上描述可知，此類算法對套用不透明，需要上層套用的支持。

基於數據挖掘的預取算法

數據挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際套用數據中，提取隱含在其中的、人們事先不知道的、 但是又潛在有用的信息和知識的過程。 由用戶暗示的訪問方式的信息，也可以由數據挖掘技術來提取； 對某些開發者無法得知每個用戶訪問特點的套用，例如 Web 套用、數據挖掘技術同樣也能發揮重要作用。 預取算法根據數據挖掘對數據的分析提取出的信息決定需要預取的數據， 此算法對套用是透明的。 但是否能夠進行高效的預取，還在於其數據挖掘算法能否準確提取出套用潛在的訪問信息， 這也正是此算法的關鍵和難點所在。