Intel SandyBridge系列CPU流水线程序的去优化

Question

我已经绞尽脑汁了一个星期，想完成这个任务，我希望这里有人能引导我走上正确的道路。我先从教官的指示说起：

你的作业与我们的第一个实验作业相反，我们的第一个实验作业是优化一个素数程序。你在这份作业中的目的是使程序悲观，即使它运行得更慢。这两个都是CPU密集型程序。在我们的实验室电脑上运行需要几秒钟的时间。您不能更改算法。

若要解除程序的优化，请使用您对Intel i7管道运行方式的了解。想象一下重新排列指令路径以引入WAR、RAW和其他危险的方法。想办法最小化缓存的有效性。极其无能。

作业给出了Whetstone或Monte-Carlo程序的选择。缓存-有效性的注释大多只适用于Whetstone，但我选择了蒙特卡罗模拟程序：

// Un-modified baseline for pessimization, as given in the assignment
#include <algorithm>    // Needed for the "max" function
#include <cmath>
#include <iostream>

// A simple implementation of the Box-Muller algorithm, used to generate
// gaussian random numbers - necessary for the Monte Carlo method below
// Note that C++11 actually provides std::normal_distribution<> in 
// the <random> library, which can be used instead of this function
double gaussian_box_muller() {
  double x = 0.0;
  double y = 0.0;
  double euclid_sq = 0.0;

  // Continue generating two uniform random variables
  // until the square of their "euclidean distance" 
  // is less than unity
  do {
    x = 2.0 * rand() / static_cast<double>(RAND_MAX)-1;
    y = 2.0 * rand() / static_cast<double>(RAND_MAX)-1;
    euclid_sq = x*x + y*y;
  } while (euclid_sq >= 1.0);

  return x*sqrt(-2*log(euclid_sq)/euclid_sq);
}

// Pricing a European vanilla call option with a Monte Carlo method
double monte_carlo_call_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) {
  double S_adjust = S * exp(T*(r-0.5*v*v));
  double S_cur = 0.0;
  double payoff_sum = 0.0;

  for (int i=0; i<num_sims; i++) {
    double gauss_bm = gaussian_box_muller();
    S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm);
    payoff_sum += std::max(S_cur - K, 0.0);
  }

  return (payoff_sum / static_cast<double>(num_sims)) * exp(-r*T);
}

// Pricing a European vanilla put option with a Monte Carlo method
double monte_carlo_put_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) {
  double S_adjust = S * exp(T*(r-0.5*v*v));
  double S_cur = 0.0;
  double payoff_sum = 0.0;

  for (int i=0; i<num_sims; i++) {
    double gauss_bm = gaussian_box_muller();
    S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm);
    payoff_sum += std::max(K - S_cur, 0.0);
  }

  return (payoff_sum / static_cast<double>(num_sims)) * exp(-r*T);
}

int main(int argc, char **argv) {
  // First we create the parameter list                                                                               
  int num_sims = 10000000;   // Number of simulated asset paths                                                       
  double S = 100.0;  // Option price                                                                                  
  double K = 100.0;  // Strike price                                                                                  
  double r = 0.05;   // Risk-free rate (5%)                                                                           
  double v = 0.2;    // Volatility of the underlying (20%)                                                            
  double T = 1.0;    // One year until expiry                                                                         

  // Then we calculate the call/put values via Monte Carlo                                                                          
  double call = monte_carlo_call_price(num_sims, S, K, r, v, T);
  double put = monte_carlo_put_price(num_sims, S, K, r, v, T);

  // Finally we output the parameters and prices                                                                      
  std::cout << "Number of Paths: " << num_sims << std::endl;
  std::cout << "Underlying:      " << S << std::endl;
  std::cout << "Strike:          " << K << std::endl;
  std::cout << "Risk-Free Rate:  " << r << std::endl;
  std::cout << "Volatility:      " << v << std::endl;
  std::cout << "Maturity:        " << T << std::endl;

  std::cout << "Call Price:      " << call << std::endl;
  std::cout << "Put Price:       " << put << std::endl;

  return 0;
}

我所做的更改似乎使代码运行时间增加了一秒，但我不完全确定我可以更改什么来阻止管道而不添加代码。一个正确的方向将是令人敬畏的，我感谢任何回应。

• 这是社区大学第二学期的建筑课程（使用轩尼诗和帕特森的教科书）。
• 实验计算机具有Haswell CPU
• 学生已经了解了CPUID指令和如何确定缓存大小，以及intrinsics和clflush指令。
• 允许任何编译器选项，内联ASM也是如此。
• 编写自己的平方根算法被宣布为在苍白之外

Cowmoogun在meta thread上的评论表明，编译器优化并不是其中的一部分，并且假设-o0，17%的运行时间增长是合理的。

所以听起来，这个作业的目的是让学生重新安排现有的作业，以减少指令级的并行性或诸如此类的事情，但人们钻研得更深，学得更多，这也不是一件坏事。

请记住，这是一个计算机体系结构的问题，而不是关于如何使C++总体上变慢的问题。

Answer 1

重要背景阅读：Agner Fog的microarch pdf，可能还有Ulrich Drepper的每个程序员都应该知道的关于内存的内容。请参阅x86标记wiki中的其他链接，特别是Intel的优化手册，以及David Kanter对Haswell微架构的分析，并附上图表。

非常酷的任务；比我见过的那些让学生为gcc-o0优化一些代码的方法要好得多，学习了一堆在实际代码中无关紧要的技巧。在本例中，您被要求了解CPU流水线并使用它来指导您的去优化工作，而不仅仅是盲目的猜测。其中最有趣的部分是用“邪恶的无能”来为每一种悲观辩护，而不是故意的恶意。

作业措辞和代码的问题：

此代码的UARCH特定选项是有限的。它不使用任何数组，大部分开销是调用exp/log库函数。没有一种明显的方法来或多或少地实现指令级的并行性，并且循环携带的依赖链非常短。

仅仅通过重新排列表达式来改变依赖关系来减少ILP的危害是很难得到减缓的。

对于内存排序，现代CPU使用存储缓冲区将提交到缓存中的时间延迟到退休，这也避免了WAR和WAW危险。关于什么是存储缓冲区，以及对于OoO exec将执行与其他内核所能看到的东西解耦是必不可少的，请参见这个答案。

为什么mulss在Haswell上只需要3个周期，不同于Agner的指令表？（用多个累加器展开FP循环）有更多关于寄存器重命名和隐藏FP点积循环中的FMA延迟的内容。

“i7”的品牌名称是随着Nehalem（Core2的继任者）引入的，一些英特尔手册甚至说Core i7，当他们似乎指的是Nehalem，但他们为Sandybridge和后来的微架构保留了“i7”的品牌。SnB是P6家族进化成一个新物种SnB家族的时候。在许多方面，Nehalem与Pentium III相比Sandybridge有更多的共同点（例如，寄存器读停顿和Rob读停顿在SnB上不会发生，因为它改用了物理寄存器文件。还有uop缓存和不同的内部uop格式）。术语“i7架构”并不有用，因为将SNB-家族与Nehalem分组而不是Core2分组几乎没有意义。（不过，Nehalem确实引入了共享的、包容的L3缓存架构，用于将多个内核连接在一起。同时还集成了GPU。所以在芯片级，这个命名更有意义。）

即使是极不称职的人也不太可能添加明显无用的工作或无限循环，并且把C++/Boost类搞得一团糟超出了任务的范围。

• 具有单个共享std::atomic 循环计数器的多线程，因此发生正确的迭代总数。使用-m32-march=i586时，Atomic uint64_t尤其糟糕。要获得奖励点数，请将其设置为不对齐，并以不均匀的分割（不是4：4）跨越页面边界。
• 其他非原子变量的错误共享->内存顺序错误推测管道清除，以及额外的缓存丢失。
• 不是对FP变量使用-，而是使用0x80对高字节进行异或以翻转符号位，从而导致存储转发暂停。
• 对每次迭代进行独立的计时，使用的内容甚至比rdtsc还要重。例如cpuid/rdtsc或进行系统调用的time函数。序列化指令本质上是管道不友好的。
• 将常数的乘数改为常数的倒数的除数（“为便于阅读”）。div速度慢且未完全流水线化。
• 使用AVX(SIMD)向量化Multiply/SQRT，但在调用标量数学库exp()和log()函数之前无法使用vzeroupper，导致AVX<->SSE转换停滞。
• 将RNG输出存储在链表中，或者存储在无序遍历的数组中。每次迭代的结果相同，并在末尾求和。

在这个答案中也包括了，但不包括在总结中：在非流水线CPU上同样慢的建议，或者即使是极其无能的建议似乎也不合理。例如,许多产生明显不同/更差的ASM的gimp-the-compiler思想。

可能使用OpenMP进行多线程循环，迭代次数很少，开销远远大于速度增益。你的monte-carlo代码有足够的并行性来获得加速。如果我们成功地使每次迭代变慢。（每个线程计算一个部分payoff_sum，加在末尾）。该循环上的#omp parallex可能是一种优化，而不是一种悲观。

多线程，但强制两个线程共享相同的循环计数器（使用atomic增量，因此迭代的总数是正确的）。这似乎非常合乎逻辑。这意味着使用statice变量作为循环计数器。这就证明了对循环计数器使用atomic是合理的，并创建了实际的高速缓存行ping-ponging（只要线程不是在与超线程相同的物理内核上运行；那可能不会那么慢）。无论如何，这要比lockinc的无争用情况慢得多。和锁CMPxchg8b以原子递增32位系统上的争用uint64_t将必须在循环中重试，而不是让硬件仲裁原子inc。

还要创建假共享，其中多个线程将其私有数据（例如RNG状态）保留在同一高速缓存行的不同字节中。（Intel关于它的教程，包括要查看的性能计数器）。这有一个特定于微架构的方面：Intel CPU推测内存错误排序不会发生，至少在P4上会有一个内存排序机器清除性能事件来检测这一点。对Haswell的惩罚可能不会那么大。正如该链接所指出的，lockED指令假定会发生这种情况，从而避免了错误猜测。正常的加载推测，在加载执行和它按程序顺序退出之间，其他内核不会使缓存行无效（除非您使用pause)。没有lockED指令的真正共享通常是一个bug。比较一个非原子的共享循环计数器和原子的情况是很有趣的。要真正悲观，保留共享的原子循环计数器，并在相同或不同的缓存行中对其他变量造成错误共享。

如果您可以引入任何不可预测的分支，这将使代码严重悲观。现代x86 CPU有相当长的流水线，因此一次错误预测需要花费大约15个周期（当从uop缓存运行时）。

我想这是任务的目标之一。

RNG状态几乎肯定是一个比addps更长的循环携带的依赖链。

除以2.0而不是乘以0.5，依此类推。在Intel设计中，FP multiply是大量流水线的，在Haswell和更高版本上每0.5C吞吐量有一个FP multiply。FPdivsd/divpd仅部分流水线化。（尽管Skylake对于divpd xmm每4C吞吐量有一个令人印象深刻的吞吐量，延迟为13-14C，而Nehalem上根本没有流水线(7-22C)）。

做{...；euclid_sq=x*x+y*y；}而(euclid_sq>=1.0)；显然是在测试距离，因此显然应该sqrt()。:p(sqrt甚至比div)更慢）。

正如@Paul Clayton所建议的，使用关联/分布等价物重写表达式可以引入更多的工作（只要您不使用-ffast-math来允许编译器重新优化）。(exp(t*(r-0.5*v*v))可以变成exp(t*r-t*v*v/2.0)。请注意，虽然实数上的数学是关联的，但浮点数学不是关联的，即使不考虑溢出/NAN（这就是-ffast-math默认不启用的原因）。请参阅Paul的评论，了解一个非常多毛的嵌套pow()建议。

如果你能把计算缩小到很小的数字，那么当对两个正常数字的运算产生一个反正常数字时，FP的数学操作需要大约120个额外的循环来捕获微码。请参阅Agner Fog公司的微拱形pdf文件，了解确切的数字和详细信息。这是不太可能的，因为你有很多乘法，所以比例因子将被平方，并一直下溢到0.0。我看不出有什么办法可以用无能（甚至是毒辣的）来证明必要的缩放是正当的，只有故意的恶意。

###如果您可以使用intrinsics( )

使用movnti将数据从缓存中逐出。恶魔：它是新的和弱顺序的，所以应该让CPU运行得更快，对吗？或者，如果有人正处于这样做的危险中（如果是零散的写入，其中只有一些位置是热的），请查看链接问题。clflush没有恶意大概是不可能的。

在FP数学运算之间使用整数洗牌以导致旁路延迟。

在没有正确使用vzeroupper的情况下混用SSE和AVX指令会导致Skylake前出现较大的停顿（在Skylake中会受到不同的惩罚）。即使没有这一点，向量化做得很差也会比标量差（用256B个向量同时进行4次蒙特卡罗迭代的add/sub/mul/div/sqrt操作所节省的数据进出向量所花费的周期要多）。add/sub/mul执行单元是完全流水线和全宽度的，但是256B向量上的div和sqrt没有128B向量（或标量）上的速度快，因此double的加速并不显著。

exp()和log()没有硬件支持，因此该部分需要将向量元素提取回标量，并单独调用库函数，然后将结果重置为向量。libm通常被编译为只使用SSE2，因此将使用标量数学指令的遗留SSE编码。如果您的代码使用256B向量并调用exp而没有首先执行vzeroupper,那么您将停顿。返回后，类似vmovsd的AVX-128指令将下一个vector元素设置为exp的arg也将停止。然后exp()将在运行SSE指令时再次停顿。这正是这个问题中发生的情况，造成了10倍的减速。（谢谢@zboson)。

关于这段代码，请参见Nathan Kurz关于Intel数学lib vs.glibc的实验。未来的glibc将提供exp()等的矢量化实现。

如果针对IVB前，或ESP。Nehalem,试着让gcc在16位或8位操作和32位或64位操作之后导致部分寄存器停止。在大多数情况下，gcc将在8或16bit操作之后使用movzx，但这里有一种情况，gcc修改ah然后读取ax

使用（内联）asm，您可以破坏uop缓存：一个32B代码块不适合三个6uop缓存行，迫使从uop缓存切换到解码器。一个不合格的align（就像NASM的默认值）在内部循环内的分支目标上使用许多单字节的nop而不是几个长的nop可能会起到这个作用。或者将对齐填充放在标签之后，而不是之前。：p只有当前端是一个瓶颈时，这才有关系，如果我们成功地使其余代码悲观，就不会是瓶颈。

使用自修改代码触发管道清除（又名机器核）。

LCP停止的16位指令的即时太大，不能容纳8位不大可能有用。SnB和更高版本上的uop缓存意味着您只需支付一次解码惩罚。在Nehalem（第一个i7)上，它可能适用于不适合28 uop循环缓冲区的循环。gcc有时也会生成这样的指令，即使使用-mtune=intel以及本可以使用32位指令的情况下也是如此。

一个常见的定时习惯用法是cpuid（要序列化），然后是rdtsc。使用CPUID/rdtsc分别对每次迭代进行计时，以确保rdtsc没有使用以前的指令重新排序，这将大大降低运行速度。（在现实生活中，明智的计时方式是将所有迭代计时在一起，而不是将每一次分别计时并加起来）。

对某些变量使用联合{double d；char a[8]；}。通过对其中一个字节进行狭窄的存储（或读-修改-写），导致存储转发停滞。（wiki文章还介绍了许多用于加载/存储队列其他微体系结构内容）。例如，仅在高字节上使用XOR 0x80来翻转double的符号，而不是-运算符。极不称职的开发人员可能听说FP比integer慢，因此尝试尽可能多地使用integer ops。（编译器理论上仍然可以将其编译为具有常量（如-)的XORPS，但对于x87，编译器必须意识到它正在否定值和fchs或用减法替换下一个加法。）

如果使用-o3而不是使用std::atomic进行编译，请使用volatile来强制编译器实际存储/重新加载所有位置。全局变量（而不是局部变量）也会强制一些存储/重新加载，但是C++内存模型的弱排序不需要编译器一直溢出/重新加载到内存中。

用一个大结构的成员替换本地VAR，这样您就可以控制内存布局了。

在结构中使用数组进行填充（并存储随机数，以证明它们的存在是正确的）。

选择您的内存布局，使所有内容都进入L1缓存中同一“集合”中的不同行。它只是8路联想，即每组有8个“路”。高速缓存线为64B。

如果您可以让编译器使用索引寻址模式，这将会挫败uop微融合。可以使用#defines用my_data[constant]替换简单的标量变量。

如果您可以引入一个额外的间接级别，这样加载/存储地址就不能及早知道，这可能会进一步使人悲观。

我认为我们首先可以提出引入数组的不恰当的理由：它让我们将随机数的生成与随机数的使用分开。每次迭代的结果也可以存储在一个数组中，以供以后求和（更可怕的无能）。

对于“最大随机性”，我们可以让一个线程在随机数组上循环，将新的随机数写入其中。使用随机数的线程可以生成一个随机索引来加载随机数。（这里有一些工作，但在微体系结构上，它有助于尽早知道加载地址，以便在需要加载数据之前解决任何可能的加载延迟。）在不同的内核上拥有读取器和写入器将导致内存排序错误猜测管道清除（正如前面针对错误共享情况所讨论的）。

为了达到最大程度的悲观，以4096字节（即512倍）的步幅在数组上循环。例如。

for (int i=0 ; i<512; i++)
    for (int j=i ; j<UPPER_BOUND ; j+=512)
        monte_carlo_step(rng_array[j]);

因此访问模式为0,4096,8192,...,
8,4104,8200,...
16,4112,8208,...

这就是以错误的顺序访问诸如double rng_array[MAX_ROWS][512]这样的二维数组（如@jesperjuhl所建议的那样，在内部循环中循环行，而不是行内的列）所得到的结果。如果说邪恶的无能可以证明二维数组具有这样的维度，那么现实世界中常见的无能很容易证明使用错误的访问模式进行循环是正确的。这种情况发生在现实生活中的真实代码中。

如果数组不是那么大，则需要调整循环边界，以使用多个不同的页，而不是重用相同的几个页。硬件预取在页面上（也不起作用/根本不起作用）。预取器可以跟踪每个页面中的一个前向流和一个后向流（这就是这里发生的事情），但是只有在内存带宽没有被非预取饱和的情况下才会对它起作用。

这也会生成大量的TLB缺失，除非页面合并到一个hugepage中（Linux为匿名（非文件支持的）分配（如malloc/new使用mmap(MAP_ANONYMON))而机会主义地做了这件事）。

可以使用链表，而不是数组来存储结果列表。每一次迭代都需要一个指针追踪加载（对于下一个加载的加载地址而言，这是一个原始的、真正的依赖关系风险）。使用错误的分配器，您可能会设法将列表节点分散在内存中，从而破坏缓存。使用一个糟糕的玩具分配器，它可以将每个节点放在自己页面的开头。（例如，直接使用mmap(Map_Anonymony)分配，而不拆分页面或跟踪对象大小以正确支持free)。

这些并不是真正特定于微体系结构的，而且与流水线也没有多大关系（其中大多数也会导致非流水线CPU的减速）。

对于最悲观的代码，使用C++11std::atomic 和std::atomic 。MFENCEs和locked指令非常慢，即使没有来自另一个线程的争用。

-M32会制作更慢的代码，因为x87代码会比SSE2代码更差。基于堆栈的32位调用约定需要更多的指令，甚至会将堆栈上的FP参数传递给类似exp()的函数。-M32上的原子 ::operator++ 需要一个锁CMPXCHG8B循环(i586)。（所以使用for循环计数器！[邪恶的笑声])。

-march=i386也会悲观（谢谢@jesper)。FP与FCOM相比较，慢于686FCOMI。Pre-586不提供原子64bit存储（更不用说cmpxchg)，所以所有64bitatomicops都编译为libgcc函数调用（可能是为i686编译的，而不是实际使用锁）。在最后一段中的Godbolt编译器资源管理器链接上试试看。

在sizeof(long double/sqrtl/expl)为10或16（带有用于对齐的填充）的ABIs中，使用long double/sqrtl/expl可获得额外的精度和额外的慢速。(IIRC，64bit Windows使用相当于double的8bytelong double。（无论如何，10byte(80bit)FP操作数的加载/存储是4/7 uop，而float或double对于FLD M64/M32/FST每个操作数只取1 uop）。强制使用long double的x87，即使对于gcc-M64-march=haswell-o3也会失败

如果不使用原子 循环计数器，则对所有内容（包括循环计数器）使用长双。

原子 编译，但它不支持读-修改-写操作，如+=（即使在64bit上）。atomic 必须调用一个库函数，仅用于原子加载/存储。这可能真的很低效，因为x86 ISA自然不支持原子10byte加载/存储，而且我能想到的唯一不加锁的方法(cmpxchg16b)需要64bit模式。

在-o0中，通过将部分分配给临时var来分解一个大表达式将导致更多的存储/重新加载。如果没有volatile之类的东西，对于真正代码的真正构建将使用的优化设置来说，这将无关紧要。

C别名规则允许字符对任何内容进行别名，因此通过字符*存储强制编译器在字节存储之前/之后存储/重新加载所有内容，即使在-O3处也是如此。（例如，对于对uint8_t数组进行操作的代码进行自动向量化，这是一个问题。）

尝试uint16_t循环计数器，以强制截断为16bit，可能使用16bit操作数大小（潜在的停顿）和/或额外的movzx指令（安全）。带符号溢出是未定义的行为，因此除非使用-FWRAPV或至少使用-FNO-STRICTER-OVERFLOW，否则带符号的循环计数器不必在每次迭代时重新进行符号扩展，即使用作64bit指针的偏移量。

强制从integer转换为float，然后再转换回来。和/或double<=>float转换。这些指令的延迟大于1，标量int->float(CVTSI2SS)设计不当，无法将xmm寄存器的其余部分置零。（为此，gcc插入了一个额外的PXOR来中断依赖关系。）

经常将您的CPU关联设置为不同的CPU（由@egwor建议）。邪恶的推理：你不希望一个核心因为长时间运行你的线程而过热，是吗？也许交换到另一个内核会让该内核以更高的时钟速度运行。（在现实中：它们彼此之间的热非常接近，除非在多插槽系统中，否则这是极不可能的）。现在只是把调错了，而且经常这样做。除了在OS中保存/恢复线程状态所花费的时间外，新内核还具有冷的L2/L1缓存、uop缓存和分支预测器。

引入频繁的不必要的系统调用，不管它们是什么，都能让你慢下来。虽然一些重要但简单的代码（如GetTimeOfDay)可以在用户空间中实现，但不需要过渡到内核模式。（Linux上的glibc在内核的帮助下完成此操作：内核在VDSO中导出代码+数据）。

关于系统调用开销的更多信息（包括返回用户空间后的缓存/TLB丢失，而不仅仅是上下文切换本身），FlexSC论文对当前情况进行了一些出色的性能计数器分析，并提出了一个对来自大规模多线程服务器进程的系统调用进行批处理的建议。