Korrigieren Sie die Statistiken für die Meldung von Beschleunigungsergebnissen

Angenommen, ich habe langsame und schnelle Versionen eines Codes und möchte eine Beschleunigungszahl melden, die die beiden vergleicht. Ich führe die langsame Version mal und die schnelle Version mal aus und produziere die Zeiten und . Der einfachste Weg, eine Beschleunigung zu erzielen, besteht darin, die folgenden Mittelwerte zu mitteln: $n$ $m$ $(s_1, \ldots, s_n)$ $(f_1, \ldots, f_m)$ Dies berücksichtigt jedoch keine Ausreißer.

\frac{\bar{s}}{\bar{f}} = \frac{m \sum_{i < n} s_{i}}{n \sum_{j < m} f_{j}}

$\frac{\bar{s}}{\bar{f}} = \frac{m \sum_{i<n} s_i}{n \sum_{j<m} f_j}$

Frage : Was ist die beste Statistik für die Meldung von Beschleunigungszahlen?

statistics publications Geoffrey Irving
quelle

Wie groß ist die Standardabweichung im Vergleich zum Mittelwert? Was auch immer Sie tun, Sie sollten angeben, was Sie getan haben, und wahrscheinlich Fehlerbalken einfügen, wenn diese groß sind. Wenn sie wirklich groß sind, sollten Sie die Quelle untersuchen. Der meiste Computercode sollte ziemlich deterministisch ausgeführt werden, es sei denn, das Programm selbst enthält eine zufällige Komponente, oder Sie teilen Computerressourcen mit anderen (dies kann ein Netzwerk oder eine Festplatte sein, nicht nur Clusterknoten). Wenn der Wettbewerb um Datenträgerressourcen das Problem ist, sollten Sie die Berichtsleistung möglicherweise mit deaktivierter E / A (ziemlich häufig) in Betracht ziehen. Beachten Sie dies jedoch unbedingt.

Bill Barth

Auf Edison (einem Cray-Supercomputer) habe ich einen Unterschied von 2% zwischen zwei Proben. Auf meinem Laptop wird eine Standardabweichung von 6-8% angezeigt, die über 10 Proben gemessen wurde. Beide sind nur für den Rechenkern gedacht, keine E / A.

Geoffrey Irving

Um zu verdeutlichen, warum ich Ausreißer erwähne, wenn die Abweichungen bereits einigermaßen gering sind: Dies ist eine hinreichend fundamentale statistische Größe, um den idealen Weg zu kennen, um sie zu melden.

Geoffrey Irving

Die Frage ist, was versuchst du zu kommunizieren, und Formel würde das am besten kommunizieren? Ich glaube nicht, dass ich jemals ein Papier gesehen habe, das die Variabilität der Geschwindigkeit von Lauf zu Lauf angibt, es sei denn, die Ursache war im Zentrum des Papiers. Vorausgesetzt, dass wir eine lineare Beziehung zwischen Laufzeit und Prozessor / Task / Thread-Anzahl annehmen, ist es wahrscheinlich in Ordnung, das Verhältnis der Mittelwerte zu verwenden, aber dann wird das Verhältnis von Max zu Min und Min zu Max als Fehlerbalken angezeigt wenn Sie denken, dass es wichtig ist, die Reichweite anzuzeigen. Außerdem sollten Sie sich wahrscheinlich Ihre Optionen für die Frequenzskalierung und das Festlegen von Aufgaben ansehen, um Ihre Variabilität zu verringern. :)

Bill Barth

Es kann eine Menge Tricks geben, wenn man IO eliminiert. Zwischen Compiler-Optimierungen zu "Copy On Write" -Tricks kann es wirklich nicht offensichtliche Bindungen nach unten geben. Ich folge normalerweise dem Prototyp von d1 = loadData (); d2 = Kopie (d1); r1 = algo (d2); r2 = algo (d1) und berücksichtige nur den Zeitpunkt des zweiten Durchlaufs.

Meawoppl

Antworten:

Lassen Sie mich zusätzlich zu all dem, was Bill Barth oben bereits gesagt hat, erwähnen, dass die Leute oft den schnellsten von mehreren Läufen melden . Der Grund ist , dass die tatsächliche Laufzeit der ist ideal Laufzeit plus eine beliebige Anzahl von Verlangsamungen von anderen Prozessen resultierenden läuft, OS Verzögerungen, Netzwerkverzögerungen, etc. Da diese alle Lärm interessiert uns nicht, die mit am schnellsten Laufzeit kommt am nächsten zu dem, den wir wirklich wissen wollen.

Wolfgang Bangerth
quelle

Leider hilft dieses Prinzip nicht, wenn eine Beschleunigung zwischen zwei Algorithmen gemeldet wird.

Geoffrey Irving

@GeoffreyIrving, warum nicht? Beide Algorithmen haben eine theoretische Leistungserwartung gegenüber der Problemgröße (oder der Prozessoranzahl oder einem anderen nicht statistischen Parameter), wobei Terme niedriger Ordnung und parameterunabhängig ignoriert werden. Wenn Sie die schnellste Zeit verwenden (und diese Tatsache beachten), können Sie diese zusätzlichen Begriffe einfach ignorieren. Das scheint eine gute Strategie zu sein. Sofern Sie uns nichts anderes mitteilen, scheint es so, als würden Sie versuchen, den Unterschied zwischen Algorithmen am effektivsten zu kommunizieren, und der Vorschlag von Wolfgang ist konventionell und wird erwartet, um diese Informationen am besten zu vermitteln.

Bill Barth

Ups, ja, du hast recht. Ich ziehe meine Erklärung gerne zurück.

Geoffrey Irving

(+1) Eine Nebenfrage: Ich vervollständige Ihren Standpunkt zur nicht symmetrischen Rauschverteilung usw. Nehmen wir an, ich mache eine Implementierung A und eine Implementierung B und vergleiche sie und nach einer angemessenen Anzahl von Läufen die Das 25. Quantil und der Median und der Mittelwert sind in A ~ 4,5x schneller als in B, während das 0% -Quantil ~ 3x ist. Wenn Sie Implementierung A mit B vergleichen, obwohl: Ist yes A is theoretically only ~3x fastereine Beschleunigung von ~ 3x nicht nicht repräsentativ für die erwartete Beschleunigung, wenn Implementierung A anstelle von B verwendet wird? (Dies ist übrigens ein reales Beispiel)

usεr11852 sagt Reinstate Monic

@ usεr11852: Es hängt alles von dem System ab, auf dem Sie sich befinden. Wenn Ihr Median oder Ihr 25. Quantil so weit voneinander entfernt sind, dass die Statistik in der von Ihnen hier angenommenen Weise verzerrt wird, dann haben Sie wahrscheinlich ein System mit viel Rauschen. Zum Beispiel kann es von anderen gleichzeitig verwendet werden, usw. Das ist möglicherweise nicht repräsentativ für die Systeme, die andere für ihre Wiederholungsexperimente haben, und es würde sich für mich so anhören, als würden Sie in diesem Fall Ihre Ergebnisse übertreiben. Daher schlage ich immer noch vor, die besten Läufe zu melden. Was auch immer Sie tun, Sie sollten auf dem Papier angeben, welche Statistiken Sie verwenden.

Wolfgang Bangerth

Ich schlage vor, Sie verwenden den Median , um eine statistische Schätzung zu geben. Im Gegensatz zum Mittelwert wird der Median nicht durch Ausreißer verfälscht.

Jan
quelle

Bei Daten, bei denen das gesamte Rauschen positiv ist (dh bei einer nicht symmetrischen Rauschverteilung), ist der Median so schlecht wie bei jeder anderen Statistik. Für Laufzeiten ist dies in der Tat der Fall, siehe meine Antwort oben.

Wolfgang Bangerth

Wenn die Standardabweichung nicht vernachlässigbar ist, können Sie zwei Box-Plots nebeneinander verwenden, die jeweils mit dem Timing eines der Algorithmen erstellt wurden. Sie sind in der numerischen Analyse keineswegs Standard, aber sie leisten hervorragende Arbeit bei der Anzeige dieser Art von Informationen.

Federico Poloni
quelle