小談 CPU 緩存體系

　　現(xiàn)在的 CPU 依舊采用馮諾伊曼體系，喜歡像傻子一樣從頭執(zhí)行到尾，中途沒有任何的跳轉(zhuǎn)停頓等待。可是現(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 個時鐘周期，速度非常快，應該是僅次于寄存器了。數(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 位對應（ 0-4 位已經(jīng)忽略了），也可以理解為，關(guān)聯(lián)值是內(nèi)存段地址的一部分。 PPro 中，有 128 個關(guān)聯(lián)值對應到 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)值。

? 　　讓我們用匯編加深一下印象，假設 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ù)汀．斈阆胱x取 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ù)臒┈崱８釉愀獾氖牵斢中枰x取 EAX 的時候，還需要重復上述的過程，需要對內(nèi)存緩存來回操作，效率相當?shù)牡停踔敛蝗绮挥镁彺妗？墒牵绻覀儼训谌懈某桑?/span>

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

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

　　可是判斷要訪問的部分數(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 種方法，硬件預取（ Prefetch ）、軟件預取、使用緩存指令。關(guān)于預取的注意事項主要有這些：

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

<!--[if !supportLists]--> 2、? <!--[endif]--> 使用編譯器提供的預取指令。比如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

先復習一下對齊指令， __declspec(aliagn(#)) ， # 替換為字節(jié)數(shù)。比如想聲明一個 16 字結(jié)對齊的浮點數(shù)組， __declspec(aliagn(16)) float Array[128] 。需要注意的是，最好充分了解你 CPU 的類型，支持哪些指令集。 SIMD 主要使用在需要同時操作大量數(shù)據(jù)的工作領(lǐng)域，比如 3D 圖形處理（游戲），物理建模（ CAD ），加密，以及科學計算領(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 來說非常昂貴，而且對于多任務操作系統(tǒng)來說，近乎于不可能完成的任務 —— 同時有許多程序，有些需要 MMX ，有些不需要，而正確地進行調(diào)度會變得非常困難。所以 Intel 將保存狀態(tài)的工作完全交給了 CPU 自己，軟件人員無須作太多這方面的工作，這樣一來，就向前向后兼容了多任務操作系統(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ù)預取指令。額外的 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 指令。線程同步指令。

適用范圍：科學計算 多線程程序

手頭工具

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)提高了許多，性能也強了許多，可是在諸多對性能要求高的地方，還是非常烤煙程序員的水平的。

??? 歡迎大家拍磚！