每個(gè)程序員都應(yīng)該了解的 CPU 高速緩存

英文原文：Memorypart2:CPUcaches來(lái)源：oschina

[編者按：這是Ulrich Drepper寫“程序員都該知道存儲(chǔ)器”的第二部。那些沒(méi)有讀過(guò)第一部的讀者可能希望從這一部開始。這本書寫的非常好，并且感謝Ulrich授權(quán)我們出版。

一點(diǎn)說(shuō)明：書籍出版時(shí)可能會(huì)有一些印刷錯(cuò)誤，如果你發(fā)現(xiàn)，并且想讓它在后續(xù)的出版中更正，請(qǐng)將意見(jiàn)發(fā)郵件到lwn@lwn.net ，我們一定會(huì)更正，并反饋給Ulrich的文檔副本，別的讀者就不會(huì)受到這些困擾。]

現(xiàn)在的CPU比25年前要精密得多了。在那個(gè)年代，CPU的頻率與內(nèi)存總線的頻率基本在同一層面上。內(nèi)存的訪問(wèn)速度僅比寄存器慢那么一點(diǎn)點(diǎn)。但是，這一局面在上世紀(jì)90年代被打破了。CPU的頻率大大提升，但內(nèi)存總線的頻率與內(nèi)存芯片的性能卻沒(méi)有得到成比例的提升。并不是因?yàn)樵觳怀龈斓膬?nèi)存，只是因?yàn)樘F了。內(nèi)存如果要達(dá)到目前CPU那樣的速度，那么它的造價(jià)恐怕要貴上好幾個(gè)數(shù)量級(jí)。

如果有兩個(gè)選項(xiàng)讓你選擇，一個(gè)是速度非常快、但容量很小的內(nèi)存，一個(gè)是速度還算快、但容量很多的內(nèi)存，如果你的工作集比較大，超過(guò)了前一種情況，那么人們總是會(huì)選擇第二個(gè)選項(xiàng)。原因在于輔存(一般為磁盤)的速度。由于工作集超過(guò)主存，那么必須用輔存來(lái)保存交換出去的那部分?jǐn)?shù)據(jù)，而輔存的速度往往要比主存慢上好幾個(gè)數(shù)量級(jí)。

好在這問(wèn)題也并不全然是非甲即乙的選擇。在配置大量DRAM的同時(shí)，我們還可以配置少量SRAM。將地址空間的某個(gè)部分劃給SRAM，剩下的部分劃給DRAM。一般來(lái)說(shuō)，SRAM可以當(dāng)作擴(kuò)展的寄存器來(lái)使用。

上面的做法看起來(lái)似乎可以，但實(shí)際上并不可行。首先，將SRAM內(nèi)存映射到進(jìn)程的虛擬地址空間就是個(gè)非常復(fù)雜的工作，而且，在這種做法中，每個(gè)進(jìn)程都需要管理這個(gè)SRAM區(qū)內(nèi)存的分配。每個(gè)進(jìn)程可能有大小完全不同的SRAM區(qū)，而組成程序的每個(gè)模塊也需要索取屬于自身的SRAM，更引入了額外的同步需求。簡(jiǎn)而言之，快速內(nèi)存帶來(lái)的好處完全被額外的管理開銷給抵消了。 基于以上的原因，我們不將SRAM放在OS或用戶的控制下，而是將它交由處理器來(lái)使用和管理。在這種模式下，SRAM用于對(duì)存儲(chǔ)在主存中、即將使用的數(shù)據(jù)進(jìn)行臨時(shí)拷貝(換句話說(shuō)，緩存)。這種做法的依據(jù)是程序代碼和數(shù)據(jù)具有時(shí)間局部性和空間局部性。也就是說(shuō)，在一段較短的時(shí)間內(nèi)，同一份代碼和數(shù)據(jù)有很大的可能被重復(fù)使用。對(duì)代碼來(lái)說(shuō)，是循環(huán)，即同一段代碼被反復(fù)執(zhí)行(完美的空間局部性)。對(duì)數(shù)據(jù)來(lái)說(shuō)，是反復(fù)訪問(wèn)某一小片區(qū)域中的數(shù)據(jù)。即使在短時(shí)間內(nèi)對(duì)內(nèi)存的訪問(wèn)并不連續(xù)，但仍有很大可能在不長(zhǎng)的時(shí)間內(nèi)重復(fù)訪問(wèn)同一份數(shù)據(jù)(空間局部性)。這兩個(gè)局部性是我們理解CPU高速緩存的關(guān)鍵。

我們先用一個(gè)簡(jiǎn)單的計(jì)算來(lái)展示一下高速緩存的效率。假設(shè)，訪問(wèn)主存需要200個(gè)周期，而訪問(wèn)高速緩存需要15個(gè)周期。如果使用100個(gè)數(shù)據(jù)元素100次，那么在沒(méi)有高速緩存的情況下，需要2000000個(gè)周期，而在有高速緩存、而且所有數(shù)據(jù)都已被緩存的情況下，只需要168500個(gè)周期。節(jié)約了91.5%的時(shí)間。

用作高速緩存的SRAM容量比主存小得多。以我的經(jīng)驗(yàn)來(lái)說(shuō)，高速緩存的大小一般是主存的千分之一左右(目前一般是4GB主存、4MB緩存)。這一點(diǎn)本身并不是什么問(wèn)題。只是，計(jì)算機(jī)一般都會(huì)有比較大的主存，因此工作集的大小總是會(huì)大于緩存。特別是那些運(yùn)行多進(jìn)程的系統(tǒng)，它的工作集大小是所有進(jìn)程加上內(nèi)核的總和。

處理高速緩存大小的限制需要制定一套很好的策略來(lái)決定在給定的時(shí)間內(nèi)什么數(shù)據(jù)應(yīng)該被緩存。由于不是所有數(shù)據(jù)的工作集都是在完全相同的時(shí)間段內(nèi)被使用的，我們可以用一些技術(shù)手段將需要用到的數(shù)據(jù)臨時(shí)替換那些當(dāng)前并未使用的緩存數(shù)據(jù)。這種預(yù)取將會(huì)減少部分訪問(wèn)主存的成本，因?yàn)樗c程序的執(zhí)行是異步的。所有的這些技術(shù)將會(huì)使高速緩存在使用的時(shí)候看起來(lái)比實(shí)際更大。我們將在3.3節(jié)討論這些問(wèn)題。我們將在第6章討論如何讓這些技術(shù)能很好地幫助程序員，讓處理器更高效地工作。

3.1 高速緩存的位置

在深入介紹高速緩存的技術(shù)細(xì)節(jié)之前，有必要說(shuō)明一下它在現(xiàn)代計(jì)算機(jī)系統(tǒng)中所處的位置。

圖3.1: 最簡(jiǎn)單的高速緩存配置圖

圖3.1展示了最簡(jiǎn)單的高速緩存配置。早期的一些系統(tǒng)就是類似的架構(gòu)。在這種架構(gòu)中，CPU核心不再直連到主存。{在一些更早的系統(tǒng)中，高速緩存像CPU與主存一樣連到系統(tǒng)總線上。那種做法更像是一種hack，而不是真正的解決方案。}數(shù)據(jù)的讀取和存儲(chǔ)都經(jīng)過(guò)高速緩存。CPU核心與高速緩存之間是一條特殊的快速通道。在簡(jiǎn)化的表示法中，主存與高速緩存都連到系統(tǒng)總線上，這條總線同時(shí)還用于與其它組件通信。我們管這條總線叫“FSB”——就是現(xiàn)在稱呼它的術(shù)語(yǔ)，參見(jiàn)第2.2節(jié)。在這一節(jié)里，我們將忽略北橋。

在過(guò)去的幾十年，經(jīng)驗(yàn)表明使用了馮諾伊曼結(jié)構(gòu)的計(jì)算機(jī)，將用于代碼和數(shù)據(jù)的高速緩存分開是存在巨大優(yōu)勢(shì)的。自1993年以來(lái)，Intel并且一直堅(jiān)持使用獨(dú)立的代碼和數(shù)據(jù)高速緩存。由于所需的代碼和數(shù)據(jù)的內(nèi)存區(qū)域是幾乎相互獨(dú)立的，這就是為什么獨(dú)立緩存工作得更完美的原因。近年來(lái)，獨(dú)立緩存的另一個(gè)優(yōu)勢(shì)慢慢顯現(xiàn)出來(lái)：常見(jiàn)處理器解碼指令的步驟是緩慢的，尤其當(dāng)管線為空的時(shí)候，往往會(huì)伴隨著錯(cuò)誤的預(yù)測(cè)或無(wú)法預(yù)測(cè)的分支的出現(xiàn)，將高速緩存技術(shù)用于指令解碼可以加快其執(zhí)行速度。

在高速緩存出現(xiàn)后不久，系統(tǒng)變得更加復(fù)雜。高速緩存與主存之間的速度差異進(jìn)一步拉大，直到加入了另一級(jí)緩存。新加入的這一級(jí)緩存比第一級(jí)緩存更大，但是更慢。由于加大一級(jí)緩存的做法從經(jīng)濟(jì)上考慮是行不通的，所以有了二級(jí)緩存，甚至現(xiàn)在的有些系統(tǒng)擁有三級(jí)緩存，如圖3.2所示。隨著單個(gè)CPU中核數(shù)的增加，未來(lái)甚至可能會(huì)出現(xiàn)更多層級(jí)的緩存。

圖3.2: 三級(jí)緩存的處理器

圖3.2展示了三級(jí)緩存，并介紹了本文將使用的一些術(shù)語(yǔ)。L1d是一級(jí)數(shù)據(jù)緩存，L1i是一級(jí)指令緩存，等等。請(qǐng)注意，這只是示意圖，真正的數(shù)據(jù)流并不需要流經(jīng)上級(jí)緩存。CPU的設(shè)計(jì)者們?cè)谠O(shè)計(jì)高速緩存的接口時(shí)擁有很大的自由。而程序員是看不到這些設(shè)計(jì)選項(xiàng)的。

另外，我們有多核CPU，每個(gè)核心可以有多個(gè)“線程”。核心與線程的不同之處在于，核心擁有獨(dú)立的硬件資源({早期的多核CPU甚至有獨(dú)立的二級(jí)緩存。})。在不同時(shí)使用相同資源(比如，通往外界的連接)的情況下，核心可以完全獨(dú)立地運(yùn)行。而線程只是共享資源。Intel的線程只有獨(dú)立的寄存器，而且還有限制——不是所有寄存器都獨(dú)立，有些是共享的。綜上，現(xiàn)代CPU的結(jié)構(gòu)就像圖3.3所示。

圖3.3 多處理器、多核心、多線程

在上圖中，有兩個(gè)處理器，每個(gè)處理器有兩個(gè)核心，每個(gè)核心有兩個(gè)線程。線程們共享一級(jí)緩存。核心(以深灰色表示)有獨(dú)立的一級(jí)緩存，同時(shí)共享二級(jí)緩存。處理器(淡灰色)之間不共享任何緩存。這些信息很重要，特別是在討論多進(jìn)程和多線程情況下緩存的影響時(shí)尤為重要。

3.2 高級(jí)的緩存操作

了解成本和節(jié)約使用緩存，我們必須結(jié)合在第二節(jié)中講到的關(guān)于計(jì)算機(jī)體系結(jié)構(gòu)和RAM技術(shù)，以及前一節(jié)講到的緩存描述來(lái)探討。

默認(rèn)情況下，CPU核心所有的數(shù)據(jù)的讀或?qū)懚即鎯?chǔ)在緩存中。當(dāng)然，也有內(nèi)存區(qū)域不能被緩存的，但是這種情況只發(fā)生在操作系統(tǒng)的實(shí)現(xiàn)者對(duì)數(shù)據(jù)考慮的前提下；對(duì)程序?qū)崿F(xiàn)者來(lái)說(shuō)，這是不可見(jiàn)的。這也說(shuō)明，程序設(shè)計(jì)者可以故意繞過(guò)某些緩存，不過(guò)這將是第六節(jié)中討論的內(nèi)容了。

如果CPU需要訪問(wèn)某個(gè)字(word)，先檢索緩存。很顯然，緩存不可能容納主存所有內(nèi)容(否則還需要主存干嘛)。系統(tǒng)用字的內(nèi)存地址來(lái)對(duì)緩存條目進(jìn)行標(biāo)記。如果需要讀寫某個(gè)地址的字，那么根據(jù)標(biāo)簽來(lái)檢索緩存即可。這里用到的地址可以是虛擬地址，也可以是物理地址，取決于緩存的具體實(shí)現(xiàn)。

標(biāo)簽是需要額外空間的，用字作為緩存的粒度顯然毫無(wú)效率。比如，在x86機(jī)器上，32位字的標(biāo)簽可能需要32位，甚至更長(zhǎng)。另一方面，由于空間局部性的存在，與當(dāng)前地址相鄰的地址有很大可能會(huì)被一起訪問(wèn)。再回憶下2.2.1節(jié)——內(nèi)存模塊在傳輸位于同一行上的多份數(shù)據(jù)時(shí)，由于不需要發(fā)送新CAS信號(hào)，甚至不需要發(fā)送RAS信號(hào)，因此可以實(shí)現(xiàn)很高的效率?；谝陨系脑?，緩存條目并不存儲(chǔ)單個(gè)字，而是存儲(chǔ)若干連續(xù)字組成的“線”。在早期的緩存中，線長(zhǎng)是32字節(jié)，現(xiàn)在一般是64字節(jié)。對(duì)于64位寬的內(nèi)存總線，每條線需要8次傳輸。而DDR對(duì)于這種傳輸模式的支持更為高效。

當(dāng)處理器需要內(nèi)存中的某塊數(shù)據(jù)時(shí)，整條緩存線被裝入L1d。緩存線的地址通過(guò)對(duì)內(nèi)存地址進(jìn)行掩碼操作生成。對(duì)于64字節(jié)的緩存線，是將低6位置0。這些被丟棄的位作為線內(nèi)偏移量。其它的位作為標(biāo)簽，并用于在緩存內(nèi)定位。在實(shí)踐中，我們將地址分為三個(gè)部分。32位地址的情況如下:

如果緩存線長(zhǎng)度為2O，那么地址的低O位用作線內(nèi)偏移量。上面的S位選擇“緩存集”。后面我們會(huì)說(shuō)明使用緩存集的原因?，F(xiàn)在只需要明白一共有2S個(gè)緩存集就夠了。剩下的32 – S – O = T位組成標(biāo)簽。它們用來(lái)區(qū)分別名相同的各條線{有相同S部分的緩存線被稱為有相同的別名。}用于定位緩存集的S部分不需要存儲(chǔ)，因?yàn)閷儆谕痪彺婕乃芯€的S部分都是相同的。

當(dāng)某條指令修改內(nèi)存時(shí)，仍然要先裝入緩存線，因?yàn)槿魏沃噶疃疾豢赡芡瑫r(shí)修改整條線(只有一個(gè)例外——第6.1節(jié)中將會(huì)介紹的寫合并(write-combine))。因此需要在寫操作前先把緩存線裝載進(jìn)來(lái)。如果緩存線被寫入，但還沒(méi)有寫回主存，那就是所謂的“臟了”。臟了的線一旦寫回主存，臟標(biāo)記即被清除。

為了裝入新數(shù)據(jù)，基本上總是要先在緩存中清理出位置。L1d將內(nèi)容逐出L1d，推入L2(線長(zhǎng)相同)。當(dāng)然，L2也需要清理位置。于是L2將內(nèi)容推入L3，最后L3將它推入主存。這種逐出操作一級(jí)比一級(jí)昂貴。這里所說(shuō)的是現(xiàn)代AMD和VIA處理器所采用的獨(dú)占型緩存(exclusive cache)。而Intel采用的是包容型緩存(inclusive cache)，{并不完全正確，Intel有些緩存是獨(dú)占型的，還有一些緩存具有獨(dú)占型緩存的特點(diǎn)。}L1d的每條線同時(shí)存在于L2里。對(duì)這種緩存，逐出操作就很快了。如果有足夠L2，對(duì)于相同內(nèi)容存在不同地方造成內(nèi)存浪費(fèi)的缺點(diǎn)可以降到最低，而且在逐出時(shí)非常有利。而獨(dú)占型緩存在裝載新數(shù)據(jù)時(shí)只需要操作L1d，不需要碰L2，因此會(huì)比較快。

處理器體系結(jié)構(gòu)中定義的作為存儲(chǔ)器的模型只要還沒(méi)有改變，那就允許多CPU按照自己的方式來(lái)管理高速緩存。這表示，例如，設(shè)計(jì)優(yōu)良的處理器，利用很少或根本沒(méi)有內(nèi)存總線活動(dòng)，并主動(dòng)寫回主內(nèi)存臟高速緩存行。這種高速緩存架構(gòu)在如x86和x86-64各種各樣的處理器間存在。制造商之間，即使在同一制造商生產(chǎn)的產(chǎn)品中，證明了的內(nèi)存模型抽象的力量。

在對(duì)稱多處理器（SMP）架構(gòu)的系統(tǒng)中，CPU的高速緩存不能獨(dú)立的工作。在任何時(shí)候，所有的處理器都應(yīng)該擁有相同的內(nèi)存內(nèi)容。保證這樣的統(tǒng)一的內(nèi)存視圖被稱為“高速緩存一致性”。如果在其自己的高速緩存和主內(nèi)存間，處理器設(shè)計(jì)簡(jiǎn)單，它將不會(huì)看到在其他處理器上的臟高速緩存行的內(nèi)容。從一個(gè)處理器直接訪問(wèn)另一個(gè)處理器的高速緩存這種模型設(shè)計(jì)代價(jià)將是非常昂貴的，它是一個(gè)相當(dāng)大的瓶頸。相反，當(dāng)另一個(gè)處理器要讀取或?qū)懭氲礁咚倬彺婢€上時(shí)，處理器會(huì)去檢測(cè)。

如果CPU檢測(cè)到一個(gè)寫訪問(wèn)，而且該CPU的cache中已經(jīng)緩存了一個(gè)cache line的原始副本，那么這個(gè)cache line將被標(biāo)記為無(wú)效的cache line。接下來(lái)在引用這個(gè)cache line之前，需要重新加載該cache line。需要注意的是讀訪問(wèn)并不會(huì)導(dǎo)致cache line被標(biāo)記為無(wú)效的。

更精確的cache實(shí)現(xiàn)需要考慮到其他更多的可能性，比如第二個(gè)CPU在讀或者寫他的cache line時(shí)，發(fā)現(xiàn)該cache line在第一個(gè)CPU的cache中被標(biāo)記為臟數(shù)據(jù)了，此時(shí)我們就需要做進(jìn)一步的處理。在這種情況下，主存儲(chǔ)器已經(jīng)失效，第二個(gè)CPU需要讀取第一個(gè)CPU的cache line。通過(guò)測(cè)試，我們知道在這種情況下第一個(gè)CPU會(huì)將自己的cache line數(shù)據(jù)自動(dòng)發(fā)送給第二個(gè)CPU。這種操作是繞過(guò)主存儲(chǔ)器的，但是有時(shí)候存儲(chǔ)控制器是可以直接將第一個(gè)CPU中的cache line數(shù)據(jù)存儲(chǔ)到主存儲(chǔ)器中。對(duì)第一個(gè)CPU的cache的寫訪問(wèn)會(huì)導(dǎo)致本地cache line的所有拷貝被標(biāo)記為無(wú)效。

隨著時(shí)間的推移，一大批緩存一致性協(xié)議已經(jīng)建立。其中，最重要的是MESI,我們將在第3.3.4節(jié)進(jìn)行介紹。以上結(jié)論可以概括為幾個(gè)簡(jiǎn)單的規(guī)則:

一個(gè)臟緩存線不存在于任何其他處理器的緩存之中。
同一緩存線中的干凈拷貝可以駐留在任意多個(gè)其他緩存之中。

如果遵守這些規(guī)則,處理器甚至可以在多處理器系統(tǒng)中更加有效的使用它們的緩存。所有的處理器需要做的就是監(jiān)控其他每一個(gè)寫訪問(wèn)和比較本地緩存中的地址。在下一節(jié)中,我們將介紹更多細(xì)節(jié)方面的實(shí)現(xiàn),尤其是存儲(chǔ)開銷方面的細(xì)節(jié)。

最后，我們至少應(yīng)該關(guān)注高速緩存命中或未命中帶來(lái)的消耗。下面是英特爾奔騰 M 的數(shù)據(jù)：

To Where	Cycles
Register	<= 1
L1d	~3
L2	~14
Main Memory	~240

這是在CPU周期中的實(shí)際訪問(wèn)時(shí)間。有趣的是，對(duì)于L2高速緩存的訪問(wèn)時(shí)間很大一部分（甚至是大部分）是由線路的延遲引起的。這是一個(gè)限制，增加高速緩存的大小變得更糟。只有當(dāng)減小時(shí)（例如，從60納米的Merom到45納米Penryn處理器），可以提高這些數(shù)據(jù)。

表格中的數(shù)字看起來(lái)很高，但是，幸運(yùn)的是，整個(gè)成本不必須負(fù)擔(dān)每次出現(xiàn)的緩存加載和緩存失效。某些部分的成本可以被隱藏?，F(xiàn)在的處理器都使用不同長(zhǎng)度的內(nèi)部管道，在管道內(nèi)指令被解碼，并為準(zhǔn)備執(zhí)行。如果數(shù)據(jù)要傳送到一個(gè)寄存器，那么部分的準(zhǔn)備工作是從存儲(chǔ)器（或高速緩存）加載數(shù)據(jù)。如果內(nèi)存加載操作在管道中足夠早的進(jìn)行，它可以與其他操作并行發(fā)生，那么加載的全部發(fā)銷可能會(huì)被隱藏。對(duì)L1D常常可能如此；某些有長(zhǎng)管道的處理器的L2也可以。

提早啟動(dòng)內(nèi)存的讀取有許多障礙。它可能只是簡(jiǎn)單的不具有足夠資源供內(nèi)存訪問(wèn)，或者地址從另一個(gè)指令獲取，然后加載的最終地址才變得可用。在這種情況下，加載成本是不能隱藏的（完全的）。

對(duì)于寫操作，CPU并不需要等待數(shù)據(jù)被安全地放入內(nèi)存。只要指令具有類似的效果，就沒(méi)有什么東西可以阻止CPU走捷徑了。它可以早早地執(zhí)行下一條指令，甚至可以在影子寄存器(shadow register)的幫助下，更改這個(gè)寫操作將要存儲(chǔ)的數(shù)據(jù)。

圖3.4: 隨機(jī)寫操作的訪問(wèn)時(shí)間

圖3.4展示了緩存的效果。關(guān)于產(chǎn)生圖中數(shù)據(jù)的程序，我們會(huì)在稍后討論。這里大致說(shuō)下，這個(gè)程序是連續(xù)隨機(jī)地訪問(wèn)某塊大小可配的內(nèi)存區(qū)域。每個(gè)數(shù)據(jù)項(xiàng)的大小是固定的。數(shù)據(jù)項(xiàng)的多少取決于選擇的工作集大小。Y軸表示處理每個(gè)元素平均需要多少個(gè)CPU周期，注意它是對(duì)數(shù)刻度。X軸也是同樣，工作集的大小都以2的n次方表示。

圖中有三個(gè)比較明顯的不同階段。很正常，這個(gè)處理器有L1d和L2，沒(méi)有L3。根據(jù)經(jīng)驗(yàn)可以推測(cè)出，L1d有213字節(jié)，而L2有220字節(jié)。因?yàn)?，如果整個(gè)工作集都可以放入L1d，那么只需不到10個(gè)周期就可以完成操作。如果工作集超過(guò)L1d，處理器不得不從L2獲取數(shù)據(jù)，于是時(shí)間飄升到28個(gè)周期左右。如果工作集更大，超過(guò)了L2，那么時(shí)間進(jìn)一步暴漲到480個(gè)周期以上。這時(shí)候，許多操作將不得不從主存中獲取數(shù)據(jù)。更糟糕的是，如果修改了數(shù)據(jù)，還需要將這些臟了的緩存線寫回內(nèi)存。

看了這個(gè)圖，大家應(yīng)該會(huì)有足夠的動(dòng)力去檢查代碼、改進(jìn)緩存的利用方式了吧？這里的性能改善可不只是微不足道的幾個(gè)百分點(diǎn)，而是幾個(gè)數(shù)量級(jí)呀。在第6節(jié)中，我們將介紹一些編寫高效代碼的技巧。而下一節(jié)將進(jìn)一步深入緩存的設(shè)計(jì)。雖然精彩，但并不是必修課，大家可以選擇性地跳過(guò)。

3.3 CPU 緩存實(shí)現(xiàn)細(xì)節(jié)

高速緩存的實(shí)現(xiàn)者遇到這樣的難題：巨大的主內(nèi)存中每一個(gè)單元都潛在的需要緩存。如果程序的工作集足夠大，這意味著很多主內(nèi)存單元競(jìng)爭(zhēng)高速緩存的每一個(gè)地方。先前有過(guò)提示，主存和高速緩存的大小比是1000：1，這是不常見(jiàn)的。

3.3.1 關(guān)聯(lián)性

可以這樣實(shí)現(xiàn)一個(gè)高速緩存，每個(gè)高速緩存段（高速緩存行：cache line）都可以容納任何內(nèi)存位置的一個(gè)副本。這就是所謂的全關(guān)聯(lián)。要訪問(wèn)一個(gè)緩存段，處理器核心不得不用所有緩存段的標(biāo)簽和請(qǐng)求地址的標(biāo)簽一一做比較。標(biāo)簽將包含除去緩存段的偏移量全部的地址，（譯注：也就是去除3.2節(jié)中圖的O）（這意味著，S在3.2節(jié)的圖中是零）

高速緩存有類似這樣的實(shí)現(xiàn)，但是，看看在今天使用的L2的數(shù)目，表明這是不切實(shí)際的。給定4MB的高速緩存和64B的高速緩存段，高速緩存將有65,536個(gè)項(xiàng)。為了達(dá)到足夠的性能，緩存邏輯必須能夠在短短的幾個(gè)時(shí)鐘周期內(nèi)，從所有這些項(xiàng)中，挑一個(gè)匹配給定的標(biāo)簽。實(shí)現(xiàn)這一點(diǎn)的工作將是巨大的。

Figure 3.5: 全關(guān)聯(lián)高速緩存原理圖

對(duì)于每個(gè)高速緩存行，比較器是需要比較大標(biāo)簽（注意，S是零）。每個(gè)連接旁邊的字母表示位的寬度。如果沒(méi)有給出，它是一個(gè)單比特線。每個(gè)比較器都要比較兩個(gè)T-位寬的值。然后，基于該結(jié)果，適當(dāng)?shù)母咚倬彺嫘械膬?nèi)容被選中，并使其可用。這需要合并多套O數(shù)據(jù)線，因?yàn)樗麄兪蔷彺嫱埃ㄗg注：這里類似把O輸出接入多選器，所以需要合并）。實(shí)現(xiàn)僅僅一個(gè)比較器，需要晶體管的數(shù)量就非常大，特別是因?yàn)樗仨毞浅？?。沒(méi)有迭代比較器是可用的。節(jié)省比較器的數(shù)目的唯一途徑是通過(guò)反復(fù)比較標(biāo)簽，以減少它們的數(shù)目。這是不適合的，出于同樣的原因，迭代比較器不可用：它的時(shí)間太長(zhǎng)。

全關(guān)聯(lián)高速緩存對(duì)小緩存是實(shí)用的（例如，在某些Intel處理器的TLB緩存是全關(guān)聯(lián)的），但這些緩存都很小，非常小的。我們正在談?wù)摰淖疃鄮资?xiàng)。

對(duì)于L1i，L1d和更高級(jí)別的緩存，需要采用不同的方法。可以做的就是是限制搜索。最極端的限制是，每個(gè)標(biāo)簽映射到一個(gè)明確的緩存條目。計(jì)算很簡(jiǎn)單：給定的4MB/64B緩存有65536項(xiàng)，我們可以使用地址的bit6到bit21（16位）來(lái)直接尋址高速緩存的每一個(gè)項(xiàng)。地址的低6位作為高速緩存段的索引。

Figure 3.6: Direct-Mapped Cache Schematics

在圖3.6中可以看出，這種直接映射的高速緩存，速度快，比較容易實(shí)現(xiàn)。它只是需要一個(gè)比較器，一個(gè)多路復(fù)用器（在這個(gè)圖中有兩個(gè)，標(biāo)記和數(shù)據(jù)是分離的，但是對(duì)于設(shè)計(jì)這不是一個(gè)硬性要求），和一些邏輯來(lái)選擇只是有效的高速緩存行的內(nèi)容。由于速度的要求，比較器是復(fù)雜的，但是現(xiàn)在只需要一個(gè)，結(jié)果是可以花更多的精力，讓其變得快速。這種方法的復(fù)雜性在于在多路復(fù)用器。一個(gè)簡(jiǎn)單的多路轉(zhuǎn)換器中的晶體管的數(shù)量增速是O（log N）的，其中N是高速緩存段的數(shù)目。這是可以容忍的，但可能會(huì)很慢，在某種情況下，速度可提升，通過(guò)增加多路復(fù)用器晶體管數(shù)量，來(lái)并行化的一些工作和自身增速。晶體管的總數(shù)只是隨著快速增長(zhǎng)的高速緩存緩慢的增加，這使得這種解決方案非常有吸引力。但它有一個(gè)缺點(diǎn)：只有用于直接映射地址的相關(guān)的地址位均勻分布，程序才能很好工作。如果分布的不均勻，而且這是常態(tài)，一些緩存項(xiàng)頻繁的使用，并因此多次被換出，而另一些則幾乎不被使用或一直是空的。

Figure 3.7: 組關(guān)聯(lián)高速緩存原理圖

可以通過(guò)使高速緩存的組關(guān)聯(lián)來(lái)解決此問(wèn)題。組關(guān)聯(lián)結(jié)合高速緩存的全關(guān)聯(lián)和直接映射高速緩存特點(diǎn)，在很大程度上避免那些設(shè)計(jì)的弱點(diǎn)。圖3.7顯示了一個(gè)組關(guān)聯(lián)高速緩存的設(shè)計(jì)。標(biāo)簽和數(shù)據(jù)存儲(chǔ)分成不同的組并可以通過(guò)地址選擇。這類似直接映射高速緩存。但是，小數(shù)目的值可以在同一個(gè)高速緩存組緩存，而不是一個(gè)緩存組只有一個(gè)元素，用于在高速緩存中的每個(gè)設(shè)定值是相同的一組值的緩存。所有組的成員的標(biāo)簽可以并行比較，這類似全關(guān)聯(lián)緩存的功能。

其結(jié)果是高速緩存，不容易被不幸或故意選擇同屬同一組編號(hào)的地址所擊敗，同時(shí)高速緩存的大小并不限于由比較器的數(shù)目，可以以并行的方式實(shí)現(xiàn)。如果高速緩存增長(zhǎng)，只（在該圖中）增加列的數(shù)目，而不增加行數(shù)。只有高速緩存之間的關(guān)聯(lián)性增加，行數(shù)才會(huì)增加。今天，處理器的L2高速緩存或更高的高速緩存，使用的關(guān)聯(lián)性高達(dá)16。 L1高速緩存通常使用8。

L2 Cache Size	Associativity
Direct	2	4	8
CL=32	CL=64	CL=32	CL=64	CL=32	CL=64	CL=32	CL=64
512k	27,794,595	20,422,527	25,222,611	18,303,581	24,096,510	17,356,121	23,666,929	17,029,334
1M	19,007,315	13,903,854	16,566,738	12,127,174	15,537,500	11,436,705	15,162,895	11,233,896
2M	12,230,962	8,801,403	9,081,881	6,491,011	7,878,601	5,675,181	7,391,389	5,382,064
4M	7,749,986	5,427,836	4,736,187	3,159,507	3,788,122	2,418,898	3,430,713	2,125,103
8M	4,731,904	3,209,693	2,690,498	1,602,957	2,207,655	1,228,190	2,111,075	1,155,847
16M	2,620,587	1,528,592	1,958,293	1,089,580	1,704,878	883,530	1,671,541	862,324

Table 3.1: 高速緩存大小，關(guān)聯(lián)行，段大小的影響

給定我們4MB/64B高速緩存，8路組關(guān)聯(lián)，相關(guān)的緩存留給我們的有8192組，只用標(biāo)簽的13位，就可以尋址緩集。要確定哪些（如果有的話）的緩存組設(shè)置中的條目包含尋址的高速緩存行，8個(gè)標(biāo)簽都要進(jìn)行比較。在很短的時(shí)間內(nèi)做出來(lái)是可行的。通過(guò)一個(gè)實(shí)驗(yàn)，我們可以看到，這是有意義的。

表3.1顯示一個(gè)程序在改變緩存大小，緩存段大小和關(guān)聯(lián)集大小，L2高速緩存的緩存失效數(shù)量（根據(jù)Linux內(nèi)核相關(guān)的方面人的說(shuō)法，GCC在這種情況下，是他們所有中最重要的標(biāo)尺）。在7.2節(jié)中，我們將介紹工具來(lái)模擬此測(cè)試要求的高速緩存。

萬(wàn)一這還不是很明顯，所有這些值之間的關(guān)系是高速緩存的大小為：

cache line size × associativity × number of sets

地址被映射到高速緩存使用

O= log2cache line size
S= log2number of sets

在第3.2節(jié)中的圖顯示的方式。

Figure 3.8: 緩存段大小 vs 關(guān)聯(lián)行 (CL=32)

圖3.8表中的數(shù)據(jù)更易于理解。它顯示一個(gè)固定的32個(gè)字節(jié)大小的高速緩存行的數(shù)據(jù)。對(duì)于一個(gè)給定的高速緩存大小，我們可以看出，關(guān)聯(lián)性，的確可以幫助明顯減少高速緩存未命中的數(shù)量。對(duì)于8MB的緩存，從直接映射到2路組相聯(lián)，可以減少近44％的高速緩存未命中。組相聯(lián)高速緩存和直接映射緩存相比，該處理器可以把更多的工作集保持在緩存中。

在文獻(xiàn)中，偶爾可以讀到，引入關(guān)聯(lián)性，和加倍高速緩存的大小具有相同的效果。在從4M緩存躍升到8MB緩存的極端的情況下，這是正確的。關(guān)聯(lián)性再提高一倍那就肯定不正確啦。正如我們所看到的數(shù)據(jù)，后面的收益要小得多。我們不應(yīng)該完全低估它的效果，雖然。在示例程序中的內(nèi)存使用的峰值是5.6M。因此，具有8MB緩存不太可能有很多（兩個(gè)以上）使用相同的高速緩存的組。從較小的緩存的關(guān)聯(lián)性的巨大收益可以看出，較大工作集可以節(jié)省更多。

在一般情況下，增加8以上的高速緩存之間的關(guān)聯(lián)性似乎對(duì)只有一個(gè)單線程工作量影響不大。隨著介紹一個(gè)使用共享L2的多核處理器，形勢(shì)發(fā)生了變化?，F(xiàn)在你基本上有兩個(gè)程序命中相同的緩存， 實(shí)際上導(dǎo)致高速緩存減半（對(duì)于四核處理器是1/4）。因此，可以預(yù)期，隨著核的數(shù)目的增加，共享高速緩存的相關(guān)性也應(yīng)增長(zhǎng)。一旦這種方法不再可行（16 路組關(guān)聯(lián)性已經(jīng)很難）處理器設(shè)計(jì)者不得不開始使用共享的三級(jí)高速緩存和更高級(jí)別的，而L2高速緩存只被核的一個(gè)子集共享。

從圖3.8中，我們還可以研究緩存大小對(duì)性能的影響。這一數(shù)據(jù)需要了解工作集的大小才能進(jìn)行解讀。很顯然，與主存相同的緩存比小緩存能產(chǎn)生更好的結(jié)果，因此，緩存通常是越大越好。

上文已經(jīng)說(shuō)過(guò)，示例中最大的工作集為5.6M。它并沒(méi)有給出最佳緩存大小值，但我們可以估算出來(lái)。問(wèn)題主要在于內(nèi)存的使用并不連續(xù)，因此，即使是16M的緩存，在處理5.6M的工作集時(shí)也會(huì)出現(xiàn)沖突(參見(jiàn)2路集合關(guān)聯(lián)式16MB緩存vs直接映射式緩存的優(yōu)點(diǎn))。不管怎樣，我們可以有把握地說(shuō)，在同樣5.6M的負(fù)載下，緩存從16MB升到32MB基本已沒(méi)有多少提高的余地。但是，工作集是會(huì)變的。如果工作集不斷增大，緩存也需要隨之增大。在購(gòu)買計(jì)算機(jī)時(shí)，如果需要選擇緩存大小，一定要先衡量工作集的大小。原因可以參見(jiàn)圖3.10。

圖3.9: 測(cè)試的內(nèi)存分布情況

我們執(zhí)行兩項(xiàng)測(cè)試。第一項(xiàng)測(cè)試是按順序地訪問(wèn)所有元素。測(cè)試程序循著指針n進(jìn)行訪問(wèn)，而所有元素是鏈接在一起的，從而使它們的被訪問(wèn)順序與在內(nèi)存中排布的順序一致，如圖3.9的下半部分所示，末尾的元素有一個(gè)指向首元素的引用。而第二項(xiàng)測(cè)試(見(jiàn)圖3.9的上半部分)則是按隨機(jī)順序訪問(wèn)所有元素。在上述兩個(gè)測(cè)試中，所有元素都構(gòu)成一個(gè)單向循環(huán)鏈表。

3.3.2 Cache的性能測(cè)試

用于測(cè)試程序的數(shù)據(jù)可以模擬一個(gè)任意大小的工作集：包括讀、寫訪問(wèn)，隨機(jī)、連續(xù)訪問(wèn)。在圖3.4中我們可以看到，程序?yàn)楣ぷ骷瘎?chuàng)建了一個(gè)與其大小和元素類型相同的數(shù)組：

1 2 3 4

struct l { struct l *n; long int pad[NPAD]; };

n字段將所有節(jié)點(diǎn)隨機(jī)得或者順序的加入到環(huán)形鏈表中，用指針從當(dāng)前節(jié)點(diǎn)進(jìn)入到下一個(gè)節(jié)點(diǎn)。pad字段用來(lái)存儲(chǔ)數(shù)據(jù)，其可以是任意大小。在一些測(cè)試程序中，pad字段是可以修改的, 在其他程序中，pad字段只可以進(jìn)行讀操作。

在性能測(cè)試中，我們談到工作集大小的問(wèn)題，工作集使用結(jié)構(gòu)體l定義的元素表示的。2N字節(jié)的工作集包含

2N/sizeof(struct l)

個(gè)元素. 顯然sizeof(struct l) 的值取決于NPAD的大小。在32位系統(tǒng)上，NPAD=7意味著數(shù)組的每個(gè)元素的大小為32字節(jié)，在64位系統(tǒng)上，NPAD=7意味著數(shù)組的每個(gè)元素的大小為64字節(jié)。

單線程順序訪問(wèn)

最簡(jiǎn)單的情況就是遍歷鏈表中順序存儲(chǔ)的節(jié)點(diǎn)。無(wú)論是從前向后處理，還是從后向前，對(duì)于處理器來(lái)說(shuō)沒(méi)有什么區(qū)別。下面的測(cè)試中，我們需要得到處理鏈表中一個(gè)元素所需要的時(shí)間，以CPU時(shí)鐘周期最為計(jì)時(shí)單元。圖3.10顯示了測(cè)試結(jié)構(gòu)。除非有特殊說(shuō)明, 所有的測(cè)試都是在Pentium4 64-bit 平臺(tái)上進(jìn)行的，因此結(jié)構(gòu)體l中NPAD=0，大小為8字節(jié)。

圖 3.10: 順序讀訪問(wèn), NPAD=0

圖 3.11: 順序讀多個(gè)字節(jié)

一開始的兩個(gè)測(cè)試數(shù)據(jù)收到了噪音的污染。由于它們的工作負(fù)荷太小，無(wú)法過(guò)濾掉系統(tǒng)內(nèi)其它進(jìn)程對(duì)它們的影響。我們可以認(rèn)為它們都是4個(gè)周期以內(nèi)的。這樣一來(lái)，整個(gè)圖可以劃分為比較明顯的三個(gè)部分:

工作集小于214字節(jié)的。
工作集從215字節(jié)到220字節(jié)的。
工作集大于221字節(jié)的。

這樣的結(jié)果很容易解釋——是因?yàn)樘幚砥饔?6KB的L1d和1MB的L2。而在這三個(gè)部分之間，并沒(méi)有非常銳利的邊緣，這是因?yàn)橄到y(tǒng)的其它部分也在使用緩存，我們的測(cè)試程序并不能獨(dú)占緩存的使用。尤其是L2，它是統(tǒng)一式的緩存，處理器的指令也會(huì)使用它(注: Intel使用的是包容式緩存)。

測(cè)試的實(shí)際耗時(shí)可能會(huì)出乎大家的意料。L1d的部分跟我們預(yù)想的差不多，在一臺(tái)P4上耗時(shí)為4個(gè)周期左右。但L2的結(jié)果則出乎意料。大家可能覺(jué)得需要14個(gè)周期以上，但實(shí)際只用了9個(gè)周期。這要?dú)w功于處理器先進(jìn)的處理邏輯，當(dāng)它使用連續(xù)的內(nèi)存區(qū)時(shí)，會(huì)預(yù)先讀取下一條緩存線的數(shù)據(jù)。這樣一來(lái)，當(dāng)真正使用下一條線的時(shí)候，其實(shí)已經(jīng)早已讀完一半了，于是真正的等待耗時(shí)會(huì)比L2的訪問(wèn)時(shí)間少很多。

在工作集超過(guò)L2的大小之后，預(yù)取的效果更明顯了。前面我們說(shuō)過(guò)，主存的訪問(wèn)需要耗時(shí)200個(gè)周期以上。但在預(yù)取的幫助下，實(shí)際耗時(shí)保持在9個(gè)周期左右。200 vs 9，效果非常不錯(cuò)。

我們可以觀察到預(yù)取的行為，至少可以間接地觀察到。圖3.11中有4條線，它們表示處理不同大小結(jié)構(gòu)時(shí)的耗時(shí)情況。隨著結(jié)構(gòu)的變大，元素間的距離變大了。圖中4條線對(duì)應(yīng)的元素距離分別是0、56、120和248字節(jié)。

圖中最下面的這一條線來(lái)自前一個(gè)圖，但在這里更像是一條直線。其它三條線的耗時(shí)情況比較差。圖中這些線也有比較明顯的三個(gè)階段，同時(shí)，在小工作集的情況下也有比較大的錯(cuò)誤(請(qǐng)?jiān)俅魏雎赃@些錯(cuò)誤)。在只使用L1d的階段，這些線條基本重合。因?yàn)檫@時(shí)候還不需要預(yù)取，只需要訪問(wèn)L1d就行。

在L2階段，三條新加的線基本重合，而且耗時(shí)比老的那條線高很多，大約在28個(gè)周期左右，差不多就是L2的訪問(wèn)時(shí)間。這表明，從L2到L1d的預(yù)取并沒(méi)有生效。這是因?yàn)椋瑢?duì)于最下面的線(NPAD=0)，由于結(jié)構(gòu)小，8次循環(huán)后才需要訪問(wèn)一條新緩存線，而上面三條線對(duì)應(yīng)的結(jié)構(gòu)比較大，拿相對(duì)最小的NPAD=7來(lái)說(shuō)，光是一次循環(huán)就需要訪問(wèn)一條新線，更不用說(shuō)更大的NPAD=15和31了。而預(yù)取邏輯是無(wú)法在每個(gè)周期裝載新線的，因此每次循環(huán)都需要從L2讀取，我們看到的就是從L2讀取的時(shí)延。

更有趣的是工作集超過(guò)L2容量后的階段?？炜?，4條線遠(yuǎn)遠(yuǎn)地拉開了。元素的大小變成了主角，左右了性能。處理器應(yīng)能識(shí)別每一步(stride)的大小，不去為NPAD=15和31獲取那些實(shí)際并不需要的緩存線(參見(jiàn)6.3.1)。元素大小對(duì)預(yù)取的約束是根源于硬件預(yù)取的限制——它無(wú)法跨越頁(yè)邊界。如果允許預(yù)取器跨越頁(yè)邊界，而下一頁(yè)不存在或無(wú)效，那么OS還得去尋找它。這意味著，程序需要遭遇一次并非由它自己產(chǎn)生的頁(yè)錯(cuò)誤，這是完全不能接受的。在NPAD=7或者更大的時(shí)候，由于每個(gè)元素都至少需要一條緩存線，預(yù)取器已經(jīng)幫不上忙了，它沒(méi)有足夠的時(shí)間去從內(nèi)存裝載數(shù)據(jù)。 另一個(gè)導(dǎo)致慢下來(lái)的原因是TLB緩存的未命中。TLB是存儲(chǔ)虛實(shí)地址映射的緩存，參見(jiàn)第4節(jié)。為了保持快速，TLB只有很小的容量。如果有大量頁(yè)被反復(fù)訪問(wèn)，超出了TLB緩存容量，就會(huì)導(dǎo)致反復(fù)地進(jìn)行地址翻譯，這會(huì)耗費(fèi)大量時(shí)間。TLB查找的代價(jià)分?jǐn)偟剿性厣?，如果元素越大，那么元素的?shù)量越少，每個(gè)元素承擔(dān)的那一份就越多。

為了觀察TLB的性能，我們可以進(jìn)行另兩項(xiàng)測(cè)試。第一項(xiàng)：我們還是順序存儲(chǔ)列表中的元素，使NPAD=7，讓每個(gè)元素占滿整個(gè)cache line，第二項(xiàng)：我們將列表的每個(gè)元素存儲(chǔ)在一個(gè)單獨(dú)的頁(yè)上，忽略每個(gè)頁(yè)沒(méi)有使用的部分以用來(lái)計(jì)算工作集的大小。（這樣做可能不太一致，因?yàn)樵谇懊娴臏y(cè)試中，我計(jì)算了結(jié)構(gòu)體中每個(gè)元素沒(méi)有使用的部分，從而用來(lái)定義NPAD的大小，因此每個(gè)元素占滿了整個(gè)頁(yè)，這樣以來(lái)工作集的大小將會(huì)有所不同。但是這不是這項(xiàng)測(cè)試的重點(diǎn)，預(yù)取的低效率多少使其有點(diǎn)不同）。結(jié)果表明，第一項(xiàng)測(cè)試中，每次列表的迭代都需要一個(gè)新的cache line，而且每64個(gè)元素就需要一個(gè)新的頁(yè)。第二項(xiàng)測(cè)試中，每次迭代都會(huì)在一個(gè)新的頁(yè)中加載一個(gè)新的cache line。

圖 3.12: TLB 對(duì)順序讀的影響

結(jié)果見(jiàn)圖3.12。該測(cè)試與圖3.11是在同一臺(tái)機(jī)器上進(jìn)行的?；诳捎肦AM空間的有限性，測(cè)試設(shè)置容量空間大小為2的24次方字節(jié)，這就需要1GB的容量將對(duì)象放置在分頁(yè)上。圖3.12中下方的紅色曲線正好對(duì)應(yīng)了圖3.11中NPAD等于7的曲線。我們看到不同的步長(zhǎng)顯示了高速緩存L1d和L2的大小。第二條曲線看上去完全不同，其最重要的特點(diǎn)是當(dāng)工作容量到達(dá)2的13次方字節(jié)時(shí)開始大幅度增長(zhǎng)。這就是TLB緩存溢出的時(shí)候。我們能計(jì)算出一個(gè)64字節(jié)大小的元素的TLB緩存有64個(gè)輸入。成本不會(huì)受頁(yè)面錯(cuò)誤影響，因?yàn)槌绦蜴i定了存儲(chǔ)器以防止內(nèi)存被換出。

可以看出，計(jì)算物理地址并把它存儲(chǔ)在TLB中所花費(fèi)的周期數(shù)量級(jí)是非常高的。圖3.12的表格顯示了一個(gè)極端的例子，但從中可以清楚的得到：TLB緩存效率降低的一個(gè)重要因素是大型NPAD值的減緩。由于物理地址必須在緩存行能被L2或主存讀取之前計(jì)算出來(lái)，地址轉(zhuǎn)換這個(gè)不利因素就增加了內(nèi)存訪問(wèn)時(shí)間。這一點(diǎn)部分解釋了為什么NPAD等于31時(shí)每個(gè)列表元素的總花費(fèi)比理論上的RAM訪問(wèn)時(shí)間要高。

圖3.13 NPAD等于1時(shí)的順序讀和寫

通過(guò)查看鏈表元素被修改時(shí)測(cè)試數(shù)據(jù)的運(yùn)行情況，我們可以窺見(jiàn)一些更詳細(xì)的預(yù)取實(shí)現(xiàn)細(xì)節(jié)。圖3.13顯示了三條曲線。所有情況下元素寬度都為16個(gè)字節(jié)。第一條曲線“Follow”是熟悉的鏈表走線在這里作為基線。第二條曲線，標(biāo)記為“Inc”，僅僅在當(dāng)前元素進(jìn)入下一個(gè)前給其增加thepad[0]成員。第三條曲線，標(biāo)記為”Addnext0″， 取出下一個(gè)元素的thepad[0]鏈表元素并把它添加為當(dāng)前鏈表元素的thepad[0]成員。

在沒(méi)運(yùn)行時(shí)，大家可能會(huì)以為”Addnext0″更慢，因?yàn)樗龅氖虑楦唷跊](méi)進(jìn)到下個(gè)元素之前就需要裝載它的值。但實(shí)際的運(yùn)行結(jié)果令人驚訝——在某些小工作集下，”Addnext0″比”Inc”更快。這是為什么呢？原因在于，系統(tǒng)一般會(huì)對(duì)下一個(gè)元素進(jìn)行強(qiáng)制性預(yù)取。當(dāng)程序前進(jìn)到下個(gè)元素時(shí)，這個(gè)元素其實(shí)早已被預(yù)取在L1d里。因此，只要工作集比L2小，”Addnext0″的性能基本就能與”Follow”測(cè)試媲美。

但是，”Addnext0″比”Inc”更快離開L2，這是因?yàn)樗枰獜闹鞔嫜b載更多的數(shù)據(jù)。而在工作集達(dá)到221字節(jié)時(shí)，”Addnext0″的耗時(shí)達(dá)到了28個(gè)周期，是同期”Follow”14周期的兩倍。這個(gè)兩倍也很好解釋。”Addnext0″和”Inc”涉及對(duì)內(nèi)存的修改，因此L2的逐出操作不能簡(jiǎn)單地把數(shù)據(jù)一扔了事，而必須將它們寫入內(nèi)存。因此FSB的可用帶寬變成了一半，傳輸?shù)攘繑?shù)據(jù)的耗時(shí)也就變成了原來(lái)的兩倍。

圖3.14: 更大L2/L3緩存的優(yōu)勢(shì)

決定順序式緩存處理性能的另一個(gè)重要因素是緩存容量。雖然這一點(diǎn)比較明顯，但還是值得一說(shuō)。圖3.14展示了128字節(jié)長(zhǎng)元素的測(cè)試結(jié)果(64位機(jī)，NPAD=15)。這次我們比較三臺(tái)不同計(jì)算機(jī)的曲線，兩臺(tái)P4，一臺(tái)Core 2。兩臺(tái)P4的區(qū)別是緩存容量不同，一臺(tái)是32k的L1d和1M的L2，一臺(tái)是16K的L1d、512k的L2和2M的L3。Core 2那臺(tái)則是32k的L1d和4M的L2。

圖中最有趣的地方，并不是Core 2如何大勝兩臺(tái)P4，而是工作集開始增長(zhǎng)到連末級(jí)緩存也放不下、需要主存熱情參與之后的部分。

Set Size	Sequential	Random
L2 Hit	L2 Miss	#Iter	Ratio Miss/Hit	L2 Accesses Per Iter	L2 Hit	L2 Miss	#Iter	Ratio Miss/Hit	L2 Accesses Per Iter
220	88,636	843	16,384	0.94%	5.5	30,462	4721	1,024	13.42%	34.4
221	88,105	1,584	8,192	1.77%	10.9	21,817	15,151	512	40.98%	72.2
222	88,106	1,600	4,096	1.78%	21.9	22,258	22,285	256	50.03%	174.0
223	88,104	1,614	2,048	1.80%	43.8	27,521	26,274	128	48.84%	420.3
224	88,114	1,655	1,024	1.84%	87.7	33,166	29,115	64	46.75%	973.1
225	88,112	1,730	512	1.93%	175.5	39,858	32,360	32	44.81%	2,256.8
226	88,112	1,906	256	2.12%	351.6	48,539	38,151	16	44.01%	5,418.1
227	88,114	2,244	128	2.48%	705.9	62,423	52,049	8	45.47%	14,309.0
228	88,120	2,939	64	3.23%	1,422.8	81,906	87,167	4	51.56%	42,268.3
229	88,137	4,318	32	4.67%	2,889.2	119,079	163,398	2	57.84%	141,238.5

表3.2: 順序訪問(wèn)與隨機(jī)訪問(wèn)時(shí)L2命中與未命中的情況，NPAD=0

與我們預(yù)計(jì)的相似，最末級(jí)緩存越大，曲線停留在L2訪問(wèn)耗時(shí)區(qū)的時(shí)間越長(zhǎng)。在220字節(jié)的工作集時(shí)，第二臺(tái)P4(更老一些)比第一臺(tái)P4要快上一倍，這要完全歸功于更大的末級(jí)緩存。而Core 2拜它巨大的4M L2所賜，表現(xiàn)更為卓越。

對(duì)于隨機(jī)的工作負(fù)荷而言，可能沒(méi)有這么驚人的效果，但是，如果我們能將工作負(fù)荷進(jìn)行一些裁剪，讓它匹配末級(jí)緩存的容量，就完全可以得到非常大的性能提升。也是由于這個(gè)原因，有時(shí)候我們需要多花一些錢，買一個(gè)擁有更大緩存的處理器。

單線程隨機(jī)訪問(wèn)模式的測(cè)量

前面我們已經(jīng)看到，處理器能夠利用L1d到L2之間的預(yù)取消除訪問(wèn)主存、甚至是訪問(wèn)L2的時(shí)延。

圖3.15: 順序讀取vs隨機(jī)讀取，NPAD=0

但是，如果換成隨機(jī)訪問(wèn)或者不可預(yù)測(cè)的訪問(wèn)，情況就大不相同了。圖3.15比較了順序讀取與隨機(jī)讀取的耗時(shí)情況。

換成隨機(jī)之后，處理器無(wú)法再有效地預(yù)取數(shù)據(jù)，只有少數(shù)情況下靠運(yùn)氣剛好碰到先后訪問(wèn)的兩個(gè)元素挨在一起的情形。

圖3.15中有兩個(gè)需要關(guān)注的地方。首先，在大的工作集下需要非常多的周期。這臺(tái)機(jī)器訪問(wèn)主存的時(shí)間大約為200-300個(gè)周期，但圖中的耗時(shí)甚至超過(guò)了450個(gè)周期。我們前面已經(jīng)觀察到過(guò)類似現(xiàn)象(對(duì)比圖3.11)。這說(shuō)明，處理器的自動(dòng)預(yù)取在這里起到了反效果。

其次，代表隨機(jī)訪問(wèn)的曲線在各個(gè)階段不像順序訪問(wèn)那樣保持平坦，而是不斷攀升。為了解釋這個(gè)問(wèn)題，我們測(cè)量了程序在不同工作集下對(duì)L2的訪問(wèn)情況。結(jié)果如圖3.16和表3.2。

從圖中可以看出，當(dāng)工作集大小超過(guò)L2時(shí)，未命中率(L2未命中次數(shù)/L2訪問(wèn)次數(shù))開始上升。整條曲線的走向與圖3.15有些相似: 先急速爬升，隨后緩緩下滑，最后再度爬升。它與耗時(shí)圖有緊密的關(guān)聯(lián)。L2未命中率會(huì)一直爬升到100%為止。只要工作集足夠大(并且內(nèi)存也足夠大)，就可以將緩存線位于L2內(nèi)或處于裝載過(guò)程中的可能性降到非常低。

緩存未命中率的攀升已經(jīng)可以解釋一部分的開銷。除此以外，還有一個(gè)因素。觀察表3.2的L2/#Iter列，可以看到每個(gè)循環(huán)對(duì)L2的使用次數(shù)在增長(zhǎng)。由于工作集每次為上一次的兩倍，如果沒(méi)有緩存的話，內(nèi)存的訪問(wèn)次數(shù)也將是上一次的兩倍。在按順序訪問(wèn)時(shí)，由于緩存的幫助及完美的預(yù)見(jiàn)性，對(duì)L2使用的增長(zhǎng)比較平緩，完全取決于工作集的增長(zhǎng)速度。

圖3.16: L2d未命中率

圖3.17: 頁(yè)意義上(Page-Wise)的隨機(jī)化，NPAD=7

而換成隨機(jī)訪問(wèn)后，單位耗時(shí)的增長(zhǎng)超過(guò)了工作集的增長(zhǎng)，根源是TLB未命中率的上升。圖3.17描繪的是NPAD=7時(shí)隨機(jī)訪問(wèn)的耗時(shí)情況。這一次，我們修改了隨機(jī)訪問(wèn)的方式。正常情況下是把整個(gè)列表作為一個(gè)塊進(jìn)行隨機(jī)(以∞表示)，而其它11條線則是在小一些的塊里進(jìn)行隨機(jī)。例如，標(biāo)簽為’60′的線表示以60頁(yè)(245760字節(jié))為單位進(jìn)行隨機(jī)。先遍歷完這個(gè)塊里的所有元素，再訪問(wèn)另一個(gè)塊。這樣一來(lái)，可以保證任意時(shí)刻使用的TLB條目數(shù)都是有限的。 NPAD=7對(duì)應(yīng)于64字節(jié)，正好等于緩存線的長(zhǎng)度。由于元素順序隨機(jī)，硬件預(yù)取不可能有任何效果，特別是在元素較多的情況下。這意味著，分塊隨機(jī)時(shí)的L2未命中率與整個(gè)列表隨機(jī)時(shí)的未命中率沒(méi)有本質(zhì)的差別。隨著塊的增大，曲線逐漸逼近整個(gè)列表隨機(jī)對(duì)應(yīng)的曲線。這說(shuō)明，在這個(gè)測(cè)試?yán)铮阅苁艿絋LB命中率的影響很大，如果我們能提高TLB命中率，就能大幅度地提升性能(在后面的一個(gè)例子里，性能提升了38%之多)。

3.3.3 寫入時(shí)的行為

在我們開始研究多個(gè)線程或進(jìn)程同時(shí)使用相同內(nèi)存之前，先來(lái)看一下緩存實(shí)現(xiàn)的一些細(xì)節(jié)。我們要求緩存是一致的，而且這種一致性必須對(duì)用戶級(jí)代碼完全透明。而內(nèi)核代碼則有所不同，它有時(shí)候需要對(duì)緩存進(jìn)行轉(zhuǎn)儲(chǔ)(flush)。

這意味著，如果對(duì)緩存線進(jìn)行了修改，那么在這個(gè)時(shí)間點(diǎn)之后，系統(tǒng)的結(jié)果應(yīng)該是與沒(méi)有緩存的情況下是相同的，即主存的對(duì)應(yīng)位置也已經(jīng)被修改的狀態(tài)。這種要求可以通過(guò)兩種方式或策略實(shí)現(xiàn)：

寫通(write-through)
寫回(write-back)

寫通比較簡(jiǎn)單。當(dāng)修改緩存線時(shí)，處理器立即將它寫入主存。這樣可以保證主存與緩存的內(nèi)容永遠(yuǎn)保持一致。當(dāng)緩存線被替代時(shí)，只需要簡(jiǎn)單地將它丟棄即可。這種策略很簡(jiǎn)單，但是速度比較慢。如果某個(gè)程序反復(fù)修改一個(gè)本地變量，可能導(dǎo)致FSB上產(chǎn)生大量數(shù)據(jù)流，而不管這個(gè)變量是不是有人在用，或者是不是短期變量。

寫回比較復(fù)雜。當(dāng)修改緩存線時(shí)，處理器不再馬上將它寫入主存，而是打上已弄臟(dirty)的標(biāo)記。當(dāng)以后某個(gè)時(shí)間點(diǎn)緩存線被丟棄時(shí)，這個(gè)已弄臟標(biāo)記會(huì)通知處理器把數(shù)據(jù)寫回到主存中，而不是簡(jiǎn)單地扔掉。

寫回有時(shí)候會(huì)有非常不錯(cuò)的性能，因此較好的系統(tǒng)大多采用這種方式。采用寫回時(shí)，處理器們甚至可以利用FSB的空閑容量來(lái)存儲(chǔ)緩存線。這樣一來(lái)，當(dāng)需要緩存空間時(shí)，處理器只需清除臟標(biāo)記，丟棄緩存線即可。

但寫回也有一個(gè)很大的問(wèn)題。當(dāng)有多個(gè)處理器(或核心、超線程)訪問(wèn)同一塊內(nèi)存時(shí)，必須確保它們?cè)谌魏螘r(shí)候看到的都是相同的內(nèi)容。如果緩存線在其中一個(gè)處理器上弄臟了(修改了，但還沒(méi)寫回主存)，而第二個(gè)處理器剛好要讀取同一個(gè)內(nèi)存地址，那么這個(gè)讀操作不能去讀主存，而需要讀第一個(gè)處理器的緩存線。在下一節(jié)中，我們將研究如何實(shí)現(xiàn)這種需求。

在此之前，還有其它兩種緩存策略需要提一下:

寫入合并
不可緩存

這兩種策略用于真實(shí)內(nèi)存不支持的特殊地址區(qū)，內(nèi)核為地址區(qū)設(shè)置這些策略(x86處理器利用內(nèi)存類型范圍寄存器MTRR)，余下的部分自動(dòng)進(jìn)行。MTRR還可用于寫通和寫回策略的選擇。

寫入合并是一種有限的緩存優(yōu)化策略，更多地用于顯卡等設(shè)備之上的內(nèi)存。由于設(shè)備的傳輸開銷比本地內(nèi)存要高的多，因此避免進(jìn)行過(guò)多的傳輸顯得尤為重要。如果僅僅因?yàn)樾薷牧司彺婢€上的一個(gè)字，就傳輸整條線，而下個(gè)操作剛好是修改線上的下一個(gè)字，那么這次傳輸就過(guò)于浪費(fèi)了。而這恰恰對(duì)于顯卡來(lái)說(shuō)是比較常見(jiàn)的情形——屏幕上水平鄰接的像素往往在內(nèi)存中也是靠在一起的。顧名思義，寫入合并是在寫出緩存線前，先將多個(gè)寫入訪問(wèn)合并起來(lái)。在理想的情況下，緩存線被逐字逐字地修改，只有當(dāng)寫入最后一個(gè)字時(shí)，才將整條線寫入內(nèi)存，從而極大地加速內(nèi)存的訪問(wèn)。

最后來(lái)講一下不可緩存的內(nèi)存。一般指的是不被RAM支持的內(nèi)存位置，它可以是硬編碼的特殊地址，承擔(dān)CPU以外的某些功能。對(duì)于商用硬件來(lái)說(shuō)，比較常見(jiàn)的是映射到外部卡或設(shè)備的地址。在嵌入式主板上，有時(shí)也有類似的地址，用來(lái)開關(guān)LED。對(duì)這些地址進(jìn)行緩存顯然沒(méi)有什么意義。比如上述的LED，一般是用來(lái)調(diào)試或報(bào)告狀態(tài)，顯然應(yīng)該盡快點(diǎn)亮或關(guān)閉。而對(duì)于那些PCI卡上的內(nèi)存，由于不需要CPU的干涉即可更改，也不該緩存。

3.3.4 多處理器支持

在上節(jié)中我們已經(jīng)指出當(dāng)多處理器開始發(fā)揮作用的時(shí)候所遇到的問(wèn)題。甚至對(duì)于那些不共享的高速級(jí)別的緩存（至少在L1d級(jí)別）的多核處理器也有問(wèn)題。

直接提供從一個(gè)處理器到另一處理器的高速訪問(wèn)，這是完全不切實(shí)際的。從一開始，連接速度根本就不夠快。實(shí)際的選擇是，在其需要的情況下，轉(zhuǎn)移到其他處理器。需要注意的是，這同樣應(yīng)用在相同處理器上無(wú)需共享的高速緩存。

現(xiàn)在的問(wèn)題是，當(dāng)該高速緩存線轉(zhuǎn)移的時(shí)候會(huì)發(fā)生什么？這個(gè)問(wèn)題回答起來(lái)相當(dāng)容易：當(dāng)一個(gè)處理器需要在另一個(gè)處理器的高速緩存中讀或者寫的臟的高速緩存線的時(shí)候。但怎樣處理器怎樣確定在另一個(gè)處理器的緩存中的高速緩存線是臟的？假設(shè)它僅僅是因?yàn)橐粋€(gè)高速緩存線被另一個(gè)處理器加載將是次優(yōu)的（最好的）。通常情況下，大多數(shù)的內(nèi)存訪問(wèn)是只讀的訪問(wèn)和產(chǎn)生高速緩存線，并不臟。在高速緩存線上處理器頻繁的操作（當(dāng)然，否則為什么我們有這樣的文件呢？），也就意味著每一次寫訪問(wèn)后，都要廣播關(guān)于高速緩存線的改變將變得不切實(shí)際。

多年來(lái)，人們開發(fā)除了MESI緩存一致性協(xié)議(MESI=Modified, Exclusive, Shared, Invalid，變更的、獨(dú)占的、共享的、無(wú)效的)。協(xié)議的名稱來(lái)自協(xié)議中緩存線可以進(jìn)入的四種狀態(tài):

變更的: 本地處理器修改了緩存線。同時(shí)暗示，它是所有緩存中唯一的拷貝。
獨(dú)占的: 緩存線沒(méi)有被修改，而且沒(méi)有被裝入其它處理器緩存。
共享的: 緩存線沒(méi)有被修改，但可能已被裝入其它處理器緩存。
無(wú)效的: 緩存線無(wú)效，即，未被使用。

MESI協(xié)議開發(fā)了很多年，最初的版本比較簡(jiǎn)單，但是效率也比較差?，F(xiàn)在的版本通過(guò)以上4個(gè)狀態(tài)可以有效地實(shí)現(xiàn)寫回式緩存，同時(shí)支持不同處理器對(duì)只讀數(shù)據(jù)的并發(fā)訪問(wèn)。

圖3.18: MESI協(xié)議的狀態(tài)躍遷圖

在協(xié)議中，通過(guò)處理器監(jiān)聽(tīng)其它處理器的活動(dòng)，不需太多努力即可實(shí)現(xiàn)狀態(tài)變更。處理器將操作發(fā)布在外部引腳上，使外部可以了解到處理過(guò)程。目標(biāo)的緩存線地址則可以在地址總線上看到。在下文講述狀態(tài)時(shí)，我們將介紹總線參與的時(shí)機(jī)。

一開始，所有緩存線都是空的，緩存為無(wú)效(Invalid)狀態(tài)。當(dāng)有數(shù)據(jù)裝進(jìn)緩存供寫入時(shí)，緩存變?yōu)樽兏?Modified)狀態(tài)。如果有數(shù)據(jù)裝進(jìn)緩存供讀取，那么新?tīng)顟B(tài)取決于其它處理器是否已經(jīng)狀態(tài)了同一條緩存線。如果是，那么新?tīng)顟B(tài)變成共享(Shared)狀態(tài)，否則變成獨(dú)占(Exclusive)狀態(tài)。

如果本地處理器對(duì)某條Modified緩存線進(jìn)行讀寫，那么直接使用緩存內(nèi)容，狀態(tài)保持不變。如果另一個(gè)處理器希望讀它，那么第一個(gè)處理器將內(nèi)容發(fā)給第一個(gè)處理器，然后可以將緩存狀態(tài)置為Shared。而發(fā)給第二個(gè)處理器的數(shù)據(jù)由內(nèi)存控制器接收，并放入內(nèi)存中。如果這一步?jīng)]有發(fā)生，就不能將這條線置為Shared。如果第二個(gè)處理器希望的是寫，那么第一個(gè)處理器將內(nèi)容發(fā)給它后，將緩存置為Invalid。這就是臭名昭著的”請(qǐng)求所有權(quán)(Request For Ownership,RFO)”操作。在末級(jí)緩存執(zhí)行RFO操作的代價(jià)比較高。如果是寫通式緩存，還要加上將內(nèi)容寫入上一層緩存或主存的時(shí)間，進(jìn)一步提升了代價(jià)。 對(duì)于Shared緩存線，本地處理器的讀取操作并不需要修改狀態(tài)，而且可以直接從緩存滿足。而本地處理器的寫入操作則需要將狀態(tài)置為Modified，而且需要將緩存線在其它處理器的所有拷貝置為Invalid。因此，這個(gè)寫入操作需要通過(guò)RFO消息發(fā)通知其它處理器。如果第二個(gè)處理器請(qǐng)求讀取，無(wú)事發(fā)生。因?yàn)橹鞔嬉呀?jīng)包含了當(dāng)前數(shù)據(jù)，而且狀態(tài)已經(jīng)為Shared。如果第二個(gè)處理器需要寫入，則將緩存線置為Invalid。不需要總線操作。

Exclusive狀態(tài)與Shared狀態(tài)很像，只有一個(gè)不同之處: 在Exclusive狀態(tài)時(shí)，本地寫入操作不需要在總線上聲明，因?yàn)楸镜氐木彺媸窍到y(tǒng)中唯一的拷貝。這是一個(gè)巨大的優(yōu)勢(shì)，所以處理器會(huì)盡量將緩存線保留在Exclusive狀態(tài)，而不是Shared狀態(tài)。只有在信息不可用時(shí)，才退而求其次選擇shared。放棄Exclusive不會(huì)引起任何功能缺失，但會(huì)導(dǎo)致性能下降，因?yàn)镋→M要遠(yuǎn)遠(yuǎn)快于S→M。

從以上的說(shuō)明中應(yīng)該已經(jīng)可以看出，在多處理器環(huán)境下，哪一步的代價(jià)比較大了。填充緩存的代價(jià)當(dāng)然還是很高，但我們還需要留意RFO消息。一旦涉及RFO，操作就快不起來(lái)了。

RFO在兩種情況下是必需的:

線程從一個(gè)處理器遷移到另一個(gè)處理器，需要將所有緩存線移到新處理器。
某條緩存線確實(shí)需要被兩個(gè)處理器使用。{對(duì)于同一處理器的兩個(gè)核心，也有同樣的情況，只是代價(jià)稍低。RFO消息可能會(huì)被發(fā)送多次。}

多線程或多進(jìn)程的程序總是需要同步，而這種同步依賴內(nèi)存來(lái)實(shí)現(xiàn)。因此，有些RFO消息是合理的，但仍然需要盡量降低發(fā)送頻率。除此以外，還有其它來(lái)源的RFO。在第6節(jié)中，我們將解釋這些場(chǎng)景。緩存一致性協(xié)議的消息必須發(fā)給系統(tǒng)中所有處理器。只有當(dāng)協(xié)議確定已經(jīng)給過(guò)所有處理器響應(yīng)機(jī)會(huì)之后，才能進(jìn)行狀態(tài)躍遷。也就是說(shuō)，協(xié)議的速度取決于最長(zhǎng)響應(yīng)時(shí)間。{這也是現(xiàn)在能看到三插槽AMD Opteron系統(tǒng)的原因。這類系統(tǒng)只有三個(gè)超級(jí)鏈路(hyperlink)，其中一個(gè)連接南橋，每個(gè)處理器之間都只有一跳的距離。}總線上可能會(huì)發(fā)生沖突，NUMA系統(tǒng)的延時(shí)很大，突發(fā)的流量會(huì)拖慢通信。這些都是讓我們避免無(wú)謂流量的充足理由。

此外，關(guān)于多處理器還有一個(gè)問(wèn)題。雖然它的影響與具體機(jī)器密切相關(guān)，但根源是唯一的——FSB是共享的。在大多數(shù)情況下，所有處理器通過(guò)唯一的總線連接到內(nèi)存控制器(參見(jiàn)圖2.1)。如果一個(gè)處理器就能占滿總線(十分常見(jiàn))，那么共享總線的兩個(gè)或四個(gè)處理器顯然只會(huì)得到更有限的帶寬。

即使每個(gè)處理器有自己連接內(nèi)存控制器的總線，如圖2.2，但還需要通往內(nèi)存模塊的總線。一般情況下，這種總線只有一條。退一步說(shuō)，即使像圖2.2那樣不止一條，對(duì)同一個(gè)內(nèi)存模塊的并發(fā)訪問(wèn)也會(huì)限制它的帶寬。

對(duì)于每個(gè)處理器擁有本地內(nèi)存的AMD模型來(lái)說(shuō)，也是同樣的問(wèn)題。的確，所有處理器可以非?？焖俚赝瑫r(shí)訪問(wèn)它們自己的內(nèi)存。但是，多線程呢？多進(jìn)程呢？它們?nèi)匀恍枰ㄟ^(guò)訪問(wèn)同一塊內(nèi)存來(lái)進(jìn)行同步。

對(duì)同步來(lái)說(shuō)，有限的帶寬嚴(yán)重地制約著并發(fā)度。程序需要更加謹(jǐn)慎的設(shè)計(jì)，將不同處理器訪問(wèn)同一塊內(nèi)存的機(jī)會(huì)降到最低。以下的測(cè)試展示了這一點(diǎn)，還展示了與多線程代碼相關(guān)的其它效果。

多線程測(cè)量

為了幫助大家理解問(wèn)題的嚴(yán)重性，我們來(lái)看一些曲線圖，主角也是前文的那個(gè)程序。只不過(guò)這一次，我們運(yùn)行多個(gè)線程，并測(cè)量這些線程中最快那個(gè)的運(yùn)行時(shí)間。也就是說(shuō)，等它們?nèi)窟\(yùn)行完是需要更長(zhǎng)時(shí)間的。我們用的機(jī)器有4個(gè)處理器，而測(cè)試是做多跑4個(gè)線程。所有處理器共享同一條通往內(nèi)存控制器的總線，另外，通往內(nèi)存模塊的總線也只有一條。

圖3.19: 順序讀操作，多線程

圖3.19展示了順序讀訪問(wèn)時(shí)的性能，元素為128字節(jié)長(zhǎng)(64位計(jì)算機(jī)，NPAD=15)。對(duì)于單線程的曲線，我們預(yù)計(jì)是與圖3.11相似，只不過(guò)是換了一臺(tái)機(jī)器，所以實(shí)際的數(shù)字會(huì)有些小差別。

更重要的部分當(dāng)然是多線程的環(huán)節(jié)。由于是只讀，不會(huì)去修改內(nèi)存，不會(huì)嘗試同步。但即使不需要RFO，而且所有緩存線都可共享，性能仍然分別下降了18%(雙線程)和34%(四線程)。由于不需要在處理器之間傳輸緩存，因此這里的性能下降完全由以下兩個(gè)瓶頸之一或同時(shí)引起: 一是從處理器到內(nèi)存控制器的共享總線，二是從內(nèi)存控制器到內(nèi)存模塊的共享總線。當(dāng)工作集超過(guò)L3后，三種情況下都要預(yù)取新元素，而即使是雙線程，可用的帶寬也無(wú)法滿足線性擴(kuò)展(無(wú)懲罰)。

當(dāng)加入修改之后，場(chǎng)面更加難看了。圖3.20展示了順序遞增測(cè)試的結(jié)果。

圖3.20: 順序遞增，多線程

圖中Y軸采用的是對(duì)數(shù)刻度，不要被看起來(lái)很小的差值欺騙了?，F(xiàn)在，雙線程的性能懲罰仍然是18%，但四線程的懲罰飆升到了93%！原因在于，采用四線程時(shí)，預(yù)取的流量與寫回的流量加在一起，占滿了整個(gè)總線。

我們用對(duì)數(shù)刻度來(lái)展示L1d范圍的結(jié)果?？梢园l(fā)現(xiàn)，當(dāng)超過(guò)一個(gè)線程后，L1d就無(wú)力了。單線程時(shí)，僅當(dāng)工作集超過(guò)L1d時(shí)訪問(wèn)時(shí)間才會(huì)超過(guò)20個(gè)周期，而多線程時(shí)，即使在很小的工作集情況下，訪問(wèn)時(shí)間也達(dá)到了那個(gè)水平。

這里并沒(méi)有揭示問(wèn)題的另一方面，主要是用這個(gè)程序很難進(jìn)行測(cè)量。問(wèn)題是這樣的，我們的測(cè)試程序修改了內(nèi)存，所以本應(yīng)看到RFO的影響，但在結(jié)果中，我們并沒(méi)有在L2階段看到更大的開銷。原因在于，要看到RFO的影響，程序必須使用大量?jī)?nèi)存，而且所有線程必須同時(shí)訪問(wèn)同一塊內(nèi)存。如果沒(méi)有大量的同步，這是很難實(shí)現(xiàn)的，而如果加入同步，則會(huì)占滿執(zhí)行時(shí)間。

圖3.21: 隨機(jī)的Addnextlast，多線程

最后，在圖3.21中，我們展示了隨機(jī)訪問(wèn)的Addnextlast測(cè)試的結(jié)果。這里主要是為了讓大家感受一下這些巨大到爆的數(shù)字。極端情況下，甚至用了1500個(gè)周期才處理完一個(gè)元素。如果加入更多線程，真是不可想象哪。我們把多線程的效能總結(jié)了一下:

#Threads	Seq Read	Seq Inc	Rand Add
2	1.69	1.69	1.54
4	2.98	2.07	1.65

表3.3: 多線程的效能

這個(gè)表展示了圖3.21中多線程運(yùn)行大工作集時(shí)的效能。表中的數(shù)字表示測(cè)試程序在使用多線程處理大工作集時(shí)可能達(dá)到的最大加速因子。雙線程和四線程的理論最大加速因子分別是2和4。從表中數(shù)據(jù)來(lái)看，雙線程的結(jié)果還能接受，但四線程的結(jié)果表明，擴(kuò)展到雙線程以上是沒(méi)有什么意義的，帶來(lái)的收益可以忽略不計(jì)。只要我們把圖3.21換個(gè)方式呈現(xiàn)，就可以很容易看清這一點(diǎn)。

圖3.22: 通過(guò)并行化實(shí)現(xiàn)的加速因子

圖3.22中的曲線展示了加速因子，即多線程相對(duì)于單線程所能獲取的性能加成值。測(cè)量值的精確度有限，因此我們需要忽略比較小的那些數(shù)字。可以看到，在L2與L3范圍內(nèi)，多線程基本可以做到線性加速，雙線程和四線程分別達(dá)到了2和4的加速因子。但是，一旦工作集的大小超出L3，曲線就崩塌了，雙線程和四線程降到了基本相同的數(shù)值(參見(jiàn)表3.3中第4列)。也是部分由于這個(gè)原因，我們很少看到4CPU以上的主板共享同一個(gè)內(nèi)存控制器。如果需要配置更多處理器，我們只能選擇其它的實(shí)現(xiàn)方式(參見(jiàn)第5節(jié))。

可惜，上圖中的數(shù)據(jù)并不是普遍情況。在某些情況下，即使工作集能夠放入末級(jí)緩存，也無(wú)法實(shí)現(xiàn)線性加速。實(shí)際上，這反而是正常的，因?yàn)槠胀ǖ木€程都有一定的耦合關(guān)系，不會(huì)像我們的測(cè)試程序這樣完全獨(dú)立。而反過(guò)來(lái)說(shuō)，即使是很大的工作集，即使是兩個(gè)以上的線程，也是可以通過(guò)并行化受益的，但是需要程序員的聰明才智。我們會(huì)在第6節(jié)進(jìn)行一些介紹。

特例: 超線程

由CPU實(shí)現(xiàn)的超線程(有時(shí)又叫對(duì)稱多線程，SMT)是一種比較特殊的情況，每個(gè)線程并不能真正并發(fā)地運(yùn)行。它們共享著除寄存器外的絕大多數(shù)處理資源。每個(gè)核心和CPU仍然是并行工作的，但核心上的線程則受到這個(gè)限制。理論上，每個(gè)核心可以有大量線程，不過(guò)到目前為止，Intel的CPU最多只有兩個(gè)線程。CPU負(fù)責(zé)對(duì)各線程進(jìn)行時(shí)分復(fù)用，但這種復(fù)用本身并沒(méi)有多少厲害。它真正的優(yōu)勢(shì)在于，CPU可以在當(dāng)前運(yùn)行的超線程發(fā)生延遲時(shí)，調(diào)度另一個(gè)線程。這種延遲一般由內(nèi)存訪問(wèn)引起。

如果兩個(gè)線程運(yùn)行在一個(gè)超線程核心上，那么只有當(dāng)兩個(gè)線程合起來(lái)的運(yùn)行時(shí)間少于單線程運(yùn)行時(shí)間時(shí)，效率才會(huì)比較高。我們可以將通常先后發(fā)生的內(nèi)存訪問(wèn)疊合在一起，以實(shí)現(xiàn)這個(gè)目標(biāo)。有一個(gè)簡(jiǎn)單的計(jì)算公式，可以幫助我們計(jì)算如果需要某個(gè)加速因子，最少需要多少的緩存命中率。

程序的執(zhí)行時(shí)間可以通過(guò)一個(gè)只有一級(jí)緩存的簡(jiǎn)單模型來(lái)進(jìn)行估算(參見(jiàn)[htimpact]):

Texe= N[(1-Fmem)Tproc+ Fmem(GhitTcache+ (1-Ghit)Tmiss)]

各變量的含義如下:

N	=	指令數(shù)
Fmem	=	N中訪問(wèn)內(nèi)存的比例
Ghit	=	命中緩存的比例
Tproc	=	每條指令所用的周期數(shù)
Tcache	=	緩存命中所用的周期數(shù)
Tmiss	=	緩沖未命中所用的周期數(shù)
Texe	=	程序的執(zhí)行時(shí)間

為了讓任何判讀使用雙線程，兩個(gè)線程之中任一線程的執(zhí)行時(shí)間最多為單線程指令的一半。兩者都有一個(gè)唯一的變量緩存命中數(shù)。 如果我們要解決最小緩存命中率相等的問(wèn)題需要使我們獲得的線程的執(zhí)行率不少于50%或更多，如圖 3.23.

圖3.23: 最小緩存命中率-加速

X軸表示單線程指令的緩存命中率Ghit，Y軸表示多線程指令所需的緩存命中率。這個(gè)值永遠(yuǎn)不能高于單線程命中率，否則，單線程指令也會(huì)使用改良的指令。為了使單線程的命中率在低于55%的所有情況下優(yōu)于使用多線程，cup要或多或少的足夠空閑因?yàn)榫彺鎭G失會(huì)運(yùn)行另外一個(gè)超線程。

綠色區(qū)域是我們的目標(biāo)。如果線程的速度沒(méi)有慢過(guò)50%，而每個(gè)線程的工作量只有原來(lái)的一半，那么它們合起來(lái)的耗時(shí)應(yīng)該會(huì)少于單線程的耗時(shí)。對(duì)我們用的示例系統(tǒng)來(lái)說(shuō)(使用超線程的P4機(jī)器)，如果單線程代碼的命中率為60%，那么多線程代碼至少要達(dá)到10%才能獲得收益。這個(gè)要求一般來(lái)說(shuō)還是可以做到的。但是，如果單線程代碼的命中率達(dá)到了95%，那么多線程代碼要做到80%才行。這就很難了。而且，這里還涉及到超線程，在兩個(gè)超線程的情況下，每個(gè)超線程只能分到一半的有效緩存。因?yàn)樗谐€程是使用同一個(gè)緩存來(lái)裝載數(shù)據(jù)的，如果兩個(gè)超線程的工作集沒(méi)有重疊，那么原始的95%也會(huì)被打?qū)φ邸?7%，遠(yuǎn)低于80%。

因此，超線程只在某些情況下才比較有用。單線程代碼的緩存命中率必須低到一定程度，從而使緩存容量變小時(shí)新的命中率仍能滿足要求。只有在這種情況下，超線程才是有意義的。在實(shí)踐中，采用超線程能否獲得更快的結(jié)果，取決于處理器能否有效地將每個(gè)進(jìn)程的等待時(shí)間與其它進(jìn)程的執(zhí)行時(shí)間重疊在一起。并行化也需要一定的開銷，需要加到總的運(yùn)行時(shí)間里，這個(gè)開銷往往是不能忽略的。

在6.3.4節(jié)中，我們會(huì)介紹一種技術(shù)，它將多個(gè)線程通過(guò)公用緩存緊密地耦合起來(lái)。這種技術(shù)適用于許多場(chǎng)合，前提是程序員們樂(lè)意花費(fèi)時(shí)間和精力擴(kuò)展自己的代碼。

如果兩個(gè)超線程執(zhí)行完全不同的代碼(兩個(gè)線程就像被當(dāng)成兩個(gè)處理器，分別執(zhí)行不同進(jìn)程)，那么緩存容量就真的會(huì)降為一半，導(dǎo)致緩沖未命中率大為攀升，這一點(diǎn)應(yīng)該是很清楚的。這樣的調(diào)度機(jī)制是很有問(wèn)題的，除非你的緩存足夠大。所以，除非程序的工作集設(shè)計(jì)得比較合理，能夠確實(shí)從超線程獲益，否則還是建議在BIOS中把超線程功能關(guān)掉。{我們可能會(huì)因?yàn)榱硪粋€(gè)原因開啟超線程，那就是調(diào)試，因?yàn)镾MT在查找并行代碼的問(wèn)題方面真的非常好用。}

3.3.5 其它細(xì)節(jié)

我們已經(jīng)介紹了地址的組成，即標(biāo)簽、集合索引和偏移三個(gè)部分。那么，實(shí)際會(huì)用到什么樣的地址呢？目前，處理器一般都向進(jìn)程提供虛擬地址空間，意味著我們有兩種不同的地址: 虛擬地址和物理地址。

虛擬地址有個(gè)問(wèn)題——并不唯一。隨著時(shí)間的變化，虛擬地址可以變化，指向不同的物理地址。同一個(gè)地址在不同的進(jìn)程里也可以表示不同的物理地址。那么，是不是用物理地址會(huì)比較好呢？

問(wèn)題是，處理器指令用的虛擬地址，而且需要在內(nèi)存管理單元(MMU)的協(xié)助下將它們翻譯成物理地址。這并不是一個(gè)很小的操作。在執(zhí)行指令的管線(pipeline)中，物理地址只能在很后面的階段才能得到。這意味著，緩存邏輯需要在很短的時(shí)間里判斷地址是否已被緩存過(guò)。而如果可以使用虛擬地址，緩存查找操作就可以更早地發(fā)生，一旦命中，就可以馬上使用內(nèi)存的內(nèi)容。結(jié)果就是，使用虛擬內(nèi)存后，可以讓管線把更多內(nèi)存訪問(wèn)的開銷隱藏起來(lái)。

處理器的設(shè)計(jì)人員們現(xiàn)在使用虛擬地址來(lái)標(biāo)記第一級(jí)緩存。這些緩存很小，很容易被清空。在進(jìn)程頁(yè)表樹發(fā)生變更的情況下，至少是需要清空部分緩存的。如果處理器擁有指定變更地址范圍的指令，那么可以避免緩存的完全刷新。由于一級(jí)緩存L1i及L1d的時(shí)延都很小(~3周期)，基本上必須使用虛擬地址。

對(duì)于更大的緩存，包括L2和L3等，則需要以物理地址作為標(biāo)簽。因?yàn)檫@些緩存的時(shí)延比較大，虛擬到物理地址的映射可以在允許的時(shí)間里完成，而且由于主存時(shí)延的存在，重新填充這些緩存會(huì)消耗比較長(zhǎng)的時(shí)間，刷新的代價(jià)比較昂貴。

一般來(lái)說(shuō)，我們并不需要了解這些緩存處理地址的細(xì)節(jié)。我們不能更改它們，而那些可能影響性能的因素，要么是應(yīng)該避免的，要么是有很高代價(jià)的。填滿緩存是不好的行為，緩存線都落入同一個(gè)集合，也會(huì)讓緩存早早地出問(wèn)題。對(duì)于后一個(gè)問(wèn)題，可以通過(guò)緩存虛擬地址來(lái)避免，但作為一個(gè)用戶級(jí)程序，是不可能避免緩存物理地址的。我們唯一可以做的，是盡最大努力不要在同一個(gè)進(jìn)程里用多個(gè)虛擬地址映射同一個(gè)物理地址。

另一個(gè)細(xì)節(jié)對(duì)程序員們來(lái)說(shuō)比較乏味，那就是緩存的替換策略。大多數(shù)緩存會(huì)優(yōu)先逐出最近最少使用(Least Recently Used,LRU)的元素。這往往是一個(gè)效果比較好的策略。在關(guān)聯(lián)性很大的情況下(隨著以后核心數(shù)的增加，關(guān)聯(lián)性勢(shì)必會(huì)變得越來(lái)越大)，維護(hù)LRU列表變得越來(lái)越昂貴，于是我們開始看到其它的一些策略。

在緩存的替換策略方面，程序員可以做的事情不多。如果緩存使用物理地址作為標(biāo)簽，我們是無(wú)法找出虛擬地址與緩存集之間關(guān)聯(lián)的。有可能會(huì)出現(xiàn)這樣的情形: 所有邏輯頁(yè)中的緩存線都映射到同一個(gè)緩存集，而其它大部分緩存卻空閑著。即使有這種情況，也只能依靠OS進(jìn)行合理安排，避免頻繁出現(xiàn)。

虛擬化的出現(xiàn)使得這一切變得更加復(fù)雜。現(xiàn)在不僅操作系統(tǒng)可以控制物理內(nèi)存的分配。虛擬機(jī)監(jiān)視器（VMM，也稱為hypervisor）也負(fù)責(zé)分配內(nèi)存。

對(duì)程序員來(lái)說(shuō)，最好 a) 完全使用邏輯內(nèi)存頁(yè)面b) 在有意義的情況下，使用盡可能大的頁(yè)面大小來(lái)分散物理地址。更大的頁(yè)面大小也有其他好處，不過(guò)這是另一個(gè)話題（見(jiàn)第4節(jié)）。

3.4 指令緩存

其實(shí)，不光處理器使用的數(shù)據(jù)被緩存，它們執(zhí)行的指令也是被緩存的。只不過(guò)，指令緩存的問(wèn)題相對(duì)來(lái)說(shuō)要少得多，因?yàn)?

執(zhí)行的代碼量取決于代碼大小。而代碼大小通常取決于問(wèn)題復(fù)雜度。問(wèn)題復(fù)雜度則是固定的。
程序的數(shù)據(jù)處理邏輯是程序員設(shè)計(jì)的，而程序的指令卻是編譯器生成的。編譯器的作者知道如何生成優(yōu)良的代碼。
程序的流向比數(shù)據(jù)訪問(wèn)模式更容易預(yù)測(cè)。現(xiàn)如今的CPU很擅長(zhǎng)模式檢測(cè)，對(duì)預(yù)取很有利。
代碼永遠(yuǎn)都有良好的時(shí)間局部性和空間局部性。

有一些準(zhǔn)則是需要程序員們遵守的，但大都是關(guān)于如何使用工具的，我們會(huì)在第6節(jié)介紹它們。而在這里我們只介紹一下指令緩存的技術(shù)細(xì)節(jié)。

隨著CPU的核心頻率大幅上升，緩存與核心的速度差越拉越大，CPU的處理開始管線化。也就是說(shuō)，指令的執(zhí)行分成若干階段。首先，對(duì)指令進(jìn)行解碼，隨后，準(zhǔn)備參數(shù)，最后，執(zhí)行它。這樣的管線可以很長(zhǎng)(例如，Intel的Netburst架構(gòu)超過(guò)了20個(gè)階段)。在管線很長(zhǎng)的情況下，一旦發(fā)生延誤(即指令流中斷)，需要很長(zhǎng)時(shí)間才能恢復(fù)速度。管線延誤發(fā)生在這樣的情況下: 下一條指令未能正確預(yù)測(cè)，或者裝載下一條指令耗時(shí)過(guò)長(zhǎng)(例如，需要從內(nèi)存讀取時(shí))。

為了解決這個(gè)問(wèn)題，CPU的設(shè)計(jì)人員們?cè)诜种ьA(yù)測(cè)上投入大量時(shí)間和芯片資產(chǎn)(chip real estate)，以降低管線延誤的出現(xiàn)頻率。

在CISC處理器上，指令的解碼階段也需要一些時(shí)間。x86及x86-64處理器尤為嚴(yán)重。近年來(lái)，這些處理器不再將指令的原始字節(jié)序列存入L1i，而是緩存解碼后的版本。這樣的L1i被叫做“追蹤緩存(trace cache)”。追蹤緩存可以在命中的情況下讓處理器跳過(guò)管線最初的幾個(gè)階段，在管線發(fā)生延誤時(shí)尤其有用。

前面說(shuō)過(guò)，L2以上的緩存是統(tǒng)一緩存，既保存代碼，也保存數(shù)據(jù)。顯然，這里保存的代碼是原始字節(jié)序列，而不是解碼后的形式。

在提高性能方面，與指令緩存相關(guān)的只有很少的幾條準(zhǔn)則:

生成盡量少的代碼。也有一些例外，如出于管線化的目的需要更多的代碼，或使用小代碼會(huì)帶來(lái)過(guò)高的額外開銷。
盡量幫助處理器作出良好的預(yù)取決策，可以通過(guò)代碼布局或顯式預(yù)取來(lái)實(shí)現(xiàn)。

這些準(zhǔn)則一般會(huì)由編譯器的代碼生成階段強(qiáng)制執(zhí)行。至于程序員可以參與的部分，我們會(huì)在第6節(jié)介紹。

3.4.1 自修改的代碼

在計(jì)算機(jī)的早期歲月里，內(nèi)存十分昂貴。人們想盡千方百計(jì)，只為了盡量壓縮程序容量，給數(shù)據(jù)多留一些空間。其中，有一種方法是修改程序自身，稱為自修改代碼(SMC)?，F(xiàn)在，有時(shí)候我們還能看到它，一般是出于提高性能的目的，也有的是為了攻擊安全漏洞。

一般情況下，應(yīng)該避免SMC。雖然一般情況下沒(méi)有問(wèn)題，但有時(shí)會(huì)由于執(zhí)行錯(cuò)誤而出現(xiàn)性能問(wèn)題。顯然，發(fā)生改變的代碼是無(wú)法放入追蹤緩存(追蹤緩存放的是解碼后的指令)的。即使沒(méi)有使用追蹤緩存(代碼還沒(méi)被執(zhí)行或有段時(shí)間沒(méi)執(zhí)行)，處理器也可能會(huì)遇到問(wèn)題。如果某個(gè)進(jìn)入管線的指令發(fā)生了變化，處理器只能扔掉目前的成果，重新開始。在某些情況下，甚至需要丟棄處理器的大部分狀態(tài)。

最后，由于處理器認(rèn)為代碼頁(yè)是不可修改的(這是出于簡(jiǎn)單化的考慮，而且在99.9999999%情況下確實(shí)是正確的)，L1i用到并不是MESI協(xié)議，而是一種簡(jiǎn)化后的SI協(xié)議。這樣一來(lái)，如果萬(wàn)一檢測(cè)到修改的情況，就需要作出大量悲觀的假設(shè)。

因此，對(duì)于SMC，強(qiáng)烈建議能不用就不用。現(xiàn)在內(nèi)存已經(jīng)不再是一種那么稀缺的資源了。最好是寫多個(gè)函數(shù)，而不要根據(jù)需要把一個(gè)函數(shù)改來(lái)改去。也許有一天可以把SMC變成可選項(xiàng)，我們就能通過(guò)這種方式檢測(cè)入侵代碼。如果一定要用SMC，應(yīng)該讓寫操作越過(guò)緩存，以免由于L1i需要L1d里的數(shù)據(jù)而產(chǎn)生問(wèn)題。更多細(xì)節(jié)，請(qǐng)參見(jiàn)6.1節(jié)。

在Linux上，判斷程序是否包含SMC是很容易的。利用正常工具鏈(toolchain)構(gòu)建的程序代碼都是寫保護(hù)(write-protected)的。程序員需要在鏈接時(shí)施展某些關(guān)鍵的魔術(shù)才能生成可寫的代碼頁(yè)?，F(xiàn)代的Intel x86和x86-64處理器都有統(tǒng)計(jì)SMC使用情況的專用計(jì)數(shù)器。通過(guò)這些計(jì)數(shù)器，我們可以很容易判斷程序是否包含SMC，即使它被準(zhǔn)許運(yùn)行。

3.5 緩存未命中的因素

我們已經(jīng)看過(guò)內(nèi)存訪問(wèn)沒(méi)有命中緩存時(shí)，那陡然猛漲的高昂代價(jià)。但是有時(shí)候，這種情況又是無(wú)法避免的，因此我們需要對(duì)真正的代價(jià)有所認(rèn)識(shí)，并學(xué)習(xí)如何緩解這種局面。

3.5.1 緩存與內(nèi)存帶寬

為了更好地理解處理器的能力，我們測(cè)量了各種理想環(huán)境下能夠達(dá)到的帶寬值。由于不同處理器的版本差別很大，所以這個(gè)測(cè)試比較有趣，也因?yàn)槿绱耍@一節(jié)都快被測(cè)試數(shù)據(jù)灌滿了。我們使用了x86和x86-64處理器的SSE指令來(lái)裝載和存儲(chǔ)數(shù)據(jù)，每次16字節(jié)。工作集則與其它測(cè)試一樣，從1kB增加到512MB，測(cè)量的具體對(duì)象是每個(gè)周期所處理的字節(jié)數(shù)。

圖3.24: P4的帶寬

圖3.24展示了一顆64位Intel Netburst處理器的性能圖表。當(dāng)工作集能夠完全放入L1d時(shí)，處理器的每個(gè)周期可以讀取完整的16字節(jié)數(shù)據(jù)，即每個(gè)周期執(zhí)行一條裝載指令(moveaps指令，每次移動(dòng)16字節(jié)的數(shù)據(jù))。測(cè)試程序并不對(duì)數(shù)據(jù)進(jìn)行任何處理，只是測(cè)試讀取指令本身。當(dāng)工作集增大，無(wú)法再完全放入L1d時(shí)，性能開始急劇下降，跌至每周期6字節(jié)。在218工作集處出現(xiàn)的臺(tái)階是由于DTLB緩存耗盡，因此需要對(duì)每個(gè)新頁(yè)施加額外處理。由于這里的讀取是按順序的，預(yù)取機(jī)制可以完美地工作，而FSB能以5.3字節(jié)/周期的速度傳輸內(nèi)容。但預(yù)取的數(shù)據(jù)并不進(jìn)入L1d。當(dāng)然，真實(shí)世界的程序永遠(yuǎn)無(wú)法達(dá)到以上的數(shù)字，但我們可以將它們看作一系列實(shí)際上的極限值。

更令人驚訝的是寫操作和復(fù)制操作的性能。即使是在很小的工作集下，寫操作也始終無(wú)法達(dá)到4字節(jié)/周期的速度。這意味著，Intel為Netburst處理器的L1d選擇了寫通(write-through)模式，所以寫入性能受到L2速度的限制。同時(shí)，這也意味著，復(fù)制測(cè)試的性能不會(huì)比寫入測(cè)試差太多(復(fù)制測(cè)試是將某塊內(nèi)存的數(shù)據(jù)拷貝到另一塊不重疊的內(nèi)存區(qū))，因?yàn)樽x操作很快，可以與寫操作實(shí)現(xiàn)部分重疊。最值得關(guān)注的地方是，兩個(gè)操作在工作集無(wú)法完全放入L2后出現(xiàn)了嚴(yán)重的性能滑坡，降到了0.5字節(jié)/周期！比讀操作慢了10倍！顯然，如果要提高程序性能，優(yōu)化這兩個(gè)操作更為重要。

再來(lái)看圖3.25，它來(lái)自同一顆處理器，只是運(yùn)行雙線程，每個(gè)線程分別運(yùn)行在處理器的一個(gè)超線程上。

圖3.25: P4開啟兩個(gè)超線程時(shí)的帶寬表現(xiàn)

圖3.25采用了與圖3.24相同的刻度，以方便比較兩者的差異。圖3.25中的曲線抖動(dòng)更多，是由于采用雙線程的緣故。結(jié)果正如我們預(yù)期，由于超線程共享著幾乎所有資源(僅除寄存器外)，所以每個(gè)超線程只能得到一半的緩存和帶寬。所以，即使每個(gè)線程都要花上許多時(shí)間等待內(nèi)存，從而把執(zhí)行時(shí)間讓給另一個(gè)線程，也是無(wú)濟(jì)于事——因?yàn)榱硪粋€(gè)線程也同樣需要等待。這里恰恰展示了使用超線程時(shí)可能出現(xiàn)的最壞情況。

圖3.26: Core 2的帶寬表現(xiàn)

再來(lái)看Core 2處理器的情況。看看圖3.26和圖3.27，再對(duì)比下P4的圖3.24和3.25，可以看出不小的差異。Core 2是一顆雙核處理器，有著共享的L2，容量是P4 L2的4倍。但更大的L2只能解釋寫操作的性能下降出現(xiàn)較晚的現(xiàn)象。

當(dāng)然還有更大的不同?？梢钥吹?，讀操作的性能在整個(gè)工作集范圍內(nèi)一直穩(wěn)定在16字節(jié)/周期左右，在220處的下降同樣是由于DTLB的耗盡引起。能夠達(dá)到這么高的數(shù)字，不但表明處理器能夠預(yù)取數(shù)據(jù)，并且按時(shí)完成傳輸，而且還意味著，預(yù)取的數(shù)據(jù)是被裝入L1d的。

寫/復(fù)制操作的性能與P4相比，也有很大差異。處理器沒(méi)有采用寫通策略，寫入的數(shù)據(jù)留在L1d中，只在必要時(shí)才逐出。這使得寫操作的速度可以逼近16字節(jié)/周期。一旦工作集超過(guò)L1d，性能即飛速下降。由于Core 2讀操作的性能非常好，所以兩者的差值顯得特別大。當(dāng)工作集超過(guò)L2時(shí)，兩者的差值甚至超過(guò)20倍！但這并不表示Core 2的性能不好，相反，Core 2永遠(yuǎn)都比Netburst強(qiáng)。

圖3.27: Core 2運(yùn)行雙線程時(shí)的帶寬表現(xiàn)

在圖3.27中，啟動(dòng)雙線程，各自運(yùn)行在Core 2的一個(gè)核心上。它們?cè)L問(wèn)相同的內(nèi)存，但不需要完美同步。從結(jié)果上看，讀操作的性能與單線程并無(wú)區(qū)別，只是多了一些多線程情況下常見(jiàn)的抖動(dòng)。

有趣的地方來(lái)了——當(dāng)工作集小于L1d時(shí)，寫操作與復(fù)制操作的性能很差，就好像數(shù)據(jù)需要從內(nèi)存讀取一樣。兩個(gè)線程彼此競(jìng)爭(zhēng)著同一個(gè)內(nèi)存位置，于是不得不頻頻發(fā)送RFO消息。問(wèn)題的根源在于，雖然兩個(gè)核心共享著L2，但無(wú)法以L2的速度處理RFO請(qǐng)求。而當(dāng)工作集超過(guò)L1d后，性能出現(xiàn)了迅猛提升。這是因?yàn)?，由于L1d容量不足，于是將被修改的條目刷新到共享的L2。由于L1d的未命中可以由L2滿足，只有那些尚未刷新的數(shù)據(jù)才需要RFO，所以出現(xiàn)了這樣的現(xiàn)象。這也是這些工作集情況下速度下降一半的原因。這種漸進(jìn)式的行為也與我們期待的一致:由于每個(gè)核心共享著同一條FSB，每個(gè)核心只能得到一半的FSB帶寬，因此對(duì)于較大的工作集來(lái)說(shuō)，每個(gè)線程的性能大致相當(dāng)于單線程時(shí)的一半。

由于同一個(gè)廠商的不同處理器之間都存在著巨大差異，我們沒(méi)有理由不去研究一下其它廠商處理器的性能。圖3.28展示了AMD家族10h Opteron處理器的性能。這顆處理器有64kB的L1d、512kB的L2和2MB的L3，其中L3緩存由所有核心所共享。

圖3.28: AMD家族10h Opteron的帶寬表現(xiàn)

大家首先應(yīng)該會(huì)注意到，在L1d緩存足夠的情況下，這個(gè)處理器每個(gè)周期能處理兩條指令。讀操作的性能超過(guò)了32字節(jié)/周期，寫操作也達(dá)到了18.7字節(jié)/周期。但是，不久，讀操作的曲線就急速下降，跌到2.3字節(jié)/周期，非常差。處理器在這個(gè)測(cè)試中并沒(méi)有預(yù)取數(shù)據(jù)，或者說(shuō)，沒(méi)有有效地預(yù)取數(shù)據(jù)。

另一方面，寫操作的曲線隨幾級(jí)緩存的容量而流轉(zhuǎn)。在L1d階段達(dá)到最高性能，隨后在L2階段下降到6字節(jié)/周期，在L3階段進(jìn)一步下降到2.8字節(jié)/周期，最后，在工作集超過(guò)L3后，降到0.5字節(jié)/周期。它在L1d階段超過(guò)了Core 2，在L2階段基本相當(dāng)(Core 2的L2更大一些)，在L3及主存階段比Core 2慢。

復(fù)制的性能既無(wú)法超越讀操作的性能，也無(wú)法超越寫操作的性能。因此，它的曲線先是被讀性能壓制，隨后又被寫性能壓制。

圖3.29顯示的是Opteron處理器在多線程時(shí)的性能表現(xiàn)。

圖3.29: AMD Fam 10h在雙線程時(shí)的帶寬表現(xiàn)

讀操作的性能沒(méi)有受到很大的影響。每個(gè)線程的L1d和L2表現(xiàn)與單線程下相仿，L3的預(yù)取也依然表現(xiàn)不佳。兩個(gè)線程并沒(méi)有過(guò)渡爭(zhēng)搶L3。問(wèn)題比較大的是寫操作的性能。兩個(gè)線程共享的所有數(shù)據(jù)都需要經(jīng)過(guò)L3，而這種共享看起來(lái)卻效率很差。即使是在L3足夠容納整個(gè)工作集的情況下，所需要的開銷仍然遠(yuǎn)高于L3的訪問(wèn)時(shí)間。再來(lái)看圖3.27，可以發(fā)現(xiàn)，在一定的工作集范圍內(nèi)，Core 2處理器能以共享的L2緩存的速度進(jìn)行處理。而Opteron處理器只能在很小的一個(gè)范圍內(nèi)實(shí)現(xiàn)相似的性能，而且，它僅僅只能達(dá)到L3的速度，無(wú)法與Core 2的L2相比。

3.5.2 關(guān)鍵字加載

內(nèi)存以比緩存線還小的塊從主存儲(chǔ)器向緩存?zhèn)魉?。如?4位可一次性傳送，緩存線的大小為64或128比特。這意味著每個(gè)緩存線需要8或16次傳送。

DRAM芯片可以以觸發(fā)模式傳送這些64位的塊。這使得不需要內(nèi)存控制器的進(jìn)一步指令和可能伴隨的延遲，就可以將緩存線充滿。如果處理器預(yù)取了緩存，這有可能是最好的操作方式。

如果程序在訪問(wèn)數(shù)據(jù)或指令緩存時(shí)沒(méi)有命中(這可能是強(qiáng)制性未命中或容量性未命中，前者是由于數(shù)據(jù)第一次被使用，后者是由于容量限制而將緩存線逐出)，情況就不一樣了。程序需要的并不總是緩存線中的第一個(gè)字，而數(shù)據(jù)塊的到達(dá)是有先后順序的，即使是在突發(fā)模式和雙倍傳輸率下，也會(huì)有明顯的時(shí)間差，一半在4個(gè)CPU周期以上。舉例來(lái)說(shuō)，如果程序需要緩存線中的第8個(gè)字，那么在首字抵達(dá)后它還需要額外等待30個(gè)周期以上。

當(dāng)然，這樣的等待并不是必需的。事實(shí)上，內(nèi)存控制器可以按不同順序去請(qǐng)求緩存線中的字。當(dāng)處理器告訴它，程序需要緩存中具體某個(gè)字，即「關(guān)鍵字(critical word)」時(shí)，內(nèi)存控制器就會(huì)先請(qǐng)求這個(gè)字。一旦請(qǐng)求的字抵達(dá)，雖然緩存線的剩余部分還在傳輸中，緩存的狀態(tài)還沒(méi)有達(dá)成一致，但程序已經(jīng)可以繼續(xù)運(yùn)行。這種技術(shù)叫做關(guān)鍵字優(yōu)先及較早重啟(Critical Word First & Early Restart)。

現(xiàn)在的處理器都已經(jīng)實(shí)現(xiàn)了這一技術(shù)，但有時(shí)無(wú)法運(yùn)用。比如，預(yù)取操作的時(shí)候，并不知道哪個(gè)是關(guān)鍵字。如果在預(yù)取的中途請(qǐng)求某條緩存線，處理器只能等待，并不能更改請(qǐng)求的順序。

圖3.30: 關(guān)鍵字位于緩存線尾時(shí)的表現(xiàn)

在關(guān)鍵字優(yōu)先技術(shù)生效的情況下，關(guān)鍵字的位置也會(huì)影響結(jié)果。圖3.30展示了下一個(gè)測(cè)試的結(jié)果，圖中表示的是關(guān)鍵字分別在線首和線尾時(shí)的性能對(duì)比情況。元素大小為64字節(jié)，等于緩存線的長(zhǎng)度。圖中的噪聲比較多，但仍然可以看出，當(dāng)工作集超過(guò)L2后，關(guān)鍵字處于線尾情況下的性能要比線首情況下低0.7%左右。而順序訪問(wèn)時(shí)受到的影響更大一些。這與我們前面提到的預(yù)取下條線時(shí)可能遇到的問(wèn)題是相符的。

3.5.3 緩存設(shè)定

緩存放置的位置與超線程，內(nèi)核和處理器之間的關(guān)系，不在程序員的控制范圍之內(nèi)。但是程序員可以決定線程執(zhí)行的位置，接著高速緩存與使用的CPU的關(guān)系將變得非常重要。

這里我們將不會(huì)深入（探討）什么時(shí)候選擇什么樣的內(nèi)核以運(yùn)行線程的細(xì)節(jié)。我們僅僅描述了在設(shè)置關(guān)聯(lián)線程的時(shí)候，程序員需要考慮的系統(tǒng)結(jié)構(gòu)的細(xì)節(jié)。

超線程，通過(guò)定義，共享除去寄存器集以外的所有數(shù)據(jù)。包括 L1 緩存。這里沒(méi)有什么可以多說(shuō)的。多核處理器的獨(dú)立核心帶來(lái)了一些樂(lè)趣。每個(gè)核心都至少擁有自己的 L1 緩存。除此之外，下面列出了一些不同的特性：

早期多核心處理器有獨(dú)立的 L2 緩存且沒(méi)有更高層級(jí)的緩存。
之后英特爾的雙核心處理器模型擁有共享的L2 緩存。對(duì)四核處理器，則分對(duì)擁有獨(dú)立的L2 緩存，且沒(méi)有更高層級(jí)的緩存。
AMD 家族的 10h 處理器有獨(dú)立的 L2 緩存以及一個(gè)統(tǒng)一的L3 緩存。

關(guān)于各種處理器模型的優(yōu)點(diǎn)，已經(jīng)在它們各自的宣傳手冊(cè)里寫得夠多了。在每個(gè)核心的工作集互不重疊的情況下，獨(dú)立的L2擁有一定的優(yōu)勢(shì)，單線程的程序可以表現(xiàn)優(yōu)良?？紤]到目前實(shí)際環(huán)境中仍然存在大量類似的情況，這種方法的表現(xiàn)并不會(huì)太差。不過(guò)，不管怎樣，我們總會(huì)遇到工作集重疊的情況。如果每個(gè)緩存都保存著某些通用運(yùn)行庫(kù)的常用部分，那么很顯然是一種浪費(fèi)。

如果像Intel的雙核處理器那樣，共享除L1外的所有緩存，則會(huì)有一個(gè)很大的優(yōu)點(diǎn)。如果兩個(gè)核心的工作集重疊的部分較多，那么綜合起來(lái)的可用緩存容量會(huì)變大，從而允許容納更大的工作集而不導(dǎo)致性能的下降。如果兩者的工作集并不重疊，那么則是由Intel的高級(jí)智能緩存管理(Advanced Smart Cache management)發(fā)揮功用，防止其中一個(gè)核心壟斷整個(gè)緩存。

即使每個(gè)核心只使用一半的緩存，也會(huì)有一些摩擦。緩存需要不斷衡量每個(gè)核心的用量，在進(jìn)行逐出操作時(shí)可能會(huì)作出一些比較差的決定。我們來(lái)看另一個(gè)測(cè)試程序的結(jié)果。

圖3.31: 兩個(gè)進(jìn)程的帶寬表現(xiàn)

這次，測(cè)試程序兩個(gè)進(jìn)程，第一個(gè)進(jìn)程不斷用SSE指令讀/寫2MB的內(nèi)存數(shù)據(jù)塊，選擇2MB，是因?yàn)樗檬荂ore 2處理器L2緩存的一半，第二個(gè)進(jìn)程則是讀/寫大小變化的內(nèi)存區(qū)域，我們把這兩個(gè)進(jìn)程分別固定在處理器的兩個(gè)核心上。圖中顯示的是每個(gè)周期讀/寫的字節(jié)數(shù)，共有4條曲線，分別表示不同的讀寫搭配情況。例如，標(biāo)記為讀/寫(read/write)的曲線代表的是后臺(tái)進(jìn)程進(jìn)行寫操作(固定2MB工作集)，而被測(cè)量進(jìn)程進(jìn)行讀操作(工作集從小到大)。

圖中最有趣的是220到223之間的部分。如果兩個(gè)核心的L2是完全獨(dú)立的，那么所有4種情況下的性能下降均應(yīng)發(fā)生在221到222之間，也就是L2緩存耗盡的時(shí)候。但從圖上來(lái)看，實(shí)際情況并不是這樣，特別是背景進(jìn)程進(jìn)行寫操作時(shí)尤為明顯。當(dāng)工作集達(dá)到1MB(220)時(shí)，性能即出現(xiàn)惡化，兩個(gè)進(jìn)程并沒(méi)有共享內(nèi)存，因此并不會(huì)產(chǎn)生RFO消息。所以，完全是緩存逐出操作引起的問(wèn)題。目前這種智能的緩存處理機(jī)制有一個(gè)問(wèn)題，每個(gè)核心能實(shí)際用到的緩存更接近1MB，而不是理論上的2MB。如果未來(lái)的處理器仍然保留這種多核共享緩存模式的話，我們唯有希望廠商會(huì)把這個(gè)問(wèn)題解決掉。

推出擁有雙L2緩存的4核處理器僅僅只是一種臨時(shí)措施，是開發(fā)更高級(jí)緩存之前的替代方案。與獨(dú)立插槽及雙核處理器相比，這種設(shè)計(jì)并沒(méi)有帶來(lái)多少性能提升。兩個(gè)核心是通過(guò)同一條總線(被外界看作FSB)進(jìn)行通信，并沒(méi)有什么特別快的數(shù)據(jù)交換通道。

未來(lái)，針對(duì)多核處理器的緩存將會(huì)包含更多層次。AMD的10h家族是一個(gè)開始，至于會(huì)不會(huì)有更低級(jí)共享緩存的出現(xiàn)，還需要我們拭目以待。我們有必要引入更多級(jí)別的緩存，因?yàn)轭l繁使用的高速緩存不可能被許多核心共用，否則會(huì)對(duì)性能造成很大的影響。我們也需要更大的高關(guān)聯(lián)性緩存，它們的數(shù)量、容量和關(guān)聯(lián)性都應(yīng)該隨著共享核心數(shù)的增長(zhǎng)而增長(zhǎng)。巨大的L3和適度的L2應(yīng)該是一種比較合理的選擇。L3雖然速度較慢，但也較少使用。

對(duì)于程序員來(lái)說(shuō)，不同的緩存設(shè)計(jì)就意味著調(diào)度決策時(shí)的復(fù)雜性。為了達(dá)到最高的性能，我們必須掌握工作負(fù)載的情況，必須了解機(jī)器架構(gòu)的細(xì)節(jié)。好在我們?cè)谂袛鄼C(jī)器架構(gòu)時(shí)還是有一些支援力量的，我們會(huì)在后面的章節(jié)介紹這些接口。

3.5.4 FSB的影響

FSB在性能中扮演了核心角色。緩存數(shù)據(jù)的存取速度受制于內(nèi)存通道的速度。我們做一個(gè)測(cè)試，在兩臺(tái)機(jī)器上分別跑同一個(gè)程序，這兩臺(tái)機(jī)器除了內(nèi)存模塊的速度有所差異，其它完全相同。圖3.32展示了Addnext0測(cè)試(將下一個(gè)元素的pad[0]加到當(dāng)前元素的pad[0]上)在這兩臺(tái)機(jī)器上的結(jié)果(NPAD=7，64位機(jī)器)。兩臺(tái)機(jī)器都采用Core 2處理器，一臺(tái)使用667MHz的DDR2內(nèi)存，另一臺(tái)使用800MHz的DDR2內(nèi)存(比前一臺(tái)增長(zhǎng)20%)。

圖3.32: FSB速度的影響

圖上的數(shù)字表明，當(dāng)工作集大到對(duì)FSB造成壓力的程度時(shí)，高速FSB確實(shí)會(huì)帶來(lái)巨大的優(yōu)勢(shì)。在我們的測(cè)試中，性能的提升達(dá)到了18.5%，接近理論上的極限。而當(dāng)工作集比較小，可以完全納入緩存時(shí)，F(xiàn)SB的作用并不大。當(dāng)然，這里我們只測(cè)試了一個(gè)程序的情況，在實(shí)際環(huán)境中，系統(tǒng)往往運(yùn)行多個(gè)進(jìn)程，工作集是很容易超過(guò)緩存容量的。

如今，一些英特爾的處理器，支持前端總線(FSB)的速度高達(dá)1,333 MHz，這意味著速度有另外60％的提升。將來(lái)還會(huì)出現(xiàn)更高的速度。速度是很重要的，工作集會(huì)更大，快速的RAM和高FSB速度的內(nèi)存肯定是值得投資的。我們必須小心使用它，因?yàn)榧词固幚砥骺梢灾С指叩那岸丝偩€速度，但是主板的北橋芯片可能不會(huì)。使用時(shí)，檢查它的規(guī)范是至關(guān)重要的。

總結(jié)

以上是生活随笔為你收集整理的每个程序员都应该了解的 CPU 高速缓存的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。