x86_64 上是否有一个真正有效的示例显示 ILP（指令级并行）的好处？

Question

众所周知 CPU 是流水线，如果命令序列彼此独立，它的工作效率最高 - 这称为 ILP（指令级并行）：http://en.wikipedia.org/wiki/Instruction-level_parallelism

但是对于 CPU x86_64（但是 对于相同数量的 cmp/jne 在这两种情况下 )?

我会写下面的例子——将数组的所有元素相加，但它并没有显示出ILP的任何优势：http://ideone.com/fork/poWfsm

顺序：

        for(i = 0; i < arr_size; i += 8) {
            result += arr[i+0] + arr[i+1] + 
                    arr[i+2] + arr[i+3] + 
                    arr[i+4] + arr[i+5] +
                    arr[i+6] + arr[i+7];
        }

ILP:

        register unsigned int v0, v1, v2, v3;
        v0 = v1 = v2 = v3 = 0;
        for(i = 0; i < arr_size; i += 8) {              
            v0 += arr[i+0] + arr[i+1];
            v1 += arr[i+2] + arr[i+3];
            v2 += arr[i+4] + arr[i+5];
            v3 += arr[i+6] + arr[i+7];
        }
        result = v0+v1+v2+v3;

结果：

seq: 0.100000 sec, res: 1000000000, ipl: 0.110000 sec, faster 0.909091 X, res: 1000000000

seq: 0.100000 sec, res: 1000000000, ipl: 0.100000 sec, faster 1.000000 X, res: 1000000000

seq: 0.100000 sec, res: 1000000000, ipl: 0.110000 sec, faster 0.909091 X, res: 1000000000

seq: 0.100000 sec, res: 1000000000, ipl: 0.100000 sec, faster 1.000000 X, res: 1000000000

seq: 0.110000 sec, res: 1000000000, ipl: 0.110000 sec, faster 1.000000 X, res: 1000000000

seq: 0.100000 sec, res: 1000000000, ipl: 0.110000 sec, faster 0.909091 X, res: 1000000000

seq: 0.100000 sec, res: 1000000000, ipl: 0.110000 sec, faster 0.909091 X, res: 1000000000

seq: 0.110000 sec, res: 1000000000, ipl: 0.100000 sec, faster 1.100000 X, res: 1000000000

seq: 0.110000 sec, res: 1000000000, ipl: 0.100000 sec, faster 1.100000 X, res: 1000000000

seq: 0.110000 sec, res: 1000000000, ipl: 0.120000 sec, faster 0.916667 X, res: 1000000000

faster AVG: 0.975303

ILP 甚至比 Sequential 慢一点。

C 代码：http://ideone.com/fork/poWfsm

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

int main() {
    // create and init array
    const size_t arr_size = 100000000;
    unsigned int *arr = (unsigned int*) malloc(arr_size * sizeof(unsigned int));
    size_t i, k;
    for(i = 0; i < arr_size; ++i)
        arr[i] = 10;

    unsigned int result = 0;
    clock_t start, end;
    const int c_iterations = 10;    // iterations of experiment
    float faster_avg = 0;
    // -----------------------------------------------------------------


    for(k = 0; k < c_iterations; ++k) {
        result = 0; 

        // Sequential
        start = clock();

        for(i = 0; i < arr_size; i += 8) {
            result += arr[i+0] + arr[i+1] + 
                    arr[i+2] + arr[i+3] + 
                    arr[i+4] + arr[i+5] +
                    arr[i+6] + arr[i+7];
        }

        end = clock();
        const float c_time_seq = (float)(end - start)/CLOCKS_PER_SEC;   
        printf("seq: %f sec, res: %u, ", c_time_seq, result);
        // -----------------------------------------------------------------

        result = 0;

        // IPL-optimization
        start = clock();

        register unsigned int v0, v1, v2, v3;
        v0 = v1 = v2 = v3 = 0;

        for(i = 0; i < arr_size; i += 8) {

            v0 += arr[i+0] + arr[i+1];
            v1 += arr[i+2] + arr[i+3];
            v2 += arr[i+4] + arr[i+5];
            v3 += arr[i+6] + arr[i+7];


        }
        result = v0+v1+v2+v3;


        end = clock();
        const float c_time_ipl = (float)(end - start)/CLOCKS_PER_SEC;
        const float c_faster = c_time_seq/c_time_ipl;

        printf("ipl: %f sec, faster %f X, res: %u \n", c_time_ipl, c_faster, result);           
        faster_avg += c_faster;
    }

    faster_avg = faster_avg/c_iterations;
    printf("faster AVG: %f \n", faster_avg);

    return 0;
}

更新：

顺序（反汇编程序 MS Visual Studio 2013）:

    for (i = 0; i < arr_size; i += 8) {
        result += arr[i + 0] + arr[i + 1] +
            arr[i + 2] + arr[i + 3] +
            arr[i + 4] + arr[i + 5] +
            arr[i + 6] + arr[i + 7];
    }

000000013F131080  mov         ecx,dword ptr [rdx-18h]  
000000013F131083  lea         rdx,[rdx+20h]  
000000013F131087  add         ecx,dword ptr [rdx-34h]  
000000013F13108A  add         ecx,dword ptr [rdx-30h]  
000000013F13108D  add         ecx,dword ptr [rdx-2Ch]  
000000013F131090  add         ecx,dword ptr [rdx-28h]  
000000013F131093  add         ecx,dword ptr [rdx-24h]  
000000013F131096  add         ecx,dword ptr [rdx-1Ch]  
000000013F131099  add         ecx,dword ptr [rdx-20h]  
000000013F13109C  add         edi,ecx  
000000013F13109E  dec         r8  
000000013F1310A1  jne         main+80h (013F131080h)

ILP（反汇编程序 MS Visual Studio 2013）:

    for (i = 0; i < arr_size; i += 8) {
        v0 += arr[i + 0] + arr[i + 1];
000000013F1310F0  mov         ecx,dword ptr [rdx-0Ch]  
        v1 += arr[i + 2] + arr[i + 3];
        v2 += arr[i + 4] + arr[i + 5];
000000013F1310F3  mov         eax,dword ptr [rdx+8]  
000000013F1310F6  lea         rdx,[rdx+20h]  
000000013F1310FA  add         ecx,dword ptr [rdx-28h]  
000000013F1310FD  add         eax,dword ptr [rdx-1Ch]  
000000013F131100  add         ebp,ecx  
000000013F131102  mov         ecx,dword ptr [rdx-24h]  
000000013F131105  add         ebx,eax  
000000013F131107  add         ecx,dword ptr [rdx-20h]  
        v3 += arr[i + 6] + arr[i + 7];
000000013F13110A  mov         eax,dword ptr [rdx-10h]  
        v3 += arr[i + 6] + arr[i + 7];
000000013F13110D  add         eax,dword ptr [rdx-14h]  
000000013F131110  add         esi,ecx  
000000013F131112  add         edi,eax  
000000013F131114  dec         r8  
000000013F131117  jne         main+0F0h (013F1310F0h) 
    }
    result = v0 + v1 + v2 + v3;

编译命令行：

/GS /GL /W3 /Gy /Zc:wchar_t /Zi /Gm- /O2 /Ob2 /sdl /Fd"x64\Release\vc120.pdb" /fp:precise /D "_MBCS" /errorReport:prompt /WX- /Zc:forScope /Gd /Oi /MT /Fa"x64\Release\" /EHsc /nologo /Fo"x64\Release\" /Ot /Fp"x64\Release\IPL_reduce_test.pch"

答案的补充说明：

显示 50000000 双元素数组的展开循环和展开循环+ILP 之间的 ILP 优势的简单示例：http://ideone.com/LgTP6b

faster AVG: 1.152778

False-Sequential 可以通过 CPU-pipeline (Disassembler MS Visual Studio 2013) 优化 - 在每次迭代中添加 8 个元素使用临时注册 xmm0 然后添加到结果 xmm6，即可以使用 Register renaming:

result += arr[i + 0] + arr[i + 1] + arr[i + 2] + arr[i + 3] +
    arr[i + 4] + arr[i + 5] + arr[i + 6] + arr[i + 7];
000000013FBA1090  movsd       xmm0,mmword ptr [rcx-10h]  
000000013FBA1095  add         rcx,40h  
000000013FBA1099  addsd       xmm0,mmword ptr [rcx-48h]  
000000013FBA109E  addsd       xmm0,mmword ptr [rcx-40h]  
000000013FBA10A3  addsd       xmm0,mmword ptr [rcx-38h]  
000000013FBA10A8  addsd       xmm0,mmword ptr [rcx-30h]  
000000013FBA10AD  addsd       xmm0,mmword ptr [rcx-28h]  
000000013FBA10B2  addsd       xmm0,mmword ptr [rcx-20h]  
000000013FBA10B7  addsd       xmm0,mmword ptr [rcx-18h]  
000000013FBA10BC  addsd       xmm6,xmm0  
000000013FBA10C0  dec         rdx  
000000013FBA10C3  jne         main+90h (013FBA1090h)

True-Sequential 无法通过 CPU-pipeline (Disassembler MS Visual Studio 2013) 优化 - 在每次迭代中添加 8 个元素结果寄存器xmm6，即不能使用Register renaming:

            result += arr[i + 0];
000000013FFC1090  addsd       xmm6,mmword ptr [rcx-10h]  
000000013FFC1095  add         rcx,40h  
            result += arr[i + 1];
000000013FFC1099  addsd       xmm6,mmword ptr [rcx-48h]  
            result += arr[i + 2];
000000013FFC109E  addsd       xmm6,mmword ptr [rcx-40h]  
            result += arr[i + 3];
000000013FFC10A3  addsd       xmm6,mmword ptr [rcx-38h]  
            result += arr[i + 4];
000000013FFC10A8  addsd       xmm6,mmword ptr [rcx-30h]  
            result += arr[i + 5];
000000013FFC10AD  addsd       xmm6,mmword ptr [rcx-28h]  
            result += arr[i + 6];
000000013FFC10B2  addsd       xmm6,mmword ptr [rcx-20h]  
            result += arr[i + 7];
000000013FFC10B7  addsd       xmm6,mmword ptr [rcx-18h]  
000000013FFC10BC  dec         rdx  
000000013FFC10BF  jne         main+90h (013FFC1090h)

Answer 1

在大多数 Intel 处理器上，执行浮点加法需要 3 个周期。但如果它们是独立的，它最多可以维持 1 个/周期。

我们可以通过在关键路径上添加浮点数来轻松演示 ILP。

环境：

海湾合作委员会 4.8.2：-O2
桑迪桥至强

确保编译器不会进行不安全的浮点优化。

#include <iostream>
using namespace std;

#include <time.h>

const int iterations = 1000000000;

double sequential(){
    double a = 2.3;
    double result = 0;

    for (int c = 0; c < iterations; c += 4){
        //  Every add depends on the previous add. No ILP is possible.
        result += a;
        result += a;
        result += a;
        result += a;
    }

    return result;
}
double optimized(){
    double a = 2.3;
    double result0 = 0;
    double result1 = 0;
    double result2 = 0;
    double result3 = 0;

    for (int c = 0; c < iterations; c += 4){
        //  4 independent adds. Up to 4 adds can be run in parallel.
        result0 += a;
        result1 += a;
        result2 += a;
        result3 += a;
    }

    return result0 + result1 + result2 + result3;
}

int main(){

    clock_t start0 = clock();
    double sum0 = sequential();
    clock_t end0 = clock();
    cout << "sum = " << sum0 << endl;
    cout << "sequential time: " << (double)(end0 - start0) / CLOCKS_PER_SEC << endl;

    clock_t start1 = clock();
    double sum1 = optimized();
    clock_t end1 = clock();
    cout << "sum = " << sum1 << endl;
    cout << "optimized time:  " << (double)(end1 - start1) / CLOCKS_PER_SEC << endl;

}

输出：

sum = 2.3e+09
sequential time: 0.948138
sum = 2.3e+09
optimized time:  0.317293

请注意差异几乎正好是 3 倍。这是因为浮点加法的 3 周期延迟和 1 周期吞吐量。

顺序版本的 ILP 很少，因为所有浮点加法都在关键路径上。（每次添加都需要等到前一个添加完成） unrolled 版本有 4 个独立的依赖链，最多有 4 个独立的添加 - 所有这些都可以运行并行。只需 3 个即可使处理器内核饱和。

Answer 2

对于整数代码也可以使差异可见，例如

global cmp1
proc_frame cmp1
[endprolog]
    mov ecx, -10000000
    mov r8d, 1
    xor eax, eax
_cmp1_loop:
    add eax, r8d
    add eax, r8d
    add eax, r8d
    add eax, r8d
    add ecx, 1
    jnz _cmp1_loop
    ret
endproc_frame

global cmp2
proc_frame cmp2
[endprolog]
    mov ecx, -10000000
    mov r8d, 1
    xor eax, eax
    xor edx, edx
    xor r9d, r9d
    xor r10d, r10d
_cmp2_loop:
    add eax, r8d
    add edx, r8d
    add r9d, r8d
    add r10d, r8d
    add ecx, 1
    jnz _cmp2_loop
    add r9d, r10d
    add eax, edx
    add eax, r9d
    ret
endproc_frame

我的 4770K 的结果是第一个约为 3590 万 TSC 滴答，而第二个为 1190 万（最少运行时间超过 1k）。

在第一个中，eax 上的依赖链是最慢的，每次迭代有 4 个周期。其他都不重要，ecx 上的依赖链更快，并且有足够的吞吐量来隐藏它和控制流。顺便说一句，3590 万个 TSC 节拍可以计算出 4000 万个周期，因为 TSC 以 3.5GHz 的基本时钟频率节拍，但最大睿频频率为 3.9GHz，3.9/3.5 * 35.9 约为 40。

我在评论中提到的第二个版本（4 个累加器，但使用 [rsp] 来存储常量 1）需要 17.9，这使得每次迭代有 2 个周期。这与内存负载的吞吐量相匹配，在 Haswell 上为 2/周期。 4 个负载，所以 2 个周期。循环开销仍然可以隐藏。

上面发布的第二个每次迭代需要 1.3333 个周期。前四个添加可以转到端口 0、1、5 和 6，add/jnz 融合对只能转到端口 6。将融合对放在 p6 中，留下 3 个端口用于 4 µops，因此有 1.3333 个周期。

x86_64 上是否有一个真正有效的示例显示 ILP（指令级并行）的好处？

Is there a really working example which showing the benefits of ILP(Instruction-Level Parallelism) on x86_64?

c++

optimization

performance

x86

assembly