對于軟件的緩存訪問問題進行優化的第一步應該是選擇合適的編譯器選項，使得編譯器能夠根據你的應用和要針對的處理器進行優化。每個處理器采用不同的緩存，比如通過QxW針對P4處理器進行優化，/O3允許一些循環分割、合并等激進優化，/Qipo通過過程間優化可以減少代碼的大小，通過代碼移動優化使得經常調用的變量和函數可以放在一起，增加了空間的局部性，采用Profile導向的優化，可以知道哪些分支經常使用，提高指令緩存和數據緩存的利用率。 雖然編譯器的功能非常強大，但是也不是萬能的，只有程序員才知道程序的具體行為，有的時候程序員也可以手工修改代碼來幫助編譯器進行更進一步的優化。那些具有更好的時間局部性的空間和時間局部性的代碼一般會有更低的緩存缺失率，從而在大部分情況下回比那些高缺失率的代碼運行得更快。考慮到好的時間局部性，那些經常訪問的數據可以通過一個局部變量來保存，考慮到空間局部性，步長為1的內存訪問顯然是最好的。大部分的緩存優化都是針對那些訪問數組元素的循環的，而提高這些循環的局部性，需要考慮循環訪問數組的模式，從而分析是什么原因引起的緩存缺失，然后通過改變循環的順序、結構、數組的布局等來減少緩存的缺失。 示例1：考慮下面的代碼：點擊(此處)折疊或打開 1.int sumarrarcols(int a[M][N])2.{3.int i,j,sum=0;4.for(j=0;j<N;j++)5. for(i=0;i<M;i++)6. sum+=a[i][j];7.8.return sum;9.} 由于C語言的數組是按照行來進行存儲的，也就是a[0][0],a[0][1],...a[0][N-1],a[1][0],a[1][1],....，而sumarrarcols則是按照列順序訪問的，也就是a[0][0],a[1][0],a[2][0],...,a[M-1][0],a[0][1],a[1][1]...，步長為M，這些不連續的元素可能會位于不同的緩存行，會出現較多的強制性缺失，因此在優化時可以通過循環交換來改變循環的順序來提高空間的局部性。點擊(此處)折疊或打開 1.int sumarraryrows(int a[M][N])2.{3.int i,j,sum=0;4.for(i=0;i<M;i++)5. for(j=0;j<N;j++)6. sum+=a[i][j];7.8.9.return sum;10.} 對于第二個函數，二維數組a求和訪問的內存順序與內存中的屬性一致，步長為1，在第一次訪問a[0][0]時會出現緩存缺失，但是因為內存中的數據是以緩存行為單位加載進緩存的，因此訪問后面的元素就會緩存命中，知道數組元素屬于另外衣蛾緩存行，這時再把下一個緩存行加載到緩存中。示例2 考慮下面的代碼：點擊(此處)折疊或打開 1.for(i=0;i<N;i++)2. a[i]=b[i]+1;3.4.for(i=0;i<N;i++)5. c[i]=b[i]*3; 兩個循環都要訪問數組b[i],可以把兩個循環合并，這樣可以通過時間局部性來減少對于數組b[i]的訪問：點擊(此處)折疊或打開 1.for(i=0;i<N;i++)2.{3. a[i]=b[i]+1; 4. c[i]=b[i]*3;5.} 示例3 考慮下面的代碼：點擊(此處)折疊或打開 1.for(i=0;i<N;i++)2. {3. a[i]=b[i]+1;4. c[i]=b[i]*3;5. f[i] = g[i]+h[i];6. } 假設N非常大，采用4-way緩存，但是在循環里面需要訪問六個數組，這些數組的地址間的距離比較大，可能會導致這些數組都映射為同一個組，那么在每次循環過程中后面兩次對于數組的訪問都會導致緩存缺失沖突，這時可以把循環分割成為兩個，每次循環訪問的數組不超過四個，從而減少沖突缺失：點擊(此處)折疊或打開 1.for(i=0;i<N;i++)2.{3. a[i]=b[i]+1;4. c[i]=b[i]*3; 5. }6.7.for(i=0;i<N;i++)8.{9. f[i] = g[i]+h[i];10.} 如果要訪問的對象占用的空間非常大，而緩存行相對來說比較小，這個時候對緩存的利用變得非常重要，看看下面的矩陣加法的運算代碼. 示例4點擊(此處)折疊或打開 1.void add(int a[MAX][MAX],int b[MAX][MAX])2.{3. int i,j;4. for(i=0;i<MAX;i++)5. for(j=0;j<MAX;j++)6. a[i][j] = a[i][j]+b[j][i];7.} 在上面的循環中，對于a的訪問步長為1，可以利用空間的局部性，但是b的訪問是按列進行訪問的，也就是b[0][i],b[1][i]...，步長為MAX，如果數組比較大，數組中的一行業大于緩存的大小，這樣每次訪問b都可能會出現缺失，要重新載入一個緩存行。循環塊優化可以把數組分成一個個的小塊數據，這個數據塊可以容納入緩存之中，在對于塊緩存進行處理之后就可以完全丟棄，然后繼續處理下一個數據，優化后的代碼為：點擊(此處)折疊或打開 1.#define BS //block size is selected as the loop-blocking factor2.void add(int a[MAX][MAX],int b[MAX][MAX])3.{4. int i,j,ii,jj;5.for(i=0;i<MAX;i+=BS)6. for(j=0;j<MAX;j+=BS)7. for(ii=0;ii<BS;ii++)8. for(jj=0;jj<BS;jj++)9. a[ii][jj]=a[ii][jj]+b[jj][ii];10.} 除了通過改變循環的順序和循環的結構來進行緩存優化之外，還可以通過選擇合適的數據布局來進行優化，其基本原則就是把那些經常使用的數據放在一起，這樣可以利用空間的局部性。比如有兩個數組，每次訪問一個數組時，總是要訪問另外一個數組： 示例5：點擊(此處)折疊或打開 1.#define N 10242.int a[N],b[N];3.for(i=0;i<N;i++)4. a[i]=Func(b[i]); 這個時候可以把兩個數組合并起來，先定義一個結構體類型，然后再頂一個結構體數組：點擊(此處)折疊或打開 1.#define N 10242.struct ALL{int a,b};3.struct ALL M[N];4.for(i=0;i<N;i++)5. M[i].a = Func(M[i].b); 如果一個大的結構中只有少數幾個字段會被經常訪問，但是大部分字段的訪問次數相對比較小，這個時候可以把原來的結構數組分割成多個數組，考慮下面的代碼：點擊(此處)折疊或打開 1.typdef struct __LISY{2.char key[8];3.cahr val[48];4.struct _LIST *next;5.}List;6.7.List *lookup(char *key,List *head){8.while(head != NULL){9.if(strncmp(key,head->key,strlen(key))==0)10.return head;11.12.head = head->next;13.}14.} 查找List的循環中只用到結構中的8個字節，但是val占用的字節相對比較大，這樣按照順序訪問時容易出現緩存的浪費，代碼可以優化為：點擊(此處)折疊或打開 1.typdef struct __LIST{ 2. cahr val[64];3. struct _LIST *next;4. }List;5. List list[MAX];6. char keylist[MAX*8];7. List *lookup(char *key,List *head,char *keyList,int nlist){8.int i=0;9. while(i<nlist){10. if(strncmp(key,keylist,strlen(keylist))==0)11. return head[i];12. i++;13. headList += strlen(keyList)+1;14. }15. } 除了緩存缺失影響內存的訪問速度之后，另外一個影響內存的訪問速度的因素就是數據對齊。一般來說，一個對齊的數據的訪問是最為有效的，這就要求變量的地址應該是能夠被該變量占用的字節數整除。比如，一個double需要8個字節的存儲空間，因此，如果double的地址不是8的倍數時，訪問該變量會帶來額外的延遲。值得注意的是，如果一個變量分配的空間跨越緩存行時，比如考慮變量的地址為0xFF0000FC，前面四個字節和后面四個字節在不同的緩存行，訪問該變量需要加載進兩個緩存行，這種跨越L緩存行（64B）邊界的未對齊數據訪問被稱為載入分離或者存儲分離。考慮下面的代碼行： double *p = (double *)malloc(sizeof(double)*number_of_doubles);這行代碼不能保證p的地址一定是8字節對齊的，這是因為malloc訪問的變量會保證4字節對齊，那么訪問double數據時的性能將會非常糟糕，上面的代碼可以優化為： double *p; double *np; p== (double *)malloc(sizeof(double)*(number_of_doubles+7L)); np = (double *)(((long )(p)+7L)&(-8L));有時你可能希望大的對象或者數組能夠與緩存行對齊，這是可以采用declspec來說明： __declspec(align(64)) int BigArray[1024]; 在使用多維數組時，維數不是2的冪時，可能會導致訪問后面的數組元素出現不對齊的情況，考慮下面的代碼： int a[64][63]; for(i=0;i<64;i++)for(j=0;j<63;j++)a[i][j] = i*64 +j;假設數組的起始位置是16字節對齊的，a[0][0],a[0][1],...,a[0][62]為16字節對齊，但是現在a[1][0]的距離16字節的邊界差12字節，不是16字節對齊的，顯然上面的代碼可能通過填充來保證每個數組元素都是16字節對齊。犧牲了空間來換取對齊帶來的內存訪問的性能提升： int a[64][64]; for(i=0;i<64;i++)for(j=0;j<63;j++)a[i][j] = i*64 +j;

總結

以上是生活随笔為你收集整理的Intel 平台编程总结----缓存的优化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。