計算機高速緩存相關概念的案例教學

趙佳利，彭雙和，韓 靜

（北京交通大學 智能交通數據安全與隱私保護技術北京市重點實驗室，北京 100044）

0 引言

近年來，基于計算機微體系結構相關知識進行側信道攻擊[1]的研究成為熱點之一。其中，基于計算機存儲體系訪問不同存儲部件時間差異的側信道攻擊，利用Cache與主存之間的存取時間差異進行攻擊，從而獲取密碼算法中的私鑰信息，給信息安全造成了極大的威脅。

Cache[2]是一種高速緩沖存儲器，用于保存CPU頻繁使用的數據，解決CPU與內存之間的顯著速度差異。在使用Cache技術的處理器上，當一條指令要訪問內存的數據時，首先查詢Cache緩存中是否有數據以及數據是否過期，如果數據未過期，則從Cache讀出數據。處理器會定期回寫Cache中的數據到內存。

目前主流的CPU Cache分為一級緩存[3]（簡稱為L1）和二級緩存，部分還有三級緩存。一個四核三級緩存的緩存結構見圖1，每一級緩存中存儲的全部數據都是下一級緩存的一部分。CPU在讀取數據時，首先會在一級緩存中尋找數據，如果沒有找到就去二級緩存中尋找，如果還沒有找到就去三級緩存中尋找，如果整個Cache都沒有，則去內存中尋找，然后將數據緩存到Cache中。Cache的級別越低，離CPU越近，相應地速度越快，而存儲容量越小。

圖1 四核CPU三級緩存的緩存結構

這種側信道攻擊從理論上來講，比較容易理解，但實現起來學生覺得無從下手，主要原因是教學涉及的實踐環節比較少。

1 教學改革的重要性

在本科教學中，很多課程（如操作系統、計算機組成原理、系統結構等）都提到了Cache；在最終考核中，Cache也占一席之地。然而在實際教學中，教師往往只對Cache進行簡單介紹，導致學生只學會了概念而沒有理解原理，就進行下一步的學習；教師也將重點放在如何進行Cache分組等內容上。因此，學生難以理解和吃透這部分內容，后續想針對Cache進行進一步的研究存在一定的困難。

當前真正研究硬件和計算機微體系結構的人才越來越少，因此教學改革不僅是為了讓學生理解Cache的相關概念，也想激發學生對計算機底層研究的興趣。

2 相關原理介紹

2.1 預取技術

預取技術[4]的好壞很大程度上決定了CPU的性能，是CPU 設計者在設計CPU時需要重點考慮的問題，現代處理器大多實現了硬件預取。預取技術主要利用時間和空間局部性原理[5]：時間局部性指程序即將用到的指令/數據可能就是目前正在使用的指令/數據，即訪問過的數據在未來仍有可能被訪問；空間局部性指程序即將用到的指令/數據可能與目前正在使用的指令/數據在空間上相鄰或者相近，即訪問數據的鄰近數據在未來可能會被訪問。

CPU檢測運行程序的存儲訪問模式，并且預測哪些數據下次會被訪問。舉例來說，固定步長預取[6]是：如果運行的程序有規律地讀取數據，則CPU讀取一次數據就進行預取。如果預取未命中，說明預取的地址與偏離的地址有一定的距離，CPU調整預取值；而當一次預取命中后，CPU會將固定偏移值的數據緩存到Cache中，使下一次讀取不必再從內存中讀取數據。

預取的目的是為了使CPU讀取需要的數據時，直接命中緩存，從而避免從更慢的數據源訪問，提升系統的性能。CPU將數據緩存到Cache中都是以Cache Line為單位的，Cache Line[7]是Cache的基本單位，一般為64字節。也就是說，一次緩存會緩存64字節的數據到Cache中。

2.2 Pointer-chase

現代CPU通常具有多種預取方式來提高性能，但在用時間測試Cache大小時往往會因為CPU的預取功能而使測試遇到阻礙，可以參考Afborchert[8]的pointer-chase消除CPU的預取。

Pointer-chase[9]是一種指針遍歷機制，即用指針將下一個元素地址存放在上一個元素中，有多種方式，如線性的或者隨機的。筆者采用隨機方式，其原理見圖2。

以10個元素的存儲空間為例，每個元素都存有下一元素的地址，見圖2。Mem[3]←&Mem[1]，Mem[1]←&Mem[4]，Mem[4]←&Mem[8]……這樣，遍歷Mem中元素時消除了CPU預取的發生。

圖2 random-chase原理圖

3 實驗設計

實驗的設計原則是讓學生對Cache的各種概念（如：預取時Cache Line的大小，各級Cache的大小及其工作原理）有更深的認識。可根據Cache 的工作原理和特性設計如下的相關實驗，通過實驗，教師在上課時能更直觀地講解Cache及其相關知識內容。

論文設計實驗的測試都基于Intel(R) Core(TM)i5-2400@3.10GHz的PC，其CPU相關信息見表1。

表1 測試機CPU配置信息 KB

3.1 實驗一：Cache Line預取

本實驗主要讓學生理解Cache基本單元Cache Line的概念及其大小。依據計算機存儲體系，數據訪問時Cache命中的時間要比Cache未命中的時間短很多，而Cache預取是將一個Cache Line大小的字節緩存到Cache中。當數據第一次被訪問時，一般都處于未命中狀態。隨后預取部件將該地址處的數據及其后續連續一個Cache Line的數據從內存中緩存到Cache中，因此接下來的63字節都是命中的狀態。通過比較兩次未命中的間隔可以得出Cache Line的大小。

實現過程：定義兩個char型字符數組data1和data2，定義兩個循環。循環1順序訪問data1中的數據，循環2每隔8步訪問data2中的數據，time_access_no_flush是一個記錄訪問時間的函數。假設Cache Line的大小為64，則循環1兩次未命中的時間間隔為63，而循環2兩次未命中的時間間隔為7，通過記錄訪問時間可以得到Cache Line的大小，也驗證了Cache預取，核心代碼如下：

實驗結果分析：隨著數組下表的增長繪制訪問時間得到圖3，可以看出步長為1時，大概每隔63個點出現一個峰值，此時為Cache未命中狀態，因此訪問時間較長；而步長為8時，每隔7個點出現一次峰值，此時也為Cache未命中狀態。由圖3可以看出，CPU一次緩存一個Cache Line的大小是64字節，即Cache Line = 64B。

3.2 實驗二：固定步長預取（兩種方式）

本實驗讓學生理解CPU在訪問數據時會進行固定步長數據的預取，因此會大大提高CPU訪問數據的效率，分兩種方式進行驗證。

1）通過不同步長的平均訪問時間驗證預取。

CPU會進行固定步長的預取，不管步長為多少，CPU每次訪問數據的時間應該是一樣的。

實現過程：對于固定步長預取，首先定義一個整型數組times存放每次訪問數據所需時間，設計二層循環。第一層循環代表步長逐漸增大，每次重新分配一段固定的內存用來數據訪問，確保將要訪問的數據不在Cache中；第二層循環則使用設置的步長間隔地訪問數據，最后將得到的數據除以訪問的次數得到平均一次訪問時間。核心代碼如下：

圖3 Cache Line 大小測試結果

實驗結果分析：隨著步長的增長繪制實驗數據平均訪問時間得到圖4。隨著步長的增大，平均訪問時間一直保持在較平穩的狀態。因此固定步長訪問數據時，CPU會對固定步長的數據進行預取從而優化性能。

2）通過比較隨機步長和固定步長的訪問時間來驗證。

固定步長的平均訪問時間是相同的，那么隨機步長的訪問時間是怎樣的呢？根據猜想，固定步長時CPU能正確預取，但是隨機步長時，CPU無法成功預取，因此每次訪問應該都是未命中的情況。

圖4 固定步長預取平均訪問時間

實現過程：定義循環1，為了消除Cache Line預取帶來的影響，固定步長為64，記錄每次訪問數據所需的時間；定義循環2，將步長設置為大于64的隨機數，但為了獲得較多組數據，因此設置上限為320（可自定義），并將每次訪問數據的時間記錄下來。核心代碼如下：

實驗結果分析：隨步長變化將固定步長和隨機步長的平均訪問時間繪制成圖5。固定步長為64時，CPU在幾次訪問后能調整預取值，成功進行預取，之后一直都是Cache命中狀態。而隨機步長時，因為每次的步長都為隨機值，CPU無法預取成功，因此一直都是Cache未命中狀態。

3.3 實驗三：各級Cache 大小

本實驗是讓學生理解Cache的緩存結構，目前通常分為三級緩存，Cache的級別越低，容量越小，速度越快。

圖5 固定步長和隨機步長的差異

在Cache Size測試時設計了幾個實驗，都無法得到Cache Size。經過分析，發現是預取引起的，因此參考了pointer-chase的random-chase機制，創建一個隨機指針追逐的數組來消除CPU預取。每個數組元素存放的是下一個隨機的數組元素地址，使用指針可以輕松地遍歷數組元素。

random-chase的實現過程：首先定義一個索引數組indices，一個隨機指針追逐數組len和二重指針memory，然后順序賦值索引數組indices，使每個數組元素等于它的索引值。使用g++11的隨機數生成器，隨機交換元素的值，生成亂序的indices數組，然后根據亂序的索引數組indices賦值隨機指針追逐數組len。使用二重指針memory以及打亂的indices索引為len的每個元素賦值，將memory[indices[i]]的地址賦值給memory[indices[i-1]]，生成隨機指針追逐數組len。核心代碼如下：

通過random-chase機制，消除了Cache測試中預取帶來的麻煩，接下來對Cache Line的大小進行測試，由于每級Cache的大小不同，并且每級Cache的訪問速度也不同，越接近CPU的L1越快越小，以此類推。因此，對不同大小的數組進行大量訪問（例如230次），根據數組的大小和Cache每級大小的關系[10]（以3級Cache為例），可以分為以下4種情況。

（1）Array_Size

（2）L1≤Array_Size

（3）L2≤Array_SizeL2的訪問時間>L1的訪問時間，因此平均訪問時間會比2大但在此階段內保持相對穩定。

（4）Array_Size>L3：數組大小大于L3，則整個Cache緩存不下所有數組，部分數據會存在內存中。訪問內存的時間肯定大大高于訪問Cache的時間，因此平均訪問時間一定突增并隨著Array_Size的變大而持續增大。

每個階段代表每級Cache的平均訪問時間，但每兩個階段之間會有一個時間上的突變，而臨界點即是每級Cache的大小。

定義二重指針p，將隨機指針追逐數組的首地址賦值給p，然后使用p進行SAMPLES次指針訪問，記錄時間，并除以SAMPLES得到平均一次訪問的時間，核心代碼如下：

實驗結果分析：隨著數組大小的增長繪制平均訪問時間得到圖6。可以看出，在數組大小為32KB之前，平均訪問時間都是較小的平穩值，在32KB之后平均訪問時間產生了變化，因此可得出L1級數據Cache的大小是32KB的結論；在256KB的時候，平均訪問時間又增大，因此可得出L2級Cache的大小是256KB的結論；在6MB之后，平均訪問時間迅速增大，因此可得出L3級Cache的大小是6MB的結論。由實驗得到的結果與表1測試機器的配置完全吻合。

4 結語

筆者就Cache的相關特性、預取、Cache Line的大小、各級Cache的大小和訪問速度進行了實驗設計和驗證。Cache及其相關特性是本科計算機教學中相當重要的一塊。對學生而言，可以自己動手設計幾個實驗獲得計算機相關Cache信息，能更深刻地領會其中的原理，且動手參與實驗能增加學生的思考能力，激發學生興趣，增強學生的動手實踐能力。

后續，筆者將依據虛擬地址與物理地址轉換[11]、TLB相關原理[12]設計實驗進行原理展示與驗證，讓學生對操作系統內部地址轉換機制有更深層次的理解與探索。