Break the Serial Dependency Chain

本文为学习 Computer Enhance - Instructions Per Clock 的整理。

前情回顾

上一篇博客中，我们通过循环展开进行了示例代码的优化，也遇到了串行依赖链的问题。这篇博客就来进一步说明。

之前的优化代码：

u32 Unroll4Scalar(u32 Count, u32 *Input)
{
    u32 Sum = 0;
    for (u32 Index = 0; Index < Count; Index += 4)
    {
        Sum += Input[Index];
        Sum += Input[Index + 1];
        Sum += Input[Index + 2];
        Sum += Input[Index + 3];
    }
    return Sum;
}

什么是串行依赖链？

每个 add 的第一个操作数始终是同一个累加值 Sum。它既是 add 的源，也是其目的地。

这部分代码是一个 串行依赖链：整个求和过程中的每一次加法，都依赖于前一次加法的结果，一路追溯到循环的第一次迭代。

当 CPU 看到这样一条链时，它没有任何办法加速——必须按顺序执行。它必须等前一条加法完成，才能开始下一条。我们写出来的循环体里，CPU 唯一能并行做的只有循环本身的维护工作。它可以一边维护循环，一边执行加法，但 永远无法把加法本身并行化。

打破依赖链

加法满足 结合律 和 交换律——我们可以随意重新排列。我们可以调换加法的顺序，可以先把数两两相加再把结果相加，也可以把偶数下标和奇数下标分别求和，最后再合并。

因此，我们完全可以通过修改代码，增加临时变量，打破这个串行依赖链。

双累加器 (DualScalar)

u32 DualScalar(u32 Count, u32 *Input)
{
    u32 SumA = 0;
    u32 SumB = 0;
    for (u32 Index = 0; Index < Count; Index += 2)
    {
        SumA += Input[Index + 0];
        SumB += Input[Index + 1];
    }
    u32 Sum = SumA + SumB;
    return Sum;
}

四累加器 (QuadScalar)

u32 QuadScalar(u32 Count, u32 *Input)
{
    u32 SumA = 0;
    u32 SumB = 0;
    u32 SumC = 0;
    u32 SumD = 0;
    for (u32 Index = 0; Index < Count; Index += 4)
    {
        SumA += Input[Index + 0];
        SumB += Input[Index + 1];
        SumC += Input[Index + 2];
        SumD += Input[Index + 3];
    }
    u32 Sum = SumA + SumB + SumC + SumD;
    return Sum;
}

进一步优化：指针遍历 (QuadScalarPtr)

可以进一步优化循环结构，去除地址计算，改为固定偏移：

u32 QuadScalarPtr(u32 Count, u32 *Input)
{
    u32 SumA = 0;
    u32 SumB = 0;
    u32 SumC = 0;
    u32 SumD = 0;
    Count /= 4;
    while (Count--)
    {
        SumA += Input[0];
        SumB += Input[1];
        SumC += Input[2];
        SumD += Input[3];
        Input += 4;
    }
    u32 Sum = SumA + SumB + SumC + SumD;
    return Sum;
}

性能测试结果

函数	周期数	adds/cycle
DualScalar	2336	1.753
QuadScalar	1916	2.138
QuadScalarPtr	950	4.312

回顾：编译器的优化

在上篇博客中，我们说了 Unroll4Scalar 被额外优化了。这个额外优化就是 打破依赖链，编译器生成的代码大致如下：

u32 Unroll4Scalar(u32 Count, u32 *Input)
{
    u32 Sum = 0;
    for (u32 Index = 0; Index < Count; Index += 4)
    {
        u32 tmp = Input[Index + 2]; 
        tmp += Input[Index + 1];     
        tmp += Input[Index];          
        tmp += Input[Index + 3];     
        Sum += tmp;                   
    }
    return Sum;
}