Vektorisierung



  • Ich habe eine Berechnung, die etwa so aufgebaut ist:

    for(int i=0; i < N; i++)
      y[i] = a[i] * f(t,i,y_2)
    

    Das würde ich gerne vektorisiert haben, da keine schleifengetragenen Abhängigkeiten bestehen.

    foo() hat den Rückgabewert double und scheint die Autovektorisierung zu blockieren.

    Wie kann ich dem Compiler klar machen, dass das irgendwie gehen muss?
    Oder wie kann ich es selbst bewerkstelligen?



  • Compiler?
    Sprache bzw Sprachstandard?
    Eventuelle weitere Werkzeuge wie OpenMP oder MPI?


  • Mod

    Das würde ich gerne vektorisiert haben, da keine schleifengetragenen Abhängigkeiten bestehen.

    Und wie sieht f aus? Was passiert wenn du das inlinen forcierst?

    Sprache bzw Sprachstandard?

    Da er im C++ Board postet ist die Sprache C++, und der Sprachstandard ist völlig irrelevant.

    Compiler?

    Wird wohl GCC sein, blind geraten.



  • Compiler:
    Mehere. Programm hat switches für gcc, icc, clang und noch irgendwas exotisches.

    Architektur:
    Ebenfalls verschieden, hätte aber kein Problem mehrere Intrinsics oder Compiler-Optionen je Architektir einzufügen, müsste nur wissen, wie ich das am besten mache.

    Programmiermodelle:
    mehrere: MPI, OPenMP, Pthreads, alles mögliche wird verwendet.

    Es reicht mir auch erstmal ein Beispiel, wie ich das machen kann zB mit dem Intel Compiler, da der Vektorisierung besinders schön anzeigt



  • das wie ich finde einfachste wäre: Vor den for-Loop en

    #pragma omp parallel for
    

    zu schreiben



  • @shisha
    Ist N konstant und klein? (Ich schätze mal ja und ja, aber weiss ja nicht.)
    Und du willst Vektorisierung im Sinne von SIMD, ja? Also nicht parallelisierung mit mehreren Threads ala OpenMP?

    Die Multiplikation kannst du dabei schonmal ziemlich sicher vektorisierbar machen. Und zwar indem du

    for(int i=0; i < N; i++)
      temp[i] = f(t,i,y_2);
    for(int i=0; i < N; i++)
      y[i] = a[i] * temp[i];
    

    machst.
    Bzw. statt der 2. Schleife kannst du dann natürlich auch gleich ein SIMD intrinsic aufrufen.

    Ob die erste Schleife vektorisierbar ist, hängt davon ab was f macht. Wenn f irgendwelche beobachtbaren Nebeneffekte hat (bzw. haben könnte, wie z.B. Exceptions), dann wird es nicht gehen. Dann müsstest du f so umschreiben dass es eben keine beobachtbaren Nebeneffekte mehr gibt.
    (Ich hab' ehrlich gesagt keine Ahnung ob Compiler Floatingpoint-Exceptions (signaling NaN, ...) als beobachtbaren Nebeneffekte zählen. Falls ja, dann weiss ich im Moment auch nicht wie man das am elegantesten löst.)



  • Ja, ich meine SIMD-Parallelität, sei es AVX, oder was auch immer gerade zur Verfügung steht.

    Allerdings kann N sehr groß sein, zwar versuche ich es in manchem Implementierungen mit Loop-Tiling, aber die Basis-Variante ist eigentlich ein sehr großes N, welches jedoch dann auch wieder durch p Prozessoren geteilt wird ... aber generell halte ich es für keine gute Idee zwei Schleifendurchläufe zu machen, da Geschwindigkeit alles ist, was bei unserem Programm zählt.



  • OK. Hmmm...
    Was steht denn in f?



  • f ist eine Funktionsauswertung eines Differentialgleichungssystems. Das kann sich dabei um unterschiedliche Rechnungen mit unterschiedlichem Rechenaufwand handeln.

    Der Code ist natürlich stark vereinfacht.

    Fakt ist jedoch, dass f keinerlei zusätzlichen Abhängigkeiten oder Nebeneffekte mit sich bringt.



  • Auch wenn ich es nutr ungern tue ... stups^



  • Funktionsauswertung eines Differentialgleichungssystems ... unterschiedliche Rechnungen mit unterschiedlichem Rechenaufwand

    Kannst du mal ein konkretes Beispiel bringen?
    Ich schätze nämlich dass f einfach nicht bzw. nicht sinnvoll vekorisierbar ist.

    Ansonsten, ein paar Dinge man mMn. beachten sollte wenn man vektorisierbaren Code schreiben will:

    * Alles muss inlinebar sein. D.h. keine Funktionszeiger, kein virtual, keine Calls über DLL/SO Grenzen, keine OS Calls, keine non-inline/non-intrinsic Standard-Library Calls. Das schliesst natürlich sämtliche Dinge wie setjmp/farjmp, Exceptions, Trace-Ausgaben, Asserts etc. mit ein.

    * Entweder muss alles was vektorisiert werden soll in der selben Translation-Unit als Source vorliegen, oder "Link-Time-Code-Generation" muss aktiviert sein.

    * Es darf keine Möglichkeit geben wie der Loop "vorzeitig" verlassen werden kann (also unabhängig vom "Schleifenzähler"). Also keine Exceptions o.ä. (OK, das hatten wir ja schon).

    * Idealerweise keine Typen mischen (alles float oder alles double ). Ich glaube gelesen zu haben dass aktuelle Compiler damit umgehen können, aber ich gehe mal davon aus dass es trotzdem besser ist wenn man sich auf einen Typ beschränkt.

    * Der Compiler muss wissen dass sämtliche Zeiger Alias-frei sind. => __restrict

    * Man sollte den Compiler vermutlich wissen lassen dass er Dinge wie Denormals oder Floatingpoint Exceptions ignorieren kann. Je nach Compiler könnten dafür bestimmte Switches oder das Verwenden von bestimmten Datentypen notwendig sein. Bei MSVC muss man soweit ich weiss mit /fp:fast compilieren wenn man vektorisierten Code haben will. Möglicherweise ist auch /arch:SSE , /arch:SSE2 oder /arch:AVX erforderlich (sollte mMn. aber nicht).

    Und sowohl GCC als auch MSVC haben Switches mittels derer man Diagnostics darüber bekommt was vektorisiert worden ist:
    http://stackoverflow.com/questions/17602290/existence-of-simd-reduction-in-gcc-and-msvc
    Vom MSVC kannst du mit /Qvec-report:2 sogar den Grund dafür bekommen warum etwas nicht vektorisiert wurde.



  • ps:
    Hab's grad selbst mal ausprobiert. Die Infos die MSVC ausspuckt sind ganz gut.
    Allerdings auch nicht "deppensicher".
    z.B. sagt MSVC bei

    double sumsum(double* a, size_t n)
    {
    	double accu = 0;
    	for (size_t i = 0; i < n; i++)
    		accu = accu + a[i];
    	return accu;
    }
    

    mit Default-Einstellungen info C5002: loop not vectorized due to reason '1105' , wobei 1105 für Loop includes a unrecognized reduction operation steht.
    Gibt man allerdings /fp:fast mit, dann tut er brav vektorisieren.

    Wobei er dagegen

    void loop(double* a, double* b, double* c, size_t n)
    {
    	for (size_t i = 0; i < n; i++)
    		a[i] = b[i] + c[i];
    }
    

    auch ohne /fp:fast vektorisiert.

    => Hat wohl nen Grund dass es für diese Optimierung spezielle Diagnostics gibt 🙂

    Und MSVC scheint schon bei den einfachsten Flow-Control Statements auszusteigen. Sogar wenn's nur ein einfaches i % 2 == 0 ist: Reason 1100: Loop contains control flow—for example, "if" or "?".

    Dafür ist es MSVC egal ob man __restrict angibt oder nicht -- er generiert einfach zusätzlich eine nicht-vektorisierte Variante, und macht dann zur Laufzeit nen Aliasing-Check. Hab ich sogar mal wo gelesen, ist mir aber erst grad wieder eingefallen nachdem ich erfolglos versucht habe durch Aliasing die vektorisierung eines einfachen Loops zu verhindern.



  • ps:
    Clang und GCC brauchen -ffast-math damit sie vernünftig vektorisieren können.


  • Mod

    hustbaer schrieb:

    ps:
    Clang und GCC brauchen -ffast-math damit sie vernünftig vektorisieren können.

    -ffast-math ist nötig für Vektorisierung bei Fließkommazahlen. (Sollte man erwähnen.)

    Ich glaube gelesen zu haben dass aktuelle Compiler damit umgehen können

    Wie denn? Ich habe keine Ahnung von Vektorisierung, aber sind die Vector-Instructions auch auf zwei verschiedene Typen spezialisiert? Oder macht der Compiler da 'nen impliziten Cast (wobei letzteres doch anderes Verhalten erzeugen würde)?



  • @Arcoth
    Ja, richtig, wenn man ohne Fliesskommazahlen auskommt dann braucht man auch kein -ffast-math.

    Arcoth schrieb:

    Ich glaube gelesen zu haben dass aktuelle Compiler damit umgehen können

    Wie denn? Ich habe keine Ahnung von Vektorisierung, aber sind die Vector-Instructions auch auf zwei verschiedene Typen spezialisiert? Oder macht der Compiler da 'nen impliziten Cast (wobei letzteres doch anderes Verhalten erzeugen würde)?

    Es gibt keine Vector-Instructions die z.B. 4 float + 2 double innerhalb eines Vektorregisters verwenden. Ist aber auch nicht nötig. Die Elemente des Vektors stehen ja immer für die selbe Loop-Variable, nur für unterschiedliche Durchläufe.

    Die Frage ist also bloss ob es Vektor-Befehle gibt, mit denen man z.B. aus einem 8x float Vektor zwei 4x double Vektoren machen kann -- damit man eben nach einer float Berechnung mit double weiterrechnen kann. Und die gibt es soweit ich weiss. Ist halt nur die Frage wie effizient der Code der dabei rauskommt dann ist.


Log in to reply