在L1缓存中缓存2KB数据时内存带宽崩溃的原因

Question

在一个自学项目中,我借助以下代码测量内存的带宽(这里解释,整个代码在问题的最后跟随):

unsigned int doit(const std::vector<unsigned int> &mem){
   const size_t BLOCK_SIZE=16;
   size_t n = mem.size();
   unsigned int result=0;
   for(size_t i=0;i<n;i+=BLOCK_SIZE){           
             result+=mem[i];
   }
   return result;
}

//... initialize mem, result and so on
int NITER = 200; 
//... measure time of
   for(int i=0;i<NITER;i++)
       resul+=doit(mem)

BLOCK_SIZE以这种方式选择,每个整数加法获取整个64字节高速缓存行.我的机器(Intel-Broadwell)每个整数附加需要大约0.35纳秒,所以上面的代码可以使带宽饱和到高达182GB/s(这个值只是一个上限,可能很大,很重要的是不同尺寸的带宽比率).代码用g++和编译-O3.

改变向量的大小,我可以观察到L1(*) - ,L2-,L3-高速缓存和RAM-内存的预期带宽:

但是,我真的很难解释一下:L1高速缓存测量带宽的崩溃大小约为2 kB,这里的分辨率要高一些:

我可以在我有权访问的所有机器上重现结果(具有Intel-Broadwell和Intel-Haswell处理器).

我的问题:内存大小大约2 KB的性能崩溃是什么原因？

(*)我希望我理解正确,对于L1缓存而言,不是64字节,而是每次添加只有4个字节被读取/传输(没有更快的缓存,其中必须填充缓存行),因此L1的绘制带宽是只有上限而不是badwidth本身.

编辑:当选择内部for循环中的步长时

• 8(而不是16)崩溃发生1KB
• 4(而不是16)崩溃发生0.5KB

即当内环由约31-35步/读时组成时.这意味着崩溃不是由于内存大小,而是由于内循环中的步数.

可以通过分支未命中来解释,如@ user10605163的好答案所示.

---

列出重现结果

bandwidth.cpp:

#include <vector>
#include <chrono>
#include <iostream>
#include <algorithm>


//returns minimal time needed for one execution in seconds:
template<typename Fun>
double timeit(Fun&& stmt, int repeat, int number)
{  
   std::vector<double> times;
   for(int i=0;i<repeat;i++){
       auto begin = std::chrono::high_resolution_clock::now();
       for(int i=0;i<number;i++){
          stmt();
       }
       auto end = std::chrono::high_resolution_clock::now();
       double time = std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count()/1e9/number;
       times.push_back(time);
   }
   return *std::min_element(times.begin(), times.end());
}


const int NITER=200;
const int NTRIES=5;
const size_t BLOCK_SIZE=16;


struct Worker{
   std::vector<unsigned int> &mem;
   size_t n;
   unsigned int result;
   void operator()(){
        for(size_t i=0;i<n;i+=BLOCK_SIZE){           
             result+=mem[i];
        }
   }

   Worker(std::vector<unsigned int> &mem_):
       mem(mem_), n(mem.size()), result(1)
   {}
};

double PREVENT_OPTIMIZATION=0.0;


double get_size_in_kB(int SIZE){
   return SIZE*sizeof(int)/(1024.0);
}

double get_speed_in_GB_per_sec(int SIZE){
   std::vector<unsigned int> vals(SIZE, 42);
   Worker worker(vals);
   double time=timeit(worker, NTRIES, NITER);
   PREVENT_OPTIMIZATION+=worker.result;
   return get_size_in_kB(SIZE)/(1024*1024)/time;
}


int main(){

   int size=BLOCK_SIZE*16;
   std::cout<<"size(kB),bandwidth(GB/s)\n";
   while(size<10e3){
       std::cout<<get_size_in_kB(size)<<","<<get_speed_in_GB_per_sec(size)<<"\n";
       size=(static_cast<int>(size+BLOCK_SIZE)/BLOCK_SIZE)*BLOCK_SIZE;
   }

   //ensure that nothing is optimized away:
   std::cerr<<"Sum: "<<PREVENT_OPTIMIZATION<<"\n";
}

create_report.py:

import sys
import pandas as pd
import matplotlib.pyplot as plt

input_file=sys.argv[1]
output_file=input_file[0:-3]+'png'
data=pd.read_csv(input_file)

labels=list(data)    
plt.plot(data[labels[0]], data[labels[1]], label="my laptop")
plt.xlabel(labels[0])
plt.ylabel(labels[1])   
plt.savefig(output_file)
plt.close()

建立/运行/创建报告:

>>> g++ -O3 -std=c++11 bandwidth.cpp -o bandwidth
>>> ./bandwidth > report.txt
>>> python create_report.py report.txt
# image is in report.png

Answer 1

我略微改变了值:NITER = 100000并且NTRIES=1得到了一个不那么嘈杂的结果.

我现在没有Broadwell可用,但是我在Coffee-Lake上尝试了你的代码并且性能下降,不是2KB,而是大约4.5KB.此外,我发现吞吐量的不稳定行为略高于2KB.

图表中的蓝线对应于您的测量值(左轴):

这里的红线是结果perf stat -e branch-instructions,branch-misses,给出了未正确预测的分支分数(百分比,右轴).正如您所看到的,两者之间存在明显的反相关性.

在查看更详细的perf报告时,我发现基本上所有这些分支错误预测都发生在最内部的循环中Worker::operator().如果循环分支采取/不采取模式过长的分支预测将不能够保持它的轨道,因此内循环的退出分支将预测失误,导致产量锐减.随着迭代次数的进一步增加,这种单一误预测的影响将变得不那么显着,导致吞吐量的缓慢恢复.

有关丢弃前的不稳定行为的更多信息,请参阅下面的@PeterCordes所做的评论.

在任何情况下,避免分支错误预测的最佳方法是避免分支,因此我手动展开循环Worker::operator(),例如:

void operator()(){
    for(size_t i=0;i+3*BLOCK_SIZE<n;i+=BLOCK_SIZE*4){
         result+=mem[i];
         result+=mem[i+BLOCK_SIZE];
         result+=mem[i+2*BLOCK_SIZE];
         result+=mem[i+3*BLOCK_SIZE];
    }
}

展开2,3,4,6或8次迭代会得到以下结果.请注意,我没有更正向量末尾的块,这些块因展开而被忽略.因此,应忽略蓝线中的周期性峰值,周期性图案的下限基线是实际带宽.

正如您所看到的,分支错误预测的分数并没有真正改变,但由于分支总数减少了展开迭代的因子,它们将不再对性能做出强烈贡献.

如果循环展开,处理器还可以更自由地无序地进行计算,这也是一个额外的好处.

如果这是应该有实际的应用程序,我会建议尽量给热循环固定迭代或可分一些担保的数量编译时间,使(也许有一些额外的提示),编译器可以在最佳数量的决定迭代展开.