通过一个程序说明cache命中率对内存访问速度的影响

liangbch

我们知道，现代的CPU包含cache部件，cache亦称高速缓冲，其中存储了CPU最近访问过的或者将要访问的数据。和通常的RAM相比，cache也是一种存储器，其特点存储速度非常快，但同样容量的cache比同样的RAM成本高了很多，因此不能做的太大。 cache亦采用多级存储结构，通常的CPU有8-64K的一级cache,256K-12M的2级cache，有的CPU还有3级cache.许多现代的CPU的2级cache与CPU同频，因此速度非常快。 按照intel的说法，在通常情况下，对RAM的访问实际上近似等同于对cache的访问，因为在90%以上的情况下，RAM中的数据已经被缓冲到cache. 因为程序对RAM的访问具有局部性，也就是说，下次访问的数据的地址和这次访问的数据的地址相邻，所有当访问d[ i ]时，CPU的后台"程序"自动把和d[ i ]相邻的数据载入cache. 下次访问d[ i+1 ]时，可直接从cache中读写数据. 只用当访问的数据不在cache中，CPU才直接从RAM读取数据，由于RAM的很高的延时，故直接从RAM中读写数据比从cache中读写数据要慢得多。 显然，对数据的顺序访问具有极高的cache命中率，因此对数据的顺序访问的性能几乎可达到内存带宽这个上限。内存带宽指内存和cache间批量数据传递的速率,注意内存带宽和内存延时无必然的联系，因为通常情况下，CPU在后台做内存和cache间数据交换，所有内存的高延时被隐藏了。 反之，对数据的随机访问则使得cache命中率大大降低，一旦cache未命中，CPU不得不与内存之间交换数据，此时，内存的高延时就成为瓶颈。 楼下的代码分别测试 对1M*4,4M*4,16M*4,64M*4的内存块进行顺序读取和随机读取所耗费的时间。其速度比如下(测试机的L2 cache is 6M) 块大小 速度比 4M 3.0 16M 7.1 64M 11.2 256M 12.5

liangbch

2. #include <stdlib.h>
3. #include <stdio.h>
4. #include <memory.h>
6. #include "currTime.h"
8. typedef unsigned long DWORD;
11. void initAccessTable(int accessTab[], int len, int isRand )
12. {
13. int i,idx;
15. if (isRand==0) //sequential access
16. {
17. for (i=0;i<len;i++)
18. {
19. accessTab[i]=i;
20. }
21. }
22. else
23. {
24. char *tmpBuff=(char *)malloc(len);
25. memset(tmpBuff,0,len);
27. for (i=0;i<len;)
28. {
29. idx= ((rand() << 15)+ rand()) % len;
30. if ( tmpBuff[idx]==0)
31. {
32. accessTab[i++]=idx;
33. tmpBuff[idx]=1;
34. }
35. }
36. free(tmpBuff);
37. }
38. }
40. int sum(DWORD pBuff[], int accessTab[], int len)
41. {
42. DWORD s=0;
43. int i,idx;
44. for (i=0;i<len;i++)
45. {
46. idx=accessTab[i];
47. s += pBuff[idx];
48. }
49. return s;
50. }
52. //mode=0, sequential access
53. //mode=1, random access
54. void test_access_RAM(int blk_len, int mode)
55. {
56. DWORD *pBuff=malloc(sizeof(DWORD)*blk_len);
57. int *accessTab=malloc(sizeof(int)*blk_len);
58. DWORD i,s;
59. double t;
61. for (i=0;i<blk_len;i++)
62. {
63. pBuff[i]=rand() & 15;
64. }
66. initAccessTable(accessTab, blk_len, mode);
68. t=currTime();
69. s=sum(pBuff,accessTab,blk_len);
70. t=currTime()-t;
72. printf("s=%d\n",s);
73. if ( mode ==0)
74. printf("sequential access %d number, it take %.6f ms\n",blk_len,t*1000 );
75. else
76. printf("random access %d number, it take %.6f ms\n",blk_len,t*1000 );
78. free(pBuff);
79. free(accessTab);
81. }
83. void test()
84. {
85. int blk_len;
86. int i,loop;
88. loop=3;
89. blk_len=1024*1024;
91. for (i=0;i<loop;i++)
92. { test_access_RAM(blk_len,0); }
94. for (i=0;i<loop;i++)
95. { test_access_RAM(blk_len,1); }
97. //----------------------------
98. blk_len=4*1024*1024;
99. for (i=0;i<loop;i++)
100. { test_access_RAM(blk_len,0); }
102. for (i=0;i<loop;i++)
103. { test_access_RAM(blk_len,1); }
105. //----------------------------
106. blk_len=16*1024*1024;
107. for (i=0;i<loop;i++)
108. { test_access_RAM(blk_len,0); }
110. for (i=0;i<loop;i++)
111. { test_access_RAM(blk_len,1); }
113. //----------------------------
114. blk_len=64*1024*1024;
115. for (i=0;i<loop;i++)
116. { test_access_RAM(blk_len,0); }
118. for (i=0;i<loop;i++)
119. { test_access_RAM(blk_len,1); }
120. }
122. int main(int argc, char* argv[])
123. {
124. test();
125. return 0;
126. }

复制代码

kenmark

的确，random access 现在已经不能简单认为是O(1)了，但是细化的研究还是比较欠缺，做cache的还是做编译器的比较多，系统里面大家对cache的认识都比较简化。 最近在思索如果提供给programmer在cache-aware 的programming model，但又不至于增加复杂度