L’analyse algorithmique par comptage flop est-elle obsolète?

Dans mes cours d’analyse numérique, j’ai appris à analyser l’efficacité des algorithmes en comptant le nombre d’opérations à virgule flottante (flops) qu’ils requièrent, par rapport à l’ampleur du problème. Par exemple, dans le texte de Trefethen & Bau sur l'algèbre linéaire numérique, il y a même des images en 3D du décompte du flop.

Maintenant, il est à la mode de dire que "les flops sont gratuits" car la latence de la mémoire pour extraire tout ce qui n’est pas dans le cache est beaucoup plus grande que le coût d’un flop. Mais nous continuons d’enseigner aux étudiants à compter les échecs, du moins dans les cours d’analyse numérique. Devrions-nous leur apprendre à compter les accès mémoire? Avons-nous besoin d'écrire de nouveaux manuels? Ou bien l’accès à la mémoire est-il trop spécifique à la machine pour y passer du temps? Quelle sera la tendance à long terme quant à savoir si les flops ou l’accès à la mémoire sont le goulot d’étranglement?

Remarque: certaines des réponses ci-dessous semblent répondre à une question différente, telle que "Devrais-je réécrire de manière obsessionnelle mon implémentation pour enregistrer quelques flops ou améliorer les performances du cache?" Mais ce que je demande, c'est plutôt dans le sens de " Est-il plus utile d'estimer la complexité algorithmique en termes d'opérations arithmétiques ou d'accès mémoire ?"

Je pense que la bonne chose à faire (au premier ordre) est de regarder le ratio flop / octets requis dans l'algorithme, que j'appelle . Soit le taux maximal de flop du processeur et la bande passante maximale. Si , alors l'algorithme aura une bande passante limitée. Si , l'algorithme est limité par le flop.$\beta$$F_{\mathrm{max}}$$B_{\mathrm{max}}$$\frac{F_{\mathrm{max}}}{\beta} > B_{\mathrm{max}}$$B_{\mathrm{max}}\beta > F_{\mathrm{max}}$

Je pense que compter les accès à la mémoire est obligatoire, mais nous devrions aussi penser à:

• Combien de mémoire locale est nécessaire

• Combien de simultanéité possible nous avons

Ensuite, vous pouvez commencer à analyser des algorithmes pour du matériel moderne.

Je ne vois pas pourquoi on doit être le "gagnant"; Ce n'est pas un jeu à somme nulle, où le compte du flop et l'accès à la mémoire doivent noyer l'autre. Vous pouvez enseigner aux deux, et je pense qu'ils ont tous les deux leur utilité. Après tout, il est difficile de dire que votre algorithme avec des accès mémoire va nécessairement être plus rapide que votre algorithme avec des accès . Tout dépend des coûts relatifs des différentes parties (ce pré-facteur embêtant que nous ignorons toujours dans ces analyses!).$O(N^4)$$O(N)$$O(N \log N)$$O(N^2)$

Dans une perspective plus large, je pense que l'analyse de la performance algorithmique devrait être "tout compris". Si nous enseignons aux utilisateurs à devenir de véritables développeurs et utilisateurs HPC, ils doivent comprendre quels sont les coûts de la programmation dans le monde réel. Les modèles d'analyse abstraits que nous avons ne prennent pas en compte le temps du programmeur. Nous devrions penser en termes de "temps total de résolution", plutôt que de simples comptages d'échec et d'efficacité algorithmique. Il est peu logique de passer trois ou quatre jours de programmation à réécrire une routine qui vous fera gagner une seconde de temps d’ordinateur par travail, à moins que vous ne prévoyiez exécuter quelques millions de calculs. De même, un investissement de quelques jours pour économiser une heure ou deux de temps de calcul rapporte rapidement. Ce nouvel algorithme peut être incroyable,

Comme d'autres l'ont souligné, la réponse dépend bien entendu du fait que le goulot d'étranglement soit le processeur ou la bande passante mémoire. Pour de nombreux algorithmes fonctionnant sur des ensembles de données de taille arbitraire, le goulot d'étranglement correspond généralement à la bande passante mémoire, car l'ensemble de données ne rentre pas dans le cache du processeur.

En outre, Knuth mentionne que l'analyse de l'accès à la mémoire résiste mieux à l'épreuve du temps, probablement parce qu'elle est relativement simple (même en tenant compte de la convivialité du cache) par rapport aux complexités des pipelines de processeurs modernes et de la prédiction de branche.

Knuth utilise le terme gigamems dans le volume 4A de TAOCP, lors de l'analyse de BDD. Je ne sais pas s'il l'utilise dans les volumes précédents. Il a fait le commentaire ci-dessus à propos de l’épreuve du temps lors de sa conférence annuelle sur l’arbre de Noël en 2010.

Fait intéressant, vous faites une mauvaise chose montre que même l’analyse des performances basées sur des opérations de mémoire n’est pas toujours simple car des éléments tels que la pression de la machine virtuelle entrent en jeu si les données ne rentrent pas toutes en même temps dans la RAM physique.

La manière dont vous déterminez les coûts d'un algorithme dépend du "niveau" d'informatique scientifique sur lequel vous travaillez et de la classe de problèmes (étroite ou large) à prendre en compte.

Si vous pensez à l'optimisation du cache, cela est clairement plus pertinent, par exemple, pour la mise en œuvre de packages d'algèbre linéaire numérique tels que BLAS et des bibliothèques similaires. Cela appartient donc à l'optimisation de bas niveau, et c'est bien si vous avez un algorithme fixe pour un problème spécifique et avec des contraintes suffisantes sur l'entrée. Par exemple, l'optimisation du cache peut être utile pour une implémentation rapide de l'itération à gradient conjugué si la matrice est supposée être suffisamment clairsemée.

D'un autre côté, plus la classe de problèmes est large, moins vous pouvez prédire l'informatique réelle (par exemple, vous ne savez pas à quel point les matrices d'entrée de votre implémentation CG seront rares). Plus la classe de machines sur laquelle votre programme est supposé s'exécuter est large, moins vous pouvez prédire l'architecture du cache.

En outre, à un niveau supérieur de calcul scientifique, il pourrait être plus pertinent de modifier la structure du problème. Par exemple, si vous passez du temps à trouver un bon préconditionneur pour un système d'équations linéaire, ce type d'optimisation surpasse en général toute optimisation de bas niveau, car le nombre d'itérations est considérablement réduit.

En conclusion, l'optimisation du cache n'est utile que s'il ne reste plus rien à optimiser par le parallélisme et la réduction du nombre asymptotique de FLOP.

Je pense qu'il est sage d'adapter l'orientation de l'informatique théorique: au final, l'amélioration de la complexité asymptotique d'un algorithme a plus de rendement que la micro-optimisation de certaines lignes de code existantes. Par conséquent, le comptage des FLOP est toujours préférable.

J'ai toujours refusé de penser même à compter les flops, les accès à la mémoire, ou ce que vous avez. C'est un concept des années 1960 où ce que vous faisiez était à peu près donné et la manière dont vous le faisiez relevait de l'optimisation algorithmique. Pensez à résoudre un problème d'éléments finis sur un maillage xyz uniforme en utilisant soit l'élimination gaussienne de l'itération de Jacobi.

Maintenant, vous pouvez optimiser cela au maximum et économiser quelques flops en gagnant 10% du temps d'exécution. Vous pouvez également envisager de mettre en œuvre une méthode multigrille et un préconditionneur de blocs optimal, en multipliant par 10 le temps d’exécution. C’est ce que nous devrions apprendre à nos étudiants: pensez à la complexité des algorithmes externes qui peuvent vous aider à essayer de trouver un meilleur algorithme interne. Votre patron (Keyes) a ces diapositives sur les progrès des calculs MHD qui rendent ce point très évident.

Oui, obsolète L'analyse algorithmique par flops, ou par toute autre méthode, est aussi utile que le modèle abstrait de la machine pour déterminer la taille du problème à résoudre. Les performances réelles dépendent à la fois de la mise en œuvre et du matériel, et l'applicabilité de tout modèle abstrait de ce dernier à la réalité diminue avec le temps. Par exemple, au fur et à mesure que vous parallélisez la mise en œuvre d'un algorithme complexe, comme la dynamique moléculaire, différents aspects limitent la vitesse sur un matériel différent, l'analyse algorithmique n'a rien à voir avec les observations. En un sens, la seule chose importante est de mesurer les performances de la ou des implémentations du ou des algorithmes sur le ou les types de matériel en question.

Ces abstractions sont-elles utiles en tant qu'outil d'apprentissage? Oui, comme beaucoup de modèles utilisés pour l’enseignement, ils sont utiles dans la mesure où ils sont placés parallèlement à la compréhension des limites du modèle. La mécanique classique est acceptable si vous comprenez qu'elle ne fonctionnera pas sur des échelles de faible distance ou de grande vitesse ...

Pas vraiment répondre à votre question, mais plutôt ajouter une autre variable à prendre en compte: quelque chose à prendre en compte sont les fonctionnalités du langage de programmation. Par exemple, Python sortutilise l' algorithme Timsort , conçu (entre autres propriétés intéressantes) pour minimiser le nombre de comparaisons, ce qui peut être potentiellement lent pour les objets Python. D'autre part, comparer deux flottants en C ++ est extrêmement rapide, mais les échanger étant plus coûteux, ils utilisent d' autres algorithmes.

D'autres exemples sont l'allocation dynamique de la mémoire (trivial dans une liste Python, rapide à la fois pour l'exécution et les développeurs, simplement .append()), vs FORTRAN ou C, où, bien que possible et plus rapide une fois correctement implémenté, cela prend beaucoup plus de temps de programmation et de cerveau. Voir Python est plus rapide que FORTRAN.