c++ - 是否有一个真正有效的示例显示了 x86_64 上 ILP(指令级并行)的好处？

Question

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

但是否有一个真正有效的示例显示 ILP 的好处，至少是合成示例，对于 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];
        }

• 国际语言学院:

        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 双元素数组的 Unroll-loop 和 Unroll-loop+ILP 之间的 ILP 的好处:http://ideone.com/LgTP6b

faster AVG: 1.152778

• False-Sequential 可以通过 CPU 管道(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 管道(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 很少，因为所有浮点加法都在关键路径上。 (每个添加都需要等到前一个添加完成)展开的版本有 4 个独立的依赖链，最多有 4 个独立的添加——所有这些都可以并行运行。只需 3 个即可使处理器内核饱和。