Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3663326
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8581
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: C/C++

2011-09-11 17:44:23

     首先言明,本文严格意义上将不能算作原创,因为我写这些东西只不过是博客 的学习心得,不能将版权划到自己名下,毕竟咱不是喜欢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个组
  1. EAX
  2. (55h) Instruction TLB: 2-MB or 4-MB pages, fully associative, 7 entries
  3. (03h) Data TLB: 4-KB Pages, 4-way set associative, 64 entries
  4. (5Ah) Data TLB0: 2-MB or 4-MB pages, 4-way associative, 32 entries
  5. (01h) Instruction TLB: 4-KB Pages, 4-way set associative, 32 entries
  6. EBX:
  7. (F0h) 64-byte Prefetching
  8. (B2h) Instruction TLB: 4-KB pages, 4-way set associative, 64 entries
  9. (DDh) 3rd-level cache: 3-MB, 12-way set associative, 64-byte line size
  10. EDX:
  11. (09h) 1st-level Instruction Cache: 32-KB, 4-way set associative, 64-byte line size
  12. (CAh) Shared 2nd-level TLB: 4-KB pages, 4-way set associative, 512 entries
  13. (21h) 256KB L2 (MLC), 8-way set associative, 64-byte line size
  14. (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左右。是不是这样的。看下第一个测试用例的结果。
  1. int test_cache_linesize(int array[],int len,int K)
  2. {
  3.     int i;
  4.     for( i = 0;i<len;i += K)
  5.     {
  6.           array[i] *=3;
  7.     }
  8.     return 0;
  9. }

          当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左右。
  1. int test_cache_capacity(int array[],int cap)
  2. {
  3.     int i;
  4.     int lenmod = cap -1;
  5.     int times = 64*SIZE_1MB;
  6.      for(i = 0;i<times;i++)
  7.      {
  8.          array[(i*16) & (lenmod)]++;/*16 means linesize/sizeof(int) = 16*/
  9.      }
  10.      return 0;
  11. }


      第三部分我就不讲了,源代码给出大家可以自己在电脑上研究。不过第三部分要比较难懂,而且我前面提到的那篇讲的也不是很好懂。 

    下面是我的测试全代码
  1. /* http://igoro.com/archive/gallery-of-processor-cache-effects/ */

  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<linux/types.h>
  5. #include<string.h>

  6. #define SIZE_1KB (1024)
  7. #define SIZE_1MB (1024*1024)

  8. #define NUMBER 64*SIZE_1MB
  9. #define MILLION 1000000

  10. __u64 rdtsc()
  11. {
  12.   __u32 hi;
  13.     __u32 lo;
  14.     
  15.     __asm__ __volatile__
  16.     (
  17.      "rdtsc":"=a"(lo),"=d"(hi)
  18.     );
  19.     return (__u64)hi<<32|lo;
  20. }

  21. __u64 gettime()
  22. {
  23.        struct timeval tv;
  24.         gettimeofday(&tv,NULL);
  25.         return ((__u64)(tv.tv_sec))*MILLION+tv.tv_usec;
  26. }

  27. int test_cache_linesize(int array[],int len,int K)
  28. {
  29.  int i;
  30.     for( i = 0;i<len;i += K)
  31.     {
  32.           array[i] *=3;
  33.     }
  34.     return 0;
  35. }

  36. int test_cache_capacity(int array[],int cap)
  37. {
  38.     int i;
  39.     int lenmod = cap -1;
  40.     int times = 64*SIZE_1MB;
  41.      for(i = 0;i<times;i++)
  42.      {
  43.          array[(i*16) & (lenmod)]++;/*16 means linesize/sizeof(int) = 16*/
  44.      }
  45.      return 0;
  46. }

  47. int test_cache_associative(int array[],int size,int K)
  48. {
  49.     int i;
  50.      int cur =0;
  51.      __u64 begin;
  52.      __u64 end;
  53.      begin =gettime();
  54.      for( i = 0;i<SIZE_1MB;i++)
  55.      {
  56.          array[cur]++;
  57.          cur += K;
  58.          if(cur >= size)
  59.          cur = 0;
  60.      }
  61.      end = gettime();
  62.     
  63.      printf("when size = %10d, K = %10d : test_cache_associative cost %14llu us\n",
  64.      size,K ,end-begin);
  65.      return 0;
  66. }
  67. int test_cache()
  68. {
  69.     int *array = NULL;
  70.     array = malloc(NUMBER*sizeof(int));
  71.     __u64 begin ;
  72.     __u64 end;
  73.     int i;
  74.     int K;
  75.     int cap ;
  76.     int size;
  77.     if(array == NULL)
  78.     {
  79.          printf("malloc space for array failed \n");
  80.          return -1;
  81.     }
  82.     
  83.     for(i = 0;i<NUMBER;i++)
  84.     {
  85.      array[i] = i;
  86.     }
  87.    
  88.    printf("---------test cache linesize-------------------------------------------\n");
  89.     for(K = 1;K < 64*1024;K *= 2)
  90.     {
  91.          begin = gettime();
  92.          test_cache_linesize(array,NUMBER,K);
  93.          end = gettime();
  94.          printf("when K = %10d,multiply %10d times,cost %14llu us,average cost %llu us\n",
  95.          K,NUMBER/K,end - begin,(end-begin)/(NUMBER/K));
  96.          if(K == 1)
  97.          {
  98.                      begin = gettime();
  99.                      test_cache_linesize(array,NUMBER,K);
  100.                      end = gettime();
  101.                      printf("when K = %10d,multiply %10d times,cost %14llu us,average cost %llu us\n",
  102.                              K,NUMBER/K,end - begin,(end-begin)/(NUMBER/K));
  103.          }
  104.          
  105.      }
  106.     
  107.     printf("-----------test cache capacity-------------------------------------------\n");
  108.     for(cap = 1024;cap <= NUMBER;cap *= 2)
  109.     {
  110.          begin =gettime();
  111.          test_cache_capacity(array,cap);
  112.          end = gettime();
  113.          printf("when cap = %10d,cost %14llu us\n",
  114.          cap,end-begin);
  115.          if(cap == 2*SIZE_1MB/sizeof(int))
  116.          {
  117.               begin =gettime();
  118.               test_cache_capacity(array,3*SIZE_1MB/sizeof(int));
  119.               end = gettime();
  120.               printf("when cap = %10d,cost %14llu us\n",
  121.                        3*SIZE_1MB/sizeof(int),end-begin);
  122.          }
  123.                 
  124.     }
  125.     printf("-----------test cache associative ---------------------------------------\n");

  126.     for(size = 1*SIZE_1MB;size >= 4*SIZE_1KB;size /= 2)
  127.     {
  128.          for(K = 64;K <= 576 ;K += 64)
  129.          {
  130.               test_cache_associative(array,size,K);
  131.          }
  132.     }
  133.     free(array);
  134.     return 0;
  135.         
  136. }

  137. int main()
  138. {
  139.      test_cache();
  140.      return 0;
  141. }
阅读(9495) | 评论(2) | 转发(7) |
给主人留下些什么吧!~~

platinaluo2011-10-18 22:01:33

Algorithm拼错了~~~

GFree_Wind2011-10-11 12:27:41

一会儿去看看原版的呵。。。感谢分享