Vergleich der Iterationsmethoden: Anzahl der Iterationen vs. CPU-Zeit

Ich vergleiche zwei iterative Methoden zum Invertieren von zufälligen Quadratmatrizen. Da die Matrizen zufällig sind, benötigt jeder Testfall sowohl unterschiedliche Mengen an Iterationen als auch unterschiedliche abgelaufene Zeiten. Meine Frage ist, neben der mittleren CPU-Zeit, der Mittelwert der Iterationen, die von beiden Methoden verwendet werden. Nützliche Informationen zum Vergleichen der Methoden.

performance benchmarking srijan
quelle

Ich habe Ihre Frage umformuliert, um sie hoffentlich klarer zu machen. Bitte stellen Sie sicher, dass ich Ihre Bedeutung in keiner Weise geändert habe.

Godric Seer

@GodricSeer Deine Bearbeitung hat meine Frage verbessert. Vielen Dank

srijan

Antworten:

In der Regel haben beide Methoden des Leistungsvergleichs ihren Platz.

Der Vergleich der CPU-Zeit ist in gewisser Hinsicht die interessanteste Messgröße, da Sie am Ende des Tages wirklich interessiert sind, welche der Methoden schneller ist. (Stellen Sie jedoch sicher, dass die Abbruchkriterien vergleichbar sind; z. B. dass beide Methoden eine Annäherung mit der gleichen Genauigkeit ergeben). Der Nachteil ist, dass dies nur angibt, welche Methode (und vor allem welche Implementierung ) auf dem Computer, auf dem Sie die Tests durchgeführt haben, schneller ist. Es gibt keine Garantie dafür, dass eine andere Maschine mit unterschiedlicher Architektur oder Software den gleichen Gewinner auswählt.
Der Vergleich der Iterationszahlen ist dagegen maschinenunabhängig, kann jedoch irreführend sein, wenn die beiden Methoden sehr unterschiedliche Iterationen aufweisen. In diesem Fall ist die Methode mit weniger, aber teureren Iterationen möglicherweise nicht vorzuziehen (z. B. Newton- oder Gradientenmethoden zur Optimierung) wenn Sie nur eine sehr geringe Genauigkeit benötigen).

Also, ja, es ist sinnvoll, beide Zahlen [1] anzugeben, und ich habe es häufig in Veröffentlichungen gesehen. Es gibt auch eine dritte Option:

Vergleich der Anzahl der Elementaroperationen . Wenn beide Iterationen aus der gleichen Art von angemessen teurer Operation bestehen, aber eine andere Anzahl erfordern (möglicherweise nicht einmal die gleiche Anzahl in jeder Iteration), ist es sinnvoll, die Gesamtzahl dieser Operationen zu zählen. In Ihrem Fall wäre ein wahrscheinlicher Kandidat Matrix-Vektor- oder Matrix-Matrix-Multiplikationen.

[1] Präsentieren Sie Statistiken auf jeden Fall über mehrere Läufe. Wenn Sie Mittelwerte anzeigen, vergessen Sie nicht, auch Standardabweichungen anzugeben.

Christian Clason
quelle

Nehmen Sie nicht nur Mittel! Wenn Sie genügend Testpunkte mit zufälligen Eingaben haben, zeichnen Sie eine Verteilung.

Bill Barth

@BillBarth - guter Punkt, obwohl das nicht immer machbar ist; Die Angabe von Standardabweichungen zusammen mit dem Mittelwert sollte jedoch immer möglich sein. In der Tat klingt es nach einer hervorragenden Frage, welche Statistiken für die Berichterstattung über die Leistung vorgelegt werden sollen.

Christian Clason

@ BillBarth Du hast einen guten Punkt gemacht. Ich verwende jedoch mehrere Testmatrizen in aufsteigender Reihenfolge. In solchen Fällen ist es nicht möglich, die Verteilung zu zeichnen, da ich dann die Verteilungen für alle anderen Testmatrizen zeichnen muss. Deshalb wollte ich sie tabellarisch darstellen. Danke für deine Kommentare.

Srijan

@srijan: Du wirst die Daten haben, du solltest Histogramme für dich selbst zeichnen, wo immer du kannst. Sie müssen sie nicht alle veröffentlichen, aber ich verspreche Ihnen, dass ein Diagramm der Verteilung Ihnen mehr sagt als ein Meer von Zahlen oder nur die Durchschnittswerte, die es jemals geben wird.

Bill Barth

Ich würde die Ausführungszeit pro Iteration einschließen. Da jede Matrix unterschiedlich ist, können Sie eine unterschiedliche Anzahl von Iterationen mit unterschiedlichen Ausführungszeiten haben. Zusammen mit dem, was @Cristian sagte, wäre die Ausführungszeit pro Iteration nützlich.

jbcolmenares

Ich halte die Anzahl der Iterationen für eine irreführende Metrik, da sie "Geschwindigkeit" andeutet, wenn dies nicht der Fall ist. Ein einfaches Beispiel für den Vergleich einiger verschiedener Vorkonditionierer, die diesen Unterschied zeigen, finden Sie hier: http://www.dealii.org/developer/doxygen/deal.II/step_6.html#Possibilitiesforextensions

Wolfgang Bangerth
quelle

Danke für die Antwort. Ich kann diese Zeile "Anzahl der Iterationen als irreführende Metrik" nicht verstehen, da sie "Geschwindigkeit" andeutet, wenn dies nicht der Fall ist ". Das von Ihnen vorgeschlagene Beispiel ist für mich etwas schwer zu verstehen.

Srijan

Was ich damit sagen will, ist, dass wir häufig "Anzahl der Iterationen" angeben, um der "verwendeten CPU-Zeit" zu entsprechen, was bedeutet, dass eine Methode, die weniger Iterationen erfordert, auch schneller ist. Aber das stimmt nicht, wie die Zahlen zeigen, mit denen ich verbunden bin.

Wolfgang Bangerth

Nun habe ich Ihren Punkt vollständig verstanden. Gleiches habe ich mit der Newton-Methode zur Approximation der Inversen einer quadratischen Matrix beobachtet. A s die Reihenfolge der Methode zunimmt, nimmt anfangs sowohl die CPU-Zeit als auch die Anzahl der Iterationen ab, aber mit zunehmender Reihenfolge nimmt der Start der CPU-Zeit zu, obwohl die Anzahl der Iterationen abnimmt. Ich danke Ihnen sehr für Ihre Antwort.

Srijan

Falls in den anderen Antworten nicht klar ist, wofür die Anzahl der Iterationen gut ist, sind Big-O-Argumente.

Es ist nicht gut für die absolute Geschwindigkeit, da dies von der durchschnittlichen Zeit pro Iteration abhängt, die sich zwischen den Methoden um einen großen Faktor unterscheiden kann.

Beispielsweise besteht die Tendenz, die Kosten für die Berechnung von Array-Indizes zu ignorieren, und dies kann durchaus einen großen Teil der CPU-Zeit ausmachen.

HINZUGEFÜGT: Wie ich bereits an anderer Stelle ausgeführt habe, fallen für jeden Aufruf der Methode in der Regel Einrichtungskosten an. Wenn die Matrizen dann normalerweise nicht sehr groß sind, können diese Einrichtungskosten selbst einen großen Bruchteil der CPU-Zeit ausmachen (so dass das Entfernen einen großen Unterschied in der Geschwindigkeit bewirken würde).

Mike Dunlavey
quelle