2 x 1 循环展开代码展示

void psum1(float a[], float p[], long n)
{
	long i;
	p[0] = a[0];
	for(i =1; i < n-1; i++)
	{
		p[i] = p[i-1] + a[i];
	}
}


void psum2(float a[], float p[], long n)
{
	long i;
	p[0] = a[0];
	for(i = 1; i < n-1; i += 2)
	{
		float mid_val = p[i-1] + a[i];
		p[i] = mid_val;
		p[i+1] = mid_val + a[i+1];
	}

	//For even n, finish remaining element
	if(i < n)
		p[i] = p[i-1] + a[i];
}

[!NOTE] 这个 psum2 和 psum1 的区别就是减少了循环的次数，因为一个 i 可以加 1 减 1，从而得到左右两边的值，从而减少代码循环的次数。它就是利用引入一个中间变量 mid_val 从而存储一个中间值，根据情况来分配

思考

问题 1

在 loop unrolling 中，为什么循环次数是减少了，但循环中操作的次数什么的增多了，这样还是可以提高程序效率，减少 CPE

问题 1 解答

在循环展开（loop unrolling）中，循环次数减少了，但循环体内操作的次数增加了，这样仍然可以提高程序的效率并减少CPE（Cycles Per Element，每个元素的时钟周期数）。这是因为循环展开在消除一些开销的同时，更好地利用了处理器的资源。以下是详细解释：

1. 减少循环控制开销：

循环控制开销包括：条件判断、循环计数器的更新和跳转指令。这些操作本身并不对实际的计算产生贡献，但在循环中每次迭代都会执行。
展开循环后，循环控制的频率降低。比如，如果原本有 100 次迭代的循环，现在每次展开 4 次，那么只需要执行 25 次循环控制操作，而不是 100 次。
这种减少循环控制操作的方式直接减少了无用的开销，从而提高了效率。

2. 增加指令级并行性（ILP）：

现代处理器具有流水线和多发射架构，它们可以在同一个时钟周期内执行多个指令。
当循环展开时，更多的实际工作（计算操作）在循环内被放大，增加了同时可执行的指令数量。
通过展开循环，可以让编译器或硬件调度更多的指令并行执行，从而更好地利用处理器的流水线资源。

3. 减少分支预测失误：

每次循环跳转都需要进行分支预测，预测是否要继续执行循环。如果分支预测失误，处理器的流水线可能会被冲刷，导致性能损失。
展开循环可以减少循环次数，因此分支预测的频率也减少了，进而降低了分支预测错误的影响。

4. 更好地利用缓存：

在某些情况下，循环展开有助于改善内存访问的局部性（temporal locality 和 spatial locality）。如果在展开过程中对内存的访问模式更加连续，可能减少缓存未命中的次数，从而提高效率。

5. 减少数据相关性：

如果原本的循环存在某些指令间的数据依赖，通过展开循环，可以将某些独立的计算提前执行，减少等待时间。这样就可以让处理器更好地安排指令执行次序，避免流水线阻塞。

例子：

假设一个简单的循环，每次执行一次加法操作：

for (int i = 0; i < 100; i++) {
    a[i] = a[i] + 1;
}

通过循环展开 4 次，可以将其改写为：

for (int i = 0; i < 100; i += 4) {
    a[i] = a[i] + 1;
    a[i+1] = a[i+1] + 1;
    a[i+2] = a[i+2] + 1;
    a[i+3] = a[i+3] + 1;
}

循环次数从 100 次减少到 25 次（因为每次迭代处理 4 个元素）。
循环体内的操作次数（加法）虽然增加了，但总操作数没有变化，而循环控制的频率却大大减少了。

总结：

虽然循环展开后每次迭代中执行的操作增加了，但由于减少了循环控制、分支预测的开销，并且增加了并行性和缓存利用率，最终仍能显著提高程序的执行效率，减少每个元素的时钟周期数（CPE）。