计算给定C代码的数据缓存缺失率及求解困惑咨询

基础参数 #

• 数据缓存大小：32KB = 32768字节
• 缓存行大小：128字节
• int类型大小：4字节 → 每个缓存行可容纳 128 / 4 = 32 个int元素
• 无缓存行预取

代码1：N=64，列优先访问 #

int N = 64;
int a[N*N];
for (int j = 0; j < N; j++)
  for (int i = 0; i < N; i++)
      a[i*N+j] = i*j;

数组规模 #

数组总元素数：64*64=4096，总大小：4096*4=16384字节=16KB，小于32KB缓存，整个数组可完全存入缓存。

访问模式分析 #

外层循环遍历列（j），内层循环遍历行（i），访问步长为N=64个int（即64*4=256字节），远大于缓存行大小。但缓存行包含32个连续int元素，因此：

• 当j∈[0,31]时，所有a[0*64+j]（列首元素）都落在同一个缓存行中。第一次访问j=0的列首元素时触发缺失，加载该缓存行；后续j=1~31的列首元素都命中。
• 对于j=0的列，每个行元素a[i*64+0]的地址间隔256字节，对应不同的缓存行，共64个缓存行，全部触发缺失（缓存足够容纳这些行）。
• j=1~31的列，每个行元素都已在j=0列访问时加载的缓存行中，全部命中。
• 同理，j∈[32,63]时，j=32的列触发64次缺失，j=33~63的列全部命中。

缺失率计算 #

• 总访问次数：64*64=4096
• 总缺失次数：64 + 64=128
• 缺失率：(128/4096)*100% = 3.125%

代码2：N=512，行优先访问 #

int N = 512;
int a[N*N];
for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
      a[i*N+j] = i*j;

数组规模 #

数组总元素数：512*512=262144，总大小：262144*4=1048576字节=1MB，远大于32KB缓存。

访问模式分析 #

外层循环遍历行（i），内层循环遍历列（j），访问步长为1个int（连续访问）：

• 每一行有512个元素，对应512/32=16个缓存行。
• 每个缓存行的第一个元素触发缺失，后续31个元素命中；每一行共16次缺失。
• 由于数组远大于缓存，已加载的缓存行后续不会被重复访问，因此不会出现重复缺失。

缺失率计算 #

• 总访问次数：512*512=262144
• 总缺失次数：512*16=8192
• 缺失率：(8192/262144)*100% = 3.125%

内容的提问来源于stack exchange，提问作者AlexCray