存儲(chǔ)器層次結(jié)構(gòu)設(shè)計(jì)

1、第五章 存儲(chǔ)器層次結(jié)構(gòu)設(shè)計(jì)在理想情況下，我們希望存儲(chǔ)容量無(wú)限大，這樣任何一個(gè)特定的字都可以立刻獲取我們不得不認(rèn)識(shí)到構(gòu)建存儲(chǔ)器層次結(jié)構(gòu)的可能性，它們中的每一層都比其上一層具有更大的容量和更慢的訪問(wèn)速度。 和J.von Neumann電子計(jì)算設(shè)備邏輯設(shè)計(jì)預(yù)備討論會(huì)（1946）5.1簡(jiǎn)介計(jì)算機(jī)的先驅(qū)們正確地預(yù)見(jiàn)到了編程者希望擁有無(wú)限大容量的快速存儲(chǔ)器。一個(gè)解決這個(gè)問(wèn)題較經(jīng)濟(jì)的方法就是采用存儲(chǔ)器層次結(jié)構(gòu)，其依據(jù)是程序訪問(wèn)的局部性原理和內(nèi)存技術(shù)的性能價(jià)格比原則。在第一章中所闡述的局部性原理認(rèn)為大部分程序并不是均衡的訪問(wèn)所有的代碼和數(shù)據(jù)（參見(jiàn)1.6節(jié)）。這個(gè)原理以及越小硬件、其速度越快這個(gè)指導(dǎo)思想，產(chǎn)生了

2、基于不同速度和容量的存儲(chǔ)器層次結(jié)構(gòu)。圖5.1顯示了一個(gè)多級(jí)存儲(chǔ)器層次結(jié)構(gòu)，其中包括了典型的各層次容量大小和存取速度值。圖5.1一個(gè)通用于嵌入式系統(tǒng)、桌面處理器、服務(wù)器的典型多級(jí)存儲(chǔ)器層次結(jié)構(gòu)。距離CPU越遠(yuǎn)的層次，存儲(chǔ)容量越大，存取速度越慢。注意，不同層次的存取時(shí)間的變化系數(shù)為10：從微微秒到毫秒之間變化；而容量大小的變化系數(shù)為1000：從幾字節(jié)到幾千兆字節(jié)之間變化。圖5.3將給出桌面處理器、小型服務(wù)器的更多參數(shù)指標(biāo)。由于快速存儲(chǔ)器較為昂貴，因此將存儲(chǔ)器層次結(jié)構(gòu)可以組織成幾個(gè)不同層次每一層都比它更低一層具有更小的容量，更快的速度、當(dāng)然每字節(jié)的價(jià)格也更高。這種組織結(jié)構(gòu)的目標(biāo)是提供一個(gè)存儲(chǔ)器系統(tǒng)，

3、使之能夠具有幾乎相當(dāng)于最便宜層次的存儲(chǔ)器的價(jià)格，但是訪問(wèn)速度卻與最快層次的存儲(chǔ)器接近。層次結(jié)構(gòu)中的各層之間通常是子集關(guān)系，某一層中的所有數(shù)據(jù)也總能在其低一層中找到，而低一層中的所有數(shù)據(jù)也能在更低一層中找到，如此直到層次結(jié)構(gòu)的最底層。在層次結(jié)構(gòu)中，每一層都要從一個(gè)較大的存儲(chǔ)器空間中把地址映射到一個(gè)較小、但是更快的、位于上一層的存儲(chǔ)器中。作為地址映射的一部分，存儲(chǔ)器層次結(jié)構(gòu)具有地址檢查的功能，因此，用于監(jiān)察地址的保護(hù)機(jī)制也是存儲(chǔ)器層次結(jié)構(gòu)的一部分。隨著處理器性能增長(zhǎng)，存儲(chǔ)器層次結(jié)構(gòu)的重要性不斷增加。例如，在1980年，微處理器一般是不帶Cache的，但是到了2001年，處理器芯片內(nèi)部通常帶有兩級(jí)C

4、ache。正如在第一章中提到的：1986年以前，微處理器的性能改進(jìn)是平均每年提高35；從1987年以后，微處理器的性能改進(jìn)則達(dá)到了平均每年提高55。圖5.2描繪了CPU性能伴隨著主存訪問(wèn)性能提高的預(yù)測(cè)增長(zhǎng)情況。顯然，計(jì)算機(jī)體系結(jié)構(gòu)設(shè)計(jì)者必須盡力去縮小處理器主存之間的性能差距。圖5.2以1980年性能為基準(zhǔn)，存儲(chǔ)器和CPU的性能差距隨時(shí)間的變化曲線。存儲(chǔ)器的基準(zhǔn)是1980年的64-KB DRAM，三年更新?lián)Q代、在延遲上每年都有7的性能增長(zhǎng)（參見(jiàn)圖5.30）。CPU曲線表示：1986年以前CPU性能每年增長(zhǎng)1.35倍，而此后每年增長(zhǎng)1.55倍。圖中縱軸是用對(duì)數(shù)坐標(biāo)來(lái)表示CPU-DRAM性能差距。本

5、章將描述為減少處理器-存儲(chǔ)器的性能差距而提出的一些改進(jìn)方法。為便于理解這些抽象的改進(jìn)方法，在本章中，我們以四級(jí)存儲(chǔ)器層次結(jié)構(gòu)、采用Alpha 21264微處理器的計(jì)算機(jī)系統(tǒng)作為應(yīng)用實(shí)例。在本章的最后，我們利用SPEC95 benchmark程序評(píng)價(jià)了這些層次結(jié)構(gòu)對(duì)系統(tǒng)性能的影響。21264微處理器是專(zhuān)為桌面處理器和服務(wù)器設(shè)計(jì)的。即使是這兩類(lèi)相關(guān)聯(lián)的計(jì)算機(jī)系統(tǒng)，它們?cè)诖鎯?chǔ)器層次方面也有著不同的側(cè)重點(diǎn)。桌面處理器在操作系統(tǒng)的控制下，一次只為單個(gè)用戶(hù)運(yùn)行一個(gè)應(yīng)用程序；而服務(wù)器則有可能同時(shí)為成百上千個(gè)用戶(hù)執(zhí)行大量的應(yīng)用程序。服務(wù)器的這些特征導(dǎo)致了更多的上下文切換，顯著增加了強(qiáng)制性缺失率。因此，桌面處理

6、器主要關(guān)注于存儲(chǔ)層次結(jié)構(gòu)帶來(lái)的平均延遲問(wèn)題，而服務(wù)器除此之外，還需要考慮存儲(chǔ)帶寬問(wèn)題。盡管在桌面處理器中阻止程序間數(shù)據(jù)混淆的保護(hù)機(jī)制很重要，但是服務(wù)器同時(shí)還必須兼顧防止一個(gè)用戶(hù)存取其他用戶(hù)的數(shù)據(jù)，因而更突出保護(hù)升級(jí)的重要性。服務(wù)器的發(fā)展趨向于大型化，擁有更大內(nèi)存和更多磁盤(pán)存儲(chǔ)，運(yùn)行更多更大的應(yīng)用程序。在2001年，服務(wù)器通常都是擁有成千上百個(gè)磁盤(pán)的多處理器配置，要求存儲(chǔ)層次結(jié)構(gòu)擁有很大帶寬。 嵌入式計(jì)算機(jī)與桌面處理器、服務(wù)器計(jì)算機(jī)的存儲(chǔ)層次結(jié)構(gòu)有很大不同。首先，嵌入式計(jì)算機(jī)一般用于實(shí)時(shí)處理，程序員必須考慮到最壞情況時(shí)的性能。這時(shí)，盡管采用Cache結(jié)構(gòu)能夠提高平均性能，但是會(huì)降低最壞情況時(shí)的性

7、能，因此是否采用Cache結(jié)構(gòu)還存在爭(zhēng)議。對(duì)此，我們將在本章中后續(xù)章節(jié)中討論一些改進(jìn)技術(shù)。其次，嵌入式應(yīng)用程序常常關(guān)注于電源和電池壽命。節(jié)省功耗的最好辦法是減少硬件，因此，嵌入式計(jì)算機(jī)不能象大多數(shù)桌面處理器和服務(wù)器一樣，用擴(kuò)展硬件優(yōu)化的方法來(lái)獲取更好的存儲(chǔ)層次性能。第三，典型的嵌入式應(yīng)用程序采用非常簡(jiǎn)單的操作系統(tǒng)，只運(yùn)行一個(gè)應(yīng)用程序，因而可以不考慮存儲(chǔ)層次保護(hù)機(jī)制。最后，嵌入式處理器的主存可能很小（不到1MB），并且常常不需要磁盤(pán)存儲(chǔ)。 本章我們以桌面處理器為例，對(duì)存儲(chǔ)器層次結(jié)構(gòu)的基本原理進(jìn)行討論，指出其與服務(wù)器、嵌入式計(jì)算機(jī)在存儲(chǔ)層次結(jié)構(gòu)上的不同。除了Alpha 21264 之外，本章最后將

8、會(huì)給出Sony Playstation 2 和 Sun Fire 6800服務(wù)器中的存儲(chǔ)器層次結(jié)構(gòu)。5.2Cache回顧C(jī)ache：隱藏或存儲(chǔ)東西的安全地點(diǎn)韋伯思特美語(yǔ)新世界詞典，第二版（1976）本節(jié)我們先來(lái)回顧一下Cache基本概念，涉及到的內(nèi)容有以下36項(xiàng)：高速緩存（Cache）全相聯(lián)寫(xiě)分配虛擬存儲(chǔ)器重寫(xiě)位一體Cache存儲(chǔ)器停頓周期塊內(nèi)偏移每條指令缺失次數(shù)直接映射寫(xiě)回法塊有效位數(shù)據(jù)Cache局部性塊地址命中時(shí)間地址跟蹤寫(xiě)通過(guò)Cache缺失組指令Cache頁(yè)缺失隨機(jī)替換平均存儲(chǔ)器存取時(shí)間缺失率索引域Cache命中n-路組相聯(lián)非寫(xiě)分配(no-write allocate)頁(yè)最近最少使用寫(xiě)緩

9、沖缺失代價(jià)標(biāo)志域?qū)懲ｎD(write stall)知道上面這些術(shù)語(yǔ)意義的讀者，可以跳到“一個(gè)例子：Alpha 21264數(shù)據(jù)Cache”部分，甚至直接跳到5.3節(jié)“Cache性能”。（如果覺(jué)得本節(jié)的回顧太快的話，可以參考第7章“計(jì)算機(jī)結(jié)構(gòu)與設(shè)計(jì)”，這是針對(duì)經(jīng)驗(yàn)較少的讀者編寫(xiě)的。）存儲(chǔ)器層次結(jié)構(gòu)中最重要的兩層是Cache和虛擬存儲(chǔ)器。Cache通常是存儲(chǔ)器層次結(jié)構(gòu)中第一層的名字，是距離CPU最近的存儲(chǔ)層次。既然局部性原理應(yīng)用到了許多方面，而且利用其優(yōu)點(diǎn)來(lái)提高性能是非常普遍的，所以術(shù)語(yǔ)Cache如今被應(yīng)用到了任何通過(guò)緩沖區(qū)來(lái)重復(fù)利用經(jīng)常發(fā)生事件上；這些例子包括文件Cache，命名Cache等等。當(dāng)C

10、PU在Cache中找到要訪問(wèn)的數(shù)據(jù)項(xiàng)時(shí)，被稱(chēng)為一次Cache命中；當(dāng)CPU找不到所需要的數(shù)據(jù)項(xiàng)時(shí)，稱(chēng)為Cache缺失。包含所需要的字的一固定大小的數(shù)據(jù)集合被稱(chēng)為“塊”，它從內(nèi)存中獲取、并放置到Cache中。由時(shí)間局部性原理可知，我們?cè)诓痪玫膶?lái)可能會(huì)再次用到這個(gè)字，所以將它放到CPU能較快訪問(wèn)到的Cache中是很值得的。根據(jù)空間局部性，塊內(nèi)的其他數(shù)據(jù)也可能在不久的將來(lái)被訪問(wèn)。發(fā)生Cache缺失時(shí)，數(shù)據(jù)存取時(shí)間取決于存儲(chǔ)器的延遲和帶寬。延遲決定了讀取該塊第一個(gè)字的時(shí)間，而帶寬決定了讀取該塊中其他部分所需要的時(shí)間。Cache缺失通常由硬件處理，導(dǎo)致順序執(zhí)行處理器暫停或停止處理，直到所需數(shù)據(jù)可用為止

11、。類(lèi)似地，一個(gè)程序需要的所有數(shù)據(jù)并不是都駐留在內(nèi)存中。如果系統(tǒng)中包含虛擬存儲(chǔ)器，那么一些數(shù)據(jù)可以存放在磁盤(pán)中。地址空間通常分為一些固定大小的塊，稱(chēng)為“頁(yè)”。任何時(shí)候，每個(gè)頁(yè)保存在主存儲(chǔ)器或者磁盤(pán)中。當(dāng)CPU要訪問(wèn)的數(shù)據(jù)項(xiàng)既不在Cache、又不在主存儲(chǔ)器中時(shí)，則發(fā)生“頁(yè)缺失”，需要從磁盤(pán)中取出該頁(yè)并放到主存儲(chǔ)器中。頁(yè)缺失花費(fèi)的時(shí)間比較長(zhǎng)，通常由軟件來(lái)處理，這時(shí)，CPU并不停止工作，而是切換到其他任務(wù)繼續(xù)執(zhí)行。Cache與主存儲(chǔ)器的關(guān)系和主存儲(chǔ)器與磁盤(pán)的關(guān)系相同。圖5.3顯示了從高端桌面處理器到低端服務(wù)器各類(lèi)計(jì)算機(jī)系統(tǒng)中，存儲(chǔ)器層次結(jié)構(gòu)中每一級(jí)的容量大小和存取時(shí)間范圍。圖5.3大型工作站和小型服務(wù)

12、器中典型存儲(chǔ)層次結(jié)構(gòu)：距離CPU越遠(yuǎn)，存儲(chǔ)速度越慢、容量越大。嵌入式計(jì)算機(jī)可以沒(méi)有磁盤(pán)存儲(chǔ)，并且具有小得多的內(nèi)存和Cache。存取時(shí)間隨著層次結(jié)構(gòu)從高層往低層依次增加，這種結(jié)構(gòu)對(duì)不敏感數(shù)據(jù)傳輸?shù)墓芾硎呛侠淼??！皩?shí)現(xiàn)技術(shù)”一欄給出了實(shí)現(xiàn)這些功能的典型技術(shù)。存取時(shí)間給出的是在2001年典型的納秒級(jí)數(shù)據(jù)，這些時(shí)間還會(huì)進(jìn)一步減少。存儲(chǔ)層次各級(jí)間的帶寬以兆字節(jié)秒為單位。磁盤(pán)存儲(chǔ)器的帶寬包括了存儲(chǔ)介質(zhì)和緩沖區(qū)接口。Cache性能回顧根據(jù)局部性原理和小存儲(chǔ)器具有較快存取速度原理可知，存儲(chǔ)器層次結(jié)構(gòu)能從實(shí)質(zhì)上改進(jìn)計(jì)算機(jī)性能。我們可以擴(kuò)展第一章中的CPU執(zhí)行時(shí)間公式來(lái)評(píng)估Cache的性能改進(jìn)程度。我們將CPU暫

13、停工作、等待一次存儲(chǔ)器存取的周期數(shù)稱(chēng)為存儲(chǔ)器停頓周期數(shù)，性能可以表示為CPU時(shí)鐘周期數(shù)與存儲(chǔ)器停頓周期數(shù)的和，再與時(shí)鐘周期時(shí)間的乘積：等式中假定CPU時(shí)鐘周期數(shù)包含了處理Cache命中和 Cache缺失時(shí)CPU停止的時(shí)間。5.3節(jié)將會(huì)校驗(yàn)這個(gè)簡(jiǎn)化的假設(shè)。存儲(chǔ)器停頓周期數(shù)由缺失次數(shù)和每一次的缺失代價(jià)所決定：最后一種表示形式的優(yōu)點(diǎn)是每一個(gè)因子都能很容易得到。我們已經(jīng)知道如何計(jì)算執(zhí)行指令數(shù)（對(duì)于預(yù)測(cè)型 CPU，我們只計(jì)算指令計(jì)數(shù)器IC完成的指令），測(cè)定每條指令的存儲(chǔ)器訪問(wèn)次數(shù)可用同樣的方式；每條指令都需要一次取指令，并且我們很容易判斷出該指令是否會(huì)存取數(shù)據(jù)。注意，我們把缺失代價(jià)作為平均數(shù)參與計(jì)算，但

14、在后面的討論中我們將它看作是一常數(shù)。當(dāng)發(fā)生Cache缺失時(shí)，Cache下一層次的存儲(chǔ)器由于上一層存儲(chǔ)器需求和存儲(chǔ)器刷新而變得很忙碌。并且，處理器、總線和存儲(chǔ)器間接口的時(shí)鐘周期數(shù)也是不同的。因此，我們把缺失代價(jià)簡(jiǎn)化為一個(gè)數(shù)值。缺失率是Cache訪問(wèn)中產(chǎn)生缺失所占訪問(wèn)總數(shù)的百分率（也就是產(chǎn)生缺失的Cache訪問(wèn)次數(shù)除以訪問(wèn)總次數(shù)）。缺失率可以用Cache仿真器來(lái)測(cè)量：仿真器對(duì)要進(jìn)行訪問(wèn)的指令和數(shù)據(jù)進(jìn)行地址跟蹤，模擬Cache行為來(lái)判斷是命中還是缺失，并給出命中和缺失的總數(shù)。一些微處理器提供了硬件來(lái)計(jì)算缺失數(shù)和存儲(chǔ)器引用次數(shù)，這使得缺失率的計(jì)算變得更為簡(jiǎn)單和快速。讀、寫(xiě)Cache操作的缺失率和缺失代

15、價(jià)往往是不同的，因此上面的公式只是一近似公式。存儲(chǔ)器停頓周期數(shù)可以由每條指令的訪存次數(shù)、讀和寫(xiě)的缺失代價(jià)（以時(shí)鐘周期計(jì)）和缺失率來(lái)定義：可以將讀、寫(xiě)合并，計(jì)算出它們的平均缺失率和缺失代價(jià)，從而將上述公式簡(jiǎn)化為：缺失率是Cache設(shè)計(jì)最重要的因素之一，然而，在后續(xù)的章節(jié)中，我們將會(huì)看到它并不是唯一的因素。¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

16、0;¾¾¾¾¾¾¾¾¾例 假定有一臺(tái)計(jì)算機(jī)，當(dāng)所有訪存操作都能在Cache命中時(shí)，每條指令的時(shí)鐘數(shù)（CPI）為1.0。對(duì)數(shù)據(jù)存取只包含讀入和存儲(chǔ)，這些指令占全部指令的50。缺失代價(jià)為25個(gè)時(shí)鐘周期，缺失率為2，問(wèn)當(dāng)所有指令都在Cache中命中時(shí)，計(jì)算機(jī)性能提高多少？解首先計(jì)算Cache始終命中時(shí)的機(jī)器性能：再看現(xiàn)實(shí)中有Cache的操作情況，首先計(jì)算存儲(chǔ)器停頓周期數(shù)：上式中，（10.5）表示每條指令包括一條指令存取和0.5條數(shù)據(jù)存取。因此，總性能表示如下：性能比就是兩個(gè)執(zhí)行時(shí)間的比值：由此可知，不發(fā)生Cac

17、he缺失時(shí)，計(jì)算機(jī)性能提高1.75。¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾一些設(shè)計(jì)者喜歡用平均每條指令缺失次數(shù)、而不是平均每次存儲(chǔ)器存取缺失數(shù)來(lái)度量缺失率：當(dāng)知道每條指令平均訪存次數(shù)時(shí)，可以將缺失率轉(zhuǎn)換為每條指令缺失次數(shù)，因此后一

18、個(gè)公式更為有用。例如，我們可以將上例中的訪存缺失率轉(zhuǎn)換成每條指令缺失次數(shù)：通常情況下，為了讓每條指令的缺失次數(shù)表示為整數(shù)，我們一般采用每千條指令的缺失次數(shù)來(lái)計(jì)算。這樣，上面的答案也可表示成每千條指令發(fā)生缺失30次。這種度量方法的優(yōu)點(diǎn)是它獨(dú)立于硬件實(shí)現(xiàn)。例如，21264指令預(yù)取單元取到的指令條數(shù)為實(shí)際用到的2倍，如果采用每次存儲(chǔ)器存取而不是每條指令的缺失數(shù)來(lái)度量缺失率， 就會(huì)人為的降低缺失率。它的缺點(diǎn)是平均每條指令缺失數(shù)與處理器體系結(jié)構(gòu)相關(guān)：例如，平均每條指令存儲(chǔ)器存取次數(shù)，對(duì)于80X86和MIPS來(lái)說(shuō)可能是完全不同的?？偠灾M管與RISC類(lèi)似的系統(tǒng)結(jié)構(gòu)允許我們參照其他參數(shù)，在單一計(jì)算機(jī)家族

19、情況下，系統(tǒng)結(jié)構(gòu)設(shè)計(jì)師一般采用每條指令缺失次數(shù)。¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾例為表明兩個(gè)缺失率等式的相等關(guān)系，我們重新看一下上面的例子。這次假定缺失率為每千條指令缺失30次，以指令數(shù)計(jì)算的存儲(chǔ)器停頓周期是多少？解計(jì)算存儲(chǔ)

20、器停頓周期：我們得到的答案與上面相同。¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾存儲(chǔ)器層次結(jié)構(gòu)的四個(gè)問(wèn)題通過(guò)回答四個(gè)基本問(wèn)題，我們繼續(xù)對(duì)存儲(chǔ)器層次結(jié)構(gòu)第一層次Cache進(jìn)行描述。Q1：塊的放置：在較高層中，一個(gè)塊能被放置在哪里？ Q2

21、：塊的標(biāo)識(shí)：如果一個(gè)塊在較高層中，如何找到它？ Q3：塊的替換：如果沒(méi)有命中，哪個(gè)塊應(yīng)該被替換？ Q4：寫(xiě)時(shí)策略：寫(xiě)操作時(shí)會(huì)發(fā)生什么？ 對(duì)這些問(wèn)題的回答，能幫助我們理解在存儲(chǔ)器層次結(jié)構(gòu)中各層次之間的均衡方式；因此，我們對(duì)每個(gè)例子都提出這四個(gè)問(wèn)題。Q1：一個(gè)塊可以被放置到Cache的哪里？圖5.4給出了根據(jù)塊放置策略來(lái)劃分的三種Cache組織形式：n 如果每個(gè)塊在Cache中只能出現(xiàn)在唯一位置上，那么這種映射就叫做直接映射，映射方法通常是：（塊地址）MOD（Cache中的塊數(shù)）n 如果一個(gè)塊可以放到Cache中的任何一個(gè)地方，那么這種映射就叫做全相聯(lián)映射。n 如果一個(gè)塊可以放到Cache中一個(gè)受

22、限的組里，那么這種映射就被叫做組相聯(lián)映射。一個(gè)組（set）是Cache中的一組塊。一個(gè)塊首先被映射到一個(gè)組中，然后它可以被擱置到組中的任何一塊中。組通常利用位選擇方式確定，即：（塊地址）MOD（Cache中的組數(shù)）如果一個(gè)組里有n塊，那么這種映射方法就被叫做n-路組相聯(lián)。圖5.4例中Cache分成8個(gè)塊結(jié)構(gòu)，主存有32個(gè)塊。Cache的三種策略從左到右如上所示。假定Cache開(kāi)始時(shí)是空的， 而要分配的塊地址在主存中為12。在全相聯(lián)方式中，主存塊12可以進(jìn)入到Cache的8個(gè)塊中的任何一個(gè)。在直接映射方式中，主存塊12只能放到塊4處（12模8）。組相聯(lián)方式具有上述兩種方式的某些特征，允許塊被放置

23、到組0（12模4）中的任何一個(gè)位置上。因?yàn)槊拷M兩塊，所以這意味著塊12可以被放置到Cache的塊0中或塊1中。真正的Cache包括幾百個(gè)塊結(jié)構(gòu)，而真正的主存則包含了成百萬(wàn)的塊。組相聯(lián)方式有4個(gè)組、每組兩個(gè)塊，因而叫做2-路組相聯(lián)。直接映射和全相聯(lián)實(shí)際上是組相聯(lián)的兩種特殊情況：直接映射僅僅是一個(gè)簡(jiǎn)單的1路組相聯(lián)， 而一個(gè)有m塊的全相聯(lián)Cache可以被稱(chēng)作m-路組相聯(lián)；也就是說(shuō)，直接映射可以看成是有m組的組相聯(lián)映射， 而全相聯(lián)是只有1組的組相聯(lián)映射。今天的大多數(shù)處理器的Cache采用直接映射，兩路組相聯(lián)映射，或是四路組相聯(lián)映射方式。Q2：如果某一塊在Cache中，如何找到它？Cache中的每一塊結(jié)

24、構(gòu)都有一個(gè)地址標(biāo)志，從而給出塊地址。當(dāng)查找希望獲得的信息時(shí)，是通過(guò)對(duì)每一個(gè)Cache塊標(biāo)志進(jìn)行檢查，看它是否與來(lái)自CPU的塊地址相匹配來(lái)實(shí)現(xiàn)的?？紤]到速度的重要性，所有可能的標(biāo)志都要被并行檢查。必須要有一種方法來(lái)確定一個(gè)塊中是否包含有效信息。最普通的方法是在標(biāo)志中加上一個(gè)有效位，來(lái)表明該條目（entry）是否包含有效地址。如果這個(gè)位沒(méi)有設(shè)置，則該地址不能進(jìn)行匹配。在繼續(xù)下一個(gè)問(wèn)題之前，我們先來(lái)看一下CPU地址同Cache地址間的關(guān)系。圖5.5給出了Cache地址的劃分情況：第一個(gè)劃分是在塊地址和塊內(nèi)偏移之間作出的；塊地址可以進(jìn)一步細(xì)分成標(biāo)志域和索引域。塊內(nèi)地址偏移用來(lái)從塊中選出需要的數(shù)據(jù)，索引

25、域用來(lái)選擇組，通過(guò)比較標(biāo)志域來(lái)判斷是否發(fā)生命中。判斷是否命中時(shí)，沒(méi)有必要對(duì)除標(biāo)志域以外的更多地址位進(jìn)行比較， 原因如下：n 塊內(nèi)偏移是沒(méi)有必要比較的，這是因?yàn)镃ache命中與否的單位是整個(gè)塊，因此所有塊內(nèi)的地址偏移將會(huì)是匹配的。n 由于索引域是用來(lái)選擇被檢查的組， 所以對(duì)索引域的比較是多余的。例如，一個(gè)地址存儲(chǔ)在組0中，則在索引域中必然包含0， 否則不可能被存儲(chǔ)在組0中；組1一定有索引值1；依次類(lèi)推。這種優(yōu)化通過(guò)減少Cache標(biāo)志域長(zhǎng)度來(lái)節(jié)省了硬件開(kāi)銷(xiāo)和功耗。圖5.5組相聯(lián)或直接映射中地址的三個(gè)部分。標(biāo)志域用來(lái)檢查組中的所有塊，而索引域用來(lái)選擇組。塊內(nèi)地址偏移是塊內(nèi)期望數(shù)據(jù)的地址。全相聯(lián)映射沒(méi)

26、有索引域。如果Cache的大小一定，增加相聯(lián)度將增加每一個(gè)組中的塊數(shù)，因而減少了索引域的寬度，但是增加了標(biāo)志域的寬度。也就是說(shuō)，圖5.5中的標(biāo)志索引界限將根據(jù)增加的相聯(lián)度向右移動(dòng)，最后如果變成全相聯(lián)的話，將不存在索引域。Q3：如果沒(méi)有命中，哪個(gè)塊應(yīng)該被替換？當(dāng)缺失發(fā)生時(shí)，Cache控制器必須選擇Cache中的一個(gè)塊，并用期望獲得的數(shù)據(jù)塊來(lái)替換它。使用直接映射替換方法的優(yōu)點(diǎn)是硬件決策簡(jiǎn)單事實(shí)上，它根本不需要任何選擇：只檢查一個(gè)塊結(jié)構(gòu)是否命中，當(dāng)不命中時(shí)，也只有這個(gè)塊可以用于替換。如果是全相聯(lián)或是組相聯(lián)，則發(fā)生缺失時(shí)就要從多塊中作出適當(dāng)?shù)倪x擇。有三種基本的塊替換策略：n 隨機(jī)替換策略為了均勻地分配

27、，候選塊將被隨機(jī)選擇。一些系統(tǒng)產(chǎn)生偽隨機(jī)數(shù)塊號(hào)，以獲得可重復(fù)的行為，當(dāng)調(diào)試硬件時(shí)，這種方式尤其有用的。n 最近最少使用（LRU）替換策略為了減少替換那些可能不久就要用到信息的機(jī)率，需要記錄塊的訪問(wèn)次數(shù)。利用歷史信息來(lái)預(yù)測(cè)未來(lái)使用情況，被替換的塊將是最長(zhǎng)時(shí)間內(nèi)沒(méi)有被訪問(wèn)的Cache塊。LRU使用了一個(gè)局部性原理的推論：如果一個(gè)最近被使用的塊很可能會(huì)被再次訪問(wèn)，那么最佳替換塊將是最近最少使用的塊。n 先進(jìn)先出（FIFO）替換策略由于計(jì)算LRU比較復(fù)雜，該替換策略將最早進(jìn)入Cache的塊作為替換塊。隨機(jī)替換的優(yōu)點(diǎn)是硬件簡(jiǎn)單。當(dāng)跟蹤的塊數(shù)增加時(shí)，LRU硬件也隨之變得更為復(fù)雜， 而且通常僅僅是近似的。圖

28、5.6給出了LRU、隨機(jī)和先進(jìn)先出三種替換策略在缺失率上的差別。圖5.6最近最少使用、隨機(jī)和先進(jìn)先出三種替換策略，在不同Cache大小和相聯(lián)度情況下，每千條指令缺失率比較。這些數(shù)據(jù)是在Alpha系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)中，通過(guò)運(yùn)行十個(gè)SPEC2000基準(zhǔn)測(cè)試程序得到的，Cache塊大小為64 字節(jié)。在十個(gè)基準(zhǔn)測(cè)試程序中，5個(gè)來(lái)自于SPECint2000（gap，gcc，gzip，mcf，perl），另外5個(gè)來(lái)自于SPECfp2000（applu，art，equake， lucas，swim）。這里，對(duì)于大容量Cache，LRU和隨機(jī)替換幾乎沒(méi)有差別；對(duì)于小容量Cache，LRU替換策略最優(yōu)，先進(jìn)先出（F

29、IFO）算法要比隨機(jī)算法性能略好一些。在本章后面的大多數(shù)圖表中，我們都會(huì)以這個(gè)計(jì)算機(jī)系統(tǒng)和這些基準(zhǔn)測(cè)試程序?yàn)槔齺?lái)說(shuō)明。Q4：寫(xiě)操作時(shí)會(huì)發(fā)生什么？讀操作決定著處理器Cache的訪問(wèn)次數(shù)。所有的指令都是通過(guò)讀操作來(lái)獲得的，而且大部分指令并不進(jìn)行存儲(chǔ)器寫(xiě)操作。第二章中圖2.32給出了一個(gè)包含了10存儲(chǔ)指令和37 加載指令的MIPS的混合程序所產(chǎn)生的寫(xiě)操作，占全部存儲(chǔ)器通訊量的10（100+37+10），即大約7；而占數(shù)據(jù)Cache的通訊量的10（37+10），即大約21。這樣，加快經(jīng)常性事件速度就意味著要優(yōu)化讀Cache的時(shí)間，尤其是對(duì)傳統(tǒng)處理器，它們需要等待讀操作完成、但是卻不必等待寫(xiě)操作完成就可

30、以進(jìn)行其他操作。然而，Amdahl定律（1.6節(jié)）提醒我們高性能的設(shè)計(jì)不能忽視寫(xiě)速度對(duì)系統(tǒng)性能的影響。幸運(yùn)的是，讀操作也是很容易提高速度的。塊可以在標(biāo)志位讀和比較的同時(shí)被讀出，所以讀塊操作是在獲得塊地址的同時(shí)就開(kāi)始了。如果讀命中，塊中所需信息立刻被傳送到CPU。如果沒(méi)有命中，這樣做雖然沒(méi)有得到好處但是在桌面機(jī)和服務(wù)器中，這也沒(méi)有什么壞處， 只需把讀到的信息丟棄即可。而在嵌入式系統(tǒng)中，降低功耗的前提要求避免進(jìn)行無(wú)用工作，因而設(shè)計(jì)者通常是把讀取數(shù)據(jù)和地址檢查分開(kāi)，使得發(fā)生缺失時(shí)數(shù)據(jù)不被讀取。對(duì)于寫(xiě)操作來(lái)說(shuō)，這樣的優(yōu)化卻不適用。只有標(biāo)志位有效而且地址命中時(shí)，塊才能被修改。因?yàn)闃?biāo)志位檢查不能與寫(xiě)數(shù)據(jù)并

31、行進(jìn)行，寫(xiě)操作通常要比讀操作需要更長(zhǎng)的時(shí)間。另一個(gè)復(fù)雜情況是處理器必須給出要寫(xiě)數(shù)據(jù)的大小，通常在1到8字節(jié)之間；只有塊中的這一部分可以被改變。與寫(xiě)操作不同，讀操作可以讀取比所需字節(jié)數(shù)更多的信息；同樣，嵌入式系統(tǒng)設(shè)計(jì)者要權(quán)衡少讀信息所帶來(lái)的功耗收益。寫(xiě)策略通?？梢杂糜趨^(qū)分Cache設(shè)計(jì)。通常有兩種基本策略用來(lái)寫(xiě)Cache：l 寫(xiě)通過(guò)（write through）信息被同時(shí)寫(xiě)到了Cache塊和更低一層存儲(chǔ)器的塊中。l 寫(xiě)回法（write back）信息只被寫(xiě)入Cache塊。只有Cache中該塊被替換出去時(shí)，信息才會(huì)被寫(xiě)回到主存中。為了減少替換時(shí)塊的寫(xiě)回頻率，通常需要使用一個(gè)叫做重寫(xiě)位（dirty

32、bit）的特征信息位。這個(gè)特征位表明一個(gè)塊是臟的（在Cache中被修改）還是干凈的（在Cache中沒(méi)有被修改）。如果它是干凈的，在發(fā)生缺失需替換該塊時(shí)，因?yàn)橄聦哟鎯?chǔ)器同Cache包含有相同的信息，該塊不必寫(xiě)回。寫(xiě)回法和寫(xiě)通過(guò)法各有優(yōu)點(diǎn)。在寫(xiě)回法中，寫(xiě)操作和Cache存儲(chǔ)器的速度是一致的，而且對(duì)同一個(gè)塊中的多次寫(xiě)入僅僅需要對(duì)下層存儲(chǔ)器一次寫(xiě)操作。因此，寫(xiě)回法需要較小的存儲(chǔ)帶寬，這種方法在多處理器的服務(wù)器系統(tǒng)中更具有吸引力。相對(duì)于寫(xiě)通過(guò)法，寫(xiě)回法對(duì)其他存儲(chǔ)器層次和存儲(chǔ)總線的使用較少，節(jié)省了功耗，因而很受嵌入式應(yīng)用程序的青睞。寫(xiě)通過(guò)法比寫(xiě)回法更易實(shí)現(xiàn)。在寫(xiě)通過(guò)法中，當(dāng)讀操作發(fā)生缺失時(shí)，由于Cache

33、始終是干凈的，因此不必對(duì)較低層存儲(chǔ)器進(jìn)行寫(xiě)操作。寫(xiě)通過(guò)法還可以保證低層存儲(chǔ)器有當(dāng)前最新數(shù)據(jù)的副本，這簡(jiǎn)化了數(shù)據(jù)一致性問(wèn)題。數(shù)據(jù)一致性（見(jiàn)5.12節(jié)）對(duì)于多處理器系統(tǒng)和IO系統(tǒng)是很重要的，我們將會(huì)在第6章和第7章中進(jìn)一步討論。正如我們將要看到的，IO系統(tǒng)和多處理器系統(tǒng)是反復(fù)無(wú)常的：它們希望處理器Cache利用寫(xiě)回法來(lái)減少存取通訊量，同時(shí)也希望利用寫(xiě)通過(guò)法來(lái)保證存儲(chǔ)器層次結(jié)構(gòu)中Cache和低層存儲(chǔ)器數(shù)據(jù)的一致性。在寫(xiě)通過(guò)法中， 如果CPU的操作必須等待寫(xiě)操作完成才能進(jìn)行時(shí)，這種CPU被稱(chēng)做是寫(xiě)停頓（write stall）的。通常用來(lái)減少寫(xiě)停頓的優(yōu)化策略是寫(xiě)緩存技術(shù)，它允許處理器把數(shù)據(jù)寫(xiě)入到緩沖區(qū)

34、之后立刻繼續(xù)工作，因此使處理器執(zhí)行時(shí)間和存儲(chǔ)器更新時(shí)間重疊。我們將會(huì)看到，即使是利用寫(xiě)緩存技術(shù)，寫(xiě)停頓仍然可能發(fā)生。因?yàn)樵趯?xiě)操作時(shí)并不需要數(shù)據(jù)，因而在寫(xiě)缺失時(shí)有兩種通常策略：n 寫(xiě)分配（write allocate） 在發(fā)生寫(xiě)缺失時(shí)，主存的塊被讀到Cache中，然后執(zhí)行前面寫(xiě)命中時(shí)的操作。與讀缺失類(lèi)似。n 非寫(xiě)分配（no-write allocate） 僅修改低層存儲(chǔ)器中的該塊，而不將該塊取到Cache中，因而寫(xiě)缺失不影響Cache內(nèi)容。在非寫(xiě)分配中，直到程序要讀一個(gè)塊時(shí)，該塊才被存取到Cache中；而在寫(xiě)分配中，只要被寫(xiě)的塊就會(huì)保存在Cache中。讓我們看一個(gè)例子。¾¾&

35、#190;¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾例有一全相聯(lián)映射的Cache，采用寫(xiě)回策略，剛開(kāi)始時(shí)Cache為空。有下面5個(gè)存儲(chǔ)器操作（方括號(hào)中為地址）：WriteMem100;WriteMem100;ReadMem 200;WriteMem200;WriteMe

36、m100;分別求寫(xiě)分配和非寫(xiě)分配下命中次數(shù)、缺失次數(shù)是多少？解先看非寫(xiě)分配的情況：地址為100號(hào)的單元不在Cache中，而Cache對(duì)寫(xiě)操作不產(chǎn)生分配，所以前面2個(gè)寫(xiě)操作是缺失的。200號(hào)單元也不在Cache中，讀操作缺失，但是該單元所在的塊已被取到Cache中，故第四條讀操作命中。最后一條寫(xiě)100號(hào)單元操作仍然發(fā)生缺失。非寫(xiě)分配的最終結(jié)果是4次缺失和1次命中。寫(xiě)分配的情況：對(duì)100號(hào)單元和200號(hào)單元第一次操作都發(fā)生缺失，其所在的塊同時(shí)被讀到Cache中，故剩下的操作都是命中的。故寫(xiě)分配結(jié)果為總共有2次缺失和3次命中。¾¾¾¾¾¾&

37、#190;¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾雖然任何一種寫(xiě)缺失策略都可以被應(yīng)用到寫(xiě)回法或?qū)懲ㄟ^(guò)法中，但是采用寫(xiě)回法Cache通常利用寫(xiě)分配（期望對(duì)該塊的接下來(lái)的寫(xiě)操作能夠在Cache中命中）策略， 而寫(xiě)通過(guò)法經(jīng)常與非寫(xiě)分配（因?yàn)閷?duì)該塊的接下來(lái)的寫(xiě)操作仍必須寫(xiě)入到下層存儲(chǔ)器中去，所以采用寫(xiě)分配并不能獲得額外的收

38、益）策略配合使用。一個(gè)例子：Alpha 21264中數(shù)據(jù)Cache為了說(shuō)明這些思想， 圖5.7給出了Compaq AlphaServer ES40的Alpha 21264處理器中數(shù)據(jù)Cache的組織結(jié)構(gòu)。該數(shù)據(jù)Cache容量為65536(64K)個(gè)字節(jié)，塊大小為64字節(jié)，使用2-路組相聯(lián)映射方式，寫(xiě)回法，在寫(xiě)缺失時(shí)使用寫(xiě)分配策略。圖5.7Alpha 21264微處理器中數(shù)據(jù)Cache的組織結(jié)構(gòu)。64KB的Cache使用64字節(jié)塊、采用2路組相聯(lián)映射，利用9位索引可以對(duì)512個(gè)組進(jìn)行選擇。讀命中的四個(gè)步驟以圈起來(lái)的數(shù)字顯示，按照發(fā)生的次序標(biāo)明了組織順序。塊內(nèi)地址偏移的3位放到索引域中，提供給RA

39、M地址以選擇正確的8個(gè)字節(jié)。這樣，Cache被劃分成2路、每路4096個(gè)長(zhǎng)度為64位的字，每路包括5122256個(gè)組。當(dāng)Cache缺失時(shí)，從存儲(chǔ)器調(diào)入一行來(lái)給Cache加載數(shù)據(jù)。由于是物理地址不是虛地址，CPU發(fā)出的地址長(zhǎng)度為44位。圖5.36給出了Cache訪問(wèn)時(shí)，虛擬地址到物理地址的映射關(guān)系。在圖5.7中，可以根據(jù)標(biāo)識(shí)的步驟順序來(lái)跟蹤一次Cache命中過(guò)程（四個(gè)步驟由圓圈中的數(shù)字表示）。我們會(huì)在圖5.36中看到，21264微處理器在Cache中使用48位的虛擬地址來(lái)做標(biāo)志比較，同時(shí)將其轉(zhuǎn)化為44位的物理地址（也可以選擇支持43位虛地址和41位物理地址模式）。Alpha沒(méi)有用上全部64位虛地

40、址的原因，是它的設(shè)計(jì)者們認(rèn)為現(xiàn)在還不會(huì)用到那么大的虛擬地址空間，同時(shí)，減少地址位數(shù)簡(jiǎn)化了Alpha的虛地址映射設(shè)計(jì)。Alpha的設(shè)計(jì)者計(jì)劃在以后的微處理器中增加虛擬地址空間。進(jìn)入Cache的物理地址被分為兩個(gè)域：38位塊地址和6位塊內(nèi)地址偏移（64=26，38+6=44）。塊地址被進(jìn)一步分為地址標(biāo)志域和Cache索引域。步驟1顯示了這個(gè)劃分。Cache索引域用于確定哪一個(gè)標(biāo)志將被檢驗(yàn)，將該標(biāo)記與CPU發(fā)出的訪存地址中的標(biāo)志進(jìn)行比較，以判斷要訪問(wèn)的塊是否在Cache中。索引域的寬度依賴(lài)于Cache的大小，塊大小，以及組相聯(lián)度。21264的Cache的組相聯(lián)度為2，索引域?qū)挾鹊挠?jì)算如下：因此索引域

41、寬度為9，而標(biāo)志域?qū)挾葹?8-929位。我們知道為得到正確的塊，需要比較索引域，但64字節(jié)相對(duì)于CPU的一次處理能力顯得太大了，因此，又將Cache存儲(chǔ)器的數(shù)據(jù)部分劃分成若干個(gè)8字節(jié)（64位Alpha處理機(jī)的一次處理長(zhǎng)度）。因此，用索引域的9位來(lái)選擇正確的Cache塊，再用塊內(nèi)偏移地址域中的3位來(lái)確定需要的8字節(jié)。圖5.7中的步驟2表示的是由索引選擇標(biāo)志的過(guò)程。通過(guò)比較2個(gè)標(biāo)志域，選擇正確的那一個(gè)（21264的虛地址轉(zhuǎn)化過(guò)程參見(jiàn)5.10小節(jié)）。從Cache中讀出標(biāo)志之后，它被用來(lái)同從CPU發(fā)來(lái)的塊地址中標(biāo)志域部分進(jìn)行比較。這是圖中的第3步。為了保證標(biāo)志域中包含有效的信息，必須要設(shè)置有效位，否則

42、比較的結(jié)果將被忽略。假定有一個(gè)標(biāo)志域匹配，則最后一步是通知CPU根據(jù)2選1多路選擇器的有效輸出從Cache中加載正確數(shù)據(jù)。21264允許在3個(gè)時(shí)鐘周期內(nèi)完成這四個(gè)步驟，所以如果在隨后兩個(gè)時(shí)鐘周期內(nèi)的指令要使用這些數(shù)據(jù)的話，那么它們需要等待加載數(shù)據(jù)完成。在21264中，寫(xiě)操作的處理比讀操作的處理更為復(fù)雜，這同任何Cache的情況是一致的。如果要寫(xiě)的字已經(jīng)在Cache中，頭三個(gè)步驟都是一樣的。由于21264是亂序執(zhí)行的，只有等到指令提交并且Cache標(biāo)志檢驗(yàn)結(jié)果是命中時(shí)，數(shù)據(jù)才被寫(xiě)到Cache中。迄今為止，我們假定的是Cache命中時(shí)的情況。如果缺失會(huì)發(fā)生什么情況呢？如果讀操作缺失，Cache就向

43、CPU發(fā)出一個(gè)要其等待的停頓信號(hào)，然后從層次結(jié)構(gòu)的下一級(jí)中讀出64個(gè)字節(jié)。21264中到較低級(jí)的通路的寬度是16個(gè)字節(jié)。在667MHz AlphaServer Es40中，每一次傳送要用2.25納秒，全部64個(gè)字節(jié)要用9納秒。因?yàn)閿?shù)據(jù)Cache是組相聯(lián)映射的，還涉及到替換塊的選擇問(wèn)題。21264采用循環(huán)法（round-robin），也叫先進(jìn)先出法（FIFO）.每?jī)蓚€(gè)塊之間需要有一標(biāo)志位來(lái)記錄下一次將被替換出局的塊。與LRU法選擇最近最少使用的那一塊不同，循環(huán)法選擇最早進(jìn)入Cache的那一塊，并且只在缺失時(shí)更新標(biāo)志位，而不是每次命中時(shí)更新，因而比LRU容易實(shí)現(xiàn)。替換一個(gè)塊意味著要更新數(shù)據(jù)、地址標(biāo)

44、志域、有效位以及循環(huán)位。21264采用寫(xiě)回法，一個(gè)被替換掉的塊可能已經(jīng)被修改，因此不能簡(jiǎn)單地將其丟棄。21264使用重寫(xiě)位記錄該塊是否曾經(jīng)被修改。如果已經(jīng)被修改，則將該塊的數(shù)據(jù)和地址送至犧牲者緩沖區(qū)（victim buffer，結(jié)構(gòu)與其它系統(tǒng)的寫(xiě)緩沖區(qū)類(lèi)似）。21264的犧牲者緩沖區(qū)最多能存8個(gè)塊，當(dāng)它將替換出來(lái)的塊寫(xiě)回低一級(jí)存儲(chǔ)器時(shí)，可與Cache操作并行執(zhí)行。如果犧牲者緩沖區(qū)已滿，Cache就必須停下來(lái)等待。21264采用寫(xiě)分配法，為讀缺失或?qū)懭笔Ф挤峙湟粋€(gè)Cache塊，故寫(xiě)缺失與讀缺失操作相類(lèi)似。我們已經(jīng)看到了數(shù)據(jù)Cache是如何工作的，但是它并不能支持處理器所有的訪存請(qǐng)求：處理器還需要

45、處理指令。雖然單獨(dú)的一個(gè)Cache能夠盡力既提供指令又提供數(shù)據(jù)給處理器，但那會(huì)成為一個(gè)瓶頸。例如，當(dāng)執(zhí)行一條取指令（load）或存指令（store）時(shí)，指令流水的處理器會(huì)同時(shí)進(jìn)行一個(gè)數(shù)據(jù)字訪存和一個(gè)指令字訪存。因此，單獨(dú)的Cache會(huì)在取或存操作時(shí)有結(jié)構(gòu)沖突，會(huì)產(chǎn)生停頓。解決這個(gè)問(wèn)題的一個(gè)簡(jiǎn)單方法是把它劃分成指令Cache和數(shù)據(jù)Cache。分離的Cache技術(shù)已被應(yīng)用到現(xiàn)代處理器中，包括Alpha 21264，它包含一個(gè)64K字節(jié)的指令Cache和一個(gè)64K字節(jié)的數(shù)據(jù)Cache。CPU知道它發(fā)出的是指令地址還是數(shù)據(jù)地址，所以可以為兩者設(shè)立分立的端口，因此CPU和存儲(chǔ)器層次結(jié)構(gòu)間的帶寬得以加倍。

46、指令Cache和數(shù)據(jù)Cache的分立也為各自進(jìn)行獨(dú)立的優(yōu)化提供了機(jī)會(huì)：不同的容量、塊大小以及相聯(lián)度可以獲得更好的性能。與21264的指令Cache和數(shù)據(jù)Cache相對(duì)應(yīng)，術(shù)語(yǔ)“一體（unified）”或“混合(mixed)”表示既包含指令Cache又包含數(shù)據(jù)的Cache。圖5.8顯示了指令Cache比數(shù)據(jù)Cache有更低的缺失率。通過(guò)指令Cache和數(shù)據(jù)Cache分立，能夠消除因指令和數(shù)據(jù)沖突而引起的缺失，但是分立也限定了兩種Cache各自的大小。究竟哪一個(gè)方面對(duì)缺失率影響更大呢？分立的指令和數(shù)據(jù)Cache同一體Cache之間合理的比較應(yīng)該是Cache總?cè)萘肯嗤?。例如，一個(gè)分立的16K的指令C

47、ache和16K的數(shù)據(jù)Cache應(yīng)該同32K的一體Cache相比較。計(jì)算分立Cache的平均缺失率必須要知道對(duì)指令Cache和數(shù)據(jù)Cache各自的訪問(wèn)頻率。圖2.32表明采用分立Cache時(shí)，對(duì)指令Cache的訪問(wèn)頻率是100（100+26+10）即74，對(duì)數(shù)據(jù)Cache的訪問(wèn)頻率是（26+10）（100+26+10）即26。正如我們將會(huì)看到的，分立Cache對(duì)性能的影響超出了缺失率變化所帶來(lái)的影響。圖5.8不同容量指令Cache、數(shù)據(jù)Cache以及一體Cache的每千條指令缺失率。指令訪問(wèn)頻率大約是74。數(shù)據(jù)Cache塊大小是64字節(jié)，采用2-路組相聯(lián)映射方式。結(jié)果是通過(guò)在與圖5.6相同的系

48、統(tǒng)上運(yùn)行相同的測(cè)試程序獲得。5.3Cache性能因?yàn)橹噶顢?shù)是獨(dú)立于硬件的，所以可以用來(lái)評(píng)價(jià)CPU的性能。然而，正如第一章所見(jiàn)，這些非直接的性能評(píng)價(jià)方法困擾了很多計(jì)算機(jī)設(shè)計(jì)者。存儲(chǔ)器層次結(jié)構(gòu)性能的評(píng)價(jià)方法主要是利用了缺失率，因?yàn)樗彩仟?dú)立于硬件速度的。我們將會(huì)看到，缺失率同指令數(shù)一樣，也會(huì)產(chǎn)生誤導(dǎo)。更好的對(duì)存儲(chǔ)器層次結(jié)構(gòu)的評(píng)價(jià)方法利用了平均存儲(chǔ)器存取時(shí)間：這里的命中時(shí)間（Hit time）是Cache命中時(shí)所需要的時(shí)間；另外兩個(gè)術(shù)語(yǔ)在前面已看到過(guò)。平均存取時(shí)間的單位可以采用絕對(duì)時(shí)間如一次命中需0.25-1.0納秒或是用CPU等待存儲(chǔ)器的時(shí)鐘周期數(shù)如缺失代價(jià)用75-100個(gè)時(shí)鐘周期表示。注意，平均

49、存儲(chǔ)器存取時(shí)間仍然是一個(gè)間接的性能評(píng)價(jià)方法；雖然它比用缺失率更好，它不能代替執(zhí)行時(shí)間。這個(gè)公式能夠幫助我們?cè)诜至ache和一體Cache間作出抉擇。¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾例一個(gè)16K指令Cache和16K數(shù)據(jù)Ca

50、che與一個(gè)32K的一體Cache相比較，哪一個(gè)具有更低的缺失率？假設(shè)36的存儲(chǔ)器訪問(wèn)是數(shù)據(jù)訪問(wèn)，使用圖5.8中的缺失率來(lái)計(jì)算正確的結(jié)果。假定Cache命中需要1個(gè)時(shí)鐘周期，缺失代價(jià)是100個(gè)時(shí)鐘周期，在一體Cache 中，Load和Store命中額外需要一個(gè)時(shí)鐘周期，因?yàn)橹挥幸粋€(gè)Cache端口來(lái)滿足這兩個(gè)同時(shí)發(fā)生的請(qǐng)求。使用上一章提到流水線的術(shù)語(yǔ)，一體Cache導(dǎo)致結(jié)構(gòu)沖突。每種情況下的平均存儲(chǔ)器存取時(shí)間是多少呢？假定是帶有寫(xiě)緩存的寫(xiě)通過(guò)Cache，而且寫(xiě)緩存的停頓時(shí)間可以忽略不記。解先將每1000條指令的缺失次數(shù)轉(zhuǎn)化為缺失率：一條指令只進(jìn)行一次取指令的訪存操作，故指令的缺失率為：由題目的假

51、設(shè)可知36的指令是數(shù)據(jù)操作指令，故數(shù)據(jù)缺失率為：一體Cache的缺失率要包括指令和數(shù)據(jù)的缺失率：如上所述，大約74的存儲(chǔ)器訪問(wèn)是訪問(wèn)指令的。因此，分立Cache的總的缺失率為：因此，32K的一體Cache有相對(duì)稍低的缺失率。平均存儲(chǔ)器存取時(shí)間公式可以分為指令和數(shù)據(jù)的訪問(wèn)：所以，兩種Cache結(jié)構(gòu)的平均存儲(chǔ)器存取時(shí)間如下：因此，本例中分立Cache在每個(gè)時(shí)鐘周期提供兩個(gè)存儲(chǔ)器端口，因此可以避免結(jié)構(gòu)沖突比只有一個(gè)端口的一體Cache有更好的平均存儲(chǔ)器存取時(shí)間，盡管它的有效缺失率更高一些。¾¾¾¾¾¾¾¾¾&#

52、190;¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾平均存儲(chǔ)器存取時(shí)間和處理器性能由上面的討論，讀者可能會(huì)問(wèn)：是否可以從Cache缺失引起的平均存儲(chǔ)器存取時(shí)間來(lái)預(yù)測(cè)處理器性能呢？首先，還有其它原因可以引起停頓，例如由于IO設(shè)備使用存儲(chǔ)器引起的競(jìng)爭(zhēng)。對(duì)不同Cache方案的評(píng)價(jià)，設(shè)計(jì)者常常假定所有的存儲(chǔ)器停頓是由于Cache缺失引起的，這是因?yàn)榇鎯?chǔ)器層次結(jié)構(gòu)

53、相對(duì)于其他原因?qū)μ幚砥魍ｎD起支配作用。我們這里也使用這個(gè)簡(jiǎn)化假定，但是在最后的性能評(píng)價(jià)時(shí)，對(duì)所有的存儲(chǔ)器停頓作出解釋是至關(guān)重要的！由前一節(jié)敘述，CPU時(shí)間可用下面的公式計(jì)算：這個(gè)CPU時(shí)間公式產(chǎn)生了這樣一個(gè)問(wèn)題，Cache命中的時(shí)鐘周期數(shù)是否應(yīng)該被認(rèn)為是CPU執(zhí)行時(shí)鐘周期數(shù)，還是存儲(chǔ)器停頓時(shí)鐘周期數(shù)的一部分呢？雖然兩種觀點(diǎn)都是有道理的，但是一般的觀點(diǎn)還是把命中時(shí)鐘周期數(shù)包含進(jìn)CPU執(zhí)行時(shí)鐘周期數(shù)中?，F(xiàn)在我們可以研究一下Cache對(duì)CPU性能的影響。¾¾¾¾¾¾¾¾¾¾¾¾&#

54、190;¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾例我們使用一個(gè)與UltraSPARC (見(jiàn)5.15節(jié))類(lèi)似、順序執(zhí)行的計(jì)算機(jī)來(lái)作為第一個(gè)例子。假定Cache缺失代價(jià)是100個(gè)時(shí)鐘周期，而且所有指令是用1.0個(gè)時(shí)鐘周期完成（忽略存儲(chǔ)器停頓）。假定平均缺失率是2，平均每條指令要訪問(wèn)存儲(chǔ)器1.5次，每1000條指令平均Cache缺失次數(shù)為30。當(dāng)考慮Cache行為時(shí)，對(duì)性能會(huì)有什么影響呢？分

55、別用缺失率和每條指令缺失次數(shù)計(jì)算Cache對(duì)計(jì)算機(jī)性能的影響。解考慮到Cache缺失時(shí)的性能為：用缺失率計(jì)算的性能為： 無(wú)論是否考慮到Cache缺失，時(shí)鐘周期時(shí)間和指令計(jì)數(shù)是同樣的，CPI從1.0(理想情況下， 不考慮Cache缺失)增加到4.00(考慮Cache缺失)，從而導(dǎo)致CPU時(shí)間增加4倍。如果不采用存儲(chǔ)器層次結(jié)構(gòu)，CPI將會(huì)增加到1.0+1001.5或者151倍，這幾乎是帶有CACHE的系統(tǒng)的40倍。¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

56、90;¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾正如本例中所指出的，Cache的行為將會(huì)極大地影響到CPU的性能。進(jìn)一步地說(shuō)，Cache缺失會(huì)對(duì)具有較低和較快時(shí)鐘CPU有雙重阻礙作用：1越低，一定的Cache缺失時(shí)鐘數(shù)對(duì)CPU時(shí)間的相對(duì)影響越大。2在計(jì)算CPI時(shí)（考慮Cache缺失情況），Cache缺失代價(jià)用缺失時(shí)花費(fèi)的CPU時(shí)鐘周期數(shù)來(lái)度量。因此，即使兩臺(tái)計(jì)算機(jī)的存儲(chǔ)器層次結(jié)構(gòu)相同，對(duì)于時(shí)鐘頻率較高的CPU，每次缺失會(huì)需

57、要較多的時(shí)鐘周期數(shù)，因此花費(fèi)在存儲(chǔ)器部分的CPI較高。Cache對(duì)于具有低CPI和高時(shí)鐘頻率CPU的性能影響顯得更為重要，因此，在評(píng)價(jià)這種計(jì)算機(jī)性能時(shí)，如果忽略Cache的行為也就更為危險(xiǎn)。Amdahl定律又一次應(yīng)驗(yàn)了！雖然追求最小平均存儲(chǔ)器存取時(shí)間是一個(gè)合理的目標(biāo)，而且我們?cè)诒菊轮械拇蟛糠謱?huì)用到它，但是要注意最終目標(biāo)是降低CPU執(zhí)行時(shí)間。下一個(gè)例子將表明這兩者是有所區(qū)別的。¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾&#

58、190;¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾例兩種不同的Cache的組織形式究竟對(duì)CPU的性能有什么樣的影響呢？假定Cache為理想狀態(tài)時(shí)，CPI為2.0，時(shí)鐘周期時(shí)間為1.0ns，平均每條指令需要存儲(chǔ)訪問(wèn)1.5次，而且兩個(gè)Cache的容量都是64K字節(jié)，塊容量都為64字節(jié)。一個(gè)Cache采用直接映射方式，另一個(gè)采用2-路組相聯(lián)映射方式。圖5.7表示了對(duì)于組相聯(lián)的Cache，我們必須增加一個(gè)多路選擇器用于根據(jù)標(biāo)志匹配從某一組中選擇出所需的塊。因?yàn)镃PU

59、速度是同Cache命中時(shí)的速度直接相關(guān)的，所以假定CPU的時(shí)鐘周期時(shí)間必須擴(kuò)展1.25倍才能與組相聯(lián)Cache的多路選擇時(shí)間相適應(yīng)。第一個(gè)近似假設(shè)：Cache的缺失代價(jià)對(duì)于每種Cache組織形式都是75ns（實(shí)際上，它必定為時(shí)鐘周期的整數(shù)倍）。首先，計(jì)算平均存儲(chǔ)器存取時(shí)間，然后計(jì)算CPU的性能。假定命中時(shí)間是1個(gè)時(shí)鐘周期，并假定采用直接映射、容量為64K字節(jié)的 Cache缺失率為1.4，而同樣大小的采用2-路組相聯(lián)映射的Cache缺失率為1.0。解因此對(duì)于每一種組織形式來(lái)說(shuō)：所以2-路組相聯(lián)的存儲(chǔ)器存取時(shí)間性能更好。CPU性能為：用75納秒替換乘式（），則采用不同Cache組織形式的CPU 性

60、能為：相對(duì)性能為：與平均存儲(chǔ)器存取時(shí)間的比較結(jié)果相反，直接映射Cache的平均性能稍微好一些，這是因?yàn)樵?-路組相聯(lián)情況下，盡管它的缺失率低一些，但是所有指令時(shí)鐘周期都延長(zhǎng)了。由于CPU時(shí)間是我們基本評(píng)估標(biāo)準(zhǔn)，而且直接映射更容易構(gòu)建，所以在這個(gè)例子中直接映射的Cache是更好的選擇。¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾&#

61、190;¾¾¾¾¾¾¾缺失代價(jià)和亂序執(zhí)行處理機(jī)對(duì)于一個(gè)亂序執(zhí)行處理機(jī)，如何定義它的缺失代價(jià)呢？是存儲(chǔ)器缺失的全部延遲時(shí)間，還是處理器必須停頓的“暴露時(shí)間”或不重疊的延遲時(shí)間？這個(gè)問(wèn)題在數(shù)據(jù)缺失完成之前采用停頓處理的處理器中是不存在的。我們可以重新定義存儲(chǔ)器停頓周期，以得到不重疊延遲時(shí)間表示的缺失代價(jià)定義：類(lèi)似的，由于一些亂序執(zhí)行CPU延長(zhǎng)了命中時(shí)間，性能方程式的一部分內(nèi)容由全部缺失延遲減去重疊缺失延遲的差值代替?？紤]到亂序執(zhí)行CPU中的存儲(chǔ)器資源競(jìng)爭(zhēng)，該方程式能進(jìn)一步擴(kuò)展，將全部缺失延遲劃分成沒(méi)有競(jìng)爭(zhēng)時(shí)的延遲和有競(jìng)爭(zhēng)時(shí)的延遲

62、。我們只關(guān)心缺失延遲。我們需要決定下面兩個(gè)問(wèn)題：n 存儲(chǔ)器延遲長(zhǎng)度 在亂序處理機(jī)中，什么是存儲(chǔ)器操作的開(kāi)始和結(jié)束？n 延遲重疊長(zhǎng)度 什么是與處理機(jī)重疊的開(kāi)始（或者說(shuō)，什么時(shí)候可以說(shuō)存儲(chǔ)器操作引起處理機(jī)停頓）？由于亂序執(zhí)行處理機(jī)的復(fù)雜性，目前還沒(méi)有一個(gè)正確的定義。既然在流水線退出階段，只能看見(jiàn)已經(jīng)提交的操作，如果在一個(gè)周期內(nèi)它不能完成最大可能數(shù)目的指令，我們稱(chēng)處理機(jī)在這個(gè)時(shí)鐘周期內(nèi)停頓。這個(gè)停頓是因?yàn)榈谝粭l不能被完成指令引起的。這個(gè)定義很有用。比如，對(duì)某一個(gè)停頓時(shí)間采用的優(yōu)化措施，由于其他類(lèi)型停頓時(shí)間的出現(xiàn)，不可能總是會(huì)提高處理器執(zhí)行時(shí)間。對(duì)于延遲開(kāi)始的時(shí)間，有下面三種方式確定：存儲(chǔ)器指令進(jìn)入指

63、令窗口的時(shí)刻；或是當(dāng)?shù)刂樊a(chǎn)生的時(shí)刻；或是指令實(shí)際被送到存儲(chǔ)器系統(tǒng)的時(shí)刻。只要使用一致，任何一個(gè)都可以。¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾例重新計(jì)算上一個(gè)例子，這次假設(shè)通過(guò)變長(zhǎng)處理器的時(shí)鐘周期來(lái)支持亂序執(zhí)行，還是采用直接映射Ca

64、che。假設(shè)缺失代價(jià)為75ns，其中30是重疊的，也就是說(shuō)，平均CPU存儲(chǔ)器停頓時(shí)間現(xiàn)在為52.5ns。解 亂序執(zhí)行（OOO）的處理機(jī)的平均存儲(chǔ)器存取時(shí)間是：OOOCache的性能：由此可見(jiàn)，盡管時(shí)鐘周期較慢，直接映射的Cache缺失率較高，亂序執(zhí)行處理機(jī)如果能重疊30的缺失代價(jià)，速度也能快一點(diǎn)。¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾&