Effektive Implementierung von Bit Spreading

[antisteo]

Hallo liebes Forum,

hat man 2D-Koordinaten, aber nur einen 1-dimensionalen RAM, gibt es ein Adressierungsschema, um trotz mehrdimensionaler Koordinaten eine Cache-Lokalität bei eindimensionaler Adressierung zu erreichen.

Um das Problem noch mal zu verdeutlichen: Zweidimensionale Datenstrukturen wie z.B. Bilder kann man entweder in Row-Order oder in Col-Order ablegen. Es gibt aber noch eine dritte Adressierungsart, welche nach einem Z-Schema adressiert, d.h.:

Code: Alles auswählen

(0)--------(1)
         /
        /
       /
      /
     /
    /
(2)--------(3)

Dieses Adressierungsschema wird dann fraktal wiederholt, d.h. ein 2x2-er-Block wird von 0..3 nach Z-Schema adressiert, bei einem 4x4er-Block wird von 0..15 adressiert, wobei die höherwertigen X/Y-Koordinaten in den höherwertigen 4-fachen der 1D-Koordinate kodiert sind.

Wenn man das auf Bitebene betrachtet, wird die X/Y-Koordinate "aufgespreizt", also aus den X-Y-Koordinaten:

Code: Alles auswählen

X = 0000
Y = 1111

wird folgende Speicheradresse:

Code: Alles auswählen

01010101

Jetzt die Frage: Haben moderne CPUs eine Anweisung, mit der diese Bitspreizung in 1 Takt gerechnet werden kann? Und wenn nicht - gibt es eine effektive Implementierung, die bei 32-Bit-Koordinaten weniger als 64 Anweisungen braucht?

[Schrompf]

Die Methode heißt Z-Ordnung oder Morton Code, siehe https://de.wikipedia.org/wiki/Z-Kurve. Vielleicht findest Du mit dem Namen was bei BitHacks. Die einzige mir bekannte Verbesserung gegenüber Deiner Bruteforce-Andeutung wäre ne Potenz-Kaskade nach dem Muster:

Code: Alles auswählen

0000 0000 abcd efgh  // <<4
0000 abcd 0000 efgh  // <<2
00ab 00cd 00ef 00gh // <<1
0a0b 0c0d 0e0f 0g0h 

[antisteo]

Also ich habe auf Stackoverflow schon folgende Lösungsvorschläge gefunden:
- Magisches Bit-Geschubse mit 4 Multiplikationen und 4 ANDs (aber gerade Multiplikationen sind teuer!)
- Eine Schleifen-Implementierung (Worst case?? Oder sollte man GENAU DAS dem Compiler geben, damit er in Zukunft mal eine passende ASM-Operation einfügen kann)
- Implementierung per Lookup-Table

[Schrompf]

Multiplikationen sind nicht nennenswert teurer als Additionen. Heutzutage. Lookup-Table kriegste mit Bitshift in ner 64bit-Konstante für bis zu drei Bits mit reinem Shift hin, 4Bits mit nem SSE-Register. Schleife würd ich nicht machen, dass ist ne Wette auf ne ferne Zukunft, in der Du dann trotzdem zumindest nochmal neu bauen musst. Du bist dann also eh schon in der Gegend. Wieviele Bits kriegst Du denn auseinander geschubst mit den 4 Mults? Der Trick klingt gut.

[Krishty]

Ah, hatte das vorgestern erst gesucht.

Falls deine CPUs das Bit Manipulation Instruction Set zur Verfügung haben, geht es in zwei Takten: https://gist.github.com/daniel-j-h/69736fb5ec147d4212c5

[Schrompf]

Oh hübsch, gibt doch ne Intrinsic dafür! Cool, damit lässt sich einiger Kram anstellen. Wikipedia zeichnet ein etwas komplexes Bild von der Prozessorunterstützung, aber wenn ich das richtig verstanden habe, werden die BMI2-Instructions bei Intel seit 2013 und bei AMD seit 2015 unterstützt, sind bei AMD aber erst mit Zen3 (2020) wirklich in Hardware implementiert. Bis dahin wird die Latenz mit 18 anstatt 3 Cycles angegeben, Du kriegst also ~6 Dependent Integer Operations in der Zeit eines pdep unter. Das ist nicht viel, aber reicht, um 8 Bits aufzuspreizen.

[edit] Die Multiply-Instructions aus dem Instruction Table haben ne Latenz von 3 bis 5 Cycles und nen Throughput von 2 per Cycle. Das ist doch bissl langsamer als ne Addition, aber echt nicht viel. Divisionen! Jo. Die sind gesäßgemütlich.

[Lord Delvin]

Als wir noch Raytracer gebaut haben, haben wir uns so Sachen auch mal angeschaut. Ich meine mich dunkel zu erinnern, dass wir irgendeinen H-förmiges Fraktal am Ende hatten; das hat's aber auch nicht so sehr gebracht, dass sich der Aufwand gelohnt hätte. Am Ende des Tages muss man an einem Punkt sein, wo man wirklich dadurch blockiert ist und nicht durch HyperThreading faktisch doch auf Vollast läuft o.ä. Wenn man an der Stelle Single Threaded oder sonst irgendwie sicher auf dem kritischen Pfad ist, ist es natürlich was anderes.

[Krishty]

Als wir noch Raytracer gebaut haben, haben wir uns so Sachen auch mal angeschaut. Ich meine mich dunkel zu erinnern, dass wir irgendeinen H-förmiges Fraktal am Ende hatten; das hat's aber auch nicht so sehr gebracht, dass sich der Aufwand gelohnt hätte.

Du meinst wahrscheinlich die Hilbert-Kurve. Die hat noch bessere Lokalität als eine Z-Kurve, ist aber auch aufwändiger zu berechnen und deshalb selten praktikabel.

Die Lokalitätsvorteile von Z-Kurven kann ich persönlich bezeugen, und ebenfalls dein Grafiktreiber – denn alle Grafikkarten legen ihre Texturen intern so ab.

[Lord Delvin]

Spannend, was gelernt :)

[antisteo]

Also ich habe die pdep-Instruktion noch gefunden (Parallel Bits Deposit)

siehe auch https://en.wikipedia.org/wiki/X86_Bit_m ... uction_set

Ansonsten habe ich mal ne hübsche log(N)-Stufen-Hilfsfunktion gebaut (in dem Fall habe ich die unteren Ebenen in 2-Bit-Gruppen gelassen)

Code: Alles auswählen

fn bit_spread_2(a: u64) -> u64 { // spread 32 bits in two-groups
        // 00004321 -> 00430021 -> 04030201
        let b = ((a & 0b0000000000000000000000000000000011111111111111110000000000000000) << 16) | (a & 0b0000000000000000000000000000000000000000000000001111111111111111);
        let c = ((b & 0b0000000000000000111111110000000011111111000000001111111100000000) <<  8) | (b & 0b0000000000000000000000001111111100000000111111110000000011111111);
        let d = ((c & 0b0000000011110000111100001111000011110000111100001111000011110000) <<  4) | (c & 0b0000000000001111000011110000111100001111000011110000111100001111);
        let e = ((d & 0b0000110011001100110011001100110011001100110011001100110011001100) <<  2) | (d & 0b0000001100110011001100110011001100110011001100110011001100110011);
        return e
}

[Spiele Programmierer]

Ich glaube, hier kann ich noch was beitragen, auch wenn das Thema schon bisschen älter ist!

Man kann "Bit Spreading" auch sehr effektiv mit übertragsloser Multiplikation umsetzen, in dem man eine Zahl so mit sich selbst multipliziert. Z.B. a=0b'wzyx, dann ist CLMUL(a, a) = BITSPREAD(a) = 0b'0w0z'0y0x.

Diese übertragslose Multiplikation gibt es sowohl bei x86 in Form von CLMUL, bei ARM und wird nun vorraussichtlich sogar bei C++ standardisiert.

Dieser Trick hat ein paar Vorteile gegenüber dem Vorschlag von Krishty...

• Gibt es schon seit 2010. Ich denke, man kann es heutzutage quasi voraussetzen.
• Er ist auch bei AMD effizient.
• Er ist vektorisiert, man kann also z.B. x und y Koordinate gleichzeitig beackern.

Warum das funktioniert? Man kann es im Prinzip einfach auszurechnen, aber grob gesagt ist es so, dass bei der Multiplikation alle "gemischten Terme von Ziffer an verschiedenen Stelle n und m doppelt auftreten, weil sie durch Vertauschung von n und m noch einen zweiten Beitrag machen (ähnlich wie bei (a+b)²=a²+2ab+b², wo der gemischte Term auch mal 2 ist). Alles was doppelt vorkommt ist aber wieder egal beim Modulo-2 Bit-Rechnen. Deswegen werden so zusagen nur die Ziffern jeweils mit sich selbst multipliziert und wandern dabei von Stelle n zu 2n.

Ich liebe diesen Trick. Wir machen das in unserem Spiel seit einer Weile so um eine Gitter-Datenstruktur in x/y-Richtung mehr oder weniger symmetrisch auszulegen.

[Krishty]

Das ist wahnsinnig interessant. Mir war bewusst, dass eine Lösung irgendwas mit Multiplikation zu tun haben muss – ich benutze Multiplikation ja auch gern, um Zahlen zu duplizieren (0xF3 * 0x01010101 == 0xF3F3F3F3), aber ich habe immer gerätselt, wie ich die Nullen “dazwischen” kriegen kann. Carry-less Multiplikation ist super; wieder was gelernt.

[Schrompf]

ich verstehe nicht, was das macht. Aber ich nehm's mal auf in die Trickkiste

[Spiele Programmierer]

Hm, eigentlich ist es nicht komplex.

Du gehst so vor wie der "normalen" schriftlichen Multiplikation aber anstelle von normaler Addition in der Breite des Integers nimmst du halt XORs, also effektiv eine Addition für jedes Bit einzeln. Bei Wikipedia ist es erklärt und es gibt auch ein Beispiel: https://en.wikipedia.org/wiki/Carry-les ... or#Example. Mathematiker lieben es dann auch, die Bits als Koeffizienten eines Polynoms zu schreiben, aber wenn dir das nicht gefällt, kannst du es vergessen.

Effektiv fällt beim CLMUL halt weg, dass 0b1 + 0b1 = 0b10, also eben der Übertrag oder eben wenn eine Ziffer überläuft (2 Einsen), es dann in die nächst höhere Stelle überspringt. Dadurch betrachtet man den Integer als echt als Kette von Bits wie bei den bitweisen Operatoren. Wenn man so will, ist die Multiplikation dann eine Faltung, wenn dir das was sagt.

Bei Wikipedia gibt es auch diese schöne Grafik...


Es wurden einfach alle Bits der blauen und roten Zahlen auf den Seiten einzeln miteinander multipliziert. Danach werden die ihrer Stelle nach zusammengezält. Also multipliziert man Bit an Stelle 2 mit einem Bit an Stelle 5, gibt einen Beitrag zu Bit an Stelle 2+5=7. Im Unterschied zur normalen Multiplikation NUR, dass eben wirklich jedes Bit einzeln bleibt und zwei 1en in einer aufsteigenden Diagonale sich komplett wegkürzen und nicht in die nächst höhere Stelle wandern. Dadurch sollte dann auch anschaulich recht schnell klar werden, was ich vorher meinte. Wenn beide Multiplikanten die selben sind, ist das Muster symmetrisch entlang der absteigenden Diagonalen (von links oben bis rechts unten). Nur die Einsen in dieser Diagonalen kommen nicht automatisch doppelt vor und die Diagonaleinträge wirken sich nur auf jedes zweite Bit aus.

Abgesehen von diesem Trick und Kryptografie/Checksummen/Zufallszahlen-Zeug ist mir bis jetzt auch noch kein Anwendungsfall begegnet aber kann ja noch kommen. :)

[Schrompf]

Ah, Danke!