SSE 행렬 - 행렬 곱셈

Question

나는 문제가 여기에

C.

에서 SSE와 행렬 - 행렬 곱셈을 수행하는 데 문제가

는 내가 지금까지 무엇을 가지고 있습니다 정확한 결과를 제공하십시오. 내가 놓친 게 있니? 그리고 dosent 검색은별로 도움이 보인다 - 모든 결과 중 단지 4 × 4 행렬을하고, 매트 VEC 또는 특별한 마법은 매우 이해하기 읽기 쉽고 단단하지 이잖아 ...

업데이트 : Woho! 나는 마침내 그것을 알아 냈다. 내 논리의 오류 (도움 Peter Cordes 덕분에) 이외에도 _mm_mul_epi32() 문제가 있었는데 생각했던 것처럼 작동하지 않았습니다. 대신 _mm_mullo_epi32()를 사용해야했습니다!

이 코드가 가장 효과적이지는 않지만 우선 올바르게 작동하도록 만들어 졌음을 알았습니다. 이제이를 최적화 할 수 있습니다. 업데이트 2

void matmulSSE(int mat1[N][N], int mat2[N][N], int result[N][N]) { 
    int i, j, k; 
    __m128i vA, vB, vR, vSum; 

    for(i = 0; i < N; ++i) { 
     for(j = 0; j < N; ++j) { 
      vR = _mm_setzero_si128(); 
      for(k = 0; k < N; k += 4) { 
       //result[i][j] += mat1[i][k] * mat2[k][j]; 
       vA = _mm_loadu_si128((__m128i*)&mat1[i][k]); 
       vB = _mm_insert_epi32(vB, mat2[k][j], 0); 
       vB = _mm_insert_epi32(vB, mat2[k + 1][j], 1); 
       vB = _mm_insert_epi32(vB, mat2[k + 2][j], 2); 
       vB = _mm_insert_epi32(vB, mat2[k + 3][j], 3); 
       vR = _mm_mullo_epi32(vA, vB); 
       vR = _mm_hadd_epi32(vR, vR); 
       vR = _mm_hadd_epi32(vR, vR); 
       result[i][j] += _mm_extract_epi32(vR, 0); 

       //DEBUG 
       //printf("vA: %d, %d, %d, %d\n", vA.m128i_i32[0], vA.m128i_i32[1], vA.m128i_i32[2], vA.m128i_i32[3]); 
       //printf("vB: %d, %d, %d, %d\n", vB.m128i_i32[0], vB.m128i_i32[1], vB.m128i_i32[2], vB.m128i_i32[3]); 
       //printf("vR: %d, %d, %d, %d\n", vR.m128i_i32[0], vR.m128i_i32[1], vR.m128i_i32[2], vR.m128i_i32[3]); 
       //printf("\n"); 
      } 
     } 
    } 
} 

:은 I-K-J 루프 순서 버전 피터스 예 변환. vR에 대한 추가로드 및 저장소에서 내부 루프로 이동해야하지만 vA 설정은 루프 위로 이동할 수 있습니다. 빠른 것으로 나타났습니다.

void matmulSSE_2(int mat1[N][N], int mat2[N][N], int result[N][N]) { 
    int i, j, k; 
    __m128i vA, vB, vR; 

    for(i = 0; i < N; ++i) { 
     for(k = 0; k < N; ++k) { 
      vA = _mm_set1_epi32(mat1[i][k]); 
      for(j = 0; j < N; j += 4) { 
       //result[i][j] += mat1[i][k] * mat2[k][j]; 
       vB = _mm_loadu_si128((__m128i*)&mat2[k][j]); 
       vR = _mm_loadu_si128((__m128i*)&result[i][j]); 
       vR = _mm_add_epi32(vR, _mm_mullo_epi32(vA, vB)); 
       _mm_storeu_si128((__m128i*)&result[i][j], vR); 

       //DEBUG 
       //printf("vA: %d, %d, %d, %d\n", vA.m128i_i32[0], vA.m128i_i32[1], vA.m128i_i32[2], vA.m128i_i32[3]); 
       //printf("vB: %d, %d, %d, %d\n", vB.m128i_i32[0], vB.m128i_i32[1], vB.m128i_i32[2], vB.m128i_i32[3]); 
       //printf("vR: %d, %d, %d, %d\n", vR.m128i_i32[0], vR.m128i_i32[1], vR.m128i_i32[2], vR.m128i_i32[3]); 

       //printf("\n"); 
      } 
     } 
    } 
} 

Answer 1

네 말이 맞아, 당신의 vB 문제입니다. 4 개의 연속 정수를로드하고 있지만 mat2[k+0..3][j]은 인접하지 않습니다. 실제로 mat2[k][j+0..3]을 받고 있습니다.

---

나는 matmul에서 잘 작동하는지 잊어 버렸습니다. 때로는 모든 결과에 대해 수평 합을 계산하는 대신 4 개의 결과를 병렬로 생성하는 것이 효과적 일 수 있습니다.

입력 행렬 중 일부를 잘 바꾸면 비용이 O (N^2)가됩니다. O (N^3) matmul이 순차적 접근을 사용할 수 있고 현재 루프 구조가 SIMD 친화적이기 때문에 가치가 있습니다.

사용하기 바로 전에 작은 블록을 이항하는 것이 더 좋은 방법이기 때문에 다시 읽으면 L1 캐시에서 여전히 뜨겁습니다. 캐시 차단, 일명 루프 타일링은 좋은 matmul 성능의 핵심 요소 중 하나입니다.

SIMD와 캐시 블로킹을 사용하여 매트릭스 곱셈을 최적화하는 방법에 대해 많이 쓰여졌습니다. 나는 당신이 그것을 구글 추천한다. 대부분이 FP에 대해 말하면 대부분이지만, 정수에 대해서도 모두 적용됩니다.

(SSE/AVX 만 FP 대한 FMA 아닌 32 비트 정수를 들어, 상기도 8 및 16 비트 입력 PMADD 지침을 가지고 수평 쌍 추가 할 제외). 실제로 I

---

여기 병렬 4 개 결과를 생성 할 수 있습니다 생각 :

void matmulSSE(int mat1[N][N], int mat2[N][N], int result[N][N]) { 

    for(int i = 0; i < N; ++i) { 
    for(int j = 0; j < N; j+=4) { // vectorize over this loop 
     __m128i vR = _mm_setzero_si128(); 
     for(int k = 0; k < N; k++) { // not this loop 
      //result[i][j] += mat1[i][k] * mat2[k][j]; 
      __m128i vA = _mm_set1_epi32(mat1[i][k]); // load+broadcast is much cheaper than MOVD + 3 inserts (or especially 4x insert, which your new code is doing) 
      __m128i vB = _mm_loadu_si128((__m128i*)&mat2[k][j]); // mat2[k][j+0..3] 
      vR = _mm_add_epi32(vR, _mm_mullo_epi32(vA, vB)); 
     } 
     _mm_storeu_si128((__m128i*)&result[i][j], vR)); 
    } 
    } 
} 

브로드 캐스트 부하 (또는 AVX없이 별도의 부하 + 방송) 여전히 수집보다 훨씬 저렴합니다.

현재 코드는 첫 번째 요소에 대해 MOVD를 사용하여 이전 반복 값의 종속성 체인을 끊는 대신 4 개의 삽입을 사용하여 수집을 수행하므로 훨씬 더 심합니다.그러나 4 개의 흩어져있는 요소가 가장 잘 모여도로드 + PSHUFD에 비해 상당히 나 빠집니다. 말할 것도없이 SSE4.1이 필요한 코드가됩니다. 어쨌든, _mm_mullo_epi32 대신에 넓히는 것 PMULDQ (_mm_mul_epi32).