Comparaison des méthodes d'itération: nombre d'itérations en fonction du temps processeur

14

Je compare deux méthodes itératives pour inverser des matrices carrées aléatoires. Étant donné que les matrices sont aléatoires, chaque cas de test prend à la fois différentes quantités d'itérations et différents temps écoulés. Ma question est, en plus du temps CPU moyen, est la valeur moyenne des itérations prises par les deux méthodes des informations utiles pour comparer les méthodes.

performance benchmarking srijan
la source
4
J'ai reformulé votre question pour, je l'espère, la rendre plus claire. Veuillez vous assurer que je n'ai en aucun cas changé votre sens.
Godric Seer
3
@GodricSeer Votre modification a amélioré ma question. Merci
srijan

Réponses:

12

En général, les deux méthodes de comparaison des performances ont leur place.

  • La comparaison du temps processeur est en quelque sorte la mesure la plus intéressante, car à la fin de la journée, vous êtes vraiment intéressé par la méthode la plus rapide. (Mais assurez-vous que les critères de terminaison sont comparables; par exemple, que les deux méthodes donnent une approximation avec la même précision). L'inconvénient est que cela ne vous indique que la méthode (et surtout, quelle implémentation ) est la plus rapide sur la machine sur laquelle vous avez effectué les tests. Il n'y a aucune garantie qu'une machine différente avec une architecture ou un logiciel différent choisirait le même gagnant.

  • La comparaison des nombres d'itérations , en revanche, est indépendante de la machine, mais peut être trompeuse si les deux méthodes ont des itérations très différentes - dans ce cas, la méthode avec des itérations moins nombreuses mais plus chères pourrait ne pas être préférable (par exemple, Newton vs méthodes de gradient pour l'optimisation). si vous n'avez besoin que d'une très faible précision).

Donc, oui, il est logique de donner les deux nombres [1], et je l'ai souvent vu faire dans des publications. Il existe également une troisième option:

  • Comparaison du nombre d'opérations élémentaires . Si les deux itérations consistent en le même type d'opération convenablement coûteuse, mais nécessitent un nombre différent (éventuellement même pas le même nombre à chaque itération), il est logique de compter le nombre total de ces opérations. Dans votre cas, un candidat probable serait des multiplications matrice-vecteur ou matrice-matrice.

[1] Présenter des statistiques sur plusieurs exécutions; si vous montrez des moyens, n'oubliez pas d'inclure également les écarts-types.

Christian Clason
la source
5
Ne vous contentez pas de moyens! Si vous avez suffisamment de points de test avec des entrées aléatoires, tracez une distribution.
Bill Barth
1
@BillBarth - bon point, bien que cela ne soit pas toujours possible; mais donner des écarts-types avec la moyenne devrait toujours être possible. En fait, quelles statistiques présenter pour rendre compte des performances semblent être une excellente question de suivi.
Christian Clason
@BillBarth Vous avez fait valoir un bon argument. Mais, j'utilise plusieurs matrices de test dans l'ordre croissant. Pour de tels cas, il n'est pas possible de tracer la distribution depuis lors, je dois tracer les distributions pour toutes les autres matrices de test. C'est pourquoi je voulais les tabuler. Merci pour vos commentaires.
srijan
1
@srijan: Vous aurez les données, vous devriez tracer des histogrammes par vous-même partout où vous le pouvez. Vous n'êtes pas obligé de les publier tous, mais je vous promets qu'un graphique de la distribution vous en dira plus qu'une mer de chiffres ou simplement les moyennes.
Bill Barth
J'inclurais le temps d'exécution par itération. Étant donné que chaque matrice est différente, vous pouvez avoir un nombre d'itérations différent avec des temps d'exécution différents. Avec ce que @Cristian a dit, le temps d'exécution par itération serait utile.
jbcolmenares
4

Je trouve que le nombre d'itérations est une mesure trompeuse car il suggère une "vitesse" quand ce n'est pas le cas. Pour un exemple simple de comparaison de quelques préconditionneurs différents qui montre cette différence, voir ici: http://www.dealii.org/developer/doxygen/deal.II/step_6.html#Possabilitiesforextensions

Wolfgang Bangerth
la source
Merci d'avoir répondu. Je ne suis pas en mesure de comprendre que cette ligne «le nombre d'itérations est une métrique trompeuse car elle suggère une« vitesse »quand elle ne l'est pas». L'exemple que vous avez proposé est quelque peu difficile à comprendre pour moi.
srijan
Ce que je dis, c'est que nous présentons souvent "nombre d'itérations" pour être équivalent à "temps CPU utilisé", ce qui implique qu'une méthode qui nécessite moins d'itérations est également plus rapide. Mais ce n'est pas vrai, comme le montrent les chiffres que j'ai liés.
Wolfgang Bangerth
Maintenant, j'ai bien compris votre point. J'ai observé la même chose avec la méthode newtons pour approximer l'inverse d'une matrice carrée. A mesure que l'ordre des méthodes augmente, le temps de calcul initial ainsi que le nombre d'itérations diminuent tous les deux, mais à mesure que l'ordre augmente, le temps de démarrage du processeur augmente même si le nombre d'itérations diminue. Merci beaucoup pour votre réponse.
srijan
2

Dans le cas où ce n'est pas clair dans les autres réponses, quel nombre d'itérations est bon pour les arguments big-O.

Ce n'est pas bon pour la vitesse absolue, car cela dépend du temps moyen par itération, qui peut différer entre les méthodes d'un facteur important.

Par exemple, il y a une tendance à ignorer le coût de calcul des indices de tableau, et cela pourrait bien représenter une grande partie du temps CPU.

AJOUTÉ: De plus, comme je l'ai souligné ailleurs, pour chaque invocation de la méthode, il y a généralement un coût d'installation. Ensuite, si les matrices ne sont généralement pas très grandes, ce coût d'installation peut lui-même représenter une grande partie du temps CPU (de sorte que sa suppression ferait une grande différence de vitesse).

Mike Dunlavey
la source