Plusieurs threads et cache CPU

Je suis en train d’implémenter une opération de filtrage d’images en C en utilisant plusieurs threads et en la rendant aussi optimisée que possible. J’ai cependant une question: si une mémoire est accédée par thread-0 et simultanément si la même mémoire est accédée par thread-1, sera-t-elle extraite du cache? Cette question découle de la possibilité que ces deux threads s’exécutent dans deux cœurs différents du processeur. Donc, une autre façon de le dire est la suivante: tous les cœurs partagent-ils la même mémoire cache commune?

Supposons que j’ai une disposition de la mémoire comme celle-ci

int output [100];

Supposons qu’il y a 2 cœurs de processeur et que par conséquent, je crée deux threads pour qu’ils fonctionnent simultanément. Un schéma pourrait consister à diviser la mémoire en deux morceaux, 0-49 et 50-99, et laisser chaque thread fonctionner sur chaque morceau. Une autre solution pourrait consister à laisser thread-0 fonctionner sur des indices pairs, tels que 0 2 4, etc., tandis que l’autre thread fonctionnera sur des indices impairs tels que 1 3 5 …. Cette dernière technique est plus facile à implémenter données), mais je ne suis pas sûr de pouvoir utiliser efficacement le cache de cette manière.

En général, il est déconseillé de partager des régions de mémoire qui se chevauchent, comme si un thread traitait les processus 0,2,4 … et les autres processus 1,3,5 … Bien que certaines architectures puissent supporter cela, la plupart des architectures ne le feraient pas. vous ne pouvez probablement pas spécifier sur quelles machines votre code sera exécuté. De plus, le système d’exploitation est libre d’affecter votre code à n’importe quel cœur (un seul, deux sur le même processeur physique ou deux cœurs sur des processeurs distincts). De plus, chaque processeur a généralement un cache de premier niveau distinct, même s’il se trouve sur le même processeur.

Dans la plupart des situations, 0,2,4 … / 1,3,5 … ralentira les performances de manière extrêmement lente, voire même plus lente qu’un processeur. Herb Sutters “Eliminer le faux partage” le montre très bien.

L’utilisation des schémas [… n / 2-1] et [n / 2 … n] permettra une meilleure adaptation à la plupart des systèmes. Cela peut même conduire à des performances super linéaires puisque la taille du cache de tous les processeurs peut éventuellement être utilisée. Le nombre de threads utilisés doit toujours être configurable et correspondre par défaut au nombre de cœurs de processeur trouvés.

La réponse à cette question dépend fortement de l’architecture et du niveau de cache, ainsi que de l’emplacement réel des threads.

Par exemple, les processeurs multicœurs Intel récents ont un cache L1 par cœur et un cache L2 partagé entre des cœurs appartenant au même package de processeurs; Cependant, différents packages de CPU auront leurs propres caches L2.

Même dans le cas où vos threads s’exécutent sur deux cœurs au sein d’un même package, si les deux threads accèdent aux données de la même cacheline, cette dernière se répercutera entre les deux caches L1. Ceci est très inefficace et vous devez concevoir votre algorithme pour éviter cette situation.


Quelques commentaires ont demandé comment éviter ce problème.

Au fond, ce n’est vraiment pas particulièrement compliqué: vous voulez simplement éviter que deux threads essaient simultanément d’accéder à des données situées sur la même ligne de cache, où au moins un thread écrit dans les données. (Tant que tous les threads ne lisent que les données, il n’y a pas de problème – sur la plupart des architectures, des données en lecture seule peuvent être présentes dans plusieurs caches).

Pour ce faire, vous devez connaître la taille de la ligne de cache – cela varie selon l’architecture, mais actuellement, la plupart des puces des familles x86 et x86-64 utilisent une ligne de cache de 64 octets (consultez votre manuel d’architecture pour les autres architectures). Vous aurez également besoin de connaître la taille de vos structures de données.

Si vous demandez à votre compilateur d’aligner la structure de données partagée d’intérêt sur une limite de 64 octets (votre output tableau, par exemple), vous saurez qu’elle commencera au début d’une ligne de cache et vous pourrez également calculer l’emplacement de la structure suivante. les limites de la ligne de cache sont. Si votre int est de 4 octets, chaque cacheline contiendra exactement 8 valeurs. Tant que le tableau commence sur une limite de cacheline, la output[0] travers la output[7] sera sur une ligne de cache et la output[8] travers la output[15] sur la suivante. Dans ce cas, vous concevriez votre algorithme de sorte que chaque thread fonctionne sur un bloc de valeurs int adjacentes qui est un multiple de 8.

Si vous struct types de struct compliqués plutôt que plain int , l’utilitaire pahole sera utile. Il parsingra les types de struct dans votre binary compilé et vous montrera la mise en page (y compris le remplissage) et la taille totale. Vous pouvez ensuite ajuster vos struct aide de cette sortie. Par exemple, vous pouvez append manuellement un remplissage afin que votre struct soit un multiple de la taille de la ligne de cache.

Sur les systèmes POSIX, la fonction posix_memalign() est utile pour allouer un bloc de mémoire avec un alignement spécifié.

Je me trompe peut-être, mais le fait que le cache du kernel soit partagé ou non dépend de la mise en œuvre du processeur. Il vous faudrait consulter les fiches techniques sur la page du fabricant pour vérifier si chaque cœur de votre CPU dispose de son propre cache ou s’il a été partagé.

Je travaillais également sur la manipulation d’images pour une entreprise de sécurité et nous obtenions parfois des images corrompues après l’exécution d’opérations de traitement par lots sur des threads. Après de longues investigations, nous sums arrivés à la conclusion que le cache était partagé entre les CPU et que, dans de rares cas, les données étaient écrasées ou remplacées par des données incorrectes.

Je ne peux pas répondre à la question de savoir si cela doit être pris en compte ou s’il s’agit plutôt d’un événement rare.