「計算機組成原理」：快取記憶體儲存器

緩衝儲存器有用嗎

一旦從儲存器讀入一個數據物件時，就儘可能使用它，使得時間區域性性最大。特別是區域性變數，編譯器會將其儲存在暫存器中。 這一章主要介紹儲存器層次結構中的快取記憶體部分，包含在CPU中，使用SRAM儲存器實現，完全由硬體管理。

當快取記憶體大小大於資料的大小，如果分配良好，則只會出現冷不命中。

快取不命中比記憶體訪問次數影響更大

由記憶體系統的設計來決定塊大小，是記憶體系統的固定引數。首先決定塊大小，然後決定期望的快取大小，然後再決定關聯性，最終就能知道組的數目。

塊的目的就是利用空間區域性性

快取是硬體自動執行的，沒有提供指令集對其進行操作

建議：

將注意力集中在內迴圈中，因為大部分的計算和記憶體訪問都集中在這裡按照資料物件儲存在記憶體中的順序，以步長為

1

來讀資料，使得空間區域性性最大。比如步長為

2

的命中率就比步長為

1

的命中率降低一半。一旦從儲存器讀入一個數據物件時，就儘可能使用它，使得時間區域性性最大。特別是區域性變數，編譯器會將其儲存在暫存器中。

這一章主要介紹儲存器層次結構中的快取記憶體部分，包含在CPU中，使用SRAM儲存器實現，完全由硬體管理。

1 快取記憶體儲存器

較早期的計算機系統的儲存器層次結構只有三層：

CPU暫存器

、

主存

和

磁碟

，但是隨著CPU的發展，使得

主存

和

CPU

之間的讀取速度逐漸拉大，由此在CPU和主存之間插入一個小而快速的

SRAM快取記憶體儲存器

，稱為

L1

快取記憶體，隨著後續的發展，又增加了

L2

快取記憶體和

L3

快取記憶體。

1.1 通用的快取記憶體儲存器組織結構

如上圖的b中所示，會將

m

位的的址劃分成三部分：

s位：

快取記憶體被組織成一個數組，而該陣列透過 $$ S=2^{s} $$ 進行索引。

b位：

每個組中包含

E

個

快取記憶體行（Cache Line）

，每個行有一個 $$ B=2^{b} $$ 位元組的資料塊（Block）組成。

t位：

每一個快取記憶體行有一個 $$ t=m-（s+b） $$ 位的標記位（Valid Bit），唯一表示儲存在這個快取記憶體行中的資料塊，用於搜尋資料塊。

該快取記憶體的結構可以透過元組

（S， E， B， m）

來描述，且容量C為所有塊的大小之和， C= S \times E \times B

C

=

S

×

E

×

B

。

注意：

如果將組索引放在最高有效位，則連續的記憶體塊就會對映到相同的快取記憶體組中，透過將組索引放在中間，可以使得連續的記憶體塊儘可能分散在各個快取記憶體組中，可以充分利用各個快取記憶體組

當一條載入指令指示CPU從主存地址A中讀取一個字w時，會將該主存地址A傳送到快取記憶體中，則快取記憶體會根據以下步驟判斷地址A是否命中：

組選擇：

根據地址劃分，將中間的s位表示為無符號數作為組的索引，可得到該地址對應的組。

行匹配：

根據地址劃分，可得到t位的標誌位，由於組內的任意一行都可以包含任意對映到該組的資料塊，所以就要線性搜尋組中的每一行，判斷是否有和標誌位匹配且設定了有效位的行，如果存在，則快取命中，否則緩衝不命中。

字抽取：

如果找到了對應的快取記憶體行，則可以將b位表示為無符號數作為塊偏移量，得到對應位置的字。

當快取記憶體命中時，會很快抽取出字w，並將其返回給CPU。如果快取不命中，CPU會進行等待，快取記憶體會向主存請求包含字w的資料塊，當請求的塊從主存到達時，快取記憶體會將這個塊儲存到它的一個快取記憶體行中，然後從被儲存的塊中抽取出字w，將其返回給CPU。

注意：

為了使得地址中的b位能夠編碼塊偏移量，要求從下一層儲存器中，根據塊偏移量的值從中截取出塊大小的資料塊。

該編碼方式具有以下特點：

能夠透過組索引位來唯一確定快取記憶體組

對映到同一個快取記憶體組的塊由標誌位唯一地標識

標記位和組索引位能夠唯一的表示記憶體中的每個塊

有可能會存在多個塊對映到同一個快取記憶體組中（只要地址的組索引相同）

可以根據每個組的快取記憶體行數E，將快取記憶體分成不同的型別

1.1.1 直接對映快取記憶體

如上圖所示，當 E = 1

E

=1 時，快取記憶體稱為

直接對映快取記憶體（Direct-mapped Cache）

，每個快取記憶體組中只含有一個快取記憶體行。

當快取不命中時需要進行快取行替換，會先從下一層的儲存器中請求得到包含目標的塊，然後根據地址計算出快取記憶體組的索引，然後由於一個組中只含有一個快取記憶體行，所以會直接將該塊替換當前的塊。

這裡需要注意的一點是：

當程式訪問大小為

2

的冪的陣列時，直接對映快取記憶體中通常會發生衝突不命中。

1。float dotprod（float x［8］， float y［8］ ）

2。{

3。 float sum = 0。0；

4。 int i；

5。

6。 for（i = 0；i < 8；i++ ）

7。 sum += x［i］ * y［i］；

8。 return sum；

9。}

我們首先假設陣列

x

排在陣列

y

之前，且

x

的地址從

0

開始。然後直接對映快取記憶體的 b=2

b

=2 和 s=2

s

=2 ，即有兩個快取記憶體組，每個快取記憶體組有一個快取記憶體行，每個快取記憶體行能儲存

16

位元組資料塊，即

4

個浮點數，則快取記憶體容量為

32

位元組，我們可以得到快取記憶體對地址的劃分如下所示（

64

位系統中）

然後我們可以根據這兩個陣列的地址得到它們在快取記憶體中的組索引（因為只有一個快取記憶體行，所以不考慮標誌位）

我們可以發現，迴圈第一次迭代引用

x［0］

時，快取不命中會使得包含

x［0］~x［3］

的資料塊儲存到快取記憶體組

0

處，但是當引用

y［0］

時，會發現快取記憶體組0處儲存的資料不匹配，又出現了快取不命中，就會使得包含

y［0］~y［3］

的資料塊儲存到快取記憶體

0

處，依次類推。可以發現始終會發生快取不命中，使得效能下降。這種情況稱為

抖動（Thrash）

，即快取記憶體反覆地載入和驅逐相同的快取記憶體塊的組。

可以發現：

即使程式的區域性性良好，且工作集的大小沒有超過快取記憶體容量，但是由於這些資料塊都被對映到了相同的快取記憶體組中，且直接對映快取記憶體每個組中只有一個快取記憶體行，所以會出現抖動，不斷出現快取不命中。

我們這裡想要相同所以的

x

和

y

可以儲存到不同的快取記憶體組中，就能避免抖動現象，這裡可以在陣列

x

後填充

B

個位元組，使得陣列

y

的地址向後偏移，得到如下形式

1.1.2 組相連快取記憶體

直接對映快取記憶體的衝突不命中是由於每個快取記憶體組中只有一個快取記憶體行，所以擴大

E

的值，當 1 < E < C/B1<

E

<

C

/

B

時，稱為

E路組相聯快取記憶體（Set Associative Cache）

，此時需要額外的硬體邏輯來進行行匹配，所以更加昂貴。（ E < C/B

E

<

C

/

B

即要求 S > 1

S

>1 ）

2路組相連快取記憶體

當快取不命中時需要進行快取行替換，如果對應的快取記憶體組中有空的快取記憶體行，則直接將其儲存到空行中。但是如果沒有空行，就要考慮合適的

替換策略：

最簡單的替換策略是隨機選擇要替換的行

最不常使用（Least-Frequently-Used，LFU）策略：

替換過去某個時間視窗內引用次數最少的一行。

最近最少使用（Least-Recently-Used，LRU）策略：

替換最後一次訪問時間最久遠的那一行

1.1.3 全相聯快取記憶體

全相聯快取記憶體（Full Associative Cache）

是用一個包含所有快取記憶體行的組組成的，其中 E = C/B

E

=

C

/

B

，即 S = 1

S

=1 。

由於全相聯快取記憶體只有一個組，所以不包含組索引編碼

其行匹配和字選擇與組相聯快取記憶體相同，只是規模大小不同。想要得到高速的全相聯快取記憶體十分困難，所以通常適合用於較小的快取記憶體，比如虛擬記憶體中的翻譯備用緩衝器（TLB）。

1.2 寫操作

當CPU想要對地址A進行寫操作時，會透過地址A判斷是否快取了該地址，如果快取了稱為

寫命中（Write Hit）

，否則稱為

寫不命中（Write Miss）

。

寫命中：

快取記憶體會先更新快取的副本，然後可以採取不同方法更新下一層的副本

直寫（Write-Though）：

立即更新下一層的副本值。缺點是每次寫都會引起匯流排流量。

寫回（Write-Back）：

為每個快取記憶體行維護一個

修改位（Dirty Bit）

，表明這個快取記憶體塊是否被修改。當被修改的快取記憶體塊被驅逐時，會檢視修改位，判斷該塊是否被修改，只有被修改才會更新下一層的副本值。能夠顯著減少匯流排流量，但是複雜性高。

寫不命中：寫不分配（Not-Write-Allocate）：

直接將字寫到下一層中。

寫分配（Write-Allocate）：

載入相應的下一層的塊到當前層的快取記憶體中，然後更新當前快取記憶體塊。得益於空間區域性性，進行一次寫分配後，下一次有較高几率會寫命中，但是缺點是每次寫不命中就要將塊從第一層向上傳輸。

直寫快取記憶體通常為寫不分配的，寫回快取記憶體通常為寫分配的。

建議採用寫回寫分配模型，因為隨著邏輯電路密度的提高，寫回的複雜性不再成為阻礙，並且和處理讀相同，都利用了局部性原理，效率較高。

1.3 真實快取記憶體結構

之前介紹的快取記憶體值儲存程式資料，但是快取記憶體同樣也能儲存指令。可以將快取記憶體分成以下幾種：

i-cache：

只儲存指令的快取記憶體

d-cache：

只儲存程式資料的快取記憶體

Unified Cache：

既能儲存指令，也能儲存程式資料的快取記憶體

如上圖所示是

Intel Core i7

的快取記憶體層次結構，可以發現在L1快取記憶體中分成了

L1 d-cache

和

L1 i-cache

，這樣做的

好處在於：

將資料和指令分別儲存在兩個快取記憶體中，使得處理器可以同時讀一個指令字和一個數據字

i-cache通常是隻讀的，所以會比較簡單

可以針對不同的訪問模式最佳化這兩個快取記憶體，使用不同的塊大小、相聯度和容量

確保資料訪問和指令訪問之間不形成衝突不命中

代價就是會導致快取記憶體容量變小，提高出現容量不命中的可能性。

1.4 引數對效能的影響

衡量快取記憶體的指標有：

命中率（Hit Rate）：

記憶體引用命中的比率，命中數量/引用數量。

不命中率（Miss Rate）：

記憶體引用不命中的比率，不命中數量/引用數量。通常，L1快取記憶體為3~10%，L2快取記憶體為<1%。

命中時間（Hit Time）：

從快取記憶體傳輸一個字到CPU的時間，包括組選擇、行匹配和字選擇時間。通常，

L1

快取記憶體需要

4

個時鐘週期，

L2

快取記憶體需要

10

個時鐘週期。

不命中處罰（Miss Penalty）：

當快取不命中時，要從下一層的儲存結構中傳輸對應塊到當前層中，需要額外的時間（不包含命中時間）。通常，貯存需要

50~200

個時鐘週期。

注意：

命中和不命中兩者對效能影響很大，比如

99%

命中率的效能會比

97%

命中率

高兩倍

。

接下來討論快取記憶體中不同引數對快取記憶體效能的影響：

引數優點缺點建議

快取記憶體大小越大提高命中率增加命中時間L1

塊大小越大利用程式的空間區域性性，提高命中率1快取記憶體固定式，塊越大，行越少，無法利用區域性性。2增加塊傳輸時間現代系統塊大小為64bits

相聯度越高降低快取記憶體由於不命中導致的抖動1實現困難，成本高，速度慢 2需要更長標誌位 3增加命中時間 4增加不命中處罰L1和L2使用8路組相聯 L3使用16組相聯

想要編寫快取記憶體友好（Cache Friendly）的程式碼，

基本方法為：

讓最常見的情況執行得快，將注意力集中在核心函式的迴圈中

儘可能減少每個迴圈內部的快取不命中，可以對區域性變數反覆引用，因為編譯器會將其儲存到暫存器中，其他的變數最好使用步長為1的引用模式。

以CSAPP書中的練習題

6。18

為例探討快取命中和不命中的情況。

首先根據題目可瞭解到，

src

陣列和

dest

陣列在記憶體中的儲存方式為

L1

快取記憶體的塊大小為

8

位元組，則

b=3

且一次存放兩個

int

，而快取記憶體大小為

16

個數據位元組，說明快取記憶體組為

2

組，則

s=1

。採用直接對映的、直寫和寫分配的快取記憶體。一開始為空的，探討以下程式碼的命中情況：

第一輪：快取記憶體為空，則對

src［0］［0］

的讀取會不命中，根據地址

。。。00000

可知，將其存放在組

0

中，且資料塊儲存了

src［0］［0］

和

src［1］［1］

。對

dest［0］［0］

寫時，根據其地址

。。。10000

可知會檢視0組的位置，由於標誌位不同，所以寫不明中，會採用寫分配，將對應的資料塊儲存到組

0

，其資料塊包含

dest［0］［0］

和

dest［0］［1］

，然後更新

dest［0］［0］

。此時的快取記憶體的內容為

第二輪：讀取

src［0］［1］

時，根據其地址

。。。00100

可知，需要訪問組

0

，由於標誌位不同，所以讀取不命中，會重新將

src［0］［0］

和

src［0］［1］

的資料塊儲存到

0

組中。對

dest［1］［0］

寫時，其地址為

。。。11000

，說明會訪問組

1

，發現其中不包含任何資料，會出現寫不命中，然後將包含

dest［1］［0］

和

dest［1］［1］

的資料塊儲存到組

1

中。

第三輪：讀取

src［1］［0］

時，根據其地址

。。。01000

，需要訪問組

1

，由於其標誌位不同，所以讀取不命中，會將包含

src［1］［0］

和

src［1］［1］

的資料塊儲存到組

1

中。對

dest［0］［1］

寫時，其地址為

。。。10100

，會訪問組

0

，發現標誌位不同，會出現寫不命中，然後將

dest［0］［0］

和

dest［0］［1］

寫入組

0

中。

第四輪：讀取

src［1］［1］

時，其地址為

。。。01100

，需要訪問組

1

，可以發現標誌位相同，快取命中了。對

dest［1］［1］

寫時，其地址為

。。。11100

，需要訪問組

1

，發現標誌位不相同，出現寫不命中，就會將包含

dest［1］［0］

和

dest［1］［1］

的資料塊儲存到組

1

中。

2 儲存器山

一個程式從儲存器系統中讀取資料的速率稱為

讀吞吐量（Read Throughput）或讀頻寬（Read Bandwidth）

，單位為

MB/s

。 我們透過以下程式碼來衡量空間區域性性和時間區域性性對程式吞吐量的影響

第37行我們首先對快取記憶體進行暖身，然後在第38行計算程式執行的時鐘週期個數。

時間區域性性：

透過

size

來控制我們工作集的大小，由此來控制工作集存放的快取記憶體的級別。假設工作集很小，則工作集會全部存放在

L1

快取記憶體中，模擬了時間區域性性優異的程式反覆讀取之前訪問過的資料，則都是從

L1

快取記憶體讀取資料的。假設工作集很大，則工作集會存放到

L3

快取記憶體中，模擬了時間區域性性很差的程式，不斷讀取新的資料，則會出現快取不命中，而不斷從

L3

快取記憶體中取資料的過程。所以透過控制工作集大小，來模擬程式區域性性。

空間區域性性：

透過

stride

來控制讀取的步長，來控制程式的空間區域性性。

透過調整

size

和

stride

來度量程式的吞吐量，可以得到以下

儲存器山（Memory Mountain）

可以保持

stride

不變，觀察快取記憶體的大小和時間區域性性對效能的影響

可以發現，當工作集大小小於

L1

快取記憶體的大小時，模擬了時間區域性性很好的程式，所有都都是直接在

L1

快取記憶體中進行的，則吞吐量較高；當工作集大小較大時，模擬了時間區域性性較差的程式，讀操作需要從更高的快取記憶體中載入，則吞吐量下降了。

可以保持工作集為

4MB

，沿著

L3

山脊檢視空間區域性性對效能的影響

可以發現，步長越小越能充分利用

L1

快取記憶體，使得吞吐量較高。當步長為

8

位元組時，會跨越

64

位元組，而當前快取記憶體的塊大小隻有

64

位元組，說明每次讀取都無法在

L2

快取記憶體中命中，都需要從

L3

快取記憶體讀取，所以後續保持不變。

綜上所述：

需要利用時間區域性性來訪問L1快取記憶體，還需要利用空間區域性性，使得儘可能多的字從一個快取記憶體行中讀取到。

3 改善程式

3.1 重新排列迴圈來改善空間區域性性

我們可以有不同的迴圈方式來實現矩陣乘法

假設每個塊中能儲存4個元素，則可以分析每個變數的命中率

說明我們可以對迴圈重排列，來提高空間區域性性，增加命中率。

3.2 使用分塊來提高時間區域性性

分塊的主要思想是將一個程式中的資料結構組織成大的

片（Chunk）

，使得能夠將一個片載入到

L1

快取記憶體中，並在這個偏重進行讀寫。

如上圖所示是一個普通的矩陣乘法函式，這裡將二維陣列想象成一個連續的位元組陣列，透過顯示計算偏移量進行計算。這裡假設每個塊中可儲存8個元素，並且快取記憶體容量遠小於矩陣的行列數。

每一次迭代就計算一個C的元素值，我們分析每一次迭代的不命中次數

對於矩陣a，一次會儲存行的8個元素到塊中，則一行元素一共會有n/8次不命中。對於矩陣b，因為是列優先讀取的，所以無法利用快取記憶體中儲存的塊，所以一行元素會有n次不命中。則一共會有9n/8次不命中，對於C中的n*n個元素，一共會有 ［公式］ 次不命中。

如上圖所示是使用分塊技術實現的矩陣乘法，將矩陣乘法分解為若干個BxB小矩陣的乘法，每次能將一個BxB的小矩陣載入到快取中。

每一次迭代就計算C中一個BxB大小的塊，我們分析每一次迭代的不命中次數

每個塊有 B^{2} /8

B

2​​/8 次不命中次數，而每一行每一列有

n/B

個塊，所以計算一次

C

中的一個塊會有 次不命中，則一共會有 nB/4 \times {（n/B）}^{2} = n^{3}/（4B） ，我們就能調整B的大小來減小不命中率。

分塊降低不命中率是因為載入一個塊後，就反覆使用該塊，提高了空間區域性性。

分塊技術的介紹：http：//csapp。cs。cmu。edu/2e/waside/waside-blocking。pdf

建議：

將注意力集中在內迴圈中，因為大部分的計算和記憶體訪問都集中在這裡

按照資料物件儲存在記憶體中的順序，以步長為

1

來讀資料，使得空間區域性性最大。比如步長為

2

的命中率就比步長為

1

的命中率降低一半。

一旦從儲存器讀入一個數據物件時，就儘可能使用它，使得時間區域性性最大。特別是區域性變數，編譯器會將其儲存在暫存器中。