10
votes

Pourquoi la vectorisation automatique de GCC ne fonctionne pas sur la matrice de convolution plus grande que 3x3?

Je l'ai mis en œuvre le programme suivant pour la convolution matrice

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


14 commentaires

Pourriez-vous compléter suffisamment cela afin qu'il compile?


Bien sûr, je viens d'ajouter la partie manquée. Le programme Hole contient de nombreuses autres fonctions implémentées avec les intrinsions AVX2. Dans le programme, j'ai aligné toutes les matrices en utilisant __ attribut __ ((aligné (32)))


J'ai compilé avec #define CDIM1 3 in clang et MVC ++ et des écarts sur gcc -o2 est 0,97 et 4.34 respectivement clang -o3 et MVC ++ O2 i activé / arc: AVX2 et Extension d'amélioration aussi bien OT mais il n'y a pas de différence.


Pas de réponse pour cette question?


Je ne pouvais rien voir définitif. Il est difficile de voir quoi que ce soit à travers l'énorme blob d'ASM qui génère. Le seul indice que j'ai vu était que de nombreux registres sont utilisés pour 3x3, 5x5 prendrait plus que possible pour 5x5 GCC d'effrayer par la quantité de choses qu'il faudrait renverser .. Puis encore une fois, cela pourrait être autre chose, il y a beaucoup de choses des décisions heuristiques à ce moment-là


Pensez-vous, GCC a une bibliothèque de convolution 3x3? et ne l'avez pas pour 5x5?


Il pourrait s'agir de la taille de la matrice de convolution, 3x3xsizeof (court int) <256 (la taille du vecteur) chaque fois 5x5x16> 256


Avoir cette matrice dans un registre unique ne semble-t-elle pas très utile cependant, il faudrait des folles fous pour aligner les données avec elle puisqu'il est 2D. Mais j'irai à travers cet énorme désordre d'ASM et voir ce qu'il fait


Il pourrait y avoir un algorithme de vectorisation automatique qui est adapté aux registres inférieurs à 256


Il utilise un vecteur par élément de conv , une taille de vecteur n'est donc pas la question. Le nombre de registres pourrait encore être, mais je ne suis vraiment pas sûr. Certes, il ne peut pas utiliser 25 vecteurs pour contenir les entrées dans le boîtier 5x5, mais cela pourrait en diffuser une partie à la volée. Le GCC continue d'être peu coopératif, j'ai passé beaucoup de temps à essayer de le convaincre de faire un bon code pour 5x5, mais cela ne le fait pas, pas même avec une intrinsèque. Eh bien, peut-être que si je suis vraiment explicite et ne laissez rien à l'optimiseur, mais je dois ensuite dérouler à la main et perdre la généralité.


Aussi GCC fait toutes les mathématiques avec D deux au moins car il n'y a pas de division de vecteur entier). Donc Courte Temp Résultats dans le code plus agréable. Pas pour 5x5 cependant, c'est toujours trop à demander, apparemment. GCC est également vraiment prudent de ne pas écraser le rembourrage, de sorte que chaque ligne commence et se termine par 15 des convolutions scalaires, elle est facile à éviter avec intrinsique (le haut et le bas doit encore avoir cela, ou la lecture ira à l'extérieur de l'entrée).


Par intrinsèque, c'est bon. En fait, ce programme est une mise en œuvre difficile pour la convolution 2D. Avec quatre boucles imbriquées, la GCC peut l'améliorer de manière significative. Mais pas pour cette mise en œuvre


Il semble que vous n'êtes pas le poing que vous envisagez dans cela, la vactorisation automatique est assez complexe et fonctionne (ou non) très dépend de la manière dont vous écrivez votre code. La réécriture de votre structure de code pourrait vous aider beaucoup, je pense que les pages de liaison ne sont pas toujours la voie à suivre sur Stackoverflow, mais je voudrais vous lier à la page suivante: LocklessSInc.com/Articles/Articles Ce gars a mis de tout de travail dans la Vactorisation et j'espère que cela pourrait vous aider à résoudre votre problème.


@Koldewb, merci beaucoup, le lien semble très utile. Oui, il est possible de changer. En effet, j'ai changé la mise en œuvre naïve avec des boucles à ceci avec 3 boucles. Le code scalaire a ralenti et vectorisateur automatique ne le comprenait pas!


3 Réponses :


2
votes

Je suppose que cela ne doit pas optimiser en raison de problèmes d'alignement de la mémoire. Vous avez spécifié la convolution d'être de 2 octets. La plupart des fonctions de SSE aiment fonctionner avec des vecteurs de 128 bits et AVX aime 512 bits de vecteurs.

sur ma machine, j'ai déclaré convaincre comme ceci: xxx

et plus tard remplacer la boucle interne Comme ceci: xxx

compilation avec: gcc so.c -wall -wextra -ofast -mtune = natif m'a donné des optimisations de vecteur!

mauvaises choses:

  • N'utilisez pas 8. Essayez de trouver un remplissage minimal requis et de faire de la macro de sorte qu'il fonctionne avec des convolutions Matrices de dimension> = 8
  • entrée de pad avec quelques zéros de sorte que le comportement non défini à la fin disparaît
  • Notez que cela n'augmente pas votre perf. En fait, cela fonctionne plus lentement!
  • Notez que vous pouvez presser quelques cycles si vous le modifiez de manière ultérieure que vous exécutez des boucles dans la commande suivante pour (ki) pour (i) pour (j) pour (kj). Cela est probablement dû à moins de pression d'enregistrement car chaque rangée de convain peut être stockée plus longtemps. Cela pourrait aussi être un problème sur mon processeur.
  • Vous voudrez peut-être envisager d'utiliser __ attribut__ ((aligné (8))) lors de la déclaration de variables. Dans ce cas, cela n'a rien changé, mais lors de l'optimisation, vous voulez aussi considérer cela aussi. Naturellement, cela ne fonctionnera que sur GCC et vous aurez besoin d'autres hacks pour MSVC.

1 commentaires

Merci, mais vous avez changé la boucle intérieure. Comme je l'ai mentionné dans des commentaires et je vais mettre à jour la question. GCC peut vectoriser quatre boucles de mise en œuvre. Mon GCC 6.2 Vectorisez-le pour les noyaux 3x3 et 5x5 par ~ 6x SpeedUp. Même GCC améliore 7x7 et 9x9. BTW, le problème concerne la mise en œuvre inhabituelle qui s'appelle SEQCONV pas la mise en œuvre naïve.



3
votes

Il semble que personne ne soit intéressé à répondre à cette question. Je vais donc partager mes conclusions et mettre à jour ma réponse à l'avenir.

première mise à jour: dans mon expérience, GCC -FOPT-info-VEC Rapports vectorisants pour csize <= 16 c'est parce que la vectorisation facteur est 16 et c'est l'une des raisons pour lesquelles GCC n'a pas vécu la mise en œuvre inhabituelle pour les autres tailles de noyau. Facteur de vectorisation fait référence au nombre d'éléments qui peuvent être placés dans un vecteur. Dans ce cas, Entier court est égal à 16 bits élément.

de Wikipedia :

Dans la première étape, le compilateur recherche des obstacles pouvant empêcher la vectorisation. Un obstacle majeur pour la vectorisation est une véritable dépendance de données plus courte que la longueur du vecteur. Les autres obstacles incluent les appels de fonction et les comptes de l'itération courts.


0 commentaires

2
votes

L'obstacle principal de l'auto-vectorisateur est une variante de boucle non constante. Dans votre implémentation si vous utilisez int csize = p * q; code> il ne sera pas vectorisé. Donc, pour aider le vecteur automatique, vous devez considérer cela. Ce n'est pas le problème car vous avez déclaré le csize code> comme #define csize code>. Mais notez-le dans vos travaux. Ensuite, votre implémentation inhabituelle est une transformation en boucle de la mise en oeuvre de la nave qui est une méthode d'optimisation dans les compilateurs. Il semble que vous avez ruiné la mise en œuvre naïve. Votre découverte dit que son restreint en raison du 16 code> donc j'ai déroulé votre fonction inhabituelle et votre vecteur automatique indique qu'il a été vectorisé.

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


0 commentaires