計算機(jī)高速緩存相關(guān)概念的案例教學(xué)

趙佳利，彭雙和，韓 靜

（北京交通大學(xué) 智能交通數(shù)據(jù)安全與隱私保護(hù)技術(shù)北京市重點實驗室，北京 100044）

0 引言

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

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

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

圖1 四核CPU三級緩存的緩存結(jié)構(gòu)

這種側(cè)信道攻擊從理論上來講，比較容易理解，但實現(xiàn)起來學(xué)生覺得無從下手，主要原因是教學(xué)涉及的實踐環(huán)節(jié)比較少。

1 教學(xué)改革的重要性

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

當(dāng)前真正研究硬件和計算機(jī)微體系結(jié)構(gòu)的人才越來越少，因此教學(xué)改革不僅是為了讓學(xué)生理解Cache的相關(guān)概念，也想激發(fā)學(xué)生對計算機(jī)底層研究的興趣。

2 相關(guān)原理介紹

2.1 預(yù)取技術(shù)

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

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

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

2.2 Pointer-chase

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

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

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

圖2 random-chase原理圖

3 實驗設(shè)計

實驗的設(shè)計原則是讓學(xué)生對Cache的各種概念（如：預(yù)取時Cache Line的大小，各級Cache的大小及其工作原理）有更深的認(rèn)識?？筛鶕?jù)Cache 的工作原理和特性設(shè)計如下的相關(guān)實驗，通過實驗，教師在上課時能更直觀地講解Cache及其相關(guān)知識內(nèi)容。

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

表1 測試機(jī)CPU配置信息 KB

3.1 實驗一：Cache Line預(yù)取

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

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

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

3.2 實驗二：固定步長預(yù)?。▋煞N方式）

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

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

CPU會進(jìn)行固定步長的預(yù)取，不管步長為多少，CPU每次訪問數(shù)據(jù)的時間應(yīng)該是一樣的。

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

圖3 Cache Line 大小測試結(jié)果

實驗結(jié)果分析：隨著步長的增長繪制實驗數(shù)據(jù)平均訪問時間得到圖4。隨著步長的增大，平均訪問時間一直保持在較平穩(wěn)的狀態(tài)。因此固定步長訪問數(shù)據(jù)時，CPU會對固定步長的數(shù)據(jù)進(jìn)行預(yù)取從而優(yōu)化性能。

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

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

圖4 固定步長預(yù)取平均訪問時間

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

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

3.3 實驗三：各級Cache 大小

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

圖5 固定步長和隨機(jī)步長的差異

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

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

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

（1）Array_Size

（2）L1≤Array_Size

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

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

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

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

實驗結(jié)果分析：隨著數(shù)組大小的增長繪制平均訪問時間得到圖6?？梢钥闯觯跀?shù)組大小為32KB之前，平均訪問時間都是較小的平穩(wěn)值，在32KB之后平均訪問時間產(chǎn)生了變化，因此可得出L1級數(shù)據(jù)Cache的大小是32KB的結(jié)論；在256KB的時候，平均訪問時間又增大，因此可得出L2級Cache的大小是256KB的結(jié)論；在6MB之后，平均訪問時間迅速增大，因此可得出L3級Cache的大小是6MB的結(jié)論。由實驗得到的結(jié)果與表1測試機(jī)器的配置完全吻合。

4 結(jié)語

筆者就Cache的相關(guān)特性、預(yù)取、Cache Line的大小、各級Cache的大小和訪問速度進(jìn)行了實驗設(shè)計和驗證。Cache及其相關(guān)特性是本科計算機(jī)教學(xué)中相當(dāng)重要的一塊。對學(xué)生而言，可以自己動手設(shè)計幾個實驗獲得計算機(jī)相關(guān)Cache信息，能更深刻地領(lǐng)會其中的原理，且動手參與實驗?zāi)茉黾訉W(xué)生的思考能力，激發(fā)學(xué)生興趣，增強(qiáng)學(xué)生的動手實踐能力。

后續(xù)，筆者將依據(jù)虛擬地址與物理地址轉(zhuǎn)換[11]、TLB相關(guān)原理[12]設(shè)計實驗進(jìn)行原理展示與驗證，讓學(xué)生對操作系統(tǒng)內(nèi)部地址轉(zhuǎn)換機(jī)制有更深層次的理解與探索。