SIMD in Code mit kleinen Branches

Sorry, den Code hab ich aus dem Kopf produziert. value ist halt einfach array[i].

knivil schrieb:

bool negative = value < 0;
if(negative) value *= -1;
Die Funktion nennt sich abs. Kein Grund fuer if .

Der Vergleich wird oben schon benötigt. Aus der positiven Zahl soll nach der Rechnung ja wieder eine negative gemacht werden, falls sie im Original negativ war. Das muss ich mir irgendwie zwischenspeichern (mit "negative").

knivil schrieb:

if(value > some_value)
value *= 23;
else
value -= 5;
Verzweigung kann nicht mit SSE umgangen werden, da sich nicht nur die Werte sondern auch die Operation unterscheidet. Vielleicht kann man beide Ausfuehren und die Teilergebnisse abhaengig von some_value mergen.

Schade.

knivil schrieb:

value *= constants[mod]
Wenn der Inhalt von constants in ein oder zwei Register passt, dann ja.

Selbst im konkreten Beispiel, an dem ich gerade arbeite, passen alle Konstanten in ein SIMD register. Kannst du vielleicht anhand des Beispiels zeigen, wie der SIMD benutzende Code aussehen würde?

Eine zusätzliche Frage: Wie siehts mit Branches aus, die eine optionale Operation darstellen? Z.B.:

int value = array[i];
if(value > 25)
   value *= 15;

value += 1;
array[i] = value;

knivil

Gehe doch bitte erstmal auf meine 3 Fragen ein ...Nein, ich gebe keinen Code an, da ich ihn vorher testen muss. Das ist mir zu viel Aufwand fuer mal eben schnell.

Achso, die Fragen hab ich aus Versehen übersehen. Ist ein i7-X980. Ob der AVX kann weiß ich nicht, aber SSE2/3/4 sollte drin sein.

rapso

der erste schritt ist, dass man branching eliminiert z.b.

int *array = //großer array mit vielen daten
int constants[4] = {42,65,21,22};

for(int i=0;i<array_size;++i)
{
    int value = array[i];
    int negative = value>>31;
    value ^= negative;

    const int Mask = (some_value-value)>>31;
    value =      ((value * 23)&Mask)|((value-5)&~Mask);
    int mod = value % 4;
    value *= constants[mod];

    value ^= negative;
}

Operationen mit Array-Indizierung (wie value *= constants[mod]).

aktuell kannst du da nicht viel machen ausser werte zu extrahieren aus den SIMD registern, damit indizieren etc. in der naechsten generation von CPUs von intel gibt es dann ein scatter/gather, was 4 bzw 8 unterschiedliche offsets/indices erlaubt. allerings klingt %4 als ob du immer SIMD4 schreiben koenntest.

Kann man solche bedingten Operationen trotzdem irgendwie mit SIMD optimieren?

ja, du musst die bedingungen wegbekommen wie ich oben angedeutet habe und dann kannst du das mit SIMD problemlos implementieren. auf x86 ist der code oben vermutlich nicht schneller als was du schriebst, aber auf konsolen und mobilen cpus sollte es schnellre laufen, da es keine branch misses gibt und der compiler zudem instruktionen besser organisieren kann, was compiler oft ueber branches hinweg nicht machen.

rapso schrieb:

der erste schritt ist, dass man branching eliminiert z.b.
int *array = //großer array mit vielen daten
int constants[4] = {42,65,21,22};

for(int i=0;i<array_size;++i)
{
    int value = array[i];
    int negative = value>>31;
    value ^= negative;

    const int Mask = (some_value-value)>>31;
    value =      ((value * 23)&Mask)|((value-5)&~Mask);
    int mod = value % 4;
    value *= constants[mod];

    value ^= negative;
}
Operationen mit Array-Indizierung (wie value *= constants[mod]).

aktuell kannst du da nicht viel machen ausser werte zu extrahieren aus den SIMD registern, damit indizieren etc. in der naechsten generation von CPUs von intel gibt es dann ein scatter/gather, was 4 bzw 8 unterschiedliche offsets/indices erlaubt. allerings klingt %4 als ob du immer SIMD4 schreiben koenntest.

Kann man solche bedingten Operationen trotzdem irgendwie mit SIMD optimieren?

ja, du musst die bedingungen wegbekommen wie ich oben angedeutet habe und dann kannst du das mit SIMD problemlos implementieren. auf x86 ist der code oben vermutlich nicht schneller als was du schriebst, aber auf konsolen und mobilen cpus sollte es schnellre laufen, da es keine branch misses gibt und der compiler zudem instruktionen besser organisieren kann, was compiler oft ueber branches hinweg nicht machen.

Erstmal danke. Aber was meinst du mit

rapso schrieb:

allerings klingt %4 als ob du immer SIMD4 schreiben koenntest.

rapso

simdler schrieb:

rapso schrieb:

allerings klingt %4 als ob du immer SIMD4 schreiben koenntest.

SIMD arbeitet oft auf 4 ints (Neon auch auf 2 und AVX auf 8,16...), wenn du %4 rechnest, dann indizierst du quasi immer auf einem SIMD register, was also mit anderen modulo werten nicht ginge aber mit %4 geht ist dass du shuffling oder select benutzt um in das SIMD register zu indizieren. das waere also ausnahmsweise vectorisierbar.

Hallo, wollte nur eine kleine Rückmeldung geben, falls irgendwer von euch in der Zukunft mal in eine ähnliche Situation kommt.

Ich hab den relevanten Code (das ist nicht der, den ich hier gepostet habe, aber er hat ähnliche kleine Branches und ein bisschen indirekte Addressierung) nun mit SIMD umgesetzt, und der Code läuft ca. 3 mal schneller. Da ich 4 Elemente gleichzeitig bearbeite, wäre vll. ein Faktor von 4 schöner, aber ich schätze mal dass das daher kommt, dass bitweise-selektieren mithilfe von Masken in mehr Operationen resultiert, die zwar von einer Superskalar-CPU in einem oder zwei Zyklen erledigt ist, aber in SIMD halt ein wenig länger braucht.

Also um noch hinzuzufügen: 3 mal schneller als der Originalcode mit Branches. Originalcode mit "umgebauten Branches so dass es sie nicht mehr gibt" hab ich noch nicht getestet (nicht dran gedacht). Sollte aber nicht schneller sein, CPU hat ja noch cmovs und dann instruction parallelism.

rapso

bei sovielen dependant instructions hilft es manchmal den loop per hand zu unrollen, 2x oder 4x, dadurch kann der compiler und die cpu unabhaengige instructiosn abarbeiten. (wenn du fuer 64bit compilierst, hast du zudem doppelt soviele register, das kann ordentlich performance bringen bei SSE code mit register pressure).

zudem ist gerade select sehr seriel

-vergleich

-and
-not

-or

falls du das noch nicht machst, verwende blendvps (instrinsic ist _mm_blendv_ps oder so), das sollte um einiges schneller sein. falls du auf vorzeichen vergleichst, sparst du dir damit sogar den vergleich, da blendvps nur das erste bit pro 32bit verwendet (ab SSE4.1 glaube ich).

3x klingt eigentlich gut, es liegt oft nicht an mehr sse instruktionen, denn die sind oft besser spezialisiert, zumeist liegt es am zugriff auf daten.