parallelizzazione della moltiplicazione della matrice tramite threading e SIM

Question

Sto cercando di accelerare la moltiplicazione della matrice su architettura multicore. Per questo scopo, cerco di utilizzare thread e SIMD contemporaneamente. Ma i miei risultati non sono buoni. I test accelerare sopra sequenziale moltiplicazione matriciale:

void sequentialMatMul(void* params) 
{ 
    cout << "SequentialMatMul started."; 
    int i, j, k; 
    for (i = 0; i < N; i++) 
    { 
     for (k = 0; k < N; k++) 
     { 
      for (j = 0; j < N; j++) 
      { 
       X[i][j] += A[i][k] * B[k][j]; 
      } 
     } 
    } 
    cout << "\nSequentialMatMul finished."; 
} 

Ho provato ad aggiungere filettatura e SIMD alla matrice di moltiplicazione come segue:

void threadedSIMDMatMul(void* params) 
{ 
    bounds *args = (bounds*)params; 
    int lowerBound = args->lowerBound; 
    int upperBound = args->upperBound; 
    int idx = args->idx; 

    int i, j, k; 
    for (i = lowerBound; i <upperBound; i++) 
    { 
     for (k = 0; k < N; k++) 
     { 
      for (j = 0; j < N; j+=4) 
      { 
       mmx1 = _mm_loadu_ps(&X[i][j]); 
       mmx2 = _mm_load_ps1(&A[i][k]); 
       mmx3 = _mm_loadu_ps(&B[k][j]); 
       mmx4 = _mm_mul_ps(mmx2, mmx3); 
       mmx0 = _mm_add_ps(mmx1, mmx4); 
       _mm_storeu_ps(&X[i][j], mmx0); 
      } 
     } 
    } 
    _endthread(); 
} 

E la sezione seguente viene utilizzata per calcolare lowerbound e limitesuperiore di ogni filo :

bounds arg[CORES]; 
for (int part = 0; part < CORES; part++) 
{ 
    arg[part].idx = part; 
    arg[part].lowerBound = (N/CORES)*part; 
    arg[part].upperBound = (N/CORES)*(part + 1); 
} 

E infine filettato versione SIMD viene chiamato in questo modo:

HANDLE handle[CORES];  
for (int part = 0; part < CORES; part++) 
{ 
    handle[part] = (HANDLE)_beginthread(threadedSIMDMatMul, 0, (void*)&arg[part]); 
} 
for (int part = 0; part < CORES; part++) 
{ 
WaitForSingleObject(handle[part], INFINITE); 
} 

Il risultato è il seguente: Test 1:

// arrays are defined as follow 
float A[N][N]; 
float B[N][N]; 
float X[N][N]; 
N=2048 
Core=1//just one thread 

tempo sequenziale: 11129ms

filettato SIMD tempo matmul: 14650ms

Accelerare = 0,75x

test 2:

//defined arrays as follow 
float **A = (float**)_aligned_malloc(N* sizeof(float), 16); 
float **B = (float**)_aligned_malloc(N* sizeof(float), 16); 
float **X = (float**)_aligned_malloc(N* sizeof(float), 16); 
for (int k = 0; k < N; k++) 
{ 
    A[k] = (float*)malloc(cols * sizeof(float)); 
    B[k] = (float*)malloc(cols * sizeof(float)); 
    X[k] = (float*)malloc(cols * sizeof(float)); 
} 
N=2048 
Core=1//just one thread 

tempo sequenziale: 15907ms

filettato SIMD tempo matmul: 18578ms

Accelerare = 0.85x

Test 3:

//defined arrays as follow 
float A[N][N]; 
float B[N][N]; 
float X[N][N]; 
N=2048 
Core=2 

tempo sequenziale: 10855ms

filettato SIMD matmul time: 27967ms

Accelerare = 0.38x

Test 4:

//defined arrays as follow 
float **A = (float**)_aligned_malloc(N* sizeof(float), 16); 
float **B = (float**)_aligned_malloc(N* sizeof(float), 16); 
float **X = (float**)_aligned_malloc(N* sizeof(float), 16); 
for (int k = 0; k < N; k++) 
{ 
    A[k] = (float*)malloc(cols * sizeof(float)); 
    B[k] = (float*)malloc(cols * sizeof(float)); 
    X[k] = (float*)malloc(cols * sizeof(float)); 
} 
N=2048 
Core=2 

tempo sequenziale: 16579ms

filettato SIMD tempo matmul: 30160ms

Accelerare = 0.51x

mio domanda: perché non ottengo velocità?

Answer 1

Qui ci sono le volte che comincia a costruire il vostro algoritmo sul mio quattro core del processore i7 IVB.

sequential:   3.42 s 
4 threads:   0.97 s 
4 threads + SSE: 0.86 s 

Qui ci sono i tempi su un P9600 2 nucleo @ 2.53 GHz, che è simile a E2200 del PO @ 2,2 GHz

sequential: time 6.52 s 
2 threads: time  3.66 s 
2 threads + SSE: 3.75 s 

ho usato OpenMP perché rende questo facile. Ogni thread in OpenMP corre sopra efficacemente

lowerBound = N*part/CORES; 
upperBound = N*(part + 1)/CORES; 

(si noti che questo è un po 'diversa da quella definizione. La tua definizione può dare il risultato sbagliato a causa dell'arrotondamento per alcuni valori di N poiché si divide per CORES prima.)

Per quanto riguarda la versione SIMD. Non è molto più veloce probabilmente a causa del limite di larghezza di banda della memoria. Probabilmente non è molto più veloce perché GCC già vectizza il loop.

La soluzione ottimale è molto più complicata. È necessario utilizzare loop tiling e riordinare gli elementi all'interno delle tessere per ottenere prestazioni ottimali. Non ho tempo per farlo oggi.

Ecco il codice che ho usato:

//c99 -O3 -fopenmp -Wall foo.c 
#include <stdio.h> 
#include <string.h> 
#include <x86intrin.h> 
#include <omp.h> 

void gemm(float * restrict a, float * restrict b, float * restrict c, int n) { 
    for(int i=0; i<n; i++) { 
     for(int k=0; k<n; k++) { 
      for(int j=0; j<n; j++) { 
       c[i*n+j] += a[i*n+k]*b[k*n+j]; 
      } 
     } 
    } 
} 

void gemm_tlp(float * restrict a, float * restrict b, float * restrict c, int n) { 
    #pragma omp parallel for 
    for(int i=0; i<n; i++) { 
     for(int k=0; k<n; k++) { 
      for(int j=0; j<n; j++) { 
       c[i*n+j] += a[i*n+k]*b[k*n+j]; 
      } 
     } 
    } 
} 

void gemm_tlp_simd(float * restrict a, float * restrict b, float * restrict c, int n) { 
    #pragma omp parallel for 
    for(int i=0; i<n; i++) { 
     for(int k=0; k<n; k++) { 
      __m128 a4 = _mm_set1_ps(a[i*n+k]); 
      for(int j=0; j<n; j+=4) { 
       __m128 c4 = _mm_load_ps(&c[i*n+j]); 
       __m128 b4 = _mm_load_ps(&b[k*n+j]); 
       c4 = _mm_add_ps(_mm_mul_ps(a4,b4),c4); 
       _mm_store_ps(&c[i*n+j], c4); 
      } 
     } 
    } 
} 

int main(void) { 
    int n = 2048; 
    float *a = _mm_malloc(n*n * sizeof *a, 64); 
    float *b = _mm_malloc(n*n * sizeof *b, 64); 
    float *c1 = _mm_malloc(n*n * sizeof *c1, 64); 
    float *c2 = _mm_malloc(n*n * sizeof *c2, 64); 
    float *c3 = _mm_malloc(n*n * sizeof *c2, 64); 
    for(int i=0; i<n*n; i++) a[i] = 1.0*i; 
    for(int i=0; i<n*n; i++) b[i] = 1.0*i; 
    memset(c1, 0, n*n * sizeof *c1); 
    memset(c2, 0, n*n * sizeof *c2); 
    memset(c3, 0, n*n * sizeof *c3); 
    double dtime; 

    dtime = -omp_get_wtime(); 
    gemm(a,b,c1,n); 
    dtime += omp_get_wtime(); 
    printf("time %f\n", dtime); 

    dtime = -omp_get_wtime(); 
    gemm_tlp(a,b,c2,n); 
    dtime += omp_get_wtime(); 
    printf("time %f\n", dtime); 

    dtime = -omp_get_wtime(); 
    gemm_tlp_simd(a,b,c3,n); 
    dtime += omp_get_wtime(); 
    printf("time %f\n", dtime); 
    printf("error %d\n", memcmp(c1,c2, n*n*sizeof *c1)); 
    printf("error %d\n", memcmp(c1,c3, n*n*sizeof *c1)); 
} 

Answer 2

Mi sembra che i thread stiano condividendo le variabili __m128 mmx*, probabilmente li avete definiti globali/statici. Anche i tuoi array X devono avere risultati errati. Definire le variabili __m128 mmx* all'interno dello scope della funzione threadedSIMDMatMul e verrà eseguito molto più velocemente.

void threadedSIMDMatMul(void* params) 
{ 
    __m128 mmx0, mmx1, mmx2, mmx3, mmx4; 
    // rest of the code here 
}