Почему gve 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. Я видел, что выходные данные сборки и автоматическая векторизация просто вносят некоторые изменения в ядро ​​3x3 и разумно улучшают производительность (в 20 раз быстрее, примечание: скалярная версия необычного функционала медленнее, чем наивное веселье), но улучшения для матрицы свертки 5x5 нет

ОБНОВЛЕНИЕ: я добавил наивную реализацию к вопросу и изменил размер изображения на NxM, свернул матрицу на ядро, 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

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

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

Из википедии:

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

Answer 2

Основным препятствием для авто-векторизатора является вариант с непостоянным циклом. В вашей реализации, если вы используете 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 основан на развертывании!.

Answer 3

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