比較三種快取映射類型

作者 : Krishnakanth Katteri Mahadeva Murthy,英特爾繪圖硬體工程師

如果處理器所需要的數據離處理器越近,存取時間就越少。因此,我們希望讓處理器所需要的數據離它更近。但這是怎麼實現的呢?

在電腦中,整個記憶體可以根據存取時間和容量分為不同的層級。1顯示記憶體階層結構中的不同層級。更小、更快的記憶體會更靠近處理器。如果處理器所需要的數據離處理器越近,存取時間就越少。因此,我們希望讓處理器所需要的數據離它更近。但這是怎麼實現的呢?

Memory Hierarchy

圖1:記憶體階層結構。

根據局部性原則,當處理器存取一個位元組的記憶體時,它更有可能再次存取該記憶體位置。此外,處理器更有可能很快存取附近的位元組。在2中,諸如比較“i”和“n”、遞增“i”、將“a”加1等指令執行了多次。像“i”、“a”、“b”、“n”和“c”這樣的變量被多次使用這些指令和變量在工作集中。如果工作集可以保存在快取中,程式將執行得更快。隨著程式的執行,工作集發生了變化。

A simple for loop in C

圖2:簡單的C語言“for”循環。

快取

快取是臨時儲存數據的高速記憶體。它們的尺寸較小,從幾KB到幾MB不等。CPU快取通常分為不同的層級(L1快取、L2快取和L3快取)。離CPU越遠,快取越大,存取時間越長。因此,L2快取可以儲存比L1快取更多的快取行,而L3快取可以儲存比L2快取更多的快取行。當處理器啓動並執行時,快取控制器會接收請求以確定所請求的數據是否存在於快取中。如果沒有,可能會要求快取控制器分配快取行。那麼,當數據從下游返回時,快取控制器如何將其放入快取中呢?

存在三種不同類型的快取映射:直接映射(direct mapping)、全相聯映射(fully associative mapping)和組相聯映射(set associative mapping)。

直接映射快取

在直接映射快取中,一個記憶體區塊只能映射到快取中的一個可能位置。例如,讓我們考慮一個8KB快取,快取行大小為64位元組。這意味著快取有128個快取行。在快取的傳入位址中,需要6位元來尋址快取行中的每個位元組(2^6=64),它們被稱為快取偏移位元(3)。位址中接下來的7位元用於將記憶體區塊映射到快取行(2^7=128),它們被稱為索引位元。其餘位元儲存在快取中以標識記憶體區塊。這些位元稱為標記。

Cache address of direct-mapped cache

圖3:直接映射快取的快取位址。

全相聯快取

在全相聯快取中,記憶體區塊可以放置在任何快取行中。如果上述示例中的同一個快取是全相聯的,那麼就不需要任何位元來索引任何快取行。因此,除了6個快取偏移位元之外,其餘的都是標記位元(4)。

Cache address of fully-associative cache

圖4:全相聯快取的快取位址。

組相聯快取

組相聯快取是直接映射快取和全相聯快取的組合。在組相聯快取中,每個記憶體區塊都可以映射到一個組,這些組可能包含「n」個快取行。例如,一個4路組相聯快取在每個組中有4個快取行。在每個組中,快取映射是全相聯的。因此,組相聯快取需要一些位元來索引位址以表示組。讓我們將上述示例中的相同快取視為4路組相聯,這意味著將有32個組(128/4=32)。索引到一個組中需要5位元(5)。

Cache address of Set-associative cache

圖5:組相聯快取的快取位址。

快取場景

現在,讓我們看一下具有8次迭代的“for”循環(6)。在每次迭代中,數組的一個元素(數據類型為「int」)都會遞增。假設在第一次迭代中,將帶有a[0]元素(4位元組)的記憶體區塊(64位元組)從主記憶體引入L1快取(7)。在接下來的連續迭代中,處理器所需要的所有數據(a[1]、a[2]、a[3]、…a[7])都將位於L1快取中。這在很大程度上降低了記憶體存取時間。

For loop in C

圖6:C語言“for”循環。Representation of a memory block in main memory and cache memory

圖7:主記憶體和快取中的記憶體區塊表示。

現在讓我們看一個不同的場景。Instructions in C

圖8:C語言指令。

讓我們考慮一個具有128個快取行和64位元組快取行大小的直接映射快取。為了執行第一條語句,需要將記憶體區塊從主記憶體中的位址0引入一級快取的索引0。執行第二條語句需要將位址為32’h80的記憶體區塊引入快取中。由於位址32’h80映射到索引0,因此需要驅逐現有的有效快取行以引入新的記憶體區塊。這增加了更多的延遲。同樣,下一條指令需要位址32’h100處的記憶體區塊,將會觸發快取行驅逐和記憶體區塊提取。當使用直接映射快取時,此程序會導致性能不佳。

現在讓我們看看具有128個快取行和64位元組快取行大小的全相聯快取行為方式。當執行這些指令中的每一個時,就會將新的記憶體區塊引入快取,但不需要驅逐記憶體區塊,因為記憶體區塊可以放置在快取中的任何位置,前提是快取具有無效的快取行。

4路組相聯快取每個組有4個快取行。因此它最多可以為同一個索引分配4個記憶體區塊而不會驅逐。因此,上面的三個指令將導致在組0下分配三個記憶體區塊。

當連續的指令獲取映射到一個索引或一個組的記憶體區塊時,直接映射快取和組相聯快取會遇到更多衝突,並將發生驅逐和引入新的記憶體區塊。但這些類型的快取也有優勢。在直接映射快取中,在快取查找期間,快取控制器只需要查找一個地方。這使得快取查找速度更快。在快取查找期間,全相聯快取需要將所有快取行與傳入位址進行比較,以確定它是否具有快取行的有效副本。

這需要許多比較器,這使得與直接映射快取相比,全相聯快取更加昂貴。這也意味著全相聯快取會消耗功率來查找快取。組相聯快取是全相聯快取和直接映射快取之間的權衡。組相聯快取受到了廣泛使用,因為它們受益於以下兩個方面:關聯性和將記憶體區塊映射到組的想法。

編譯:Franklin Zhao

(參考原文:Understanding cache placement,by Krishnakanth Katteri Mahadeva Murthy)

加入LINE@,最新消息一手掌握!

發表評論