gcc autovectorization이 3x3보다 큰 convolution 행렬에서 작동하지 않는 이유는 무엇입니까?

Question

나는 문제는 내가 자동 벡터화에 대한 -O3를 사용하는 경우, 그것은 단지 3 × 3 회선 매트릭스 작동이다 회선 매트릭스

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

#define NUM_LOOP 1000 
#define N 128 //input or output dimention 1 
#define M N  //input or output dimention 2 
#define P 5 //convolution matrix dimention 1 if you want a 3x3 convolution matrix it must be 3 
#define Q P  //convolution matrix dimention 2 
#define Csize P*Q 
#define Cdiv 1  //div for filter 
#define Coffset 0 //offset 

//functions 
void unusual(); //unusual implementation of convolution 
void naive(); 
//data 
unsigned short int input[N][M] __attribute__((aligned(32))); // input data 
unsigned short int output[N][M] __attribute__((aligned(32))); // out put data 
unsigned short int kernel[P][Q] __attribute__((aligned(32)));//convolution coefficients 

int main(){ 
    struct timespec tStart, tEnd;//used to record the processiing time 
    double tTotal , tBest=10000;//minimum of toltal time will asign to the best time 

    int w=0; 
    do{// this loop repeat the body to record the best time 
     clock_gettime(CLOCK_MONOTONIC,&tStart); 

     //function to be executed here : 

     unusual(); 

     clock_gettime(CLOCK_MONOTONIC,&tEnd); 
     tTotal = (tEnd.tv_sec - tStart.tv_sec); 
     tTotal += (tEnd.tv_nsec - tStart.tv_nsec)/1000000000.0; 

     if(tTotal<tBest) 
      tBest=tTotal; 
    } while(w++ < NUM_LOOP); 

    printf(" The best time: %lf sec in %d repetition for %dX%d matrix\n",tBest,w, MAX1, MAX2); 

    return 0; 
} 

//unusual sequential convolution 
void unusual(){ 
    int i, j,k,temp; 

    for (i=P/2; i< N-P/2; i++){ 
     for(j=Q/2; j< M-Q/2; j++){ 
      temp=0; 
      for(k=0; k< Csize; k++){ 
       temp += (kernel[k/P][k%Q]) * (input[i - (P/2) + (k/Q)][j - (Q/2) + (k%Q)]); 

      } 
      output[i][j]=((temp/(Cdiv))+Coffset); 
     } 
    } 
} 
//The naive implementation 
inline void naive(){ 
    int i, j,k,l,temp; 
    for (i=P/2; i< N-P/2; i++){ 
     for(j=Q/2; j< M-Q/2; j++){ 
      temp=0; 

      for(k = 0; k < P; k++){ 
       for(l = 0; l < Q; l++){ 
        temp += (kernel[k][l]) * (input[i - (P/2)+k][j - (Q/2)+l]); 
       } 
      } 
      output[i][j]=((temp/(Cdiv))+Coffset); 
     } 
    } 
} 

에 대해 다음 프로그램을 구현했습니다. 어셈블리 출력과 자동 벡터화가 3x3 커널을 약간 변경하고 성능을 합리적으로 향상시키는 것을 보았습니다 (20 시간 빨라짐 : 특이한 func의 스칼라 버전은 단순한 재미보다 느립니다). 그러나 5x5 회선 매트릭스에 대한 개선은 없습니다

업데이트 : 질문에 순진한 구현을 추가하고 그림 크기를 NxM, 커널에 conv 행렬, Cdim1xCdim2에서 PxQ로 변경하고 seqConv 기능을 명확히하기 위해 비정상적으로 변경했습니다. 문제는 비정상적인 기능의 구현을 향상시키는 것이 아닙니다. 문제는 모든 요소가 메모리의 동일한 위치에있는 반면 gcc는 경험적 방법을 사용하는 것입니다. gcc가이 비정상적인 구현을 향상시키지 못하는 이유는 무엇입니까? 참고 : 문제는 순진 구현에 관한 것이 아닙니다. gcc -O3은 3 배속, 5 배속 커널에 대한 순진한 구현을 ~ 7 배 향상시킵니다. 또한 1.5 배속으로 7x7 및 9x9를 처리합니다. 회선을 개선하기 위해 필자는 intrinsics를 사용했으며 속도가 비정상적인 회 돌이보다 ~ 2 배 빠른 순진 구현보다 40 배 이상 빠릅니다. 그래서 내 벡터화는 나의 특이한 것보다 80 배 빠릅니다. 손 조정 최적화는 문제가되지 않습니다. 자동 벡터화 최적화가 문제이며 실패의 원인입니다.

GCC 명령 : gcc -Wall -march=native -O3 -o "%e" "%f"

플랫폼 : 리눅스 민트, 스카이 레이크, 사전에 6.2

감사

Answer 1

내 생각 엔 그것 때문에 메모리 정렬에 문제를 최적화하기 위해 실패한다는 것입니다 GCC. 회선을 2 바이트 단락으로 지정했습니다. 대부분의 SSE 기능은 128 비트 벡터를 사용하고 AVX는 512 비트 벡터를 사용합니다. 내 컴퓨터에

는이 같은 전환 선언

uint16_t conv[Cdim1][8] = {0}; //You need to pad extra fields with zeroes 

을 그리고 나중에 같이 내부 루프를 대체 :

for(ki = 0; ki < Cdim; ++ki) 
    for(kj = 0; kj < 8; ++kj) 
     temp += (conv[ki][kj]) * (input[i - (Cdim1/2) + ki][j - (Cdim2/2) + kj]); 

를 사용하여 컴파일 : gcc so.c -Wall -Wextra -Ofast -mtune=native 나에게 벡터 최적화를 준!

나쁜 일 :

• 최소한의 필요한 패딩을 찾아 매크로 만들기 위해 8 시도를 사용하므로 그래서 일부 제로와 치수> = 8
• 패드 입력의 회선 행렬 작동하지 마십시오 결국 정의되지 않은 동작이 사라집니다.
• 실제로 이것은 perf를 증가시키지 않습니다. 사실 더 느리게 작동합니다!
• (kj)에 대해 (i) ~ (j)에 대해 (ki)에 대해 다음 순서로 루프를 실행하는 방식으로이를 수정하면 몇 가지 사이클을 압축 할 수 있습니다. 이는 conv의 각 행을 더 오래 저장할 수 있기 때문에 등록 압력이 적기 때문일 수 있습니다. 이것은 내 CPU의 결함 일 수도 있습니다.
• 변수를 선언 할 때 __attribute__ ((aligned (8)))을 사용할 수도 있습니다.이 경우에는 아무 것도 변경하지 않았지만 최적화 할 때 고려해야 할 사항이 있습니다. 물론 이것은 GCC에서만 작동하며 MSVC에 대한 다른 해킹이 필요할 것입니다.

Answer 2

아무도이 질문에 대답하는 데 관심이없는 것 같습니다. 그래서 나는 내 연구 결과를 공유하고 미래에 내 대답을 업데이트 할 것입니다.

첫 번째 업데이트 : 내 경험에서, GCC -fopt-info-vec 보고서는 벡터화 요인이 16이며, 그것은 GCC는 다른 커널 크기에 대한 특별한 구현을 벡터화하지 않는 이유 중 하나이기 때문이다 Csize <= 16에 대한 벡터화. 벡터화 요소는 벡터에 넣을 수있는 요소의 수를 나타냅니다. 이 경우 short integer은 16-bit 요소와 같습니다. wikipedia에서

: 첫 번째 단계에서

는, 컴파일러는 벡터화를 방지 할 수 장애물을 찾습니다. 벡터화의 주요 장애물은 벡터 길이보다 짧은 진정한 데이터 의존성입니다. 다른 장애물로는 함수 호출과 짧은 반복 횟수가 있습니다.

Answer 3

자동 벡터화 장치의 주된 장애물은 비상 수식 루프 변형입니다. 구현에서 int Csize = P*Q;을 사용하는 경우 벡터화되지 않습니다. 따라서 자동 벡터를 도우려면이 점을 고려해야합니다. Csize을 #define Csize (으)로 선언 했으므로 문제가되지 않습니다. 그러나 당신의 일에 주목하십시오. 그렇다면 특이한 구현은 컴파일러의 최적화 방법 인 nave 구현의 루프 변형입니다. 순진한 구현을 망치는 것 같습니다. 귀하의 발견에 따르면 16 때문에 제한적이어서 귀하의 비정상적인 기능을 풀었으며 자동 벡터 라이저는 그것이 벡터화되었다고 말합니다.

for(k=0; k< P*Q; k+=2){ 
       temp += (kernel[k/Q][k%Q]) * (input[i - (P/2) + (k/Q)][j - (Q/2) + (k%Q)]); 
       temp += (kernel[k/Q][k%Q]) * (input[i - (P/2) + ((k+1)/Q)][j - (Q/2) + ((k+1)%Q)]); 
} 

또한 7 × 7 커널 작동 : 당신은 #pragma 속성에 의해 루프 구조를 풀다하거나 변경하도록 컴파일러에 강제 할 수있을 자기하여 풀다 할 필요가없는

for(k=0; k< P*Q; k+=4){//IACA_START 
       temp += (kernel[k/Q][k%Q]) * (input[i - (P/2) + (k/Q)][j - (Q/2) + (k%Q)]); 
       temp += (kernel[k/Q][k%Q]) * (input[i - (P/2) + ((k+1)/Q)][j - (Q/2) + ((k+1)%Q)]); 
       temp += (kernel[k/Q][k%Q]) * (input[i - (P/2) + ((k+2)/Q)][j - (Q/2) + ((k+2)%Q)]); 
       temp += (kernel[k/Q][k%Q]) * (input[i - (P/2) + ((k+3)/Q)][j - (Q/2) + ((k+3)%Q)]); 
} 

. 컴파일러가 자동 벡터화에 사용하는 SLP 개념 때문입니다. 흥미롭게도 SLP은 언 롤링을 기반으로합니다.