4. Vektorisieren, wie geht das?

Vektorisieren, wie geht das?

  • O

    Hey Leute 🙂

    Ich habe vor kurzen erstmalig die magische Welt der Vektorisierung kennen gelernt. Also SSE2 etc. Da für mich momentan Performance oberste Relevanz hat, stellt sich mir die Frage, wie man Code schreibt den der Compiler (gcc, VC, LLVM) vektorisieren kann.

    Ich habe mich ein wenig beim GCC etwas in deren Vektorisierung eingelesen, aber anhand der Beispiele wurde mir leider immer noch nicht klar, wann der GCC vektorisiert. Genauso, wie ich generell nicht weiß, was andere Compiler so drauf haben.

    Hier mal der Artikel: http://gcc.gnu.org/projects/tree-ssa/vectorization.html

    Beispiel Skalarprodukt. folgendes Vektorisiert:

    double a[256];
double b[256];

double result = 0;
for(std::size_t i = 0; i != 256;++i){
    result += a[i]*b[i];
}

    Soweit ich das verstanden habe, ist das möglich, weil der Speicher von a und b aligned ist und die Größe der Arrays sowie die Anzahl der Iterationen zur Compilezeit bekannt sind.

    Das heißt, folgendes vektorisiert wohl nicht:

    size_t size;
cin >> size;
double* a = new double[size];
double* b = new double[size];

double result = 0;
for(std::size_t i = 0; i != size;++i){
    result += a[i] * b[i];
}

    (stimmt das?)

    Wenn ich das nun zum vektorisieren bringen will, muss ich das dann so machen?

    size_t size;
cin >> size;
double* a = new double[size];
double* b = new double[size];

const size_t blockSize = 64;
double result = 0;
//das Array in gleich große Teile aufteilen, bis auf den letzten Rest
for(std::size_t i = 0; i < size; i += blockSize){
    size_t block = min(blockSize, size-i);
    for(std::size_t j = 0; j != block; ++i){
        result += a[i+j] * b[i+j];
    }
}

    Kann mich vielleicht jemand erleuchten, wann genau die Vektorisierer meinen Code anfangen zu mögen?

    [wenn das Thema im C++ Unterforum besser aufgehoben ist, bitte verschieben. ich halte da seher aber eher für ein compilerspezifisches Topic]

    0
  • A

    Die Anzahl der Iterationen muss nicht unbedingt zur Compile-Zeit bekannt sein, das wäre sonst nicht sonderlich nützlich.
    Falls die Anzahl der Iterationen "krumm" ist, werden die Restelemente ohne SSE gemacht.

    Ansonsten gilt die Devise, die Schleifen so einfach wie möglich zu halten. Nicht-inlinbare Funktionsaufrufe und break/continue sind demnach tabu.
    Im Moment hat das automatische Vektorisieren noch ein wenig von Glücksspiel an sich. Beim GCC habe ich schon einige Überraschungen erlebt. Sowohl, dass er relativ einfache Schleifen nicht vektorisiert hat wie auch, dass er Schleifen vektorisiert hat (und mit großem Geschwindigkeitsgewinn), bei denen ich das erst gar nicht für vernünftig möglich gehalten habe.

    Aber auch wenn der GCC das vektorisiert, muss das für andere Compiler noch lange nicht gelten (und umgekehrt). Falls du wirklich sicher gehen willst, solltest du besser doch die Arbeit selbst machen und Intrinsics einsetzen.

    Der ICC soll in diesem Gebiet übrigens der Konkurrenz etwas voraus sein. Selbst getestet habe ich das allerdings noch nicht.

    0
  • O

    Danke schonmal für die Antwort!

    Die Anzahl der Iterationen muss nicht unbedingt zur Compile-Zeit bekannt sein, das wäre sonst nicht sonderlich nützlich.
    Falls die Anzahl der Iterationen "krumm" ist, werden die Restelemente ohne SSE gemacht.

    Laut der GCC-docu muss der Compiler aber overlapp ausschließen können und dazu braucht er die Blockgröße.

    Mein drittes Beispiel stammt abgewandelt von hier:

    http://www.boost.org/doc/libs/1_47_0/boost/numeric/ublas/operation_blocked.hpp

    Im Vergleich zum axpy_prod hat die Methode einen Performancegewinn von Faktor 3. Und der einzige wirkliche Unterschied ist die Einführung der Blöcke.

    Es scheint also nicht so zu sein, dass die einfachste Schleife den besten Vektorisierungsgewinn erzielt. Leider.

    0
  • A

    Overlap ist hier nicht wichtig, da ohnehin nur lesend zugegriffen wird.
    Probieren geht bei Performanzfragen meist über Studieren. Das zeigt, dass die Performanz von Variante 2 und 3 identisch ist, Variante 1 ist wegen dem Stackarray aus mir gerade nicht nachvollziehbaren Gründen 30% langsamer (mit gcc 4.6). Vektorisiert wird jedoch bei allen drei. Einen Geschwindigkeitsvorteil bringt es bei mir nicht.
    Mit Intrinsics ist die Performanz ebenfalls mit 2 und 3 gleichauf (mit result=_mm_add_pd(result,_mm_hadd_pd(_mm_mul_pd(a_dq[i],b_dq[i]),zero)); )

    0
  • O

    jau, ausgemessen habe ich bei mir schon den code um den es ging (ublas prod vs händische Schleifen). Da kam aber eben raus, dass die blocked variante auch bei meiner aktuelleren CPU und gcc 4.6.1 mit -O3 -mcore2 einen Geschwindigkeitsvorteil von 15% vor dem axpy prod hat, welches exakt genauso schnell ist, wie meine händische Schleife:

    void prod2(const RealMatrix& C, const RealMatrix& A, const RealMatrix& B){
  for(std::size_t i = 0; i != A.size1(); ++i){
    for(std::size_t k = 0; k != A.size2(); ++k){
      for(std::size_t j = 0; j != A.size1(); ++j){
        C(i,j)+= A(i,k) * B(k,j);
      }
    }
  }
}

    Was sich mir aber dann nicht erschließt ist, warum die ganzen numerischen Bibliotheken immer noch so extrem viel schneller sind, obwohl der Compiler die ganzen Vektorisierungen bereits durchführt? Ich bin bislang davon ausgegangen, dass sie einfach per Hand die intrinsics setzen, dadurch "perfekt" vektorisieren, und der Laden läuft.

    In der Praxis kriegt man aber solche Graphen:

    http://eigen.tuxfamily.org/index.php?title=Benchmark

    Gibt es noch mehr Optimierungstricks, die man kennen sollte?

    0
Log in to reply