小談 CPU 緩存體系

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

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

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

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

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

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

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

DEC? ?EDX

JNZ ??AGAIN

　　 Oh Year ，這里 3 個(gè)地址都有相同的關(guān)聯(lián)值，而且地址跨度都超過了數(shù)據(jù)緩存的大小，可這個(gè)循環(huán)在 PPro 上效率會(huì)相當(dāng)?shù)汀．?dāng)你想讀取 ECX 的值的時(shí)候，將沒有空閑的緩存行了 —— 因?yàn)楣蚕硪粋€(gè)關(guān)聯(lián)值，而且 2 行已經(jīng)被使用了。此時(shí) CPU 將騰出最近使用的 2 個(gè)緩存行，一個(gè)已經(jīng)被 EAX 使用。然后 CPU 把這個(gè)緩存行用 [ESI+20*4096] 到 [ESI+20*4096+31] 的內(nèi)存數(shù)據(jù)填充，然后從緩存中讀取 ECX 。聽起來好象相當(dāng)?shù)臒┈崱８釉愀獾氖牵?dāng)又需要讀取 EAX 的時(shí)候，還需要重復(fù)上述的過程，需要對(duì)內(nèi)存緩存來回操作，效率相當(dāng)?shù)牡停踔敛蝗绮挥镁彺妗？墒牵绻覀儼训谌懈某桑?/span>

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

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

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

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

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

<!--[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]--> 程序盡可能少的進(jìn)行判斷跳轉(zhuǎn)循環(huán)。

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

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

?

使用 SIMD

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

MMX

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

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

SSE1

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

適用范圍：多媒體信號(hào)處理

SSE2

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

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

SSE3

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

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

手頭工具

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

2 、 Intel 以及 AMD 的匯編指令集手冊(cè)。這個(gè)是必需的，強(qiáng)烈建議每個(gè)C++ Coder人手準(zhǔn)備一份。

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

使用范例：

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

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

??? 16字節(jié)對(duì)齊的結(jié)構(gòu)，其實(shí)本身也是16字節(jié)的東西。如果沒有對(duì)齊，運(yùn)行時(shí)會(huì)報(bào)錯(cuò)。

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

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

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

??? 歡迎大家拍磚！