缓存优化
减少伪共享
为解决数据一致性的问题，需要处理器各个核心访问缓存时都遵循缓存一致性协议。即当某个处理器核心修改缓存行数据时，其它的处理器核通过监听机制获悉并使其共享缓存行失效，此时该处理器核心将修改后的缓存行写回到主内存中。若其它处理器核需要此缓存行共享数据，则从主内存中重新加载，并放入缓存，这样可以保证读取数据的正确性，如图所示。
在多核CPU系统中，由于要操作的不同变量处于同一缓存行，某核心更新缓存行中数据并将其写回缓存，同时其它核心会使该缓存行失效，使用时需要从内存中重新加载，这种情况就是缓存行的伪共享问题，伪共享会导致大量的缓存冲突，应尽量避免。
多线程编程时往往不可避免的要遇到数据共享，编程时应该注意如下原则：
尽量少的使用共享数据，可以将不同线程操作的数据分配在不同的缓存行中，或者进行缓存行填充，避免多个线程共享同一缓存行内的数据。
在多个核心共享同一缓存行数据时，如果不进行对缓存的写入，是不会发生伪共享问题的，所以应当尽量少的修改数据。例如上述的例子中，若核心0与核心1频繁地对Arr[0]以及Arr[1]进行修改，代价是非常高的。
在内核版本4.1.0及以上的Linux系统中，perf工具包含了一些对程序中伪共享的分析功能，称为perf c2c。perf c2c可以收集高速缓存的性能数据，之后基于采样数据生成报告，以此代码为例说明如何使用perf c2c进行伪共享分析。
int main(void)
{
int sum[THRAED_NUM];
#pragma omp parallel for
for (int i = 0; i < THRAED_NUM; i++){
for (int j = 0; j < N; j++){
sum[i] += values[j] >> i;
}
}
return 0;
}
sum数组大小为64字节，在实验测试平台中恰好占用一个缓存行。当8个线程同时对该缓存行内的sum数组进行写时，程序将不可避免地发生伪共享现象。使用perf c2c对该程序的执行过程进行分析，在Linux中输入以下指令。
# gcc –fopenmp –g false_share_test.c –o false_share_test //使用gcc编译器编译目标文件
# perf c2c record ./false_share_test //通过采样，收集性能数据
# perf c2c report –stdio //基于采样数据，生成报告
生成的报告如下所示，为更清晰的予以说明，对表中的输出结果适当进行了简化。
Total records : 65407
......
LLC Misses to Local DRAM : 36.9%
LLC Misses to Remote DRAM : 33.8%
LLC Misses to Remote 缓存 (HIT) : 0.0%
LLC Misses to Remote 缓存 (HITM， Hit In The Modified) : 29.2%
......
为避免多个线程频繁访问同一缓存行，减少伪共享问题，修改后的程序如代码所示。修改后的程序避免了多个线程同时频繁地访问同一个缓存行，此时再次使用pref c2c分析，可以发现程序中的伪共享现象大幅度减少。
int main(void)
{
int sum[THRAED_NUM]；
#pragma omp parallel for
for (int i = 0； i < THRAED_NUM； i++){
int local_sum；
for (int j = 0； j < N； j++){
local_sum += values[j] >> i；
}
sum[i] = local_sum；
}
return 0；
}
优化后结果如下：
LLC Misses to Local DRAM : 88.7%
LLC Misses to Remote DRAM : 9.9%
LLC Misses to Remote 缓存 (HIT) : 0.0%
LLC Misses to Remote 缓存 (HITM) : 1.4%
......
数据预取
数据预取将待处理器所需的数据提前加载到缓存中，避免缓存不命中的情况出现。按照数据预取的效果，可将数据预取分为无预取、理想预取和非理想预取三种，如图所示。
硬件预取与软件预取
预取的实现通常有软件预取和硬件预取两种方式。硬件预取是提前把指令和数据预取到缓存中的一种硬件机制，其不需要使用预取指令或额外的编写代码。但硬件预取必需建立在能动态进行程序执行分支预测的基础上，所以预取的范围很小，且会增加系统整体开销。
在绝大部分情况下，程序对内存的访问模式是随机的、不规则的。此时需要使用软件预取，通过插入的预取指令，提前把数据取入缓存，这种方法对系统开销的影响较小，也不会减慢访问缓存的速度，是一种灵活有效的数据预取方式。
本节主要介绍软件预取对程序性能的影响，软件预取通过插入预取指令或者函数实现，使用预取函数__builtin_prefetch()，该函数原型为void__builtin_prefetch (const void*addr,rw,locality)，在测试用例合适位置插入预取指令，使用LLVM7-1版本的编译器对加入预取指令的程序进行编译，结果显示加入预取指令比未加入指令的执行时间快了13%。
__builtin_prefetch(mul1, 0, 3);
__builtin_prefetch(mul2, 0, 0);
__builtin_prefetch(res, 1, 3);
nop;nop;nop;
for (i = 0; i < N; ++i)
for (j = 0; j < N; ++j)
for (k = 0; k < N; ++k)
res[i][j] += mul1[i][k] * mul2[k][j];
