MIPS--cache管理

http://hi.baidu.com/qq520131714/blog/item/0f6adafefa7058365c600898.html

MIPS--cache管理

沒有Cache的MIPSCPU不能稱為真正的RISC。可能這樣說不公平。但為了一些特殊的目的，你可以設計一個含有小而緊密記憶體的MIPSCPU，而這些記憶體隻需要固定個數的流水線步驟（最好是一個）就可以被通路到。但絕大部分MIPS CPU都是含有cache的。

這一章将介紹MIPS的cache怎樣工作和軟體應該怎麼做才能使它可以被使用而且是可靠的。MIPSCPU重新啟動後，cache的狀态是不确定的，是以軟體必須非常小心。你有一些線索知道cache的大小（如果你直接知道cache的大小後去初始化，這是一個不好的軟體習慣。）。對于診斷程式員，我們将讨論怎樣測試cache和擷取特殊入口。

對于實時應用程式的程式員，希望在CPU運作時能夠正确地控制cache。我們也将讨論怎麼做，雖然我對使用一些竅門方式有懷疑。

當然這些也随着MIPSCPU的發展而進步。對于早期的32位MIPS處理器，初始化cache或者使其無效，首先讓cache進入一種特殊的狀态，然後通過普通的讀寫操作來完成。對于後來的處理器，一些特殊的指令被定義出來做這些相關的操作。

4.1 cache和cache的管理

cache的工作就是将記憶體中的一部分資料在cache中保留一個備份，使這些資料能一個固定的極短的時間内被快速的存取并傳回給CPU，這樣能保證流水線的連續運作。

絕大部分MIPSCPU針對指令和資料有其各自的cache（分别稱為Icache和Dcache)，這樣讀一條指令和一個資料的讀操作或者寫操作就能同時發生。

老的CPU家族（象x86)為了保證被寫入CPU的代碼的一緻性，是以沒有cache。現在的x86晶片擁有更靈活的硬體設計，進而保證軟體沒有必要從更本上了解cache（如果你正在裝一台機器跑MS/DOS，它将在本質上提供一緻性）。

但因為MIPS機器有各自的cache，是以就沒有必要那麼靈活。cache對于應用程式來說必須是透明的，除了除了能感覺到運作速度的增加。但對于系統程式或者驅動程式，擁有cache的MIPSCPU并沒有嘗試cache對它們也是透明的。cache僅僅使CPU跑得更快，而不能給系統程式員有所幫助。在象Unix一類的作業系統中，作業系統能對應用程式完全隐藏cache，當然對于更多不能的勝任的作業系統，其也能很好的隐藏大部分cache的處理，但你可能必須知道在什麼時候需要調用适當的子程式來對cache做一些必要操作。

4.2 cache怎樣工作

從概念上講，cache是一個相連記憶體（associative memory），當資料被寫入時用資料的一部分作為關鍵字來标志的一塊存儲區域。在cache中，關鍵字是整個記憶體的位址。提供一個相同的關鍵字給相連記憶體，你将得到相同的資料。一個真實的相連記憶體在存入條目時，将完全按照它們的關鍵字，除非它已經滿了。然而，由于需要這個目前的關鍵字必須和所有被存的關鍵字同時比較，是以任何大小的真實相連記憶體不是效率低或速度慢，或者就是兩者都有。

怎樣我們才能設計有用的高速緩存，使其不僅效率高而且速度快呢？圖4.1展示了一種最簡單高速緩存的基本設計方案，直接映射（direct-mapped）高速緩存。它被1992年以前的MIPSCPU廣泛使用。

直接映射cache由許多塊簡單的高速緩存排列構成（通常每一塊稱之為一line），通過位址低位在整個範圍内做索引。cache的每一條line都包含一個字或者幾個字的資料和一個标簽（tag）區域，tag記錄着資料所在記憶體的位址。

當一個讀操作時，每一條line都可以被通路到，tag将和記憶體位址的高位做比較；如果比對的話，我們知道是找到正确的資料了，這被稱之為命中（hit）。如果在這一塊中有超過一個字的資料，對應的那個字的資料通過位址的最低幾位來選擇出來。

如果tag沒有比對，這稱之為沒有命中（miss），那麼資料需要從記憶體中讀入，然後複制到cache對應的line中。這對應line中原來的資料将會被抛棄，如果CPU又需要被抛棄的資料時，需要再次從記憶體中取得。

這樣的直接映射cache有一個特征，就是對于任何一個記憶體位址，在高速緩存中隻有唯一的一條line可以用來儲存其資料。這樣有好處也有壞處。好處就是這樣的架構簡單，可以使CPU跑得更快。但簡單也有其不好的一面：如果你的程式要不停地交替使用兩個資料，而它們剛好要對應高速緩存中的同一塊（可能是它們對應記憶體位址的低位剛好一樣），這樣這兩個資料就會不停的将對方替換出高速緩存，以至高速緩存的效率被徹底的降下來。

而真正的相連記憶體将不會遇到這樣的折騰，但對于任何合理大小，它将是難以想象的複雜、昂貴和速度緩慢。

折衷的辦法就是使用two-way set-associative cache，其實就是兩個direct-mapped cache并聯，在它們中同時比對記憶體位置。如圖4.2。這時對應一個位址将有兩次機會命中。Four-way set-associative cache （就是有四個直接映射的子高速緩存)在cache的設計中也是很平常的。但是這是有懲罰的。一個set-associate cache比起直接映射cache來需要更多的總線連接配接，是以cache太大以至于很難在一塊晶片上構造直接映射。

不過也有巧妙的地方，由于直接映射cache對于你需要的資料隻有唯一的候選者，是以把一些東西放到tag比對前運作是可能的（隻要CPU不做和着個資料有關的操作）。這樣可以提高每一個時鐘使用率。

由于當運作一段時間後cache會被裝滿，是以當再次存放從記憶體讀來的資料時，就會抛棄一些cache内原有的資料。如果你知道這些資料在cache和記憶體中是一緻的，那麼你可以直接把cache中的備份抛棄；但如果cache中的資料更新的話，你就需要首先把這些資料存回到記憶體中。

這就給我們帶來一個問題，cache怎樣處理寫操作？

4.3 Write-Through Caches in Early MIPS CPUs

CPU不能僅僅是讀資料（就象上面的讨論），它們也要寫資料。由于cache隻是将主存中的一部分資料做一個備份，是以有一個顯而易見的方法來處理CPU的寫操作，被稱之為Write-Through cache。

對于Write-Through cache，寫操作時CPU總是将資料直接寫到主存中去；如果對應主存位置的資料在cache中有一個備份，那麼cache中的那個備份也要被更新。如果我們總是這樣做的，那麼cache中的任何資料将和主存中的保持一緻，是以隻要我們需要我們就可以抛棄任何一條cahce line的資料，并且除了消耗時間不會丢失任何東西。

當然這也是有危險的，當我們讓處理器等待寫操作結束時，處理器的運作速度将徹底的降下來，不過我們能修複這個問題。可以将要寫入主存的資料及其位址先儲存在另一邊，然後有主存控制器自己取得這些資料并完成寫操作。這個臨時儲存寫操作内容的地方被稱之為寫操作緩沖區 （write buffer），它是先入先出的（FIFO)。

早期的MIPS CPU有一個直接映射的write-through cache和一個寫操作緩沖區，還有一個R3000的激發設定。它在同一晶片上構造cache控制器，但需要額外的高速存貯器晶片來存貯tag和資料。隻有CPU跑一些特殊的程式很平均地産生的寫操作，主存系統在這種工作方式下才能很好的消化這些寫操作并工作的很好。

但CPU運作速度的增長比存貯器塊得多。某些時候當32位的MIPS讓位給64位R4000後，MIPS的速度就已經超過存貯器系統可以合理消化所有寫操作的臨界點了。

4.4 Write-Bach Cache in Recent MIPS CPUs

早期的MIPS CPU 使用簡單的write-through cache。後來的MIPS CPU由于速度太快而不能适用這種方法，它們會陷入存儲系統的寫操作中，速度慢得像爬行。

解決的方法就是把要寫的資料保留在cache中。要寫的資料隻寫到cache中，并且對應的那條cahce line要做一個标記，使我們肯定不會忘記在某個時候把它回寫到記憶體中(一條line需要回寫，稱之為dirty)。

Write-back cache還可以分成幾種不同的子處理方式。如果目前cache中沒有要寫位址所對應的資料，我們可以直接寫到主存中而不管cache，或者可以用特殊的方式把資料讀入cache，然後再直接寫cache，後面這種方式被稱之為寫配置設定（write allocate）。用一種自私的觀點來看一個程式運作在一個CPU上，寫配置設定（write-allocate）看起來象浪費時間；但是它可以使整個系統的設計變得簡單，因為在程式運作時讀寫記憶體都讀或者寫都是以一條cache line大小為機關的塊進行操作。

從MIPS R4000 開始，MIPS CPU在晶片内擁有cache，而且都支援write-through和write-allocate兩種工作模式，line的大小也是支援16byte和32byte兩種。

MIPS cache的這些工作模式可以被應用到使用sillicon Graphics設計R4000和其他大型CPU，其他計算機系統也因為多處理器系統而被這些cache工作模式影響到。

4.5 Cache設計的其他選擇

在上個世紀八十和九十年代針對怎樣設計cache，做了很多工作和研究。是以下面還有許多其它的設計選擇。

Physically addressed/virtually addressed:

當CPU在運作成熟的作業系統時，資料和指令在程式中的位址（程式位址或虛拟位址）會被轉換成系統記憶體使用的實體位址。

如果cache純粹地在實體位址方式下工作，将很容易被管理（我們将在後面讨論為什麼）。但合法的虛拟位址可以讓cache更早地開始查詢比對工作，這樣可以使系統跑的稍微塊一點。

但虛拟位址有什麼問題呢？它們不是唯一的；當許多不同的程式在CPU不同的位址空間中運作，它們可能會共享同樣的虛拟位址而使用不同的資料。當我們切換不同的位址空間時，每次都需要重新初始化cache；這種方式在很多年前被使用，可以作為針對非常小的cache的一種合了解決方法。但針對大的cahce這種方式不僅可笑而且效率低下，我們需要一塊區域來辨識cache tag中的位址空間，以至我們不被它們混淆。

這兒還有其它關于虛拟位址更細緻的問題：相同的實體位址可以在不同的任務中被不同的虛拟位址描述。這就會導緻相同實體位址的内容會被映射到不同的cache條目中（因為它們對應不同的虛拟位址，是以會被不同的索引所選中）。這樣的情況必須被作業系統的記憶體管理所避免掉。詳細的情況将在4.14.2節介紹。

從R4000起，MIPS的主cache都使用虛拟位址索引，進而提供快速的cache索引。但對于作為标記符來标記每一個cache-line，實體位址比虛拟位址更好。實體位址是唯一的而且效率更高，因為這樣的設計顯示出CPU在做cache索引的同時可以把虛拟位址轉換成實體位址。

line大小的選擇（Choice of line size）:

line的大小是對應每一個tag可以存貯多少字的資料。早期的MIPS的cache對應一個tag隻能存貯一個字的資料。但對應一個tag能存貯多個字的資料更好，尤其是記憶體系統支援快速的burst read。現代的MIPS cache趨向于使用四個或者八個字大小的line，并且更大的第二層和第三層cache使用更大的line。

當cache miss發生時，整個一條line的資料都要從記憶體中獲得。但很可能會取來幾line的資料；一個字的cache line的MIPS CPU經常是一次就取多個字的資料。

分開/統一（Split/unified）:

MIPS的主cache總是分成I-cache和D-cache，取指令時察看I-cache，讀寫資料時察看D-cache。（順便說一下，如果你想執行CPU剛剛拷貝到記憶體的代碼，你必須不僅僅要是D-cache一部分無效使這些代碼資料在D-cache中不再存在，而且還要保證它們被裝入I-cache）

但是不在同一塊晶片上的第二層cache很少也按這種方式來分成兩塊。這樣就沒有什麼真的優勢可言了。除非你能針對兩種cache提供分開的資料總線，但這又會需要太多的管腳。

4.6 Cache管理（Magaging Caches）

Cache系統在系統軟體的幫助下，必須保證任何應用程式資料的一緻性，和它們在沒有cache的系統下一樣，尤其是DMA I/O控制器（直接從記憶體中取得資料）取得程式認為已經寫過的資料。

對于CISC CPU，通常都不需要系統軟體對cache的幫助；因為它會花費額外的記憶體空間、silicon area、時鐘周期來使得cache變得真正的透明。

在系統啟動的時候MIPS CPU需要初始化它的cache；這是一個十分複雜的過程，下面有關于它的幾點建議。但當系統啟動後運作到三種情況CPU必須加以幹涉。

.在DMA裝置從記憶體取資料之前:

如果一個裝置從記憶體中取得資料，它必須取得正确的資料。如果D-cache是write-back，并且程式已經寫了一些資料，那麼很可能其中一些正确的資料還保留在D-cache中而沒有寫回到主存中去。CPU當然不可能看到這個問題；如果CPU需要這些資料，它會從cache中得到正确的資料。

是以在DMA裝置開始從記憶體中讀資料前，任何一個将被讀資料如果還保留在D-cache中，必須被寫回到記憶體中。

. DMA裝置寫資料到記憶體:

如果一個裝置要将資料存貯到記憶體中，要使cache中任何對應将要寫入記憶體位置的line都無效化，這是非常重要的。否則，CPU讀這些位置的資料，将得到錯誤的資料。cache應該在資料通過DMA寫入記憶體之前将對應的cache line無效化。

. 拷貝指令:

當CPU自己為了後面的執行而寫一部分指令到記憶體中，你首先必須保證這些指令會被回寫到記憶體中，其次保證I-cache中對應這些指令的line會被無效化。在MIPS CPU中，D-cache和I-cache是沒有任何聯系的。（當CPU自己寫指令到記憶體中時，這時候指令是被當作資料寫的，很可能隻被寫到cache中，是以我們必須保證這些指令都會被回寫到記憶體中；為什麼要使I-cache無效化，這和資料通過DMA直接寫入記憶體中要無效cache一樣的原因。）

如果你的軟體需要解決這些問題，就需要針對cache line的兩個獨特的操作。

第一個操作被稱之為回寫操作。CPU必須能夠針對位址在cache中查找對應的cache line。如果找到，并且對應line是dirty，就需要把這條line的資料寫回到記憶體中。

CPU增加了其他不同層次的cache（速度和大小），來減少miss的處理。是以設計者可以使内層的cache機構簡單，進而使它能在很高的時鐘頻率上作查詢。這樣很顯然越往内層的cache就會越小。從1998年開始，許多高速的cpu都在同一塊晶片上采用第二級cache，主cache的大小變小，雙重16K的主cache受到青睐。

不在同一塊晶片上的cache通常都是直接映射的，因為組相連的cache系統需要更多的總線進而需要更多的管腳來連接配接。這還是一個值得研究的領域；MIPS R10000采用隻有一個資料總線的二路組相連cache，如果命中的不是希望的那一組，通過一段延時後在傳回資料來實作（兩個組共用一個資料總線）。

在cache的發展過程中，産生了兩類主要的軟體接口來針對cache。從軟體的觀點來看，一類是建立在以R3000為代表的32位MIPS CPU的基礎上；另一類是建立在以R4000為代表的64位MIPS CPU上的。R3000這一類型的MIPS CPU的cache是write-through，直接映射的，實體位址為索引。cache通路的最小機關是一個字，是以寫一個位元組（或者是寫小于一個字）的操作必須被特殊的處理。在讀寫這一類資料是cache管理采用特殊的模式。

為什麼不通過硬體來管理cache?

通過硬體來管理cache通常被稱為“愛管閑事”。當另一個cpu或者是DMA裝置通路記憶體時，被通路位址對應的内容對于cache來說是可以看到的。

4.7 第二層和第三層cache

在大型的系統中，通常需要一個嵌套的多層cache。一個小而快的主cache最接近cpu。通路主cache出現miss時，不是直接從記憶體中查找而是從第二層cache中查找。第二層cache在速度和大小上是介于主cache和記憶體之間。cache層次的數目可以通過記憶體速度和cpu最快通路速度比較來決定；由于cpu速度發展比記憶體的發展快得多，在過去的12年裡桌上型電腦系統從沒有cache發展到有兩層cache。九十年代後期的最快cpu速度大約可以達到500MHz，擁有三層cache。

4.8 MIPS CPU cache的構造

通過觀察cache采用模式和層次的發展（看表4.1），我們可以将MIPS CPU分成兩類，古老的和現代的。

當時鐘的速度變得越快，我們就能看到越多得cache構造，因為設計者為了應付CPU跑得速度比記憶體系統越來越快。為了保證運作的順暢，cache必須提高運作速度，保證提供資料的速度比外圍得存貯器要快，同時也要保證盡可能多命中。相比較R4000類型的CPU，主cache是write back類型，是write allocate ,virtually indexed,physically tagged, 二路或四路組相連的cache。

許多R4x00和其後續cpu在同一塊上擁有第二層cache的控制器，1998年出現了這樣的第一塊cpu。

由于兩種産生的不同，我們将分兩節來詳細介紹。

注意！一些系統的第二層cache不是由mips cpu内部的硬體來控制的，而是建立在記憶體的總線上。對于這類cache的軟體接口将具有系統特殊性，和象這章介紹的由cpu内部控制的cache的軟體接口相比，可能有很大的不同。

4.9 Programming R3000-Style Caches

MIPS R2000打破了晶片内cache控制器的基礎，将cache額外的分成I-cache和D-cache。這是一個後見之明，不會讓人感到驚訝，就是這樣一個先驅者的冒險導緻了後面很多事端。cache有一個特殊的軟體通路缺點。

為了節省晶片管腳，cache将不能擁有不同的閘門來執行位元組、半個字和其他小于一個字機關的寫操作。是以在R2000系列中對cache執行一個小于字機關的寫操作時，會回寫到主存中，并将cache中這個字所在的Line無效化。這樣針對cache管理，提供了一個使cache無效的方法：隻用寫一個位元組就行了。

你可以看到支援這些簡化的觀點。R2000設計者提出理由小于字的操作通常用于字元操作，字元操作總是由庫函數提供，而這些庫函數用整個字的操作來重寫。這些假設總是被認為對對錯錯，或者半對半錯。

直到認識到不是所有系統都能用相同的函數庫，而且每個位元組寫操作都使所在cache無效也不是一個好主意，這些争論才沒有繼續下去。因為這是不能被容忍的，是以出現了一個很大的改動，R3000系列的cpu通過一個RMW(read-modify-write)序列來執行小于字機關的寫操作。這個RMW出現在是以的32位的mips cpu中，并增加了一個 時鐘周期來作為這樣一個寫操作的延時。

這樣cache無效的機制被帶入困境；R2000因為它的奇怪習慣而有一個優點，可以通過位元組的寫操作來使cache無效化。而R3000 cache 需要用一個叫isolation的模式來挽救，原來這種模式隻是用于cache診斷的。RMW隊列因為這種模式而受到壓制，在那種狀态下小于一個字機關的寫操作還是會讓該字所處的line無效化。這是不幸的但不是悲慘（災難）的，對于一些運作着的系統做一些事有着更有益的地方。顯著的就是當cache在isolation模式時的時候，cache将沒有讀寫操作，任何讀寫操作将直接和記憶體打交道。

4.9.1 Using Cache Isolation and Swapping

所有的R3000系列cpu的cache都是write-through模式的，這就是說cache中不會擁有比記憶體中更新的資料。也就是說cache中的資料從來都不需要回寫到記憶體，是以我們隻需要能使D-cache和I-cache無效就行了。

隻需要不同的cache操作按照記憶體順序來做cahce的管理，并且cache的管理沒有必要通過特殊的記憶體位址空間。是以這兒有一個狀态寄存器有一個SR位能夠使D-cache關閉isolation模式；在這種模式下讀寫操作隻影響着cache，讀還是會命中但不管tag是不是相等。當D-cache處于isolation模式時，小于一個字機關的寫操作會使對應cache Line被無效化。

CAUTION!!!

當D-cache處于isolation模式，任何讀寫操做不會受其對應位址或TLB條目的影響而按照非cache的情況操作。這樣的結果就是cache管理程式必須保證有些資料是不可以被通路的；如果你能通過你的編譯器做到很好的控制，并且能過保證所有你用的變量都儲存在寄存器中，你才能在很進階别的語言中寫它們。還必須保證運作這些程式時屏蔽中斷。

I-cache在通常運作模式下也是完全不可通路的。是以CPU提供了另一種模式，cache交換(swapped)，通過設定狀态寄存器的SwC位；這時D-cache可以擔當I-cache，I-cache可以擔當D-cache。當cache是交換模式時，isolated的I-cache條目可以被讀、寫和無效化。

D-cache可以完美的充當I-cache使用（可能I-cache也可以通過初始化使之象D-cache一樣工作），但I-cache不能完全的充當D-cache。這也是靠不住的，當cache是交換模式時有用，isolation卻沒有用。

如果你需要使用交換的I-cache來存儲字機關的資料（和以前一樣小于字機關的資料寫操作會使該資料對應的line被無效化），你必須保證在傳回到正常模式時對應的cache line必須被無效化。

4.9.2 Initializing and Sizing 初始化和判斷大小

當機器啟動時cache的狀态是不确定的，是以這時讀cache結果也是不可預知的。你也應該認識到機器重起後狀态寄存器的SwC位和IsC位也是不确定的，是以在對cache讀寫前（即使在非cache的情況）啟動軟體最好能将這些狀态設為可知的。

不同的MIPS CPU，cache有不同的大小。為了保證你軟體的可移植性，最好能在初始化的時候計算出D-cache和I-cache的大小。這樣比直接配置一個給定的值好。

下面将介紹怎樣獲得cache大小的值：

a. Isolated cache，讓I-cache處于交換模式。

b. 在R3000系列CPU中，cache的大小可能是256K，128K，64K，32K，16K，8K，4K ，2K，1K和0.5K（K等于1024，機關是位元組)。将這些可能的值n（上面那些值中的一個）寫到實體位址等于它們本身的地方（有大到小）。最簡單産生實體位址是用Kseg0段位址（n+0x80000000)。因為cache位址是重疊循環的，那麼如果n是cache大小的倍數，那麼它就會被後面小的值所覆寫。

c. 是以讀實體位址零（也就是0x80000000），就能得到cache大小的值。

初始化cache，你必須保證每一個cache條目都被無效化，而且正确對應一個記憶體位置，所含的之值也是正确的：

a. 檢查狀态寄存器SR的PZ位是不是位零（為1的話，關閉奇偶位，對于同一個晶片上的 cache這不是一個好主意）。

b. isolated D-cache，并使它和I-cache交換。

c. 對于cache的每一個字，先寫一個字的值（使cache的每條line的tag、資料、和奇偶位都正确），然後再寫一個位元組（使每條line都無效）。

不過要注意當對于每條line有四個字的I-cache，這樣做效率就很低；因為隻要寫一個位元組就足夠使每條line無效了。當然除非你要經常調用這個使cache無效程式，否則這個問題是不會表現的很明顯。不過如果你想根據實際情況來優化cache無效化程式，就需要在啟動的時候确定cache的結構。