存儲器是分層次的，離CPU越近的存儲器，速度越快，每字節的成本越高，同時容量也因此越小。寄存器速度最快，離CPU最近，成本最高，所以個數容量有限，其次是高速緩存（緩存也是分級，有L1，L2等緩存），再次是主存（普通內存），再次是本地磁盤。
寄存器的速度最快，可以在一個時鐘周期內訪問，其次是高速緩存，可以在幾個時鐘周期內訪問，普通內存可以在幾十個或幾百個時鐘周期內訪問。
（注 本圖來自Ulrich Drepper大牛的講稿，如有侵權，通知即刪）
存儲器分級，利用的是局部性原理。我們可以以經典的閱讀書籍為例。我在讀的書，捧在手裡（寄存器），我最近頻繁閱讀的書，放在書桌上（緩存），隨時取來讀。當然書桌上只能放有限幾本書。我更多的書在書架上（內存）。如果書架上沒有的書，就去圖書館（磁盤）。我要讀的書如果手裡沒有，那麼去書桌上找，如果書桌上沒有，去書架上找，如果書架上沒有去圖書館去找。可以對應寄存器沒有，則從緩存中取，緩存中沒有，則從內存中取到緩存，如果內存中沒有，則先從磁盤讀入內存，再讀入緩存，再讀入寄存器。
本系列的文章重點介紹緩存cache。了解如何獲取cache的參數，了解緩存的組織結構，了解cache對程序的影響，了解如何利用cache提升性能。
本文作為系列文章的第一篇，講述的如何獲取cache的組成結構和如何獲取cache的參數。
cache分成多個組，每個組分成多個行，linesize是cache的基本單位，從主存向cache遷移數據都是按照linesize為單位替換的。比如linesize為32Byte，那麼遷移必須一次遷移32Byte到cache。 這個linesize比較容易理解，想想我們前面書的例子，我們從書架往書桌搬書必須以書為單位，肯定不能把書撕了以頁為單位。書就是linesize。當然了現實生活中每本書頁數不同，但是同個cache的linesize總是相同的。
所謂8路組相連（ 8-way set associative）的含義是指，每個組裡面有8個行。
我們知道，cache的容量要遠遠小於主存，主存和cache肯定不是一一對應的，那麼主存中的地址和cache的映射關系是怎樣的呢？
拿到一個地址，首先是映射到一個組裡面去。如何映射？取內存地址的中間幾位來映射。
舉例來說，data cache: 32-KB, 8-way set associative, 64-byte line size
Cache總大小為32KB，8路組相連（每組有8個line），每個line的大小linesize為64Byte,OK，我們可以很輕易的算出一共有32K/8/64=64 個組。
對於32位的內存地址，每個line有2^6 = 64Byte，所以地址的【0，5】區分line中的那個字節。一共有64個組。我們取內存地址中間6為來hash查找地址屬於那個組。即內存地址的【6，11】位來確定屬於64組的哪一個組。組確定了之後，【12，31】的內存地址與組中8個line挨個比對，如果【12，31】為與某個line一致，並且這個line為有效，那麼緩存命中。
OK，cache分成三類，
1 直接映射高速緩存，這個簡單，即每個組只有一個line，選中組之後不需要和組中的每個line比對， 因為只有一個line。
2 組相聯高速緩存，這個就是我們前面介紹的cache。 S個組，每個組E個line。
3 全相聯高速緩存，這個簡單，只有一個組，就是全相聯。不用hash來確定組，直接挨個比對高位地址，來確定是否命中。可以想見這種方式不適合大的緩存。想想看，如果4M 的大緩存 linesize為32Byte，采用全相聯的話，就意味著4*1024*1024/32 = 128K 個line挨個比較，來確定是否命中，這是多要命的事情。高速緩存立馬成了低速緩存了。
描述一個cache需要以下參數 ：
1 cache分級，L1 cache, L2 cache, L3 cache,級別越低，離ｃｐｕ越近
2 cache的容量
3 cache的linesize
4 cache 每組的行個數.
組的個數完全可以根據上面的參數計算出來,所以沒有列出來.
Intel手冊中用這樣的句子來描述cache:
8-MB L3 Cache, 16-way set associative, 64-byte line size
如何獲取cache的參數呢,到了我們的老朋友cpuid指令,當eax為0x2的時候,cpuid指令獲取到cache的參數. 下面給出代碼:
#include<stdio.h>
#include<stdlib.h>
int d_eax;
int d_ebx;
int d_ecx;
int d_edx;
int parse_cache()
{
asm
(
"movl $2,%eax\n\t"
"cpuid\n\t"
"mov %eax,d_eax\n\t"
"mov %ebx,d_ebx\n\t"
"mov %ecx,d_ecx\n\t"
"mov %edx,d_edx\n\t"
);
printf("d_eax : %x\nd_ebx : %x\nd_ecx : %x\nd_edx : %x\n",
d_eax,d_ebx,d_ecx,d_edx);
return 0;
}
int main()
{
parse_cache();
return 0;
}
root@libin:~/program/assembly/cache# ./test
d_eax : 55035a01
d_ebx : f0b2dd
d_ecx : 0
d_edx : 9ca212c
我的電腦上運行結果如上圖,查看intel的手冊可知
EAX
(55h) Instruction TLB: 2-MB or 4-MB pages, fully associative, 7 entries
(03h) Data TLB: 4-KB Pages, 4-way set associative, 64 entries
(5Ah) Data TLB0: 2-MB or 4-MB pages, 4-way associative, 32 entries
(01h) Instruction TLB: 4-KB Pages, 4-way set associative, 32 entries
EBX:
(F0h) 64-byte Prefetching
(B2h) Instruction TLB: 4-KB pages, 4-way set associative, 64 entries
(DDh) 3rd-level cache: 3-MB, 12-way set associative, 64-byte line size
EDX:
(09h) 1st-level Instruction Cache: 32-KB, 4-way set associative, 64-byte line size
(CAh) Shared 2nd-level TLB: 4-KB pages, 4-way set associative, 512 entries
(21h) 256KB L2 (MLC), 8-way set associative, 64-byte line size
(2Ch) 1st-level data cache: 32-KB, 8-way set associative, 64-byte line size
參考文獻:
1 Intel? Processor Identification andthe CPUID Instruction
2 Professional Assembly Language Richard Blum著
3 深入理解計算機系統
首先言明，本文嚴格意義上將不能算作原創，因為我寫這些東西只不過是博客 Gallery
of Processor Cache Effect的學習心得，不能將版權劃到自己名下，畢竟咱不是喜歡45度角仰望天空的郭四姑娘。由於原文是英文版，而且作者用的是C++。原文提到的實驗，我做了一部分，加深了對Cache的理解。英文比較好的兄弟就不必聽我聒噪了，直接點鏈接看原文好了。
OK，繼續我們的探索之旅。深入理解cache（1）得到了我的PC的cache參數如下:
L1 Cache : 32KB , 8路組相連，linesize為 64Byte 64個組
L2 Cache：256KB 8路組相連，linesize為 64Byte 512個組
L3 Cache： 3MB 12路組相連，linesize為 64Byte 4096個組
EAX
(55h) Instruction TLB: 2-MB or 4-MB pages, fully associative, 7 entries
(03h) Data TLB: 4-KB Pages, 4-way set associative, 64 entries
(5Ah) Data TLB0: 2-MB or 4-MB pages, 4-way associative, 32 entries
(01h) Instruction TLB: 4-KB Pages, 4-way set associative, 32 entries
EBX:
(F0h) 64-byte Prefetching
(B2h) Instruction TLB: 4-KB pages, 4-way set associative, 64 entries
(DDh) 3rd-level cache: 3-MB, 12-way set associative, 64-byte line size
EDX:
(09h) 1st-level Instruction Cache: 32-KB, 4-way set associative, 64-byte line size
(CAh) Shared 2nd-level TLB: 4-KB pages, 4-way set associative, 512 entries
(21h) 256KB L2 (MLC), 8-way set associative, 64-byte line size
(2Ch) 1st-level data cache: 32-KB, 8-way set associative, 64-byte line size、
1 測試cache的linesize
代碼看起來有點長，但是分成了3段。先看第一個測試，測試cache的linesize。
我們知道，cache的遷移是以linesize為單位的，所以，用戶縱然只訪問一個int，PC需要從主存拷貝1條line 進入Cache，對於我的電腦來說，就是copy
64B。
看下面的代碼，測試linesize，如果K=1，遍歷整個數組，如果K=16，只訪問16倍數位置的值。依次類推。如果K=16，乘法的個數是K=1的時候1/16。我們可以推測，K=16的時候，程序執行時間是K=1的時候的1/16左右。是不是這樣的。看下第一個測試用例的結果。
int test_cache_linesize(int array[],int len,int K)
{
int i;
for( i = 0;i<len;i += K)
{
array[i] *=3;
}
return 0;
}
當K = 1 ，2，4 ......16的時候，雖然計算乘法的次數相差很大，但是，代碼執行的時間是相近的都是80ms附近，但是當K = 32，64的時候，隨著計算乘法的次數減半，代碼執行的時間也減半。
原因在於，16 = （linesize）/sizeof（int）= 64/4，當K <16的時候，第一個int不命中，接下來的都命中的，乘法的個數雖然減半，但是從主存向Cache拷貝數據並沒有減半。乘法消耗的指令周期要遠低於從主存往cache裡面copy數據，所以當K<16
的時候，既然從主存Cp數據到Cache的次數是相同的，那麼總的執行時間差距不大就可以理解了。
當K>16的時候，每次都需要去主存取新的line，所以步長K增大一倍，去主存copy數據到cache的次數就減少為原來的一半，所以運行時間也減少為
原來的1半。
2 Cache的大小。
我的PC 有三級Cache，容量分別是32K 256K ,3M .這些參數對程序有什麼影響呢。
下面的測試代碼，執行的次數是一樣的，都是64M次但是array的大小不一樣。我們分別傳入參數為1K，2K ，4K ,8K.....64MB 。在執行之前我們先分析下。
目前，如果array的大小是多大，循環執行的次數是一樣的。我們的1級Cache大小是32KB，也就是最多容納8192個int。如果我們的數組大小就是8192個int，那麼除了第一次執行需要將數據從
主存-->L3 Cache--->L2 Cache -->L1 Cache傳上來，後面再次執行的時候，由於整個數組全在L1 Cache，L1 Cache命中，速度很快。當然如果數組大小小於8192個int，L1更能容納的下。8192是個坎。數組大於8192個int，性能就會下降一點。
如果我們的array大小大於L1 cache容量會怎樣呢？看下我們的L2 Cache，大小256KB，即64K個int，換句話說，如果數組長度小於64K個int，也不賴，至少L2
Cache 容納的下，雖然L1 Cache每寫滿32KB就需要將交換出去。換句話說，64K是個坎，數組大於64K個int，性能就會下降。
L3Cache我就不說，畢竟我不是唐僧，一樣的情況，對於我的3M 緩存，3M/4 = 768K 是個坎，如果數組大於768個int，那麼性能又會下降。
好了可以看下面的圖了，和我們想的一樣，
當低於8192的時候，都是120ms 左右，
[8192,64K ]的時候，都是200ms 左右
[64K ,768K ]的時候，都是300ms左右
大於768的時候，1200ms左右。
int test_cache_capacity(int array[],int cap)
{
int i;
int lenmod = cap -1;
int times = 64*SIZE_1MB;
for(i = 0;i<times;i++)
{
array[(i*16) & (lenmod)]++;/*16
means linesize/sizeof(int) = 16*/
}
return 0;
}
第三部分我就不講了，源代碼給出大家可以自己在電腦上研究。不過第三部分要比較難懂，而且我前面提到的那篇講的也不是很好懂。
下面是我的測試全代碼
/*http://igoro.com/archive/gallery-of-processor-cache-effects/ */
#include<stdio.h>
#include<stdlib.h>
#include<linux/types.h>
#include<string.h>
#define SIZE_1KB (1024)
#define SIZE_1MB (1024*1024)
#define NUMBER 64*SIZE_1MB
#define MILLION 1000000
__u64 rdtsc()
{
__u32 hi;
__u32 lo;
__asm__ __volatile__
(
"rdtsc":"=a"(lo),"=d"(hi)
);
return (__u64)hi<<32|lo;
}
__u64 gettime()
{
struct timeval tv;
gettimeofday(&tv,NULL);
return ((__u64)(tv.tv_sec))*MILLION+tv.tv_usec;
}
int test_cache_linesize(int array[],int len,int K)
{
int i;
for( i = 0;i<len;i += K)
{
array[i] *=3;
}
return 0;
}
int test_cache_capacity(int array[],int cap)
{
int i;
int lenmod = cap -1;
int times = 64*SIZE_1MB;
for(i = 0;i<times;i++)
{
array[(i*16) & (lenmod)]++;/*16
means linesize/sizeof(int) = 16*/
}
return 0;
}
int test_cache_associative(int array[],int size,int K)
{
int i;
int cur =0;
__u64 begin;
__u64 end;
begin =gettime();
for( i = 0;i<SIZE_1MB;i++)
{
array[cur]++;
cur += K;
if(cur >= size)
cur = 0;
}
end = gettime();
printf("when size = %10d, K = %10d : test_cache_associative cost %14llu us\n",
size,K ,end-begin);
return 0;
}
int test_cache()
{
int *array = NULL;
array = malloc(NUMBER*sizeof(int));
__u64 begin ;
__u64 end;
int i;
int K;
int cap ;
int size;
if(array == NULL)
{
printf("malloc space for array failed \n");
return -1;
}
for(i = 0;i<NUMBER;i++)
{
array[i] = i;
}
printf("---------test cache linesize-------------------------------------------\n");
for(K = 1;K < 64*1024;K *= 2)
{
begin = gettime();
test_cache_linesize(array,NUMBER,K);
end = gettime();
printf("when K = %10d,multiply %10d times,cost %14llu us,average cost %llu us\n",
K,NUMBER/K,end - begin,(end-begin)/(NUMBER/K));
if(K == 1)
{
begin = gettime();
test_cache_linesize(array,NUMBER,K);
end = gettime();
printf("when K = %10d,multiply %10d times,cost %14llu us,average cost %llu us\n",
K,NUMBER/K,end - begin,(end-begin)/(NUMBER/K));
}
}
printf("-----------test cache capacity-------------------------------------------\n");
for(cap = 1024;cap <= NUMBER;cap *= 2)
{
begin =gettime();
test_cache_capacity(array,cap);
end = gettime();
printf("when cap = %10d,cost %14llu us\n",
cap,end-begin);
if(cap == 2*SIZE_1MB/sizeof(int))
{
begin =gettime();
test_cache_capacity(array,3*SIZE_1MB/sizeof(int));
end = gettime();
printf("when cap = %10d,cost %14llu us\n",
3*SIZE_1MB/sizeof(int),end-begin);
}
}
printf("-----------test cache associative ---------------------------------------\n");
for(size = 1*SIZE_1MB;size >= 4*SIZE_1KB;size /= 2)
{
for(K = 64;K <= 576 ;K += 64)
{
test_cache_associative(array,size,K);
}
}
free(array);
return 0;
}
int main()
{
test_cache();
return 0;
}
上文來自：http://www.360doc.com/content/14/1015/13/10249440_417146850.shtml
