小談 CPU 緩存體系

　　現(xiàn)在的 CPU 依舊采用馮諾伊曼體系，喜歡像傻子一樣從頭執(zhí)行到尾，中途沒有任何的跳轉(zhuǎn)停頓等待?？墒乾F(xiàn)實情況是，大部分程序里面還是少不了 IF ELSE 之類的判斷，循環(huán)就更加得多了。如何優(yōu)化循環(huán)大家可以自己琢磨，其實不難，可以參考一下《高質(zhì)量 C\C++ 編程指南》

　　現(xiàn)在 CPU 上都有 Level 1 指令緩存（又叫做 L1 Trace ）與 Level 1 數(shù)據(jù)緩存（ L1 Data Cache ）。 PMMX ， P2 ， P3 為二者都準備了 16kb ，我的 P4 Northwood （以下簡稱 P4NW ）有 8kbL1 數(shù)據(jù)緩存和 12kb 指令緩存。 CPU 讀取 L1 Data Cache 中的數(shù)據(jù)只需要 1 個時鐘周期，速度非?？?，應(yīng)該是僅次于寄存器了。數(shù)據(jù)緩存是由 256 或者 512 行 32bytes 組成的，也就是 32bytes 對齊的，而 P4NW 是 64bytes 字節(jié)對齊的，并行 4 路，總共 128 行。當你處理的數(shù)據(jù)沒有載入緩存的時候， CPU 將從內(nèi)存讀取緩存行大小的數(shù)據(jù)，所以緩存行總是對齊到能被 32 整除的物理地址。 CPU 對 L1 數(shù)據(jù)緩存中的數(shù)據(jù)進行操作是最快速的。所以推薦內(nèi)存地址最起碼是 32byte 對齊的。目前編譯器在這個地方的優(yōu)化已經(jīng)非常好了，一般都是 4byte 對齊，當然也都是 32 對齊的。在后面你將會看到， SSE2 要求數(shù)據(jù)是 16 字節(jié)對齊的。

? 　　緩存類似一個 C++ set 容器，但是不能賦值到一個任意的內(nèi)存地址。每行本身都有 1 個 7bit 大小的關(guān)聯(lián)值（ set value ）要和目標內(nèi)存地址的 5 到 11 位對應(yīng)（ 0-4 位已經(jīng)忽略了），也可以理解為，關(guān)聯(lián)值是內(nèi)存段地址的一部分。 PPro 中，有 128 個關(guān)聯(lián)值對應(yīng)到 2 行，所以最多可以為任意的內(nèi)存單元準備 2 個緩存行。 PMMX P2 P3 P4NW 有 4 個。由于內(nèi)存是分段的，所以說 CPU 只能為， 5-11 位地址相同的內(nèi)存準備 2 或者 4 個不同的緩存行。如何為兩個內(nèi)存地址賦予相同的關(guān)聯(lián)值呢？把 2 個地址的低 5bit 去掉，這樣就能被 32 整除了。如果這 2 個截斷了的地址都是 4096 （ 1000H ）的倍數(shù)，那么這兩個地址就有了相同的關(guān)聯(lián)值。

? 　　讓我們用匯編加深一下印象，假設(shè) ESI 中是 32 對齊的地址。

? ??????????????????????????????????????? AGAIN:? MOV? EAX,? [ESI]

MOV? EBX,? [ESI+13*4096+4]

MOV ?ECX,? [ESI+20*4096+28]

DEC? ?EDX

JNZ ??AGAIN

　　 Oh Year ，這里 3 個地址都有相同的關(guān)聯(lián)值，而且地址跨度都超過了數(shù)據(jù)緩存的大小，可這個循環(huán)在 PPro 上效率會相當?shù)?。當你想讀取 ECX 的值的時候，將沒有空閑的緩存行了 —— 因為共享一個關(guān)聯(lián)值，而且 2 行已經(jīng)被使用了。此時 CPU 將騰出最近使用的 2 個緩存行，一個已經(jīng)被 EAX 使用。然后 CPU 把這個緩存行用 [ESI+20*4096] 到 [ESI+20*4096+31] 的內(nèi)存數(shù)據(jù)填充，然后從緩存中讀取 ECX 。聽起來好象相當?shù)臒┈崱８釉愀獾氖?，當又需要讀取 EAX 的時候，還需要重復(fù)上述的過程，需要對內(nèi)存緩存來回操作，效率相當?shù)牡?，甚至不如不用緩存。可是，如果我們把第三行改成?/span>

MOV? ECX,? [ESI+20*4096+32]

　　哦，不好，看起來，我們的地址超過了 32 ，不能被整除了。可是這樣有了不同的關(guān)聯(lián)值，也就意味著有了 1 個新行，不再共享可憐的 2 個行。這樣一來，對三個寄存器的操作就不需要反復(fù)的用 2 個緩存行進行調(diào)度了，各有一個了。嘿嘿，這次只需要 3 個時鐘周期了，而上一個要 60 個周期。這是在 PPro 上的，在后來的 CPU 中都是 4 路的，也就不存在上面的問題了。搞笑的是， Intel 的文檔卻錯誤的說 P2 的緩存是 2 路的。雖然說很少人在用那么古老的 CPU ，可是其中的道理大家應(yīng)該明白。

　　可是判斷要訪問的部分數(shù)據(jù)是否有相同的關(guān)聯(lián)值，也就是關(guān)于緩存是否能夠命中的問題，是相當困難的，匯編還好，用高等級語言編譯過的程序鬼知道是否對緩存做過優(yōu)化呢。所以么，推薦，在程序的核心部分，對性能要求最高的部分，先對齊數(shù)據(jù)，然后確保使用的單個數(shù)據(jù)塊不要超過緩存大小， 2 個數(shù)據(jù)塊，單個不要超過緩存大小的一半（仔細想想為什么，因為關(guān)聯(lián)值的問題，可以緩存分為兩部分處理兩塊）。可是大部分情況下，我們都是使用遠比數(shù)據(jù)緩存大的多的結(jié)構(gòu)，以及編譯器自己返回的指針，然后為了優(yōu)化你可能希望把所有頻繁使用的變量放到一個連續(xù)的數(shù)據(jù)塊中以充分利用緩存。我們可以這樣做，把靜態(tài)變量數(shù)值拷貝到棧中的局部變量中，等子函數(shù)或者循環(huán)結(jié)束后再拷貝回來。這樣一來就相當于把靜態(tài)變量放入了連續(xù)的地址空間中去。

當讀取的數(shù)據(jù)不在 L1 Cache 內(nèi)時， CPU 將要從 L2 Cache 讀取 L1 緩存行大小的數(shù)據(jù)到 L1 里去，大概需要 200ns 的時間（也就是 100Mhz 系統(tǒng)的 20 個時鐘周期），但是直到你能夠使用這些數(shù)據(jù)前，又需要有 50-100ns 的延遲。最糟糕的是，如果數(shù)據(jù)也不在 L2 Cache 中，那么就只能從最慢速的內(nèi)存里讀取了，內(nèi)存的龜速哪能和全速的緩存相比。

好了，關(guān)于緩存的知識可以就此打住了，下面開始講如何優(yōu)化緩存。無非就是 3 種方法，硬件預(yù)?。?/span> Prefetch ）、軟件預(yù)取、使用緩存指令。關(guān)于預(yù)取的注意事項主要有這些：

<!--[if !supportLists]--> 1、? <!--[endif]--> 合理安排內(nèi)存的數(shù)據(jù)，使用塊結(jié)構(gòu)，提高緩存命中率。

<!--[if !supportLists]--> 2、? <!--[endif]--> 使用編譯器提供的預(yù)取指令。比如ICC中的_mm_prefetch _mm_stream，甚至_mm_load等比較“傳統(tǒng)”的指令。

<!--[if !supportLists]--> 3、? <!--[endif]--> 盡可能少的使用全局的變量或者指針。

<!--[if !supportLists]--> 4、? <!--[endif]--> 程序盡可能少的進行判斷跳轉(zhuǎn)循環(huán)。

<!--[if !supportLists]--> 5、? <!--[endif]--> 使用const標記，不要在代碼中混合register聲明。

不過要提醒一句，真正提高程序效率的方法不是那種，從頭到尾由于外科手術(shù)般的解剖，一個一個地方的優(yōu)化，請抓住程序最核心的部分進行優(yōu)化，記住 80-20 規(guī)則。

?

使用 SIMD

先復(fù)習(xí)一下對齊指令， __declspec(aliagn(#)) ， # 替換為字節(jié)數(shù)。比如想聲明一個 16 字結(jié)對齊的浮點數(shù)組， __declspec(aliagn(16)) float Array[128] 。需要注意的是，最好充分了解你 CPU 的類型，支持哪些指令集。 SIMD 主要使用在需要同時操作大量數(shù)據(jù)的工作領(lǐng)域，比如 3D 圖形處理（游戲），物理建模（ CAD ），加密，以及科學(xué)計算領(lǐng)域。據(jù)我所知，目前 GPGPU 也是使用 SIMD 的代表之一。

MMX

主要特性： 57 條指令， 64bit 的 FP 寄存器 MM0-MM7 ，對齊到 8 個 80bit 的 FP 寄存器 ST0-ST7 。需要數(shù)據(jù) 8 字節(jié)對齊，也就是使用 Packed 數(shù)字。

PS ：這里冒出了一個問題，為什么 Intel 要把 MMX 的寄存器和 FPU 的寄存器混合起來使用呢？因為這里牽涉到一個 FPU 狀態(tài)切換問題，后面會提到，當你在一段代碼中又要用到 MMX 指令又要用到傳統(tǒng)的 FPU 指令，那么需要保存 FPU 狀態(tài)，或者退出 MMX ?？墒沁@種操作對于 FPU 來說非常昂貴，而且對于多任務(wù)操作系統(tǒng)來說，近乎于不可能完成的任務(wù) —— 同時有許多程序，有些需要 MMX ，有些不需要，而正確地進行調(diào)度會變得非常困難。所以 Intel 將保存狀態(tài)的工作完全交給了 CPU 自己，軟件人員無須作太多這方面的工作，這樣一來，就向前向后兼容了多任務(wù)操作系統(tǒng)，比如 Windows 和 Linux 。后來隨著操作系統(tǒng)和 CPU 的不斷升級，操作系統(tǒng)開發(fā)人員發(fā)布了一個補丁包，就可以讓操作系統(tǒng)使用新的寄存器。這時人們都發(fā)現(xiàn) Intel 的這種做法是相當短視的，這可以當作一個重大的失誤。后來 Intel 通過引入了新的浮點指令集，這時才加入 XMM 寄存器?？稍斐蛇@段故事的原因卻根本不是技術(shù)問題，保證兼容性也是一個方面，總之真的說不清楚。你只要記得無法同時使用 MMX 與 FPU 就可以了， CPU 要進行模式切換。

SSE1

主要特性： 128bit 的 FP 寄存器 XMM0-XMM7 。增加了數(shù)據(jù)預(yù)取指令。額外的 64bit 整數(shù)支持。支持同時處理 4 個單精度浮點數(shù)，也就是 C\C++ 里的 float 。

適用范圍：多媒體信號處理

SSE2

主要特性： 128bit 的 FP 寄存器支持處理同時處理 2 個雙精度 double 浮點數(shù)，以及 16byte 8word 4dword 2quadword 整數(shù)。

適用范圍： 3D 處理 語音識別 視頻編碼解碼

SSE3

主要特性：增加支持非對稱 asymmetric 和水平 horizontal 計算的 SIMD 指令。為 SIMD 提供了一條特殊的寄存器 load 指令。線程同步指令。

適用范圍：科學(xué)計算 多線程程序

手頭工具

1 、選擇一個合適的編譯器，推薦用 Intel C++ Compiler （以下簡稱 ICC ），以及 Visual Studio .NET 2003 及以上 IDE 附帶的 C++ 編譯器。同時， Microsoft C++ Compiler 也支持 AMD 的 3DNow 。 GCC C++ Compiler 沒有測試。

2 、 Intel 以及 AMD 的匯編指令集手冊。這個是必需的，強烈建議每個C++ Coder人手準備一份。

? 所有的都用 C++ 混合變成的方式實現(xiàn)

使用范例：

向量乘法在 3D 處理中非常非常多，多半用于計算單位矢量的夾角。

我們先定義一個頂點結(jié)構(gòu)。

??? 16字節(jié)對齊的結(jié)構(gòu)，其實本身也是16字節(jié)的東西。如果沒有對齊，運行時會報錯。

w是其次坐標系的參數(shù)，處理向量的時候不需要用到。我的函數(shù)是這樣的：

??? VC中反匯編之：
??? 前面都是保護現(xiàn)場入Stack的代碼，沒有必要管。我之所以這樣，在Stack中聲明了一個零時變量返回之，是為了減少代碼的行數(shù)。有興趣地可以參考本文后面引用資料中的Intel范例，代碼多的多，功能卻一樣。這樣就可以利用SIMD計算點乘了。圖示：
??? 這種頂點格式稱為AoS（Array of structure），這種結(jié)構(gòu)的好處是，能夠和現(xiàn)有的程序結(jié)構(gòu)，比如D3D中的FVF頂點格式，和GL中的頂點格式。但是，由于許多情況下，并沒有使用第四各浮點數(shù)，這就讓SIMD指令浪費了25%的性能。于是有了SoA格式，讓我們重新來過。
??? 我借用了一下上面一個結(jié)構(gòu)的指令，還是沒有用_mm_128格式，讓大家看得清楚一些：
??? 依舊16字節(jié)對齊。計算函數(shù)如下：
??? Oh Yeah，就是這樣了，同時計算了1對乘法。我在代碼中借用了一下前面的頂點結(jié)構(gòu)，這樣方便一些。至于SOA格式，請看前面的聲明。很多代碼都是轉(zhuǎn)換Stack中的內(nèi)存格式，轉(zhuǎn)換成AOS格式，這樣才能使用SIMD指令計算。

??? 通過上面的演示，想必大家已經(jīng)對SIMD有了個直觀地認識，其實在自己的代碼中加入這些是非常方便與容易的。雖然說現(xiàn)在的CPU性能已經(jīng)提高了許多，性能也強了許多，可是在諸多對性能要求高的地方，還是非?？緹煶绦騿T的水平的。

??? 歡迎大家拍磚！