coût d'opération atomique

91

Quel est le coût de l'opération atomique (n'importe laquelle des opérations de comparaison et d'échange ou d'ajout / décrémentation atomique)? Combien de cycles consomme-t-il? Interrompra-t-il d'autres processeurs sur SMP ou NUMA, ou bloquera-t-il les accès à la mémoire? Videra-t-il le tampon de réorganisation dans le processeur en panne?

Quels seront les effets sur le cache?

Je m'intéresse aux processeurs modernes et populaires: x86, x86_64, PowerPC, SPARC, Itanium.

osgx
la source
@Jason S, Quelconque. Une différence entre cas et inc / dec atomique est négligeable.
osgx
2
Les opérations atomiques sur un x86 deviennent plus lentes à mesure que plus de conflits sont placés sur l'adresse mémoire. Je crois qu'en général, ils sont d'un ordre de grandeur plus lents que l'opération non verrouillée, mais cela variera clairement en fonction de l'opération, des conflits et des barrières de mémoire utilisées.
Stephen Nutt
hmmm. écrit semble être atomique sur x86. 'Comprendre le noyau Linux' -> spin_unlock
osgx
Une écriture 32 bits est atomique en Java, c'est-à-dire qu'elle est portative atomique (mais n'a pas de sémantique de barrière de mémoire, donc ce n'est souvent pas suffisant pour les pointeurs). L'ajout de 1 n'est normalement pas atomique, sauf si vous ajoutez le préfixe LOCK. A propos du noyau Linux, pas besoin de regarder spin_unlock. Voir, dans les versions actuelles, arch / x86 / include / asm / atomic_32.h (il s'agissait auparavant de include / asm-i386 / atomic.h).
Blaisorblade
@Blaisorblade, JAva n'est pas là. Quel est le coût des opérations BLOQUÉES?
osgx

Réponses:

60

J'ai recherché des données réelles ces derniers jours et je n'ai rien trouvé. Cependant, j'ai fait des recherches, qui comparent le coût des opérations atomiques avec les coûts des échecs de cache.

Le coût du préfixe x86 LOCK, (y compris lock cmpxchgpour atomic CAS), avant PentiumPro (comme décrit dans la doc), est un accès mémoire (comme un cache manquant), + l'arrêt des opérations mémoire par d'autres processeurs, + tout conflit avec d'autres processeurs essayant de VERROUILLER le bus. Cependant, depuis PentiumPro, pour la mémoire cache en réécriture normale (toute la mémoire traitée par une application, à moins que vous ne parliez directement avec le matériel), au lieu de bloquer toutes les opérations de mémoire, seule la ligne de cache appropriée est bloquée (en fonction du lien dans la réponse de @ osgx ) .

c'est-à-dire que le cœur retarde la réponse aux demandes de partage MESI et de RFO pour la ligne jusqu'à la fin de la partie stockage de l' lockopération d'édition réelle . Cela s'appelle un "verrou de cache" et n'affecte qu'une seule ligne de cache. D'autres cœurs peuvent charger / stocker ou même CASing d'autres lignes en même temps.


En fait, le cas CAS peut être plus compliqué, comme expliqué sur cette page , sans timing mais avec une description perspicace par un ingénieur de confiance. (Au moins pour le cas d'utilisation normal où vous effectuez un chargement pur avant le CAS réel.)

Avant d'entrer dans trop de détails, je dirai qu'une opération VERROUILLÉE coûte un manque de cache + le conflit possible avec un autre processeur sur la même ligne de cache, tandis que CAS + la charge précédente (qui est presque toujours requise sauf sur les mutex, où vous CAS 0 et 1) peuvent coûter deux erreurs de cache.

Il explique qu'un chargement + CAS sur un seul emplacement peut en fait coûter deux échecs de cache, comme Load-Linked / Store-Conditional (voir ici pour ce dernier). Son explication repose sur la connaissance du protocole de cohérence du cache MESI . Il utilise 4 états pour une ligne de cache: M (odifié), E (xclusive), S (hared), I (nvalid) (et donc il s'appelle MESI), expliqué ci-dessous si nécessaire. Le scénario, expliqué, est le suivant:

  • le LOAD provoque un échec du cache - la ligne de cache correspondante est chargée à partir de la mémoire dans l'état partagé (c'est-à-dire que d'autres processeurs sont toujours autorisés à garder cette ligne de cache en mémoire; aucun changement n'est autorisé dans cet état). Si l'emplacement est en mémoire, cet échec de cache est ignoré. Coût possible: 1 cache manquée. (ignoré si la ligne de cache est à l'état partagé, exclusif ou modifié, c'est-à-dire que les données sont dans le cache L1 de cette CPU).
  • le programme calcule les nouvelles valeurs à stocker,
  • et il exécute une instruction CAS atomique.
    • Il doit éviter les modifications simultanées, il doit donc supprimer des copies de la ligne de cache du cache des autres processeurs, pour déplacer la ligne de cache vers l'état Exclusif. Coût possible: 1 cache manquée. Cela n'est pas nécessaire s'il est déjà en propriété exclusive, c'est-à-dire à l'état Exclusif ou Modifié. Dans les deux états, aucun autre processeur ne détient la ligne de cache, mais dans l'état exclusif, il n'a pas (encore) été modifié.
    • Après cette communication, la variable est modifiée dans le cache local de notre CPU, à quel point elle est globalement visible par tous les autres CPU (car leurs caches sont cohérents avec le nôtre). Il sera éventuellement écrit dans la mémoire principale selon les algorithmes habituels.
    • Les autres processeurs essayant de lire ou de modifier cette variable devront d'abord obtenir cette ligne de cache en mode partagé ou exclusif et, pour ce faire, contacteront ce processeur et recevront la version mise à jour de la ligne de cache. Une opération verrouillée, à la place, ne peut coûter qu'un échec de cache (car la ligne de cache sera demandée directement à l'état exclusif).

Dans tous les cas, une demande de mise en cache peut être bloquée par d'autres processeurs modifiant déjà les données.

Blaisorblade
la source
pourquoi changer d'état sur d'autres cpus coûte 1 cache manquant?
osgx
1
Parce que c'est une communication en dehors du CPU, et donc plus lente que d'accéder au cache. Alors qu'un manque de cache doit de toute façon passer par d'autres processeurs. En fait, il se peut que parler avec un autre processeur soit plus rapide que de parler avec la mémoire, si une interconnexion directe est utilisée, comme AMD Hypertransport (depuis il y a très longtemps), ou Intel QuickPath Interconnect d'Intel, sur les tout derniers processeurs Xeon basé sur Nehalem. Sinon, la communication avec les autres CPU se fait sur le même FSB que celui pour la mémoire. Recherchez HyperTransport et Front Side Bus sur Wikipedia pour plus d'informations.
Blaisorblade
Wow, je n'ai jamais pensé que le sien était si cher - un échec de cache peut durer quelques milliers de cycles.
Lothar
2
Vraiment? Le chiffre auquel je suis habitué est: une centaine de cycles pour les échecs de cache, et des milliers de cycles pour les commutateurs de contexte / privilège (y compris les appels système).
Blaisorblade
1
Le manque de cache n'est pas quelques milliers de cycles! Son environ 100ns, ce qui correspond généralement à 300-350 cycles CPU ....
user997112
37

J'ai fait un profilage avec la configuration suivante: la machine de test (AMD Athlon64 x2 3800+) a été démarrée, commutée en mode long (interruptions désactivées) et l'instruction d'intérêt a été exécutée en boucle, 100 itérations déroulées et 1000 cycles de boucle. Le corps de la boucle était aligné sur 16 octets. Le temps a été mesuré avec une instruction rdtsc avant et après la boucle. De plus, une boucle fictive sans aucune instruction a été exécutée (qui mesurait 2 cycles par itération de boucle et 14 cycles pour le reste) et le résultat a été soustrait du résultat du temps de profilage des instructions.

Les instructions suivantes ont été mesurées:

  • " lock cmpxchg [rsp - 8], rdx" (avec correspondance de comparaison et non-correspondance),
  • " lock xadd [rsp - 8], rdx",
  • " lock bts qword ptr [rsp - 8], 1"

Dans tous les cas, le temps mesuré était d'environ 310 cycles, l'erreur d'environ +/- 8 cycles

Il s'agit de la valeur pour une exécution répétée sur la même mémoire (mise en cache). Avec un manque de cache supplémentaire, les temps sont considérablement plus élevés. De plus, cela a été fait avec un seul des 2 cœurs actifs, le cache était donc la propriété exclusive et aucune synchronisation du cache n'était nécessaire.

Pour évaluer le coût d'une instruction verrouillée sur un échec de cache, j'ai ajouté une wbinvldinstruction avant l'instruction verrouillée et mis le wbinvldplus un add [rsp - 8], raxdans la boucle de comparaison. Dans les deux cas, le coût était d'environ 80 000 cycles par paire d'instructions! En cas de verrouillage bts, le décalage horaire était d'environ 180 cycles par instruction.

Notez qu'il s'agit du débit réciproque, mais comme les opérations verrouillées sont des opérations de sérialisation, il n'y a probablement aucune différence de latence.

Conclusion: une opération verrouillée est lourde, mais un manque de cache peut être beaucoup plus lourd. Aussi: une opération verrouillée n'entraîne pas d'erreurs de cache. Il ne peut générer du trafic de synchronisation du cache que lorsqu'une ligne de cache n'est pas la propriété exclusive.

Pour démarrer la machine, j'ai utilisé une version x64 de FreeLdr du projet ReactOS. Voici le code source asm:

#define LOOP_COUNT 1000
#define UNROLLED_COUNT 100

PUBLIC ProfileDummy
ProfileDummy:

    cli

    // Get current TSC value into r8
    rdtsc
    mov r8, rdx
    shl r8, 32
    or r8, rax

    mov rcx, LOOP_COUNT
    jmp looper1

.align 16
looper1:

REPEAT UNROLLED_COUNT
    // nothing, or add something to compare against
ENDR

    dec rcx
    jnz looper1

    // Put new TSC minus old TSC into rax
    rdtsc
    shl rdx, 32
    or rax, rdx
    sub rax, r8

    ret

PUBLIC ProfileFunction
ProfileFunction:

    cli

    rdtsc
    mov r8, rdx
    shl r8, 32
    or r8, rax
    mov rcx, LOOP_COUNT

    jmp looper2

.align 16
looper2:

REPEAT UNROLLED_COUNT
    // Put here the code you want to profile
    // make sure it doesn't mess up non-volatiles or r8
    lock bts qword ptr [rsp - 8], 1
ENDR

    dec rcx
    jnz looper2

    rdtsc
    shl rdx, 32
    or rax, rdx
    sub rax, r8

    ret
Timo
la source
Merci! Pouvez-vous publier votre code de test ou tester vous-même Core2 / Core i3 / i5 / i7? Tous les cœurs ont-ils été initialisés dans votre configuration de test?
osgx
J'ai ajouté le code source. Un seul cœur a été initialisé. J'adorerais voir les résultats d'autres machines.
Timo
CLFLUSH devrait être un moyen beaucoup plus léger de vider une ligne de cache que WBINVD de l'ensemble du cache. WBINVD videra également les caches d'instructions, ce qui entraînera des erreurs de cache supplémentaires.
Peter Cordes
Peut-être intéressant de tester le cas de la ligne de cache étant chaude dans l'état partagé. Vous pouvez y arriver en demandant à un autre thread de le lire avec une charge pure.
Peter Cordes le
4

Sur le SMP basé sur le bus, le préfixe atomique LOCKaffirme (active) un signal de fil de bus LOCK#. Cela interdira à d'autres processeurs / périphériques sur le bus de l'utiliser.

Livre Ppro & P2 http://books.google.com/books?id=3gDmyIYvFH4C&pg=PA245&dq=lock+instruction+pentium&lr=&ei=_E61S5ehLI78zQSzrqwI&cd=1#v=onepage&q=lock%20instruction%20pentium&f= 24 pages

Les instructions verrouillées sont des opérations de sérialisation, de synchronisation .... / about Out-of-order / verrouillé RMW / read-modify-write = atomic lui-même / instruction garantit que le processeur exécutera toutes les instructions avant l'instruction verrouillée avant de l'exécuter. / à propos des écritures encore non vidées / il force toutes les écritures publiées dans le processeur à être vidées dans la mémoire externe avant d'exécuter l'instruction suivante.

/ à propos de SMP / sémaphore est dans le cache à l'état S ... émettant une transaction de lecture et d'invalidation pour 0 octet de date (il s'agit d'un kill / de copies partagées de la ligne de cache dans les processeurs adjacents /)

osgx
la source