前面已經說過,由于需要考慮的因素很多,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的重新整理。
本書将在下一章中介紹主存儲器系統,這裡先對cache的電路設計進行簡要說明。半導體随機通路存儲器有兩大類:靜态(static)和動态(dynamic)。靜态存儲器利用傳統數字邏輯将一位資料存儲在一個觸發器中——正如在《計算機組成原理》第2章中描述的那樣。靜态存儲器的特點是低功耗、高速和隻要有電就能夠保留資料。是以,cache通常由靜态ram構造。不幸的是,它需要6個半導體來存儲一個比特位,是以,靜态存儲器單元的實體尺寸(即所占矽片的面積)比dram單元要大得多。這意味着,靜态存儲器比dram更昂貴且容量較小,是以不能用來構造大容量的cache。
動态存儲器(dram)通過對單個半導體的電容充上電荷來儲存資料。這使得dram非常便宜和緊湊,可以用來構造大容量存儲器。不幸的是,dram需要更多的電量進行控制,且電容中的電量在幾ms内就會漏光。為了儲存dram中的資料,必須每隔4ms左右定期讀取存儲單元中的資料并将其寫回。dram不适于建構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更新。
塊是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容量越大,最佳的塊容量就越大。
有幾種政策可以用于降低失效率,進而提升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個連續的指令使用,是以隻需要做一次預取。
在20世紀90年代後期,存儲器價格暴跌,半導體技術可以将非常複雜的系統放在晶片上,時鐘頻率達到了500mhz(時鐘周期時間隻有2ns)。cache系統的容量和複雜性都增加了,計算機系統開始實作兩級cache:在cpu内部的一級cache和在主機闆上的二級cache。兩級cache系統中使用少量速度非常高的一級cache和由大量速度快的存儲器構成的二級cache。換句話說,有兩個層次的cache串在一起。首先通路速度快、容量小的一級cache。如果沒有所需資料,則通路速度較慢、容量較大的二級cache。如果仍然沒有找到資料,則需要通路主存儲器。兩級cache系統的通路時間由一級cache的通路時間加上二級cache的通路時間再加上主存儲器的通路時間;即
<code>tave = h1tc1 + (1-h1)h2tc2 + (1-h1)(1-h2)tm</code>
其中,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。是以,總的通路時間為:
該公式為一個簡化形式,因為沒有考慮cache寫回和cache加載政策。考慮下面這個例子。某計算機有一級cache和二級cache。通路一級cache沒有開銷,需要1個周期。在二級cache中命中需要4個周期。如果沒有已緩存資料,則通路主存儲器,包括cache加載,需要120個時鐘周期。如果假設一級cache的命中率為95%,二級cache的後續命中率是80%,平均通路時間是多少?
tave = h1tc1 + (1-h1)h2tc2 + (1-h1)(1-h2)tm
來自飛思卡爾半導體公司應用筆記an2663的圖1-22給出了命中率與一級cache及二級cache的容量之間的關系,并用三維圖形表示。可見,峰值命中率是96%,此時執行了特定的代碼(gcc編譯器)。該應用筆記的結論是,16kb的一級cache和1kb的二級cache的性能與1kb的一級cache和16kb的二級cache的性能幾乎相同(雖然沒有人會設計出一級cache比二級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中儲存子程式傳回位址,以減少當傳回位址儲存在堆棧中時從子程式傳回的開銷。
到目前為止,本章隻考慮了對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)之和:
<code>tave = htc + (1-h)tm + (1-h)t1</code>
上式中新出現的項(1-h)t1為失效後将取出的塊放入cache的額外時間。該表達式可以改寫為:
<code>tave = htc + (1-h) (tm + t1)</code>
通路導緻失效的元素與将存儲器中的塊調入cache可以同時進行。是以(t1 + tm)項應該是max(t1|tm),因為t1>tm,上式可以寫成:
<code>tave = htc + (1-h)t1</code>
現在來看看寫回政策對該公式的影響。當處理器執行寫操作,資料必須被寫到cache和主存儲器。在寫入cache的同時也改寫主存儲器中的資料,這稱為寫直達(write-through)政策。該政策導緻系統變慢,因為寫主存儲器的時間比寫cache的時間要長。如果下一個操作是讀cache,主存儲器可以同時完成更新(即寫直達政策并不一定會遭受過多的懲罰)。
相對較少的存儲器通路操作為寫操作。實際上,寫通路約占訪存操作的5%~30%。接下來,使用w表示寫操作的比例(0
<code>tave = htc + (1-h) (1-w)t1 + (1-h)wtm</code>
其中: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
注意出現了兩個(1-h) (1-w)t1,這是因為讀失效導緻被替換的塊寫回存儲器,同時新的塊被調入cache。
cache中的每一塊都有一個标志來描述目前塊的狀态。例如,每個塊都有一個髒(dirty)位來表示它調入cache後是否被修改過。如果該塊沒有被修改,在其被替換出cache時就不需要寫回存儲器。具有這種寫回政策cache的平均通路時間由下式給出:
<code>tave = htc + (1-h) (1-w)t1 + (1-h) pwwt1</code>
其中,pw為塊需要被寫回主存儲器的機率。
圖1-25給出了具有寫回政策cache的存儲器系統的決策樹。該圖描述了在讀失效時如何修改cache以及塊被修改後如何寫回。發生寫失效時,cache中的塊被寫回,并将新的塊裝入cache。這些參數導緻的平均通路時間為:
<code>tave = htc + (1-h) (1-w) (1-pw) t1 + (1-h) (1-w) pw·2t1 + (1-h) w·2t1</code>
上面給出了不同cache政策下系統平均通路時間的表達式。這些表達式都是近似的,真實系統的行為将取決于其具體實作。