Assemble|并行计算|SuperScalar

A super scalar processor is a CPU that implements a form of parallelism called instruction-level parallelism within a single processor.

超标量（superscalar）架构是指在一颗处理器内核中实行了指令级并行的一类并行运算。这种技术能够在相同的CPU主频下实现更高的CPU吞吐率（throughput）。

我们暂时先不管这种技术如何实现，总而言之，他能够在单核CPU中依靠不同执行单元同时执行一系列没有依赖关系的指令。

了解这种技术有助于在代码中触发这种优化。

前置：

本文附图类似于甘特图，横向可以并行计算，纵向则必须顺序执行，高度代表执行时间，每个重复单元代表一次迭代。

Naive Mode

以下是一段标准的累乘操作，每一次*=都需要上一次乘法的结果作为operand，因此构成了数据依赖。

由于Super Scalar的存在，i++这个add指令和[i]这个load指令和mul指令不存在依赖关系，可以并行，此时执行总时间近似为每次循环执行1次乘法。

Iteration Unrolling

这次我们迭代的步长增加，add的次数减少了一半，load次数不变。然而，由于在循环体内，两次乘法仍然存在依赖关系，无法并行，最终我们的执行时间不变。（减少的部分是跳转、自增，但是乘法时间较长因此最终时间没有减少，如果换成整数加法就会有一定减少）

Divide and Conquer

这次我们使用分治，由不同变量处理不同部分的累乘，最终将结果相乘。由于不同变量的累乘彼此独立，因此SuperScalar被触发，两个乘法可以并行计算。最终，通过扩大一倍步长，我们节约了一半的执行时间。随着步长递增，执行时间也会减少。

Hint:

由于计算资源有限，并行计算过多时，寄存器可能无法存下操作数，存入内存，导致减缓；此外，本身执行单元的数目有限。

Associative

我们这次把和结果相乘的operand先相乘，然后和结果相乘，由于前者并不涉及res，因此彼此之间无依赖关系，可以并行计算。而后者必须顺序执行。最终，通过扩大一倍步长，我们节约了一半的执行时间。随着步长递增，执行时间也会减少。

与上面方法的效果类似，但是显然实现更加简单。