Comptage FLOP pour les fonctions de bibliothèque

Lors de l'évaluation du nombre de FLOP dans une fonction simple, on peut souvent simplement descendre l'expression en comptant les opérateurs arithmétiques de base. Cependant, dans le cas d'instructions mathématiques impliquant une division paire, on ne peut pas le faire et s'attendre à pouvoir comparer avec les nombres FLOP à partir de fonctions avec seulement des additions et des multiplications. La situation est encore pire lorsque l'opération est implémentée dans une bibliothèque. Par conséquent, il est impératif d'avoir une certaine notion raisonnable de l'exécution des fonctions spéciales.

Par fonctions spéciales, nous entendons des choses comme:

• exp ()
• sqrt ()
• sin / cos / tan ()

qui sont généralement fournis par les bibliothèques système.

La détermination de la complexité de ceux-ci est encore plus compliquée par le fait que beaucoup d'entre eux sont adaptatifs et ont une complexité dépendante des entrées. Par exemple, les implémentations numériquement stables de exp () mettent souvent à l'échelle de manière adaptative et utilisent des recherches. Mon impression initiale ici est que la meilleure chose à faire dans ce cas est de vérifier le comportement moyen des fonctions.

Toute cette discussion est, bien sûr, fortement dépendante de l'architecture. Pour cette discussion, nous pouvons nous limiter aux architectures traditionnelles à usage général et exclure celles avec des unités de fonctions spéciales (GPU, etc.)

On peut trouver des tentatives assez simples de standardiser celles - ci pour des architectures particulières dans un souci de comparaison système vs système, mais cela n'est pas acceptable si l'on se soucie de la méthode par rapport aux performances de la méthode. Quelles méthodologies pour déterminer la complexité FLOP de ces fonctions sont considérées comme acceptables? Y a-t-il des écueils majeurs?

Il semble que vous vouliez un moyen d'évaluer la façon dont votre code est lié au FPU, ou l'efficacité avec laquelle vous utilisez le FPU, plutôt que de compter le nombre de flops selon la même définition anachronique d'un "flop". En d'autres termes, vous voulez une métrique qui atteint le même pic si chaque unité à virgule flottante fonctionne à pleine capacité à chaque cycle. Regardons un Intel Sandy Bridge pour voir comment cela pourrait se décomposer.

Opérations en virgule flottante prises en charge par le matériel

Cette puce prend en charge les instructions AVX , les registres font donc 32 octets de long (contenant 4 doubles). L'architecture superscalaire permet aux instructions de se chevaucher, la plupart des instructions arithmétiques prenant quelques cycles pour se terminer, même si une nouvelle instruction peut commencer au cycle suivant. Ces sémantiques sont généralement abrégées en écrivant latence / débit inverse, une valeur de 5/2 signifierait que l'instruction prend 5 cycles pour se terminer, mais vous pouvez démarrer une nouvelle instruction tous les deux cycles (en supposant que les opérandes sont disponibles, donc pas de données dépendance et ne pas attendre la mémoire).

Il y a trois unités arithmétiques à virgule flottante par cœur, mais la troisième n'est pas pertinente pour notre discussion, nous appellerons les deux unités pertinentes les unités A et M car leurs fonctions principales sont l'addition et la multiplication. Exemples d'instructions (voir les tableaux d'Agner Fog )

• vaddpd: addition compactée, unité d'occupation A pendant 1 cycle, latence / débit inverse de 3/1
• vmulpd: multiplication emballée, unité M, 5/1
• vmaxpd: emballé sélectionner par paire maximum, unité A, 3/1
• vdivpd: division divisée, unité M (et certains A), 21/20 à 45/44 selon l'entrée
• vsqrtpd: racine carrée tassée, certains A et M, 21/21 à 43/43 selon l'entrée
• vrsqrtps: racine carrée réciproque de faible précision compacte pour une entrée simple précision (8 floats)

La sémantique précise de ce qui peut se chevaucher vdivpdet qui vsqrtpdest apparemment subtile et AFAIK, n'est documentée nulle part. Dans la plupart des utilisations, je pense qu'il y a peu de possibilité de chevauchement, bien que le libellé du manuel suggère que plusieurs threads peuvent offrir plus de possibilité de chevauchement dans cette instruction. Nous pouvons atteindre des flops de pointe si nous commençons unvaddpd et vmulpdà chaque cycle, pour un total de 8 flops par cycle. La multiplication matrice-matrice dense ( dgemm) peut se rapprocher raisonnablement de ce pic.

Lorsque je compte les flops pour des instructions spéciales, je regarde la quantité de FPU occupée. Supposons pour l'argument que dans votre plage de saisie, il a vdivpdfallu en moyenne 24 cycles pour terminer l'unité occupant pleinement M, mais l'addition pourrait (si elle était disponible) être exécutée simultanément pendant la moitié des cycles. Le FPU est capable d'effectuer 24 multiplications et 24 ajouts compressés au cours de ces cycles (parfaitement entrelacés vaddpdet vmulpd), mais avec un vdivpd, le mieux que nous pouvons faire est de 12 ajouts compressés supplémentaires. Si nous supposons que la meilleure façon de faire la division est d'utiliser le matériel (raisonnable), nous pourrions compter les vdivpd36 "flops" emballés, indiquant que nous devrions compter chaque division scalaire comme 36 "flops".

Avec la racine carrée réciproque, il est parfois possible de battre le matériel, surtout si une précision totale n'est pas nécessaire, ou si la plage d'entrée est étroite. Comme mentionné ci-dessus, l' vrsqrtpsinstruction est très peu coûteuse, donc (si en simple précision) vous pouvez en faire une vrsqrtpssuivie d'une ou deux itérations de Newton pour nettoyer. Ces itérations de Newton sont juste

y *= (3 - x*y*y)*0.5;

Si plusieurs de ces opérations doivent être effectuées, cela peut être beaucoup plus rapide qu'une évaluation naïve de y = 1/sqrt(x). Avant la disponibilité de la racine carrée réciproque approximative du matériel, certains codes sensibles aux performances utilisaient des opérations entières infâmes pour trouver une estimation initiale de l'itération de Newton.

Fonctions mathématiques fournies par la bibliothèque

Nous pouvons appliquer une heuristique similaire aux fonctions mathématiques fournies par la bibliothèque. Vous pouvez profiler pour déterminer le nombre d'instructions SSE, mais comme nous l'avons vu, ce n'est pas toute l'histoire et un programme qui passe tout son temps à évaluer des fonctions spéciales peut ne pas sembler se rapprocher du pic, ce qui pourrait être vrai, mais ce n'est pas le cas pas utile pour vous dire que tout le temps est passé hors de votre contrôle sur le FPU.

Je suggère d'utiliser une bonne bibliothèque mathématique vectorielle comme base de référence (par exemple le VML d'Intel, une partie de MKL). Mesurez le nombre de cycles pour chaque appel et multipliez par les flops atteignables par crête sur ce nombre de cycles. Donc, si une exponentielle compressée prend 50 cycles à évaluer, comptez-la comme 100 flops fois la largeur du registre. Malheureusement, les bibliothèques de mathématiques vectorielles sont parfois difficiles à appeler et n'ont pas toutes les fonctions spéciales, vous pourriez donc finir par faire des mathématiques scalaires, auquel cas vous compteriez notre hypothétique exponentielle scalaire comme 100 flops (même si cela prend probablement encore 50 cycles, vous n'obtiendrez donc que 25% du "pic" si vous passez tout le temps à évaluer ces exponentielles).

Comme d'autres l'ont mentionné, vous pouvez compter les cycles et les compteurs d'événements matériels à l'aide de PAPI ou de diverses interfaces. Pour un comptage de cycle simple, vous pouvez lire le compteur de cycle directement en utilisant l' rdtscinstruction avec un extrait d'assemblage en ligne.

Vous pouvez les compter sur des systèmes réels en utilisant PAPI , qui accorde l'accès aux compteurs matériels et aux programmes de test simples. Mon interface / wrapper PAPI préféré est IPM (Integrated Performance Monitor) mais d'autres solutions existent ( TAU , par exemple). Cela devrait donner une comparaison de méthode à méthode assez stable.

Je vais répondre à cette question comme si vous aviez demandé:

"Comment comparer ou prédire analytiquement les performances d'algorithmes qui s'appuient fortement sur des fonctions spéciales, au lieu des décomptes FLOP traditionnels multiplier-ajouter-porter qui proviennent de l'algèbre linéaire numérique"

Je suis d'accord avec votre première prémisse, que les performances de nombreuses fonctions spéciales dépendent de l'architecture et que bien que vous puissiez généralement traiter chacune de ces fonctions comme ayant un coût constant, la taille de la constante variera, même entre deux processeurs du même mais avec des architectures différentes (voir le tableau de synchronisation des instructions d'Agner Fog pour référence).

Je ne suis pas d'accord, cependant, que la comparaison devrait se concentrer sur les coûts des opérations individuelles en virgule flottante. Je pense que le comptage des FLOP est dans une certaine mesure toujours utile, mais qu'il existe plusieurs considérations beaucoup plus importantes qui peuvent rendre le coût des fonctions spéciales moins pertinent lors de la comparaison de deux algorithmes potentiels, et ceux-ci doivent être explicitement examinés avant de passer à une comparaison de opérations en virgule flottante:

1. Évolutivité - Les algorithmes comportant des tâches qui peuvent être mises en œuvre efficacement sur des architectures parallèles domineront l'arène du calcul scientifique dans un avenir prévisible. Un algorithme avec une meilleure «évolutivité», que ce soit par une communication plus faible, un besoin moindre de synchronisation ou un meilleur équilibre de charge naturel, peut utiliser des fonctions spéciales plus lentes et donc être plus lents pour un petit nombre de processus, mais finira par rattraper le nombre. des processeurs est augmenté.

2. Localité temporelle de référence - L'algorithme réutilise-t-il les données entre les tâches, permettant au processeur d'éviter le trafic mémoire inutile? Chaque niveau de la hiérarchie de mémoire traversée par un algorithme ajoute un autre ordre de grandeur (approximativement) à chaque accès à la mémoire. En conséquence, un algorithme avec une densité élevée d'opérations spéciales sera probablement beaucoup plus rapide qu'un algorithme avec le nombre équivalent d'opérations de fonction simple sur une plus grande région de mémoire.

3. Empreinte mémoire - Ceci est fortement lié aux points précédents, mais à mesure que les ordinateurs grandissent de plus en plus, la quantité de mémoire par cœur tend en fait à la baisse. Une petite empreinte mémoire présente deux avantages. Le premier est qu'une petite quantité de données de programme sera probablement en mesure de tenir complètement dans le cache du processeur. La seconde est que, pour de très gros problèmes, un algorithme avec une empreinte mémoire plus petite peut être capable de s'adapter à la mémoire du processeur, permettant ainsi de résoudre des problèmes qui dépasseraient autrement la capacité de l'ordinateur.

Pourquoi prendre la peine de compter les flops? Il suffit de compter les cycles pour chaque opération et vous aurez quelque chose d'universel.