Mäanderförmige Array-Indizierung?

[Tom K. (ez81)]

Hallo zusammen,

vor einiger Zeit habe ich mal etwas über einen Algorithmus gefunden, der
die Elemente in einem 2D-Array nicht nach der üblichen Methode a(x,y) = 
data[x + y * xmax] zeilenweise im Speicher anordnet, sonder eher 
mäanderartig. Ziel war es, dass der Prozesor-Cache beim durchlaufen des 
Arrays in x- und y-Richtung halbwegs gleichmäßig zuschlagen kann.
Ich sitze gerade an einem Problem, wo das eventuell helfen könnte, kann 
mich aber an den Namen nicht erinnern und meine Erinnerung ist zu 
nebulös zum gezielten Suchen. Hat jemand einen Suchbegriff?

Grüße,
Tom.

PS: Ja, es wird getestet und bei wenig Performance-Gewinn verworfen, 
ausprobiert haben will ich es aber trotzdem.

[Robert L. (lrlr)]

>dass der Prozesor-Cache beim durchlaufen des
>Arrays in x- und y-Richtung halbwegs gleichmäßig zuschlagen kann.

dann vielleicht am einfachsten in "Blöcken" anlegen (also immer z.b. 
16x16)

die jeweilige Position sollte sich dann mit ein bisschen bit-schieben 
ermitteln lassen?

[Arc N. (arc)]

Tom K. schrieb:
> Hallo zusammen,
>
> vor einiger Zeit habe ich mal etwas über einen Algorithmus gefunden, der
> die Elemente in einem 2D-Array nicht nach der üblichen Methode a(x,y) =
> data[x + y * xmax] zeilenweise im Speicher anordnet, sonder eher
> mäanderartig. Ziel war es, dass der Prozesor-Cache beim durchlaufen des
> Arrays in x- und y-Richtung halbwegs gleichmäßig zuschlagen kann.
> Ich sitze gerade an einem Problem, wo das eventuell helfen könnte, kann
> mich aber an den Namen nicht erinnern und meine Erinnerung ist zu
> nebulös zum gezielten Suchen. Hat jemand einen Suchbegriff?

Blocked | nonlinear | recursive array layout

Mäanderartig könnte dann das Hilbert Layout gewesen sein
http://www.cs.duke.edu/~alvy/papers/matrix-tpds.pdf
https://engineering.purdue.edu/~mithuna/pubs/ics99.pdf

[Tom K. (ez81)]

Danke euch beiden! Hilbert und Morton waren die Namen.

[Johann L. (gjlayde)]

Tom K. schrieb:

> vor einiger Zeit habe ich mal etwas über einen Algorithmus gefunden, der
> die Elemente in einem 2D-Array nicht nach der üblichen Methode a(x,y) =
> data[x + y * xmax] zeilenweise im Speicher anordnet, sonder eher
> mäanderartig. Ziel war es, dass der Prozesor-Cache beim durchlaufen des
> Arrays in x- und y-Richtung halbwegs gleichmäßig zuschlagen kann.

Bevor du das von Hand machst: Compiler wie GCC versuchen, 
Maxrix-Operationen so umzusortieren, daß die Cache-Lokalität erhöht 
wird.

Um das zu erreichen, verwendet GCC zum Beispie CLooG, den "Chunky Loop 
Generator"

http://www.cloog.org/

Ziel ist wie gesagt, Matrix-Code zur Compilezeit so umzubauen, daß eine 
möglichst hohe Cache-Lokalität erreicht wird.

Vielleicht kann der Compiler die Optimierung ja schon von hause aus, und 
du musst garnix dazutun...

[./. (Gast)]

DSPs kennen für die FFT die bitreverse Adressierung.
Das dürfte auch recht mäanderförmig auf den Speicher zugreifen :-)

[Johann L. (gjlayde)]

Naja, Ziel der Übung ist ja nicht ein möglichst schlechte 
Cache-Ausnutzung, sondern eine möglichst gute Cache-Nutzung wenn man in 
(Neben-)Diagonalen durch die Matrix geht.

[Tom K. (ez81)]

bitreverse wäre allerdings als schlechteste Indizierung interessant, um 
den Effekt des Cachings zu vergleichen.

Ich will entlang von beliebig orientierten Geraden (Bresenham) und in 
Dreiecksflächen in die Matrix schreiben, deshalb wird der Compiler wohl 
leider nicht helfen können.

Wenn ich Zeit zum Probieren finde, werde ich die Ergebnisse hier posten.

[Robert L. (lrlr)]

nachdem es um eine PC geht
(und um irgendwas "grafik ähnliches")

und es aus irgend einem grund "schnell" gehen muss

wäre die GPU vermutlich besser geeignet..(immerhin ist die dazu da: 
Hardware unterstütztes zeichnen gibt es ja schon seit Turbo-pascal 
zeiten..)