比較三種快取映射類型
作者 : Krishnakanth Katteri Mahadeva Murthy，英特爾繪圖硬體工程師
如果處理器所需要的數據離處理器越近，存取時間就越少。因此，我們希望讓處理器所需要的數據離它更近。但這是怎麼實現的呢？
在電腦中，整個記憶體可以根據存取時間和容量分為不同的層級。圖1顯示記憶體階層結構中的不同層級。更小、更快的記憶體會更靠近處理器。如果處理器所需要的數據離處理器越近，存取時間就越少。因此，我們希望讓處理器所需要的數據離它更近。但這是怎麼實現的呢？
圖1：記憶體階層結構。
根據局部性原則，當處理器存取一個位元組的記憶體時，它更有可能再次存取該記憶體位置。此外，處理器更有可能很快存取附近的位元組。在圖2中，諸如比較“i”和“n”、遞增“i”、將“a”加1等指令執行了多次。像“i”、“a”、“b”、“n”和“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)，它們被稱為索引位元。其餘位元儲存在快取中以標識記憶體區塊。這些位元稱為標記。
圖3：直接映射快取的快取位址。
全相聯快取
在全相聯快取中，記憶體區塊可以放置在任何快取行中。如果上述示例中的同一個快取是全相聯的，那麼就不需要任何位元來索引任何快取行。因此，除了6個快取偏移位元之外，其餘的都是標記位元(圖4)。
圖4：全相聯快取的快取位址。
組相聯快取
組相聯快取是直接映射快取和全相聯快取的組合。在組相聯快取中，每個記憶體區塊都可以映射到一個組，這些組可能包含「n」個快取行。例如，一個4路組相聯快取在每個組中有4個快取行。在每個組中，快取映射是全相聯的。因此，組相聯快取需要一些位元來索引位址以表示組。讓我們將上述示例中的相同快取視為4路組相聯，這意味著將有32個組(128/4=32)。索引到一個組中需要5位元(圖5)。
圖5：組相聯快取的快取位址。
快取場景
現在，讓我們看一下具有8次迭代的“for”循環(圖6)。在每次迭代中，數組的一個元素(數據類型為「int」)都會遞增。假設在第一次迭代中，將帶有a[0]元素(4位元組)的記憶體區塊(64位元組)從主記憶體引入L1快取(圖7)。在接下來的連續迭代中，處理器所需要的所有數據(a[1]、a[2]、a[3]、…a[7])都將位於L1快取中。這在很大程度上降低了記憶體存取時間。
圖6：C語言“for”循環。
圖7：主記憶體和快取中的記憶體區塊表示。
現在讓我們看一個不同的場景。
圖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）
從無線連接、更快的處理和運算、網路安全機制、更複雜的虛擬實境(VR)到人工智慧(AI)等技術，都將在未來的每一個嵌入式系統中發揮更關鍵功能。「嵌入式系統設計研討會」將全面涵蓋在電子產業最受熱議的「智慧」、「互連」、「安全」與「運算」等系統之相關硬體和軟體設計。
會中將邀請來自嵌入式設計相關領域的研究人員、代表廠商以及專家，透過專題演講、產品展示與互動交流，從元件、模組到系統，從概念設計到開發工具，深入介紹嵌入式系統設計領域的最新趨勢、創新和關注重點，並深入分享關於嵌入式系統設計的經驗、成果以及遇到的實際挑戰及其解決方案。
加入LINE@，最新消息一手掌握！
