Statistiques correctes pour rapporter les résultats d'accélération

Supposons que j'ai des versions lentes et rapides d'un code et que je souhaite signaler un numéro d'accélération comparant les deux. Je lance la version lente fois et la version rapide fois, produisant des temps et . La façon la plus simple de produire une accélération est de faire la moyenne des moyennes: Cependant, cela ne prend pas en compte les valeurs aberrantes. $n$ $m$ $(s_1, \ldots, s_n)$ $(f_1, \ldots, f_m)$

\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}$

Question : Quelle est la meilleure statistique à utiliser lors de la déclaration des nombres d'accélération?

statistics publications Geoffrey Irving
la source

Quelle est la taille de l'écart-type par rapport à la moyenne? Quoi que vous fassiez, vous devez signaler ce que vous avez fait et probablement mettre des barres d'erreur si elles sont grandes. S'ils sont vraiment volumineux, vous devez rechercher la source. La plupart du code informatique devrait s'exécuter de manière assez déterministe dans le temps, sauf s'il existe un composant aléatoire dans le programme lui-même ou si vous partagez des ressources informatiques avec d'autres (cela peut être un réseau ou un disque, pas seulement des nœuds de cluster). Si la concurrence pour les ressources disque est le problème, vous pouvez envisager de signaler les performances avec les E / S désactivées (assez courant) - assurez-vous simplement de le noter.

Bill Barth

Sur Edison (un supercalculateur Cray), j'ai une différence de 2% entre deux échantillons. Sur mon ordinateur portable, je vois un écart-type de 6 à 8% mesuré sur 10 échantillons. Les deux sont pour le noyau de calcul uniquement, pas d'E / S.

Geoffrey Irving

Pour clarifier pourquoi je mentionne des valeurs aberrantes si les variances sont déjà raisonnablement faibles: il s'agit d'une quantité statistique suffisamment fondamentale pour que je souhaite connaître la manière idéale de la signaler, même si les méthodes non idéales conviennent dans ce cas particulier.

Geoffrey Irving

La question est de savoir ce que vous essayez de communiquer et quelle formule communiquerait le mieux? Je ne pense pas avoir jamais vu un article qui rapporte la variabilité de l'accélération à l'exécution à moins que la cause ne soit au centre de l'article. Étant donné que nous posons une relation linéaire entre le temps d'exécution et le nombre de processeurs / tâches / threads, vous êtes probablement d'accord pour utiliser le rapport des moyennes, mais ensuite la barre d'erreur avec le rapport max-min-min et min-max si vous pensez qu'il est important de montrer la plage. En outre, vous devriez probablement examiner vos options de mise à l'échelle de la fréquence et d'épinglage des tâches pour réduire votre variabilité. :)

Bill Barth

L'élimination des E / S peut être très compliquée. Entre les optimisations du compilateur et les astuces "Copier en écriture", il peut y avoir des liens vraiment non évidents vers le bas. Je suis généralement le prototype de d1 = loadData (); d2 = copie (d1); r1 = algo (d2); r2 = algo (d1), et ne considère que l'heure de la deuxième manche.

meawoppl

Réponses:

En plus de tout ce que Bill Barth a déjà dit ci-dessus, permettez-moi de mentionner que les gens signalent souvent le plus rapide de plusieurs courses. La raison en est que le temps d'exécution réel est le temps d'exécution idéal , plus un certain nombre de ralentissements résultant d'autres processus en cours d'exécution, des retards OS, des retards réseau, etc. Étant donné que ce sont tous des bruits qui ne nous intéressent pas, l'utilisation du temps d' exécution le plus rapide vient le plus proche de celui que nous voulons vraiment savoir.

Wolfgang Bangerth
la source

Malheureusement, ce principe n'aide pas à signaler une accélération entre deux algorithmes.

Geoffrey Irving le

@GeoffreyIrving, pourquoi pas? Les deux algorithmes ont une attente de performance théorique par rapport à la taille du problème (ou le nombre de processeurs ou d'autres paramètres non statistiques), les termes de faible ordre et indépendants des paramètres étant ignorés. Utiliser le temps le plus rapide (et noter ce fait) vous aide simplement à ignorer ces termes supplémentaires. Ce qui semble être une bonne stratégie. À moins que vous ne nous disiez différemment, il semble que vous essayez de comprendre comment communiquer la différence entre les algorithmes le plus efficacement possible, et la suggestion de Wolfgang est conventionnelle et attendue afin qu'elle puisse mieux transmettre ces informations.

Bill Barth

Oups, oui, vous avez raison. Je retire avec plaisir ma déclaration.

Geoffrey Irving le

(+1) Une question secondaire: je vois votre point sur la distribution de bruit non symétrique , etc. Disons cependant que je fais une implémentation A, une implémentation B et que je les compare et après un nombre raisonnable de runs, le Le 25-ème quantile et la médiane et la moyenne sont ~ 4,5x plus rapides en A que B tandis que le quantile 0% est ~ 3x. En comparant l'implémentation A à B, malgré le fait que yes A is theoretically only ~3x faster:, une accélération de ~ 3x non représentative de l'accélération sur pourrait-elle s'attendre lors de l'utilisation de l'implémentation A au lieu de B? (Ceci est un exemple réel en passant)

usεr11852

@ usεr11852: Tout dépend du système sur lequel vous vous trouvez. Si votre médiane ou votre 25e quantile sont si éloignés qu'ils faussent les statistiques de la manière dont vous faites l'hypothèse ici, alors vous êtes probablement sur un système qui a beaucoup de bruit. Par exemple, il peut être utilisé par d'autres en même temps, etc. Cela peut ne pas être représentatif des systèmes que d'autres ont pour leurs expériences répétées, et il me semble que vous surventez vos résultats dans ce cas. Donc, je suggère toujours de signaler les meilleurs runs. Quoi que vous fassiez, vous devez indiquer dans le journal les statistiques que vous utilisez.

Wolfgang Bangerth

Je vous suggère d'utiliser la médiane pour donner une estimation statistique. Contrairement à la moyenne, la médiane n'est pas corrompue par les valeurs aberrantes.

Jan
la source

Pour les données où tout le bruit est positif (c'est-à-dire avec une distribution de bruit non symétrique), la médiane est aussi mauvaise que toute autre statistique. Pour les temps d'exécution, c'est effectivement le cas, voir ma réponse ci-dessus.

Wolfgang Bangerth

Si l'écart-type n'est pas négligeable, vous pouvez utiliser deux parcelles parallèles côte à côte, construites chacune avec le timing d'un des algorithmes. Ils ne sont certainement pas standard dans l'analyse numérique, mais ils font un excellent travail en affichant ce type d'informations.

Federico Poloni
la source