speicherzugriff optimieren

ich habe hier ein Programm zu optimieren.

Dabei geht ein riesiger Teil der Zeit für
das Auslesen der Spalten eines Bildes drauf,
also in folgendem Abschnitt:

for (size_t n=0;n<N;n++)
{	
    for (size_t t=0;t<M;t++)
    {
        //hier ganz viele cache read misses
        tmp2[t].re = out[(t*M)+n].re;
        tmp2[t].im = out[(t*M)+n].im;
    }

    FFT(tmp2,tmp,M,sign);

    for (size_t t=0;t<M;t++)
    {
        //hier nochmal dasselbe
        out[(t*M)+n].re = tmp[t].re/root[0];
        out[(t*M)+n].im = tmp[t].im/root[0];	
    }
}

Hat jemand eine Idee wie ich die cache misses weg bekommen könnte?
oder andersweitig die Speicherzugriffe optimieren könnte?

Ringding

Durch Blocking. Aber musst du das denn wirklich unbedingt transponieren?

Was macht das Ding, Matrix transponieren? Dazu musst du nicht die Elemente umher kopieren. Du kannst auf einfach in die Matrix einen Zustand einbauen, der angibt, ob die Zeilen Zeilen oder Spalten sind.
Mit getter-Methoden kannst du das dann sehr transparent nach außen hin darstellen.

Optimizer schrieb:

Was macht das Ding, Matrix transponieren? Dazu musst du nicht die Elemente umher kopieren. Du kannst auf einfach in die Matrix einen Zustand einbauen, der angibt, ob die Zeilen Zeilen oder Spalten sind.
Mit getter-Methoden kannst du das dann sehr transparent nach außen hin darstellen.

hmm das bringt mir nichts weil ich zehn zeilen vorher genau dieselbe operation auf den zeilen durchführe.
also muss ich praktisch einmal transponieren.

@ringding
was verstehst du unter blocking

Ringding

Z.B. http://computing.sinica.edu.tw/service/course/lecture_note/mpi_lecture/html/ch3/node45.html http://computing.sinica.edu.tw/service/course/lecture_note/mpi_lecture/html/ch3/node47.html

rüdiger

SIMD, restrict, memcpy

cache schrieb:

ich habe hier ein Programm zu optimieren.

Dabei geht ein riesiger Teil der Zeit für
das Auslesen der Spalten eines Bildes drauf,
also in folgendem Abschnitt:
for (size_t n=0;n<N;n++)
{	
    for (size_t t=0;t<M;t++)
    {
        //hier ganz viele cache read misses
        tmp2[t].re = out[(t*M)+n].re;
[...]
Hat jemand eine Idee wie ich die cache misses weg bekommen könnte?
oder andersweitig die Speicherzugriffe optimieren könnte?

Du musst dir die beiden Schleifen nur mal etwas genauer angucken, dann siehst du, warum es so viele Cache misses gibt: Du liest das Bild nicht in Speicherrichtung ein. Guck mal da:

(t*M)+n

Das ist wohl der Index des jeweiligen Pixels. Die innere for-Schleife erhöht nun t und nicht n. t schickt dich aber vom Index nicht um eine Stelle weiter, sondern um M Stellen. Wenn du das verbessern willst, wäre es nicht schlecht, die innere und äußere Schleife zu vertauschen. ...sollte doch eigentlich möglich sein, oder?

BTW: In der Bildverarbeitung wird man normalerweise komisch angeguckt, wenn man etwas anderes als x und y für die Position des Pixels nimmt. "t" und "n" vermindern da doch deutlich die Lesbarkeit.

hmmm...

/me nimmt sein Posting da gerade zurück.

Gregor@Home schrieb:

hmmm...

/me nimmt sein Posting da gerade zurück.

^^