緩存優(yōu)化

處理器緩存內(nèi)部分為一級緩存和二級緩存，以及在多核處理器中常見的三級緩存，其中一級緩存又分為指令緩存和數(shù)據(jù)緩存兩部分。這種結(jié)構(gòu)緩和了處理器與主存之間速度不匹配的矛盾，使存儲速度、存儲容量與處理器功耗之間的關(guān)系相對平衡。

以矩陣乘代碼為例具體說明緩存分塊技術(shù)的使用方法。這段代碼中兩個內(nèi)部循環(huán)讀取了數(shù)組z的全部N*N個元素，以及數(shù)組y的某一行中的N個元素，所產(chǎn)生的N個結(jié)果被寫入數(shù)組x的某一行。下圖為i=1時，原始循環(huán)中三個數(shù)組的訪問情況，其中黑色表示最近被訪問過，灰色表示早些時候被訪問過，而白色表示尚未被訪問。

代碼：

對原始循環(huán)中的i，j層循環(huán)分別進(jìn)行分塊， 將原始的大矩陣分割為了若干個小矩陣，嵌套循環(huán)每次對一個小矩陣內(nèi)的數(shù)據(jù)進(jìn)行計算得出一個部分結(jié)果，下圖說明了分塊后三個數(shù)組的訪問情況。

為進(jìn)一步說明分析結(jié)果，針對上文中的矩陣乘示例使用x86架構(gòu)平臺進(jìn)行測試。當(dāng)固定分塊大小為50時，隨著矩陣規(guī)模的不斷增大，分塊后的矩陣乘程序相對于未分塊程序的性能提升越來越明顯，如下圖所示。

當(dāng)固定矩陣規(guī)模為1024時，此時三個矩陣并不能全部保存在緩存中。隨著分塊大小的逐漸提高，分塊前后運(yùn)行時間對比如圖所示。

造成上述現(xiàn)象的部分原因?yàn)楦咚倬彺娌煌挠成洳呗砸约疤鎿Q策略，地址映射就是主存地址與高速緩存地址的對應(yīng)方式，常見的緩存地址映射策略包括直接相聯(lián)、組相聯(lián)和全相聯(lián)。

1.?????? 全相聯(lián)高速緩存的映射策略為內(nèi)存中的每個數(shù)據(jù)塊均能夠被映射到緩存中的任意一個緩存行，但其請求數(shù)據(jù)時需要將其地址的標(biāo)記位與所有緩存行標(biāo)記位進(jìn)行對比，花費(fèi)代價較大。

2.?????? 直接相聯(lián)的映射方式是內(nèi)存中的每一個數(shù)據(jù)塊都只能存放在緩存中的一個特定的緩存行，但每個主存塊只有一個固定位置可存放，容易產(chǎn)生沖突，使緩存效率下降。

3.?????? 組相聯(lián)映射實(shí)際上是直接映射和全相聯(lián)映射的折中方案，映射方法是將主存和緩存都分組，組間采用直接映射，組內(nèi)采用全相聯(lián)映射。盡量避免了全相連和直接相連的缺點(diǎn)，適度兼顧二者的優(yōu)點(diǎn)，緩存命中率較高，因而得到普遍采用。

結(jié)合上文中矩陣乘的例子，可以將數(shù)組按照讀取效率從高到低分為三類：

一類數(shù)組

這類數(shù)組是最好的情況，其矩陣行的長度是緩存行大小的整數(shù)倍。當(dāng)程序訪問一個緩存行行大小的數(shù)據(jù)時，一類數(shù)組的這些數(shù)據(jù)會在一個緩存行中，緩存命中率高。

二類數(shù)組

第二類數(shù)組其矩陣行的長度不是緩存行的整數(shù)倍。這種情況下，程序運(yùn)行時訪存數(shù)據(jù)很有可能需要跨越兩個緩存行，與一類數(shù)組相比緩存命中率會變低。

三類數(shù)組

第三類數(shù)組其矩陣行是整個緩存大小的整數(shù)倍。這種情況下，數(shù)組的每一列數(shù)據(jù)均映射到同一緩存行組，當(dāng)進(jìn)行數(shù)組轉(zhuǎn)置時緩存的利用率非常低，會多次發(fā)生緩存不命中的情況，嚴(yán)重影響程序執(zhí)行效率。

在矩陣乘計算或者其它類似程序中，這三類數(shù)組的計算效率差異很大。所以優(yōu)化人員應(yīng)結(jié)合緩存映射方式，盡可能避免三類數(shù)組或者二類數(shù)組的出現(xiàn)。例如在計算時對對矩陣的行列進(jìn)行擴(kuò)充，使其變?yōu)橐活悢?shù)組，從而獲得性能的提升。以矩陣乘代碼為例，對其進(jìn)行不同規(guī)模下運(yùn)行時間的測試，結(jié)果如下。

代碼為：

在此例子中，若將數(shù)據(jù)由251列擴(kuò)展到256列，擴(kuò)充的部分使用0進(jìn)行補(bǔ)齊，這樣矩陣行的長度就是緩存行的整數(shù)倍，即從二類數(shù)組變成了一類數(shù)組，可以增加緩存命中率。

在進(jìn)行行列擴(kuò)充優(yōu)化后，實(shí)際的有效數(shù)據(jù)量依然為251*251，但優(yōu)化后矩陣乘耗時為100ms，加速比達(dá)到了1.6倍左右。

代碼為：