218
《計算機存儲與外設》----1.3 Cache的組織
本節書摘來自華章出版社《計算機存儲與外設》一書中的第1章，第1.3節，作者Computer Organization and Architecture: Themes and Variations［英］艾倫·克萊門茨（Alan Clements） 著，沈 立 肖曉強 王蘇峰 譯，更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看。
1.3 Cache的組織
下麵介紹Cache的組織和結構。一個Cache隻是可用存儲空間的一小部分。那麼什麼樣的數據可以進入Cache？數據會放在什麼位置？相比於主存儲器，Cache存儲係統的設計以及與計算機係統的集成都要更困難。部分是因為Cache速度快，部分是因為其複雜性高。事實上，直到20世紀80年代，隻能在小型機和大型機上見到Cache。直到20世紀80年代後期，隨著68020/30以及80386/486微處理器的出現，Cache才開始在個人計算機中出現。今天，已經可以將超過10億個晶體管集成在芯片中，這樣可以確保所有高性能處理器都包含一個大容量的片內Cache。
Cache設計的根本問題是如何構建一個存儲體來存放來自大容量主存儲器任意位置的一組數據元素。解決該映射問題的方法很多，但實際Cache係統通常使用組相聯（set associative）方式進行組織。下麵首先介紹兩個Cache結構實例，以便讀者理解組相聯Cache的操作。
1.3.1 全相聯映射Cache
在設計任何一種存儲係統時需要問的第一個問題是，基本數據單元的大小是多少？主存儲器處理單位數據的大小與機器的基本字長相同。例如，具有64位寄存器的64位機器采用64位存儲器。如果計算機需要少於一個字的數據，它首先讀取整個字，然後再忽略它不想要的位。
雖然計算機可以從Cache中讀取一個字，但該字的大小並不是Cache基本存儲單元的大小。Cache基本存儲單元為包含幾個連續字的塊（line）。假定Cache是按照字的粒度（granularity）來組織的。當訪問某條指令時，如果它不在Cache中，則必須從主存儲器中讀取。然而，下一條指令又有可能會失效。因此需要比一個字大的Cache基本存儲單元。
Cache塊（cache line）由一係列連續的字構成，這樣從Cache中可以連續讀出幾條指令從而不會發生失效。當發生失效時，包含該字的整個Cache塊將從主存調入Cache。Cache塊大小的最優值取決於Cache的總容量、代碼的屬性以及采用的數據結構。
人們希望Cache對存放在其中的數據不加限製；即Cache中的數據可以來自主存的任何地方。這種Cache使用相聯存儲器把數據存放在其中的任意位置，此時是根據其值（value）而不是根據其地址/位置（address/location）來訪問數據。
圖1-7說明了相聯存儲器的概念。每個數據項有兩個值，關鍵字（key）以及數據元素；例如，最上麵一行包含關鍵字52B1和數據F0000。此時，數據沒有排序，一個數據項可以保存在存儲器的任意位置。訪問關鍵字是檢索數據的主要手段。訪問相聯存儲器時需要將關鍵字輸入存儲器，然後將此關鍵字與存儲器中所有關鍵字進行並行匹配。如果發現了該關鍵字，該數據就被檢索到了（即與關鍵字關聯的數據）。例如，計算機向圖1-7中的係統輸入關鍵字F001。該關鍵字將同時交給存儲器中的所有位置進行比較。由於給定F001會發生匹配（即命中），存儲器將給出一個命中響應信號，同時將數值42220在數據端口輸出。
相聯Cache的工作原理看上去與圖1-7中的機製相似，用關鍵字作為處理器訪問的地址，數據就存放在該地址處。傳統存儲器與相聯存儲器的區別在於，傳統存儲器包含以0,1,2，…編號連續存儲的元素，而相聯存儲器包含的元素並沒有排序或者按順序存放。
下麵詳細討論全相聯Cache的部分細節。圖1-8所示的相聯存儲器允許Cache中的任意一塊都可以存放來自主存儲器的任意一塊數據。此例中，存儲器被劃分成包含兩個字的塊（每塊兩個字是為了簡單起見，實際的Cache可能每塊含有8個或更多的字）。
相聯Cache的大小可以任意，Cache中塊的數量與主存儲器中塊的數量之間沒有關係。考慮主存儲器為16MB，相聯映射存儲器為64KB。如果一塊包含4個32位的字（即塊大小為16字節），則主存儲器由224/16 = 1M個塊構成，而Cache包含216/16 = 4096個塊。
相聯Cache允許主存儲器的任意一塊數據存放在其任意一塊中。上例中，相聯Cache的第i塊可以存放來自主存儲器中1M塊中的任何一個。因此，Cache中第i塊需要一個標誌（tag）來唯一標識其與主存儲器中的某一塊相關聯。由於在該例中，主存儲器有1M塊，因此標誌應該為20位來代表220個塊。
當處理器產生一個地址時，將使用塊內地址來定位主存儲器或者Cache中一個字的位置（上例中，塊內地址為2位）。來自CPU的20位的塊地址A23～A04不能用於定位Cache中的塊，這是為什麼？因為相聯存儲器將主存儲器中1M個塊中的任意一個存放於其4096個塊中的任意一個，Cache並不知道要訪問的塊目前是否在Cache中。即使知道塊在Cache中，也不知道它到底在哪裏。
圖1-9說明了為什麼針對在Cache中定位一塊這個問題找不到簡單的解決方案。在該例中，同樣使用24位地址總線訪問主存中16MB的DRAM和塊大小為64KB的相聯映射Cache。Cache中每一塊有16個字節，對應4個32位的字。CPU可以訪問的全部塊的總數是224/24 = 220，使用24位地址。該地址由A23～A04（塊地址）、A03～A02（塊內地址）以及A01～A00（字節地址）組成。因此，需要20位的標誌來唯一標識一塊。
如何把來自CPU的包含1M個塊的地址映射為Cache中包括4096個塊對應的地址？圖1-9給出了一種解決方案，該方案使用220個字、每個字12位的隨機訪問存儲器來存儲指向Cache塊的4096個指針。該存儲器是稀疏的，因為1M個存儲位置中隻有Cache中的4096塊具有指針。其他位置沒有指針是因為當前塊在主存儲器中而不是在Cache中。當然，為了實現這個機製，需要在查找表中每一行增加一個額外的位來表示當前塊是否在Cache中（即“命中/失效”位）。
圖1-9所示係統實現起來不便宜，因為需要保存指向Cache的指針構成的存儲器容量可能與主存儲器一樣大或者超過主存儲器的容量！此外，查找表必須非常快以避免增加Cache的訪問時間。在該例中，64KB的Cache對應的查找表有1M個字，每個字12位（即大小為1.5MB），故該方案是不切實際的。可行的解決方案是使用相聯存儲器。
相聯存儲器
相聯Cache名稱來源於其使用相聯存儲器來存放標誌。相聯存儲器具有n位輸入但並不一定需要對應2n個唯一內部位置。n位輸入交給相聯存儲器並與每個位置上的標誌域同時進行比較。如果輸入地址與某個正存儲的標誌相匹配，則輸出與該位置關聯的數據。否則，相聯存儲器輸出不匹配。
繼續前麵的例子，相聯Cache使用相聯存儲器保存4096個20位的標誌（Cache中的每塊對應一個標誌）。當CPU進行存儲器訪問時，地址總線的高20位將作為相聯存儲器的輸入。如果相聯存儲器包含該標誌，則返回相應的Cache塊。
由於來自主存儲器的塊可位於相聯Cache中的任意位置，當Cache滿了會出現什麼情況？需要刪除哪個塊來為新調入的塊提供空間？實際上，相聯Cache會保存每塊上次被訪問的時間，這樣就可以將最久沒有使用的塊淘汰（或使用其他參數來決定將哪一塊淘汰出Cache）。Cache的替換策略與虛擬存儲器使用的類似（見下一節，例如，最近最少使用（LRU）、先入先出（FIFO），或隨機策略等）。最近最少使用算法直觀上最好，因為它旨在清除最長時間沒有被訪問的數據（如果不使用它就丟棄它）。然而，LRU算法不容易實現，因為這樣做需要記錄每塊的最後訪問時間。
相聯存儲器很昂貴，因為它需要大量的並行邏輯將輸入關鍵字（即當前的地址）與當前存儲的關鍵字同時進行匹配。市場上現有的相聯存儲器都太小，不能用來實現實用的Cache係統。
相聯Cache可能會產生兩種類型的失效：一種是在第一次訪問時的強製失效（compulsory miss）。它是強製的，因為Cache塊中初始時是沒有數據的。減少強製失效的唯一方法是在訪問所需的數據之前預先向Cache中調入數據。當相聯Cache已經滿了，所需數據不在Cache中的時候，就會產生第二種Cache失效——容量失效（capacity miss）。
1.3.2 直接映射Cache
組織Cache最簡單的方法就是采用直接映射（direct mapping），它依賴於一種簡單的算法將主存儲器中的數據塊映射到Cache中的塊。在直接映射Cache中，主存塊被分為若幹個組（set），組的大小與Cache的大小一致。如前麵的例子，一台具有16MB內存和64KB Cache的計算機會將存儲空間分為16MB/64KB = 256個組。
為說明直接映射Cache是如何工作的，假定主存儲器包括32個字，需要5位的地址來訪問，Cache的大小為8個字，塊大小為2個字。根據前麵的定義，組大小為：存儲器容量/Cache容量= 32/8 = 4。給定5位地址s0、s1、l1、l0和w，其中s位定義了組，l位定義了塊，w位定義了字。圖1-10展示處理器當前需要的字是如何根據組地址、塊地址以及字地址進行訪問的。為了方便討論，這裏隻考慮組和塊的訪問，而不管一塊中有多少個字。
圖1-10所示的組織形式被稱為直接映射Cache，因為Cache中某塊的位置與主存儲器中塊的位置之間有直接的關係。在圖1-10給出的例子中，Cache具有2位的塊地址，因此具有22=4個塊。如果直接映射Cache有b位塊地址字段，則Cache就有2b個數據塊。
當處理器產生一個地址，就會訪問Cache中對應的塊。例如，如果處理器生成5位地址01100，則訪問第2塊。圖1-10顯示了主存儲器中有4個塊編號為第2塊：第0組的第2塊、第1組的第2塊、第2組的第2塊以及第3組的第2塊。假設在這個例子中，處理器訪問第1組中的第2塊，顯然的問題是：係統如何知道Cache中被訪問的第2塊是來自主存儲器中第1組的第2塊？
圖1-11顯示了直接映射Cache是如何解決這個問題的。在Cache中每塊都有一個標誌來標識該塊來自主存儲器中的哪個組。當處理器給出的訪問地址中塊地址為3，Cache中第3塊對應的標誌將發送給比較器。同時，處理器地址中的組字段也被發送給比較器。如果它們相同，則表明Cache中的塊就是所需要的塊，發生命中。如果它們不相同，則發生失效，對應Cache塊中的數據必須更新。
當訪問第i塊並發生失效時，Cache中原來的第i塊要麼被丟棄，要麼被寫回主存儲器，這取決於主存儲器的更新是如何組織實現的。後文將對Cache這方麵的問題進行研究。
圖1-12從另一種觀點來描述直接映射Cache，其中主存儲器被當成一個組數×塊數的矩陣，該例中為4塊×4組。矩陣的旁邊是Cache，它具有與主存儲器相同的塊數。當前Cache中的塊與主存儲器中陰影部分的塊相對應。圖1-12表明，Cache中的塊是如何從組號相同的主存儲器的某組中獲得的。
圖1-13給出了直接映射Cache存儲器係統的框架結構。Cache存儲體由保存數據的高速RAM構成。Cache標誌RAM（cache tag RAM）是一種由高速隨機訪問存儲器和數據比較器構成的特殊設備。Cache標誌存儲器的地址輸入是處理器訪問的塊地址（line address），該地址用來訪問或指向包含該組標誌的標誌RAM中的位置。將該地址對應Cache標誌RAM中的數據送往比較器並與地址總線上的組地址進行比較。如果處理器給出的組字段與被訪問塊的標誌相匹配，Cache標誌RAM返回命中信號。
直接映射Cache不需要複雜的塊替換算法。如果需要訪問組y中的塊x且發生了失效，主存儲器組y中的塊x將被加載到Cache中的第x塊。當新塊載入時，直接將失效位置對應的塊淘汰出Cache。
直接映射Cache的優點是其固有的並行性。由於保存數據的Cache存儲器和Cache標誌RAM是獨立的，它們可以被同時訪問。一旦從地址總線給出的標誌字段與Cache標誌RAM的標誌字段相匹配，則命中，從Cache中獲取的數據就是有效的。
直接映射Cache的缺點是它對被緩存數據的位置敏感。可以聯係地址簿來理解，假設為每個字母保留6個位置。如果你已經有6個朋友的姓是以S開頭的，那麼下一次再碰到一個人的姓是以S開頭時就會出現問題。這很煩人，因為給Q和X預留的位置可能完全是空的而不能用。由於隻有一個編號為x的塊能夠放在Cache中，訪問主存儲器中其他不同的組中塊號為x的塊將導致Cache中第x塊被替換。
即使Cache沒有存滿，在訪問主存儲器不同組中相同塊號的兩個塊時，會導致塊在Cache和主存儲器間進行交換。該問題會導致較低的Cache利用率和高失效率。這種在即使Cache沒有存滿時也發生塊替換的情況稱為衝突失效（conflict miss），這是由於新塊和原緩存塊之間存在衝突。讀者很快會看到，提高直接映射Cache的性能並不難。
雖然在數據組織不恰當時，直接映射Cache的性能會非常差，但實際程序的統計測量結果表明，直接映射Cache在最壞情況下的性能對其平均性能的影響並不明顯。
圖1-14展示了一個非常簡單的直接映射Cache的操作，該係統具有16個字的主存儲器和8個字的直接映射Cache。為簡化討論，隻考慮對指令的訪問。該Cache可以保存來自兩個組的一個塊。圖中在Cache左側將塊編號為0～7，在其右側編號8～15，用來表明主存儲器中8～15塊被緩存。假定塊大小與字的長度相等，並運行如下代碼：
圖1-14隻顯示了取指周期。圖1-14a給出了係統的初始狀態。圖1-14b～d顯示取前3條指令，每條都存放在連續的Cache位置。當圖1-14d中調用子程序後，轉向地址為10的指令。在該直接映射Cache中，塊10和塊2將映射到相同的Cache塊。之後，在圖1-14e中，ADD覆蓋了Cache塊2中的BL指令此時發生了衝突失效，由於目的位置已經被占用，數據不能調入Cache，除非該位置被空出來。
圖1-14f中，第11塊中的MOV pc,lr指令被裝入Cache中第3塊。最後，在圖1-14g中，程序返回，第3塊中的指令B XYZ被裝入Cache中的第3塊，替換掉以前的塊。
圖1-14表明，即使在一個簡單的係統中，直接映射Cache中的元素可以很容易地被替換。如果上述這段代碼循環執行，頻繁替換Cache中的數據將降低性能。
1.3.3 組相聯Cache
上一節介紹的直接映射Cache很容易實現，不需要塊替換算法。然而，它不允許來自不同組但具有相同塊號的塊被同時緩存。全相聯Cache對塊存放的位置沒有限製，但它需要考慮一旦Cache已滿將替換哪個塊。此外，容量大的全相聯Cache實現起來十分昂貴。組相聯（set-associative）Cache結合了上述兩種Cache的優點，實現起來代價也不高。因此，它是計算機上常見的Cache組織形式。
直接映射Cache隻為每個塊i分配了一個位置。如果使用兩個直接映射Cache並行工作，就可以使塊i進入它們中的任意一個。如果使用n個直接映射Cache並行工作，就可以使塊i進入n個位置中的任意一個。這就是n路組相聯Cache。
在n路組相聯Cache中，給定塊可載入Cache中n個可能的位置。通常情況下，n的範圍是2～8。圖1-15展示了一個四路組相聯Cache的結構，它由4個並行操作的直接映射Cache構成。在此情況下，塊i可以載入4個直接映射Cache中的任意一個。因此，具有相同塊號的不同塊在調入Cache時產生的衝突將大大減少。這種方式稱為相聯（associative），因為來自處理器的塊地址被並行送給每個直接映射Cache。然而，一般並不會對成千上萬的存儲單元同時進行搜索，而隻對2～8個直接映射Cache進行並行訪問。每個Cache的比較結果（即命中）將被交給或門，其輸出結果表示是否有一個Cache命中。
圖1-16使用組相聯Cache重複了圖1-14中給出的例子。兩個例子基本相同，隻是組相聯Cache中的每個直接映射Cache隻有4塊，但總容量還是8塊。圖1-16中所示為一個二路組相聯Cache，塊可以保存在上麵或者下麵的直接映射Cache中的任意一個。
圖1-16中前幾步是一樣的，直到圖1-16e，當地址為10的ADD r1,r2,r1指令映射到第2塊（組大小為4）時，該塊已經被BL Adder指令占用。在相聯的第2個Cache的相應位置是空閑的，因此該指令可以緩存在下麵的Cache的第2塊，而不必替換上麵Cache中的塊。圖1-16f，MOV pc,lr指令的塊號為3，保存在上麵的Cache中。然而，當執行主存儲器第3塊中的B XYZ指令時，上麵的Cache的第3塊已被占用，故它被緩存在下麵Cache的第3塊中。
來自IDT應用筆記AN-07《Cache標誌RAM芯片簡化Cache存儲器設計》的表1-1展示了Cache的組織形式對失效率的影響。該失效率已經與直接映射Cache的失效率相除進行了歸一化，用來表示相對於直接映射Cache的結果。四路組相聯Cache的結果要比直接映射Cache的結果好30%。進一步增加相聯度對於性能的改善有限。
來自Freescale半導體公司應用筆記的圖1-17展示了不同容量的Cache、使用GCC編譯器時相聯度和命中率之間的關係。可以看出，Cache容量比較小時，相聯度是一個重要因子。當Cache容量達到256KB時，相聯度的作用就不十分顯著了。
1.3.4 偽相聯、Victim、Annex和Trace Cache
由於Cache非常重要，針對它的改進已經進行了大量的研究，特別是針對異常行為的處理（例如，當數據被緩存、替換並再次被緩存，等等）。
在直接映射Cache基礎上進行變更可以得到偽相聯（pseudo-associative）Cache。當直接映射Cache發生衝突失效時，為失效的塊提供一個後備位置（alternative accommodation）。下麵文本框中的“流緩衝和條緩衝”部分對衝突失效和其他類型失效的自然屬性進行了進一步的討論。當直接映射Cache發生失效時，偽相聯Cache根據舊的地址再計算一個新的地址來存放數據。通常情況下，新的地址是對當前地址高端的一位或幾位進行取反操作得到。雖然這是規避直接映射Cache限製一種巧妙方法，但它需要在一次失效以後進行第二次Cache訪問。
Victim Cache是一個小的Cache，用來保存最近被替換出Cache的項目（即遇難者（victim））。Victim Cache與原Cache並行訪問，理想情況下，它是全相聯的。因為它的容量非常小，可以同時搜索的塊數有限，因此可以使用全相聯的方式構建。
一個小的Victim Cache可以減少直接映射Cache的衝突失效，這是因為它保存的被替換塊的塊號與剛調入塊的塊號相同。Victim Cache也可以在主Cache被充滿、開始出現容量失效的時候使用。Victim Cache保存了被替換出Cache的塊，由於數據既沒有在主Cache也沒有在Victim Cache中複製，因此並沒有浪費空間。
Victim Cache典型應用的例子是嵌套循環。考慮在一個循環內調用了一段程序，循環的起點與被調用程序間有一定的距離。循環開始後，程序被調用。Cache被充滿了，就必須替換一些塊為新的指令提供空間。當程序執行完返回循環時，Cache又需要替換一些塊，依此類推。Victim Cache可以保存被替換的指令並確保它們在循環和函數調用序列被執行時命中。Jouppi針對Victim Cache的研究表明，它可以很小，但十分有效。一些基準測試表明，當使用容量少到4項的Victim Cache時，可以減少80%的衝突失效。Jouppi在研究使用Victim Cache來減少總的失效時，發現不同的基準測試程序的結果差異很大。使用容量為4項的Victim Cache時，各種基準測試程序平均會使失效率降低15%，而其中的某個基準測試程序最多會降低70%。
對Victim Cache的修改是使用選擇性（selective）Victim Cache，Victim Cache中的項可能來自Cache中被替換的塊或者主存儲器。當新的塊被預取時，采用一種預測算法來確定它是否應該被載入Cache或是Victim Cache。預測的目的是為了盡量避免Cache汙染，即避免載入不會被使用的塊。預測機製要求記錄每塊的曆史狀態信息。該機製使用了兩位指示器：一位用來表示位於Cache中的塊從來沒有被訪問過，另一位表示慣性（inertia）以避免在Cache和Victim Cache間進行過度的交換。
另一個由John和Subramanian提出的特殊Cache為Annex Cache。與Victim Cache一樣，Annex是一個專用的Cache，但位於一級Cache的前麵。即Victim Cache位於Cache的出口，而Annex Cache位於入口。Victim Cache給替換出Cache的數據第二次機會，而Annex Cache要求想進入Cache的數據證明自己的價值。
Annex Cache有助於防止很少使用的數據進入Cache，從而減少Cache汙染。如果Cache為不常使用的數據提供空間而將頻繁使用的數據替換出去的話，其效率肯定不高。在啟動時，所有數據塊以正常的方式進入Cache。最初階段後，所有進入Cache的數據都需要通過Annex。隻有在主Cache發生衝突失效且該失效塊已經在Annex Cache中被訪問了兩次時，Annex Cache中的數據塊才會被交換進入主Cache。進入Annex Cache的數據必須被證明在時間或空間局部性上存在價值。在實踐中，類似Annex Cache這樣的複雜Cache機製是不容易實現的，由於附加功能的複雜性，需要在本來簡單的組相聯Cache的基礎上增加大量的控製電路。
最後更新：2017-05-25 10:01:29