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.
>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?
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
Danke euch beiden! Hilbert und Morton waren die Namen.
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
#2571328
DSPs kennen für die FFT die bitreverse Adressierung. Das dürfte auch recht mäanderförmig auf den Speicher zugreifen :-)
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.
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.
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..)