882
《計算機存儲與外設》----1.4 Cache設計中要考慮的因素
本節書摘來自華章出版社《計算機存儲與外設》一書中的第1章，第1.4節，作者Computer Organization and Architecture: Themes and Variations［英］艾倫·克萊門茨（Alan Clements） 著，沈 立 肖曉強 王蘇峰 譯，更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看。
1.4 Cache設計中要考慮的因素
前麵已經說過，由於需要考慮的因素很多，Cache的設計比較複雜，其中一些因素依賴於計算機係統自身的屬性。在本節中將討論一些影響Cache係統設計的因素。
1.4.1 物理Cache和邏輯Cache
在具有存儲器管理單元的計算機係統中，Cache可以位於CPU和MMU之間，也可以位於MMU和物理內存之間。圖1-18顯示了這兩種情況。如果在CPU數據終端上的數據被緩存，該數據稱為邏輯數據（logical data），相應的Cache為邏輯Cache（logical Cache）。然而，如果數據經過MMU實現地址轉換後被緩存，則該數據稱為物理數據（physical data），相應的Cache為物理Cache（physical Cache）。下麵將討論邏輯Cache和物理Cache的含義以及它們之間的權衡。
物理Cache比邏輯Cache具有更長的訪問時間，這是因為在物理Cache中直到MMU進行了邏輯地址到物理地址的轉換後才可以進行數據訪問。邏輯Cache比物理Cache要快，是因為邏輯Cache中的數據可以立刻被訪問，而不必等待地址轉換。
假設在多任務係統中發生了上下文切換且要執行一個新任務。當新任務開始時，操作係統將相應的地址轉換表裝入MMU。當邏輯地址到物理地址的映射關係改變時，Cache中數據以及相應的物理數據間的關係被打破；不能使用Cache中的數據，且邏輯Cache必須刷新。物理Cache在上下文切換時就不需要刷新。
然而，使用物理Cache的代價是在存儲器訪問前需要額外的時間來執行邏輯地址到物理地址的轉換。在實踐中，如果把Cache頁麵大小設置為與存儲器頁麵大小一樣，就可以實現Cache中的塊查找與虛擬地址變換並行工作。微處理器一般使用物理Cache來減少切換上下文之後導致對Cache的刷新。
1.4.2 Cache電氣特性
本書將在下一章中介紹主存儲器係統，這裏先對Cache的電路設計進行簡要說明。半導體隨機訪問存儲器有兩大類：靜態（static）和動態（dynamic）。靜態存儲器利用傳統數字邏輯將一位數據存儲在一個觸發器中——正如在《計算機組成原理》第2章中描述的那樣。靜態存儲器的特點是低功耗、高速和隻要有電就能夠保留數據。因此，Cache通常由靜態RAM構造。不幸的是，它需要6個晶體管來存儲一個比特位，因此，靜態存儲器單元的物理尺寸（即所占矽片的麵積）比DRAM單元要大得多。這意味著，靜態存儲器比DRAM更昂貴且容量較小，因此不能用來構造大容量的Cache。
動態存儲器（DRAM）通過對單個晶體管的電容充上電荷來保存數據。這使得DRAM非常便宜和緊湊，可以用來構造大容量存儲器。不幸的是，DRAM需要更多的電量進行控製，且電容中的電量在幾ms內就會漏光。為了保存DRAM中的數據，必須每隔4ms左右定期讀取存儲單元中的數據並將其寫回。DRAM不適於構建Cache。
1.4.3 Cache一致性
Cache中的數據也在主存儲器中。當處理器在寫周期內修改數據元素時，必須對主存儲器和Cache中的數據副本進行修改，雖然這種修改不必是同時的。因此，可能會出現一個數據存在兩個不同副本的情況。如果Cache中的數據被修改，而主存儲器的數據沒有被修改（或倒過來），舊的、沒有被修改的數據稱為過時的（stale）數據。讀者可以想象，這種情況可能會導致嚴重的錯誤。假設I/O控製器使用DMA試圖從主存儲器移動一塊數據到磁盤上，此時處理器剛剛更新了其Cache中的數據但尚未修改主存儲器中的數據副本。I/O控製器將把過時的數據而不是把Cache中最新的數據從主存儲器移動到磁盤上。
Cache一致性（cache consistency）有時被稱為數據一致性（data consistency）。圖1-19中給出了這樣一個係統，兩個處理器共享一個存儲器。假設在此多處理器係統中的處理器1執行了存儲器寫操作，隻更新了自己的局部Cache而沒有寫入存儲器。Cache中的存儲器中的數據拷貝是不一致的。這種情況將持續到存儲器寫回（write back）操作將數據更新。如果處理器2在數據更新前讀取存儲器中相同位置的數據，它從存儲器中訪問到的就是過時的數據。
當多個處理器都有自己的局部Cache時也會發生類似的問題。假設處理器X同時更新了自己的局部Cache和共有的存儲器。處理器Y也可能在其局部Cache中緩存了相同數據的一個副本。處理器Y並不知道它緩存的數據已經是過時的。Cache一致性這個術語意味著在不同的Cache和主存儲器中的數據必須保持同步（即沒有過時的數據）。使Cache和主存儲器中的數據保持一致（即保證Cache一致性）是設計多處理器係統時需要主要考慮的問題之一。
有些處理器通過一種被稱為總線偵聽（bus snooping）的技術來保持Cache的一致性。處理器通過監視地址流和數據流發現那些向主存儲器的寫訪問、同時在自己的Cache中也有一個副本的情況。當主存儲器中的數據被修改，該處理器局部Cache中的內容可以被標記為無效，或將其Cache更新。
1.4.4 塊大小
塊是Cache中的基本存儲單位。一個重要的問題是，要多大的塊才能獲得最佳性能？針對塊大小和Cache性能之間的關係已經展開了大量的研究，有時是通過模擬軟件的Cache操作，有時是通過監控計算機係統中真實Cache的操作。
最佳的塊容量取決於幾個方麵，尤其是正在執行的程序的性質。負責控製處理器和存儲器之間數據流量的總線協議也會影響Cache的性能。典型計算機的總線負責將地址傳送到主存儲器，然後從數據總線發送或接收一個數據字——每次存儲器訪問都需要一個地址和一個數據元素。假設總線可以工作在突發模式（burst mode），即發送一個地址，然後獲得一批連續的數據值。
顯然，這樣的總線相對每次隻能傳輸一個數據元素的總線來說能更好地傳輸較大的塊。另一個決定最佳塊容量的因素是指令和數據的混合情況。針對指令的最佳塊容量並不一定與針對數據的最佳塊容量相同。
假設塊容量非常小。CISC微處理器，如Intel IA32係列，具有可變長度指令，其範圍從2個到10個或更多的字節。對於很長的指令，可能會出現指令的一部分在某個塊中緩存而另一部分在另一個塊中緩存的情況。當讀取這樣的一條指令時，必須兩次訪問Cache。增加塊大小減小了多次訪問Cache（或稱為塊交叉，line crosser）的現象。
增加塊容量會提高Cache的效率，因為數據對象（例如，指令、向量或線性表）是由一組連續的字節組成的，可以利用空間局部性原理。然而，當塊容量不斷增加，命中率也會下降，因為減少了塊的數量使得給定對象被緩存的概率降低。此外，大的塊的性能很大程度上依賴於數據訪問的局部性。當發生失效將一塊調入Cache時，它可能包含不經常訪問的數據，反而把經常訪問的數據替換出去了。
圖1-20給出了數據訪問的塊容量和Cache容量之間的關係。這些經典的結果是通過模擬得到的，當時Cache的容量比現在的要小得多。圖1-20畫出的是失效率而不是命中率的情況。每條曲線對應一個特定的Cache容量（從32B～32KB）。圖1-21提供指令Cache的相應結果。數據Cache的失效率首先逐漸變好（即越來越小）然後逐漸惡化（即越來越大）直到塊容量與Cache容量本身相等；而指令Cache的失效率隨塊容量的增加而減小。這表明，訪問的局部性對指令的作用比對數據的作用更強。一般情況下，隻要給定Cache容量就有一個最佳的塊容量；例如256B的Cache，最佳塊容量為64B。Cache容量越大，最佳的塊容量就越大。
1.4.5 取指策略
有幾種策略可以用於降低失效率，從而提升Cache性能（例如，按需獲取、預取、選擇性獲取）。按需獲取（demand fetch）策略在失效後調入所需塊，這是一種最簡單的選擇。預取（prefetch）策略預測未來Cache的需求（例如，如果沒有緩存塊i+1，當訪問塊i時也調入第i+1塊）。實現預取算法有許多可能的方法。選擇性獲取（selective fetch）策略在主存儲器的部分內容不能被緩存的情況下使用。例如，在多處理器係統中，由多個處理器共享的數據就不應該被緩存，如果這些數據被緩存而處理器修改了存儲器中的拷貝，Cache和存儲器中的數據將不再保持一致。
如果需要快速訪問數據，就應該盡早地獲取它。通過預取（prefetch）數據可以最大限度地發揮Cache的作用。一些微處理器的指令集包括預取指令，它隻產生操作數地址而不做其他事情。當操作數出現在總線上時，Cache係統自動緩存這個地址上的數據。該指令並沒有其他功能，隻是一個觸發預取的虛擬操作。
如果，在幾個指令後，需要訪問預取地址中的數據，相應的數據已經在Cache中。該預取操作可由程序員手工完成或編譯器自動優化過程來完成。預取不是一門精確的科學。如果預取得太晚，當CPU需要數據時，它可能不在Cache中。另一方麵，如果數據預取得太早，Cache要為新的數據塊騰出空間，而在CPU有機會訪問它之前可能會將其替換出去。這樣過早地預取數據又在使用數據之前將其替換，就是Cache汙染（cache pollution）的例子。
預取與循環密切相關，這是因為控製結構循環出現使得可以預先知道將使用的數據。預取最簡單的方式是在訪問數組元素之前包括一個預取地址。考慮表達式S = ∑ai的計算。相應的代碼是：
根據Wiel和Lilja給出的例子，這裏使用fetch(&address)來表示預取操作和預取的地址。預取最簡單的例子是在循環中使用地址前訪問該地址；即
這樣將產生下次訪問的地址，當再次循環時，i+1這個位置已經被訪問。可以在下麵兩個方麵改進該段代碼：一是初始元素沒有被預取；二是由於每次循環隻有一個有效操作所以循環效率較低。考慮下麵的代碼：
在這種情況下，一次循環執行4個操作。由於每次取指調入Cache中的數據塊中所包含16個字節可以被4個連續的指令使用，因此隻需要做一次預取。
1.4.6 多級Cache
在20世紀90年代後期，存儲器價格暴跌，半導體技術可以將非常複雜的係統放在芯片上，時鍾頻率達到了500MHz（時鍾周期時間隻有2ns）。Cache係統的容量和複雜性都增加了，計算機係統開始實現兩級Cache：在CPU內部的一級Cache和在主板上的二級Cache。兩級Cache係統中使用少量速度非常高的一級Cache和由大量速度快的存儲器構成的二級Cache。換句話說，有兩個層次的Cache串在一起。首先訪問速度快、容量小的一級Cache。如果沒有所需數據，則訪問速度較慢、容量較大的二級Cache。如果仍然沒有找到數據，則需要訪問主存儲器。兩級Cache係統的訪問時間由一級Cache的訪問時間加上二級Cache的訪問時間再加上主存儲器的訪問時間；即
tave = h1tc1 + (1-h1)h2tc2 + (1-h1)(1-h2)tm
其中，h1為一級Cache的命中率；tc1為一級Cache的訪問時間；h2為二級Cache的命中率，tc2為二級Cache的訪問時間。得到這個公式是下麵3種概率之和：
tave =訪問一級Cache的時間+訪問二級Cache的時間+訪問主存儲器的時間
一級Cache的訪問時間是h1tc1。如果一級Cache發生失效且二級Cache命中，訪問二級Cache的時間是（1-h1）h2tc2。如果數據不在兩級Cache中，訪問存儲器的時間為（1-h1）（1-h2）tm。因此，總的訪問時間為：
tave = h1tc1 + (1-h1)h2tc2 + (1-h1)(1-h2)tm
該公式為一個簡化形式，因為沒有考慮Cache寫回和Cache加載策略。考慮下麵這個例子。某計算機有一級Cache和二級Cache。訪問一級Cache沒有開銷，需要1個周期。在二級Cache中命中需要4個周期。如果沒有已緩存數據，則訪問主存儲器，包括Cache加載，需要120個時鍾周期。如果假設一級Cache的命中率為95%，二級Cache的後續命中率是80%，平均訪問時間是多少？
tave = h1tc1 + (1-h1)h2tc2 + (1-h1)(1-h2)tm
= 0.95×1 + (1-0.95)×0.80×4 + (1-0.95)×(1-0.80)×120
= 0.95 + 0.16 + 1.20
=2.31個時鍾周期
來自飛思卡爾半導體公司應用筆記AN2663的圖1-22給出了命中率與一級Cache及二級Cache的容量之間的關係，並用三維圖形表示。可見，峰值命中率是96%，此時執行了特定的代碼（GCC編譯器）。該應用筆記的結論是，16KB的一級Cache和1KB的二級Cache的性能與1KB的一級Cache和16KB的二級Cache的性能幾乎相同（雖然沒有人會設計出一級Cache比二級Cache大的係統）。
1.4.7 指令和數據Cache
數據和指令都是馮·諾依曼概念的核心；即它們共享相同的存儲器。Cache設計者可以選擇使用混合Cache（unified cache）來緩存數據和指令，或者實現分離的數據和指令Cache（split cache）。將數據和指令Cache分開是很有意義的，因為它們有不同的特性。除了將塊調入Cache以外，是不會修改指令Cache中的項目的。此外，不用擔心修改那些替換出指令Cache的指令，這是因為程序在其執行過程中不發會變化。由於指令Cache中的內容不會被修改，實現指令Cache要比實現數據Cache容易得多。將指令和數據Cache分別實現可以提高CPU與存儲器間的帶寬，這是因為指令和數據可以同時讀取。對於流水線係統來說，為了實現指令和數據的同時訪問，必須采用分離的指令和數據Cache。混合Cache和分離Cache的特點如下：
指令Cache可以為產生指令流而優化。
數據Cache可以為讀寫操作而優化。
數據Cache可以單獨進行優化。
指令Cache並不支持自修改代碼。
混合Cache支持自修改代碼。
數據Cache可以通過同時操作增加帶寬。
混合Cache需要更快速的存儲器。
混合Cache更加靈活（分離Cache中可能出現指令Cache滿而數據Cache還空著一半的情況）。
今天大多數的處理器都有分離的Cache，即使在具有多級Cache的係統中。高級別的Cache可以采用混合Cache，而低級的Cache需要分離Cache。
圖1-23中AMD的Barcelona體係結構演示了如何進行Cache的設計。Barcelona是一個多核係統，每個核心都有它自己的64KB一級Cache和512KB的二級Cache。所有4個核心共享2MB的三級Cache。一級Cache由兩個分離的32KB的Cache構成：一個數據Cache和一個指令Cache。傳統上，多級Cache的訪問順序是從最低級Cache開始根據失效情況逐漸延伸到更高級的存儲層次（先訪問一級Cache，然後詢問二級Cache，接著是三級Cache、主存儲器，直到失效的數據被找到）。在Barcelona體係結構中，一級Cache是所有Cache加載的最終目標，所有取得的數據都放到一級Cache中。二級Cache保存被替換出一級Cache中的數據。因為一級Cache和二級Cache之間是緊耦合的，所以從二級Cache到一級Cache傳輸數據所產生的延遲較低。
三級Cache被多個核共享。加載數據時將直接從三級Cache傳給一級Cache而不通過二級Cache。被傳送的數據要麼由於需要被多個處理器使用而保持在三級Cache中，要麼就因為不需要共享而刪除。與二級Cache類似，三級Cache不保存來自存儲器的數據，而是保存被替換出二級Cache的數據。
圖1-24給出了與Barcelona同期的Intel Nehalem架構。它的一級Cache、二級Cache和三級Cache的大小分別是32K、256K和8M字節。
與指令和數據Cache類似，一些計算機還實現了特殊的Cache。例如，在流水線中引入分支目標Cache（branch target cache）。分支目標Cache存儲與分支有關的信息，例如分支地址和目標地址處的指令操作碼。同樣，可以在特殊的返回地址Cache中保存子程序返回地址，以減少當返回地址保存在堆棧中時從子程序返回的開銷。
1.4.8 寫Cache
到目前為止，本章隻考慮了對Cache的讀訪問（訪問最頻繁的形式）。現在來看看更複雜的寫訪問。當處理器寫數據到Cache時，在Cache和主存儲器中的相應塊都需要修改，雖然這兩個操作不需要同時執行。然而，必須在下一次訪問前確保存儲器中的數據元素副本已被更新；即在Cache和存儲器中的數據元素必須保持一致。
前麵已經指出，在Cache和主存儲器並行訪問的係統中，平均訪問時間是tave = htc + (1-h)tm（其中，h為命中率，tc為Cache訪問時間，tm為主存儲器訪問時間）。如果數據不在Cache中，它必須從存儲器中取出，並調入Cache和目的寄存器。假定t1為Cache失效時從主存儲器中取出一塊並將其放入Cache所需的時間，存儲器係統的有效平均訪問時間是Cache訪問時間、存儲器訪問時間、由於失效導致的重新裝載時間（the reloads due to miss）之和：
tave = htc + (1-h)tm + (1-h)t1
上式中新出現的項(1-h)t1為失效後將取出的塊放入Cache的額外時間。該表達式可以改寫為：
tave = htc + (1-h) (tm + t1)
訪問導致失效的元素與將存儲器中的塊調入Cache可以同時進行。因此（t1 + tm）項應該是max(t1|tm)，因為t1>tm，上式可以寫成：
tave = htc + (1-h)t1
現在來看看寫回策略對該公式的影響。當處理器執行寫操作，數據必須被寫到Cache和主存儲器。在寫入Cache的同時也改寫主存儲器中的數據，這稱為寫直達（write-through）策略。該策略導致係統變慢，因為寫主存儲器的時間比寫Cache的時間要長。如果下一個操作是讀Cache，主存儲器可以同時完成更新（即寫直達策略並不一定會遭受過多的懲罰）。
相對較少的存儲器訪問操作為寫操作。實際上，寫訪問約占訪存操作的5%～30%。接下來，使用w表示寫操作的比例（0<w<1）。如果考慮讀操作發生失效和寫操作發生失效的情況，具有寫直達Cache的係統的平均訪問時間為：
tave = htc + (1-h) (1-w)t1 + (1-h)wtm
其中：t1為Cache失效時重新裝載所需的時間（這裏假設采用不按寫分配（no-write-allocate）策略，即寫失效時數據不調入Cache）。
(1-h) (1-w)t1這項代表讀失效時重新加載Cache所需的時間，而(1-h)wtm表示寫失效時寫入存儲器所需的時間。由於處理器可以在更新主存儲器時繼續完成另一個操作，(1-h)wtm這一項往往可以忽略，這是因為主存儲器有時間按照寫直達方式完成兩個連續的寫操作。由於假定計算機在寫失效時不更新Cache，故該公式不包括寫失效時將數據載入Cache的情況。
Cache的性能可以通過寫緩衝（write buffer）來改進，它保存了等待寫入存儲器的數據。典型的寫緩衝保存4個地址/數據對。當然，必須保證處理器要訪問的數據剛被更新、不在存儲器而在緩衝區中，此時，處理器可以訪問緩衝區。一種解決方案是在執行讀操作之前允許寫緩衝完成存儲器更新。
另一種修改存儲器的策略被稱為寫回（write-back）。在具有寫回策略的Cache係統中，向主存儲器的寫操作隻有在Cache塊被替換時才會發生，即對Cache的寫操作並不會每次都導致對主存儲器的更新。隻有在某塊由於讀失效而被替換出去時才將該塊寫回存儲器。因此上式可以寫為：
tave = htc + (1-h) (1-w)t1 + (1-h) (1-w)t1
= htc + 2(1-h) (1-w)t1
注意出現了兩個(1-h) (1-w)t1，這是因為讀失效導致被替換的塊寫回存儲器，同時新的塊被調入Cache。
Cache中的每一塊都有一個標誌來描述當前塊的狀態。例如，每個塊都有一個髒（dirty）位來表示它調入Cache後是否被修改過。如果該塊沒有被修改，在其被替換出Cache時就不需要寫回存儲器。具有這種寫回策略Cache的平均訪問時間由下式給出：
tave = htc + (1-h) (1-w)t1 + (1-h) pwwt1
其中，pw為塊需要被寫回主存儲器的概率。
圖1-25給出了具有寫回策略Cache的存儲器係統的決策樹。該圖描述了在讀失效時如何修改Cache以及塊被修改後如何寫回。發生寫失效時，Cache中的塊被寫回，並將新的塊裝入Cache。這些參數導致的平均訪問時間為：
tave = htc + (1-h) (1-w) (1-pw) t1 + (1-h) (1-w) pw·2t1 + (1-h) w·2t1
上麵給出了不同Cache策略下係統平均訪問時間的表達式。這些表達式都是近似的，真實係統的行為將取決於其具體實現。
最後更新：2017-05-25 10:31:20