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
}