# ThreadSpotter

ThreadSpotter est un outil qui diagnostique les problèmes de performances liés à la localité des données, à l'utilisation du cache et à l'interaction des threads.
De manière générale, la bande passante du bus mémoire n'a pas connu les mêmes améliorations que les augmentations de performances des CPU (une observation parfois appelée memory wall (en)), et avec les systèmes multi-cœur, la bande passante disponible est partagée entre tous les cœurs. Cela fait de la préservation de cette bande passante l'une des tâches les plus importantes à accomplir afin d'obtenir des performances optimales.
ThreadSpotter détermine les schémas des modèles d'accès mémoire sous-optimaux et leur applique une heuristique afin de les catégoriser, d'en expliquer les causes et de proposer des pistes d'améliorations du code.
L'outil dispose de capacités prédictives permettant de modéliser les caractéristiques des performances d'un code en fonction d'une architecture donnée (taille de cache, modèle de processeur...). Cette possibilité d'analyse autorise l'exploration de différents scénarios à partir d'un échantillonnage unique.

## Localité spatiale

La Localité Spatiale fait référence à la propriété avantageuse d'accéder à des emplacements mémoires proches les uns des autres. Une faible localité spatiale est pénalisante pour différentes raisons :
* Accéder à des données très éparpillées aura pour conséquence négative de transférer des données inutiles puisque ces données transitent par blocs (chunks). Cela accroît les besoins en bande passante mémoire et impose dans la pratique des limites de performances et d'évolutivité de l'application.
* Des données inutiles vont occuper les caches, réduisant ainsi leur taille effective. Cela cause des évictions plus fréquentes et davantage d'accès à la mémoire.
* Les données non utilisées vont réduire la probabilité de rencontrer plus d'un élément de données utile dans une ligne de cache mappée.
ThreadSpotter indique lorsqu'au moins l'un des points suivants devient pénalisant en matière de Localité Spatiale :
* Utilisation du Fetching
* Écriture différée
* Boucles imbriquées
* Partitionnement de boucles (aussi connu sous le nom de loop tiling (en))
* Fusion de boucles (en) (spatiale)

## Localité temporelle

La Localité Temporelle fait référence à la réutilisation des données. Réutiliser des données alors qu'elles sont encore dans le cache diminue la quantité de fetchs nécessaires et réduit généralement la charge du bus mémoire. ThreadSpotter classe ces possibilités d'optimisation en :
* Partitionnement temporel
* Fusion de boucles (en) (temporelle)

## Latence mémoire

Le temps qu'il faut pour initier un chargement mémoire (memory fetch) est appelé latence mémoire. Pendant ce temps, le CPU est bloqué. La pénalité induite par cette latence est de l'ordre de 100 cycles d'horloge.
Les caches ont été conçus pour masquer de tels problèmes, en traitant une quantité limitée de données à partir d'une mémoire de petite taille, mais extrêmement rapide. Cette méthode est efficace si l'ensemble des données peut être contraint à être contenu dans le cache.
Il existe une autre technique appelée préchargement mémoire (memory prefetch), où le transfert de données est effectué explicitement ou automatiquement avant que celles-ci ne soient requises. L'objectif est de faire que ces données soient déjà présentes dans le cache avant qu'elles ne soient sollicitées.
ThreadSpotter identifie dans ce domaine les problèmes suivants :
* Instruction de préchargement trop proche de l'utilisation des données
* Instruction de préchargement trop éloignée de l'utilisation des données (les données peuvent être évincées avant usage)
* Instruction de préchargement inutile (car les données sont déjà présentes dans le cache)
De plus, l'outil évalue l'efficacité du mécanisme matériel de préchargement (hardware prefetcher) en modélisant son comportement et en enregistrant les cas de :
* Schémas d'accès mémoire irréguliers

## Éviter la pollution du cache

Si les données occupent une quantité de mémoire plus grande que le cache disponible et qu'il n'y a pas de manière pratique de réorganiser les schémas d'accès pour améliorer la réutilisation des données, alors il n'y a aucun avantage à stocker en premier lieu ces données dans le cache. Certains processeurs disposent à cet effet d'instructions spéciales permettant de contourner l'utilisation des caches.
ThreadSpotter trouve des opportunités de :
* Remplacer les instructions d'écriture avec des instructions d'écriture non-temporelles.
* Insérer des instructions de prefetching non-temporel afin d'éviter que les données ne soient mappées dans des caches de plus haut niveau.

## Cohérence de cache

Lorsqu'il y a plusieurs caches dans un système, la consistance des uns envers les autres doit être assurée. Les activités gérant cette cohérence des données prennent un certain temps pour être menées à bien. De la même manière qu'il est important d'observer les propriétés de localité dans la façon dont vous accédez aux emplacements de la mémoire vive, il est important de prêter attention et de limiter le trafic lié à cette cohérence.
Par exemple, dans un scénario producteur / consommateur où deux threads utilisent un morceau de mémoire partagée pour transférer des données entre elles, le propriétaire de cette mémoire va à plusieurs reprises passer de cache producteur à cache consommateur. Si toutes les données dans une ligne de cache ne sont pas entièrement consommées, mais que le producteur visite à nouveau la ligne de cache, alors on est dans le cas d'un modèle de communication pauvre. Il serait plus approprié de remplir la ligne de cache dans son intégralité avant de la remettre au consommateur.

## Interaction des threads

Si deux threads utilisent chacun leur propre variable, mais si ces variables sont amenées à partager une même ligne de cache, alors son appartenance va tour à tour passer d'un thread à l'autre. Ce problème peut généralement être résolu en forçant les variables à ne pas résider sur la même ligne de cache. ThreadSpotter identifie ce phénomène comme cas de :
* Faux partage (en)

## Effets du partage de cache

Pour les CPU disposant de plusieurs niveaux de caches, leur topologie est parfois asymétrique dans le sens où le coût de communication entre deux caches de même niveau n'est pas uniforme.