Effektive Implementierung von Bit Spreading

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
antisteo
Establishment
Beiträge: 854
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Effektive Implementierung von Bit Spreading

Beitrag von 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?
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
Benutzeravatar
Schrompf
Moderator
Beiträge: 4876
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Effektive Implementierung von Bit Spreading

Beitrag von 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 
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
antisteo
Establishment
Beiträge: 854
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: Effektive Implementierung von Bit Spreading

Beitrag von 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
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
Benutzeravatar
Schrompf
Moderator
Beiträge: 4876
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Effektive Implementierung von Bit Spreading

Beitrag von 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.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8267
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Effektive Implementierung von Bit Spreading

Beitrag von 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
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4876
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Effektive Implementierung von Bit Spreading

Beitrag von 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.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 583
Registriert: 05.07.2003, 11:17

Re: Effektive Implementierung von Bit Spreading

Beitrag von 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.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Benutzeravatar
Krishty
Establishment
Beiträge: 8267
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Effektive Implementierung von Bit Spreading

Beitrag von Krishty »

Lord Delvin hat geschrieben: 05.12.2023, 16:56 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.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 583
Registriert: 05.07.2003, 11:17

Re: Effektive Implementierung von Bit Spreading

Beitrag von Lord Delvin »

Spannend, was gelernt :)
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
antisteo
Establishment
Beiträge: 854
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: Effektive Implementierung von Bit Spreading

Beitrag von 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
}

http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
Antworten