c++ C'è un esempio davvero funzionante che mostra i vantaggi di ILP(Parallelismo a livello di istruzione) su x86_64?




performance optimization (2)

Come noto, la CPU è una pipeline e funziona in modo più efficiente se la sequenza di comandi è indipendente l'una dall'altra - questo noto come ILP (Istruzione a livello di parallelismo): http://en.wikipedia.org/wiki/Instruction-level_parallelism

Ma c'è un esempio davvero funzionante che mostra i vantaggi di ILP, almeno un esempio sintetico, per CPU x86_64 (ma per la stessa quantità di cmp / jne in entrambi i casi )?

Scriverò il seguente esempio: somma tutti gli elementi dell'array, ma non mostra alcun vantaggio di ILP: http://ideone.com/fork/poWfsm

  • Sequenziale:
        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;

Risultato:

seq: 0,100000 sec, res: 1000000000, ipl: 0,110000 sec, più veloce 0,909091 X, risoluzione: 1000000000

seq: 0,100000 sec, res: 1000000000, ipl: 0,100000 sec, più veloce 1,000000 X, risoluzione: 1000000000

seq: 0,100000 sec, res: 1000000000, ipl: 0,110000 sec, più veloce 0,909091 X, risoluzione: 1000000000

seq: 0,100000 sec, res: 1000000000, ipl: 0,100000 sec, più veloce 1,000000 X, risoluzione: 1000000000

seq: 0,110000 sec, res: 1000000000, ipl: 0,110000 sec, più veloce 1,000000 X, risoluzione: 1000000000

seq: 0,100000 sec, res: 1000000000, ipl: 0,110000 sec, più veloce 0,909091 X, risoluzione: 1000000000

seq: 0,100000 sec, res: 1000000000, ipl: 0,110000 sec, più veloce 0,909091 X, risoluzione: 1000000000

seq: 0,110000 sec, res: 1000000000, ipl: 0,100000 sec, più veloce 1.100000 X, res: 1000000000

seq: 0,110000 sec, res: 1000000000, ipl: 0,100000 sec, più veloce 1.100000 X, res: 1000000000

seq: 0,110000 sec, res: 1000000000, ipl: 0,120000 sec, più veloce 0.916667 X, res: 1000000000

AVG più veloce: 0.975303

ILP anche un po 'più lento di Sequential.

Codice 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;
}

AGGIORNARE:

  • Sequenziale (Disassembler 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 (Disassembler 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;

Riga di comando del compilatore:

/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" 

Note aggiuntive alla risposta:

Il semplice esempio che mostra i vantaggi di ILP tra Unroll-loop e Unroll-loop + ILP per array di 50000000 elementi doppi: http://ideone.com/LgTP6b

AVG più veloce: 1.152778

  • False-Sequential che può essere ottimizzato dalla CPU-pipeline (Disassembler MS Visual Studio 2013) - per aggiungere 8 elementi in ogni iterazione utilizza il registro temporaneo xmm0 che quindi aggiunge al risultato xmm6 , cioè può essere usato Registra rinominare :
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 che non può essere ottimizzato dalla CPU-pipeline (Disassembler MS Visual Studio 2013) - per aggiungere 8 elementi in ogni iterazione utilizza il registro dei risultati xmm6 , cioè non può essere utilizzato Registra rinominare :
            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

La differenza può anche essere resa visibile per il codice intero, ad esempio

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

I risultati sul mio 4770K sono circa 35,9 milioni di tick TSC per il primo contro 11,9 milioni per il secondo (tempo minimo su 1k).

Nella prima, la catena delle dipendenze su eax è la cosa più lenta a 4 cicli per iterazione. Non importa nient'altro, la catena di dipendenze su ecx è più veloce e c'è un sacco di throughput per nasconderlo e il flusso di controllo. 35,9 milioni di tick TSC funzionano a 40 milioni di cicli tra l'altro, dal momento che i tick TSC alla frequenza di clock di base di 3,5 GHz, ma il turbo massimo è di 3,9 GHz, 3,9 / 3,5 * 35,9 è di circa 40.

La versione del secondo che ho menzionato nei commenti (4 accumulatori ma usando [rsp] per memorizzare la costante 1) richiede 17,9, il che rende 2 cicli per iterazione. Ciò corrisponde alla velocità effettiva dei carichi di memoria, che su Haswell è 2 / ciclo. 4 carichi quindi 2 cicli. L'overhead del loop può ancora nascondersi.

Il secondo sopra postato richiede 1,33333 cicli per iterazione. I primi quattro add possono andare alle porte 0, 1, 5 e 6, la coppia di add/jnz può andare solo alla porta 6. Mettere la coppia fusa in p6 lascia 3 porte per 4 μops, quindi 1,33333 cicli.


Answer #2

Sulla maggior parte dei processori Intel, ci vogliono 3 cicli per fare un addizione a virgola mobile. Ma può sostenere fino a 1 / ciclo se sono indipendenti.

Possiamo facilmente dimostrare ILP inserendo un punto in virgola mobile sul percorso critico.

Ambiente:

  • GCC 4.8.2: -O2
  • Sandy Bridge Xeon

Assicurarsi che il compilatore non esegua ottimizzazioni in virgola mobile non sicure.

#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;

}

Produzione:

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

Nota come la differenza è quasi esattamente 3x. Ciò è dovuto alla latenza a 3 cicli e al throughput a 1 ciclo dell'addizione a virgola mobile.

La versione sequenziale ha pochissima ILP perché tutti gli addetti a virgola mobile si trovano sul percorso critico. (ogni aggiunta deve attendere fino a quando non viene eseguita l'aggiunta precedente) La versione srotolata ha 4 catene di dipendenze separate con un massimo di 4 add-on indipendenti, che possono essere eseguiti in parallelo. Sono necessari solo 3 per saturare il core del processore.