Was ist falsch an meiner Laufzeitberechnung?

  • Ich verwende eine iterative Methode der linearen Algebra (PCG) zum Lösen von Ax = b, die Dimension der Matrix ist 10000x10000.

    Also, ich führte zwei vorläufige Analysen durch:

    • Speicheranalyse

    Die Größe der Matrix dominiert den gesamten erforderlichen Speicher. Das sind ungefähr 1E4 x 1E4 = 1E8 Elemente mit doppelter Genauigkeit, die ungefähr 0,8 GB an Daten beträgt. Die Anzahl der für die Konvergenz erforderlichen Iterationen betrug 450. Da dies nicht in den Cache passt, gehe ich von keinen Cache-Vorteilen aus. Dies würde 450 x 0,8 = 360 GB Datenübertragung bedeuten. Bei einer Speicherbandbreite von 10 GB / s sind das etwa 36 Sekunden für Speicherübertragungen.

    • Flop-Analyse

    Ich habe berechnet, dass ich pro Iteration einen Matrixvektor (dominante Operation) für 450 Iterationen ausführen werde. Dies sind cN^2 Operationen / Iterationen x 450 Iterationen = 450c N^2 Operationen mit einem 2,13 GHz Prozessor (sichergestellt, dass nur ein einzelner Prozessor verwendet werden kann). Das ist 21.12c für N = 10000.

    Um c zu finden, habe ich MatVecs für alle Größen von 1 bis 19000 durchgeführt und die Grafik für Nr. von Operationen vs (Dimension) ^ 2 (Operationen = Steigung x Dim ^ 2) wobei No. of Operations = Time x 2.13 GHz. Ich habe die Steigung dieses (linearen) Graphen als c verwendet. Was sich als 50 herausstellte.

    Somit ist die Gesamtzeit = 21.12c = 1000 Sekunden.

    Nehmen wir also beide an Speicherübertragung und -operationen finden gleichzeitig statt, theoretisch sollte es 1000 Sekunden dauern.

    In Wirklichkeit dauerte der Code jedoch maximal 120 Sekunden. Was habe ich falsch gemacht? Meine Berechnung ist ziemlich falsch.

    18 April 2012
    guitsaru
3 answers
  • Ich kann kaum glauben, dass c 50 ist. Theoretisch benötigt ein Matrix-Vektor-Produkt 2N ^ 2-Flops, wenn die Matrix N-by-N ist, was c = 2 ergibt Indizierungsoperationen, Vektorisierung und Implementierungsqualität beeinflussen dies, aber c = 50 scheint sehr hoch zu sein.

    Wenn Sie außerdem annehmen, dass PCG = vorbedingter konjugierter Gradient ist, welchen Vorkonditionierer verwenden Sie? Sind Sie sicher, dass die Kosten für die Vorkonditionierung vernachlässigt werden können?

    19 April 2012
    Jitse Niesen
  • Wie Jitse ausführte, liegt der Fehler eindeutig in Ihrer Schätzung für die Kosten von $ c $. Wie Sie wahrscheinlich bemerkt haben, ist der Graph für die Berechnung fast aller Berechnungen als Funktion der Array-Größe nicht besonders linear, es gibt viel Jitter aufgrund von seltsamen Cache-Effekten und es gibt mehrere klare Bereiche, in denen L1, L3 und der Hauptspeicher dominieren. Mir ist aufgefallen, dass Mystical Ihnen dies auch in Ihrer Chat-Diskussion

    Wenn Sie eine gute Schätzung der Kosten pro Mat-Vec aus der direkten Messung haben, berücksichtigt der $ c $, den Sie berechnen, zusätzlich den Speicher und die Flop / s.

    Das Gesamtbild für diese Art von Berechnung ist unordentlich. Es scheint, als würden Sie versuchen, in sehr feine Leistungsanalyse-Details zu gelangen, ohne ein gutes Verständnis der Computerarchitektur und der Pipeline-Leistung zu haben. Haben Sie Hennessys und Pattersons Computerarchitektur: ein quantitativer Ansatz gelesen?

    23 April 2012
    29 revs, 25 users 37%Shaik Raffi
  • Muss hier sein: Anzahl der Operationen = Zeit x 2,13 GHz, Operationen in einem Prozess können auf diese Weise nicht berechnet werden. Es gibt eine Reihe von Variablen, die dies beeinflussen werden, insbesondere die Art der verwendeten CPU, die Wärme und der Parellismus.

    "Die Leistung oder Geschwindigkeit eines Prozessors hängt von der Taktrate ab ( allgemein in Vielfachen von Hertz) und den Anweisungen pro Takt (IPC) angegeben, die zusammen die Faktoren für die Anweisungen pro Sekunde (IPS) sind, die die CPU ausführen kann. "

    Die Die einzige Variable, die Sie hier haben, ist die Taktrate.

    Lesen Sie dies hier: http://en.wikipedia.org/wiki/Central_processing_unit#Design_and_implementation

    18 April 2012