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,因此彼此之间无依赖关系,可以并行计算。而后者必须顺序执行。最终,通过扩大一倍步长,我们节约了一半的执行时间。随着步长递增,执行时间也会减少。
与上面方法的效果类似,但是显然实现更加简单。