C++ Community

Ponto

Ich weiss nicht ob hier SIMD hilft. Die Instanzen sind sehr groß und damit ist der Zugriff auf den Speicher recht nichtlinear. Vor allem durch den indirekten Zugriff (vector[columns[i]]). Die Laufzeit geht also durch die vielen L2-Misses verloren.

rapso

void mv_product() {

   const int n4  =  n&~3;
   int zeile = 0;
   for(;zeile<n8;zeile+=4)
   {
      result[zeile]   = matrix[zeile]   * vector[zeile];
      result[zeile+1] = matrix[zeile+1] * vector[zeile+1];
      result[zeile+2] = matrix[zeile+2] * vector[zeile+2];
      result[zeile+3] = matrix[zeile+3] * vector[zeile+3];
   }
   for(;zeile<n;zeile++)
      result[zeile] = matrix[zeile] * vector[zeile];

   for (int zeile = 0; zeile < n; ++zeile)
   {
      const int i = columns[zeile];
      result[zeile]      += matrix[i] * vector[columns[i]];
      result[columns[i]] += matrix[i] * vector[zeile];
   }
}

Ponto

Ein Loopunrolling des ersten Teils bringt ungefähr 2% Verbesserung, da dort nicht so viel gesprungen wird.

rüdiger

Die ersten beiden Schleifen (von rapsos-code) sollten sich aber mit SIMD formulieren lassen. Wobei der indirekte Zugriff in der 3. Schleife wohl wirklich ein Problem darstellt.

Schau dir vielleicht mal an, was der ICC für Code generiert, da der wohl ziemlich gut Schleifen in SIMD umwandeln kann und teilweise wohl für eine Schleife mehrere Optimierungen baut.

Ponto

Werde ich mal machen, auch wenn die ersten beiden Schleifen nur 15% der Gesamtlaufzeit der Funktion ausmachen.

camper

wieso eigentlich

double columns[SIZE+1];

? müssten das nicht sinnvollerweise integer sein? überhaupt sieht das ganze irgendwie nicht richtig aus. kannst du die erklärung noch einmal so posten, dass sie nicht offensichtlich falsch ist?

In den ersten n Einträgen von Matrix ist die Hauptdiagonale eingetragen. Es folgt eine unbenutzte Stelle und dann werden die restlichen Einträge Zeile für Zeile eingetragen. Die Einträge für Zeile i befinden sich in den Positionen columns[i] bis columns[i]-1 und der Eintrag an Stelle j hat die Spalte columns[j].

vielleicht bin nur ich verwirrt, aber was ist eintrag und was ist stelle? vielleicht das ganze mal an einem beispiel (etwa 4*4) zeigen.

rapso

Ponto schrieb:

Ein Loopunrolling des ersten Teils bringt ungefähr 2% Verbesserung, da dort nicht so viel gesprungen wird.

und was brachte der antere teil?

btw. ein guter compiler duerfte das vektorisieren.

wenn du wirklich optimierungen bekommen moechtest, muesstest du ne testapp(sammt source) und test-daten zur verfuegung stellen, so ist das nur ein schiessen ins blaue. wir wissen ja nichtmal welcher compilier...

Ponto

camper schrieb:

wieso eigentlich
double columns[SIZE+1];
? müssten das nicht sinnvollerweise integer sein?

Du hast Recht, es muss int sein.

Die folgende 4x4 Matrix

würde so abgespeichert werden:

Index:    0 1 2 3 4 5 6 7

matrix:   1 3 5 7 * 2 4 6
columns:  5 6 7 7 7 1 3 3

Ponto

rapso schrieb:

Ponto schrieb:

Ein Loopunrolling des ersten Teils bringt ungefähr 2% Verbesserung, da dort nicht so viel gesprungen wird.

und was brachte der antere teil?

btw. ein guter compiler duerfte das vektorisieren.

wenn du wirklich optimierungen bekommen moechtest, muesstest du ne testapp(sammt source) und test-daten zur verfuegung stellen, so ist das nur ein schiessen ins blaue. wir wissen ja nichtmal welcher compilier...

Der untere Teil scheint mir nicht korrekt zu sein. Der nimmt ja für jede Zeile nur einen Eintrag.

Ein Testprogramm könnte ich machen, aber vernünftige Matrizen sind halt ein paar Gigabyte groß. Und es nützt nicht für Randominstanzen zu optimieren.

Ich dachte eher, jemand hat eine Idee wie man die Daten besser organisieren kann, so dass es schneller wird.

Meep Meep

hoi

vielleicht bringt es ja was wenn du das erstellen von temporären objekten vermeidest bzw. wenigstens etwas reduzierst.

Meep Meep

camper

Ponto schrieb:

Der untere Teil scheint mir nicht korrekt zu sein. Der nimmt ja für jede Zeile nur einen Eintrag.

das geht auf einen schreibfehler in deinem code zurück.

Ein Testprogramm könnte ich machen, aber vernünftige Matrizen sind halt ein paar Gigabyte groß. Und es nützt nicht für Randominstanzen zu optimieren.

Ich dachte eher, jemand hat eine Idee wie man die Daten besser organisieren kann, so dass es schneller wird.

eine handvoll ideen existieren schon, es kommt aber ein wenig darauf an, wozu das ganze am ende gut ist. auf was für einer art system soll das ganze denn laufen? wenn die matrix selbst mehrere GB groß ist, handelt es sich sicher nicht um ein gewöhnliches PC-system. hat die matrix noch irgendwelche andere eigenschaften, etwa das werte nahe der hauptdiagonale dichter liegen? wie dicht ist die matrix gefüllt (Size:N^2)? soll diese operation auf mehrere vektoren angewandt werden? die optimierung einer einzelnen operation stößt schnell an grenzen, es könnte aber möglich sein, gleich mehrere vektoren zu verarbeiten, ohne das der zeitaufwand proportional steigt.

TheTester

Den Code zur eigentlichen Berechnung wirst du im Endeffekt nicht viel beschleunigen können. Deshalb müssen andere Methoden ran. Ich weiß nicht ob du das alles selbst implementieren oder nicht lieber ein schon vorhandenes Framework verwenden möchtest.

Hier ein paar Hinweise was du dir anschauen kannst.

Stichworte:

Matrix Reordering
Register Blocking
Software Pipelining
Ausnutzung der Symmetrie

Reverse Cuthill McKee Ordering
http://www.csit.fsu.edu/~burkardt/f_src/rcm/rcm.html

Dann noch die üblichen Verdächtigen, wie minimieren der Hauptspeicherzugriffe, optimieren des Cachings, Loop Unrolling, Prefetching Streaming wobei ich mich aber zuerst auf das obere konzentrieren würde.

Literatur:

S. Röllin R. Geus. Towards a fast parallel sparse matrix-vector multiplication.
In E. H. D’Hollander, J. R. Joubert, F. J. Peters, and H. Sips,
editors, Parallel Computing: Fundamentals & Applications, Proceedings
of the International Conference ParCo’99, 17-20 August 1999, Delft,
The Netherlands, pages 308–315. Imperial College Press, 2000.

Eun-Jin Im, Katherine A. Yelick, and Richard Vuduc. SPARSITY:
Framework for optimizing sparse matrix-vector multiply. International
Journal of High Performance Computing Applications, 18(1):135–158,
February 2004.

http://software.sandia.gov/trilinos/

Trilinos war vor 1-2 Jahren recht unoptimiert von den implementierten Algorithmen her, ich denke aber mal sie haben mittlerweile die "Standardsachen" wie Reordering oder Blocking mit eingebaut.

Bei Google sollte was brauchbares kommen wenn du "Matrix-Vektor-Multiplikation fur sparse Matrizen" als Suchwworte verwendest

Na dann, viel Spaß...

Ponto

Vielen Dank.

rapso@work

Ponto schrieb:

rapso schrieb:

Ponto schrieb:

Ein Loopunrolling des ersten Teils bringt ungefähr 2% Verbesserung, da dort nicht so viel gesprungen wird.

und was brachte der antere teil?

btw. ein guter compiler duerfte das vektorisieren.

wenn du wirklich optimierungen bekommen moechtest, muesstest du ne testapp(sammt source) und test-daten zur verfuegung stellen, so ist das nur ein schiessen ins blaue. wir wissen ja nichtmal welcher compilier...

Der untere Teil scheint mir nicht korrekt zu sein. Der nimmt ja für jede Zeile nur einen Eintrag.

wundert mich

for (int i = columns[zeile]; i < columns[zeile]+1; ++i) {

ist eine schleife, die immer nur einen durchlauf hat, oder uebersehe ich etwas? quasi

for (int i = z; i < z+1; ++i) {

camper

es hätte

for (int i = columns[zeile]; i < columns[zeile+1]; ++i) {

heißen müssen.

Ponto

camper schrieb:

es hätte

for (int i = columns[zeile]; i < columns[zeile+1]; ++i) {

heißen müssen.

Ja. Habe den Fehler hier die ganze Zeit übersehen.

rapso

http://www.forum-3dcenter.org/vbulletin/showthread.php?t=226285 da hatte ich mal fuer jemandes dipl. arbeit sowas geschrieben, was riesige matrizen/vektoren multiplizierte, die beste optimierung war das ganze sehr cachefreundlich anzulegen.

aber wie gesagt, ohne test-app laesst sich sowas nur sehr schwer optimieren.

Optimierung einer Matrizenmultiplikation