判定算法在数据高速缓存上的效率

3M公司决定通过在白色纸张上打印黄色方块来制作便利贴（Post-Its）。在打印过程中，他们需要为方块中的每一个点设置CMYK（青色、品红色、黄色、黑色）值。3M公司雇用你判定下面算法在一个具有2048字节、直接映射、块大小为32字节的数据高速缓存上的效率。有如下定义：

struct  point_color  {
int c;
int m;
int y;
int k;
 };
struct point_color square[16][16];
 int i, j;

  有如下假设：
  sizeof(int) 的值为 4。
  square起始于存储器地址 0 。
  高速缓存初始为空。
  唯一的存储器访问是对square数组中的元素。变量 i和j都存储在寄存器中。
 

1. 确定下列代码的高速缓存性能：

for (i = 0; i < 16; i++)
  for (j = 0; j < 16; j++) 
  {
    square[i][j].c = 0;
    square[i][j].m = 0;
    square[i][j].y = 1;
    square[i][j].k = 0;
  }

A.写总数是多少？  
B.在高速缓存中不命中的写总数是多少？ 
C.不命中率是多少？%

每条缓存行可容纳两个 16 字节的点颜色结构体。该方形数组是4096字节大小，使得缓存（容量为 2048 字节）只能容纳数组的一半。由于代码采用的是行方向上步长为 1 的引用模式，因此每条缓存行的未命中模式是：先出现一次未命中，随后出现 7 次命中。

2. 确定下列代码的高速缓存性能：

for (i = 0; i < 16; i++)
  for (j = 0; j < 16; j++) 
  {
    square[j][i].c = 0;
    square[j][i].m = 0;
    square[j][i].y = 1;
    square[j][i].k = 0;
}

1. 写总数是多少？ 1024
2. 在高速缓存中不命中的写总数是多少？ 
3. 不命中率是多少？%

  由于缓存无法容纳整个数组，在对数组后半部分进行列方向扫描时，会将在扫描前半部分时加载到缓存中的行逐出。因此，对于每一个结构体，都会出现一次未命中，随后是 3 次命中。

2. 确定下列代码的高速缓存性能：

for (i = 0; i < 16; i++)
  for (j = 0; j < 16; j++) 
    square[i][j].y = 1;
   


for (i = 0; i < 16; i++)
  for (j = 0; j < 16; j++) 
  {
    square[i][j].c = 0;
    square[i][j].m = 0;
    square[i][j].k = 0;
  }

1. 写总数是多少？ 1024
2. 在高速缓存中不命中的写总数是多少？ 256
3. 不命中率是多少？ 25%

    两个循环都以行优先顺序（row-major order）访问数组。第一个循环执行了256次写入操作。由于每条缓存行能容纳两个结构体，因此这些引用中有一半会命中缓存，另一半则未命中。第二个循环总共执行了768次写入操作。对于每对结构体，首次访问时会因缓存未预热（cold miss）而未命中，随后会有5次命中。因此，这个循环总共会遇到128次未命中。综合起来，两个循环共有256+768=1024次写入操作，以及128+128=256次未命中。