L1-cache 缓存 2KB 数据时内存带宽崩溃的原因
Reason for collapse of memory bandwidth when 2KB of data is cached in L1-cache
在一个自学项目中,我借助以下代码测量了内存的带宽(此处转述,整个代码在问题的末尾):
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 字节是 read/transfered(没有更快的缓存必须填充缓存行),所以 L1 的绘制带宽只是上限而不是 badwidth 本身。
编辑:当内部for循环中的步长选择为
- 8(而不是 16)崩溃发生在 1KB
- 4(而不是 16)崩溃发生在 0.5KB
即当内循环由大约 31-35 steps/reads 组成时。这意味着崩溃不是由于内存大小,而是由于内部循环中的步骤数。
可以用中的分支未命中来解释。
重现结果的列表
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()
Building/running/creating 报告:
>>> g++ -O3 -std=c++11 bandwidth.cpp -o bandwidth
>>> ./bandwidth > report.txt
>>> python create_report.py report.txt
# image is in report.png
我稍微更改了值:NITER = 100000
和 NTRIES=1
以获得噪音较小的结果。
我现在没有可用的 Broadwell,但是我在我的 Coffee-Lake 上尝试了您的代码并发现性能下降,不是 2KB,而是大约 4.5KB。此外,我发现略高于 2KB 的吞吐量行为不稳定。
图中的蓝线对应于您的测量值(左轴):
这里的红线是 perf stat -e branch-instructions,branch-misses
的结果,给出了未正确预测的分支部分(百分比,右轴)。如您所见,两者之间存在明显的反相关。
查看更详细的 perf
报告,我发现基本上所有这些分支预测错误都发生在 Worker::operator()
的最内层循环中。如果循环分支的 taken/non-taken 模式变得太长,分支预测器将无法跟踪它,因此内部循环的出口分支将被错误预测,导致吞吐量急剧下降。随着迭代次数的进一步增加,这个单一错误预测的影响将变得不那么显着,从而导致吞吐量恢复缓慢。
有关掉落前不稳定行为的更多信息,请参阅下面@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 次迭代得到以下结果。请注意,我没有更正矢量末尾的块,这些块由于展开而被忽略。因此应忽略蓝线中的周期性峰值,周期性模式的下界基线是实际带宽。
如您所见,分支预测错误的比例并没有真正改变,但由于分支总数因展开迭代而减少,它们将不再对性能有很大贡献。
还有一个额外的好处是,如果展开循环,处理器可以更自由地进行乱序计算。
如果这应该有实际应用,我建议尝试给热循环一个编译时固定的迭代次数或一些可除性保证,以便(可能有一些额外的提示)编译器可以决定关于要展开的最佳迭代次数。
可能无关,但您的 Linux 机器可能以 CPU 频率播放。我知道 Ubuntu 18 有一个在功率和性能之间取得平衡的调节器。您还想尝试处理进程亲和性,以确保它不会在 运行 时迁移到不同的核心。
在一个自学项目中,我借助以下代码测量了内存的带宽(此处转述,整个代码在问题的末尾):
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 字节是 read/transfered(没有更快的缓存必须填充缓存行),所以 L1 的绘制带宽只是上限而不是 badwidth 本身。
编辑:当内部for循环中的步长选择为
- 8(而不是 16)崩溃发生在 1KB
- 4(而不是 16)崩溃发生在 0.5KB
即当内循环由大约 31-35 steps/reads 组成时。这意味着崩溃不是由于内存大小,而是由于内部循环中的步骤数。
可以用
重现结果的列表
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()
Building/running/creating 报告:
>>> g++ -O3 -std=c++11 bandwidth.cpp -o bandwidth
>>> ./bandwidth > report.txt
>>> python create_report.py report.txt
# image is in report.png
我稍微更改了值:NITER = 100000
和 NTRIES=1
以获得噪音较小的结果。
我现在没有可用的 Broadwell,但是我在我的 Coffee-Lake 上尝试了您的代码并发现性能下降,不是 2KB,而是大约 4.5KB。此外,我发现略高于 2KB 的吞吐量行为不稳定。
图中的蓝线对应于您的测量值(左轴):
这里的红线是 perf stat -e branch-instructions,branch-misses
的结果,给出了未正确预测的分支部分(百分比,右轴)。如您所见,两者之间存在明显的反相关。
查看更详细的 perf
报告,我发现基本上所有这些分支预测错误都发生在 Worker::operator()
的最内层循环中。如果循环分支的 taken/non-taken 模式变得太长,分支预测器将无法跟踪它,因此内部循环的出口分支将被错误预测,导致吞吐量急剧下降。随着迭代次数的进一步增加,这个单一错误预测的影响将变得不那么显着,从而导致吞吐量恢复缓慢。
有关掉落前不稳定行为的更多信息,请参阅下面@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 次迭代得到以下结果。请注意,我没有更正矢量末尾的块,这些块由于展开而被忽略。因此应忽略蓝线中的周期性峰值,周期性模式的下界基线是实际带宽。
如您所见,分支预测错误的比例并没有真正改变,但由于分支总数因展开迭代而减少,它们将不再对性能有很大贡献。
还有一个额外的好处是,如果展开循环,处理器可以更自由地进行乱序计算。
如果这应该有实际应用,我建议尝试给热循环一个编译时固定的迭代次数或一些可除性保证,以便(可能有一些额外的提示)编译器可以决定关于要展开的最佳迭代次数。
可能无关,但您的 Linux 机器可能以 CPU 频率播放。我知道 Ubuntu 18 有一个在功率和性能之间取得平衡的调节器。您还想尝试处理进程亲和性,以确保它不会在 运行 时迁移到不同的核心。