3. Optimierung einer Matrizenmultiplikation

Optimierung einer Matrizenmultiplikation

  • P

    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

    1 2 0 0
2 3 0 4
0 0 5 6
0 4 6 7

    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
    0
  • P

    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.

    0
  • M

    hoi

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

    Meep Meep

    0
  • C

    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.

    0
  • T

    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ß... 👍

    0
  • P

    Vielen Dank.

    0
  • ?

    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) {
    0
  • C

    es hätte

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

    heißen müssen.

    0
  • P

    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.

    0
  • R

    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.

    0
Anmelden zum Antworten