小談 CPU 緩存體系

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

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

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

? 　　讓我們用匯編加深一下印象，假設 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 個地址都有相同的關聯值，而且地址跨度都超過了數據緩存的大小，可這個循環在 PPro 上效率會相當低。當你想讀取 ECX 的值的時候，將沒有空閑的緩存行了 —— 因為共享一個關聯值，而且 2 行已經被使用了。此時 CPU 將騰出最近使用的 2 個緩存行，一個已經被 EAX 使用。然后 CPU 把這個緩存行用 [ESI+20*4096] 到 [ESI+20*4096+31] 的內存數據填充，然后從緩存中讀取 ECX 。聽起來好象相當的煩瑣。更加糟糕的是，當又需要讀取 EAX 的時候，還需要重復上述的過程，需要對內存緩存來回操作，效率相當的低，甚至不如不用緩存。可是，如果我們把第三行改成：

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

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

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

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

好了，關于緩存的知識可以就此打住了，下面開始講如何優化緩存。無非就是 3 種方法，硬件預取（ Prefetch ）、軟件預取、使用緩存指令。關于預取的注意事項主要有這些：

<!--[if !supportLists]--> 1、? <!--[endif]--> 合理安排內存的數據，使用塊結構，提高緩存命中率。

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

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

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

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

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

?

使用 SIMD

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

MMX

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

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

SSE1

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

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

SSE2

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

適用范圍： 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++ 混合變成的方式實現

使用范例：

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

我們先定義一個頂點結構。

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

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

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

??? 通過上面的演示，想必大家已經對SIMD有了個直觀地認識，其實在自己的代碼中加入這些是非常方便與容易的。雖然說現在的CPU性能已經提高了許多，性能也強了許多，可是在諸多對性能要求高的地方，還是非常烤煙程序員的水平的。

??? 歡迎大家拍磚！