Почему gcc autovectorization не работает на матрице свертки больше 3x3?

Question

Я реализовал следующую программу для свертки матрицы

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

Проблема заключается в том, когда я использую -O3 для автоматической векторизации, он просто работает для матрицы 3x3 свертки. Я видел, что выход Assembly и автоматическая векторная нарисовка просто вносят некоторые изменения в ядро ​​3x3 и позволяют разумно улучшить производительность (в 20 раз быстрее: скалярная версия необычной функции медленнее, чем наивная забава), но нет улучшения в матрице свертки 5x5

UPDATE: Я добавил наивную реализацию к вопросу и изменил размер изображения на NxM, conv-матрицу на ядро, Cdim1xCdim2 на PxQ и функцию seqConv до необычного для пояснения. Вопрос заключается не в том, чтобы улучшить реализацию необычной функции. Вопрос в том, что все элементы находятся в одних и тех же местах памяти, gcc использует эвристику и т. Д., Почему gcc не может улучшить эту необычную реализацию? ПРИМЕЧАНИЕ: проблема не в наивном исполнении. gcc -O3 улучшают наивную реализацию для ядер 3x3, 5x5 на ~ 7 ускорение. и он также делает для 7x7 и 9x9 на ~ 1,5 ускорения. Чтобы улучшить свертку, я использовал встроенные функции и ускорение более чем в 40 раз по сравнению с наивной реализацией, которая в 2 раза быстрее, чем необычная свертка. Таким образом, моя векторизация ~ 80 раз быстрее, чем моя необычная. Оптимизация ручной настройки не является проблемой. Автоматическая оптимизация векторных изображений является проблемой, и причина неудачи.

команда GCC: gcc -Wall -march=native -O3 -o "%e" "%f"

Платформа: Linux Mint, Skylake, GCC 6.2

Заранее спасибо

Answer 1

Я предполагаю, что он не в состоянии оптимизировать из-за проблем с выравниванием памяти. Вы указали свертку на 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
• ввода Pad с некоторыми нулями так что неопределенное поведение в конце исчезает
• Обратите внимание, что на самом деле это не увеличивает ваш перфоманс. На самом деле он работает медленнее!
• Обратите внимание, что вы можете сжать несколько циклов, если вы измените это дальше так, чтобы вы выполняли циклы в следующем порядке для (ki) для (i) для (j) для (kj). Вероятно, это связано с меньшим давлением регистров, поскольку каждая строка conv может храниться дольше. Это также может быть сбой на моем процессоре.
• При объявлении переменных вы также можете использовать __attribute__ ((aligned (8))).В этом случае это ничего не изменило, но при оптимизации вы тоже хотите это рассмотреть. Естественно, это будет работать только на GCC, и вам понадобятся другие хаки для MSVC.

Answer 2

Кажется, никто не заинтересован в ответе на этот вопрос. Поэтому я поделюсь своими выводами и уточню свой ответ в будущем.

Первое обновление: По моему опыту, GCC -fopt-info-vec отчеты векторизации для Csize <= 16 Это потому, что фактор векторизация 16 и это одна из причин того, что НКУ не векторизации необычное реализацию других размеров ядра. Фактор векторизации относится к числу элементов, которые могут быть помещены в вектор. В этом случае short integer равен 16-bit.

От wikipedia:

На первом этапе, компилятор ищет препятствия, которые могут помешать векторизации. Основным препятствием для векторизации является истинная зависимость данных, меньшая длины вектора. Другие препятствия включают вызовы функций и подсчеты короткой итерации.

Answer 3

Основным препятствием для автоинтерватора является вариант с непостоянным контуром. В вашей реализации, если вы используете int Csize = P*Q; Это не будет векторизовать. Поэтому для помощи авто вектор вы должны рассмотреть это. Это не проблема, потому что вы объявили Csize как #define Csize. Но обратите внимание на это в ваших работах. Тогда ваша необычная реализация - это преобразование цикла в реализацию нефа, которая является методом оптимизации в компиляторах. Кажется, вы испортили наивную реализацию. Ваше открытие говорит о том, что он ограничен из-за 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)]); 
} 

Он также работает для 7x7 ядра:

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)]); 
} 

вам не нужно раскатать его вашей собственной личности, вы можете быть в состоянии заставить компилятор раскатать или изменить структуру цикла по #pragma атрибутов , Это из-за концепции SLP, которую компиляторы используют для авто-векторизации, и интересно SLP основан на разворачивании !.