coût de l'opération atomique

StackOverflow https://stackoverflow.com/questions/2538070

Question

Quel est le coût de l'opération atomique (toute de comparer et-swap ou ajouter / décrément atomique)? Comment les cycles coûte-t-il consommer? Est-il une pause d'autres processeurs sur SMP ou NUMA, ou il va bloquer les accès mémoire? Est-ce que ce tampon de réordonnancement de chasse en hors-commande CPU?

Quels sont les effets seront sur le cache?

Je suis intéressé par les processeurs modernes, populaires. X86, x86_64, PowerPC, SPARC, Itanium

Était-ce utile?

La solution

Je l'ai cherché des données réelles pour les jours, et n'a rien trouvé. Cependant, je l'ai fait quelques recherches, qui compare le coût des opérations atomiques des coûts de défauts de cache.

Le coût du préfixe x86 LOCK, ou CAS, avant PentiumPro (tel que décrit dans le document), est un accès à la mémoire (comme un défaut de cache), + arrêt des opérations de mémoire par d'autres processeurs, + toute prétention avec d'autres processeurs essayer pour verrouiller le bus. Cependant, depuis PentiumPro, pour Writeback (c.-à-cacheable) mémoire (toute la mémoire une traite d'applications avec, à moins que vous parlez directement avec le matériel), au lieu de bloquer toutes les opérations de mémoire, seul le cacheline concerné est bloqué (basé sur le lien affiché ci-dessus).

En fait, le cas CAS peut être plus compliqué, comme expliqué à la cette page , sans timings, mais une description perspicace par un ingénieur digne de confiance.

Avant d'entrer dans trop de détails, je vais dire qu'une opération coûte LOCKED un cache miss + l'affirmation possible avec un autre processeur sur le même cacheline, tandis que CAS + la charge précédente (qui est presque toujours nécessaire sauf le mutex, où vous CAS toujours 0 et 1) peut coûter deux défauts de cache.

Il explique qu'une charge + CAS sur un seul emplacement peut coûter en fait deux erreurs de cache, comme Load-Linked / stockage conditionnel (voir là pour ce dernier). Son explication repose sur la connaissance du . Il utilise 4 états pour un cacheline: M (odified), E (Xclusive), S (Hared), I (NVALID) (et donc on l'appelle MESI), expliqué ci-dessous en cas de besoin. Le scénario, a expliqué, est le suivant:

  • la charge provoque un manque de cache - la cacheline correspondant est chargé de la mémoire dans l'état partagé (à savoir d'autres processeurs sont toujours autorisés à garder en mémoire que cacheline, aucune modification ne sont pas admis dans cet état). Si l'emplacement est en mémoire, ce défaut de cache est ignorée. Coût possible:.. 1 cache miss (si le sautée cacheline est partagée, de l'état exclusif ou modifié, à savoir les données dans le cache L1 de cette CPU)
  • le programme calcule les nouvelles valeurs pour stocker,
  • et il exécute une instruction CAS atomique.
    • Il doit éviter une modification concurrente, il doit retirer les copies du cacheline du cache des autres processeurs, pour déplacer le cacheline à l'état exclusif. coût possible. 1 cache miss Ce n'est pas nécessaire si elle est déjà la propriété exclusive, à savoir dans l'état exclusif ou modifié. Dans les deux Etats, pas d'autres unités centrales détiennent la cacheline, mais dans l'état exclusif, il n'a pas été modifié (encore).
    • Après cette communication, la variable est modifiée dans notre cache local de CPU, à quel point il est globalement visible à tous les autres processeurs (parce que leurs caches sont cohérentes avec les nôtres). Il sera finalement écrit à la mémoire principale en fonction d'algorithmes habituels.
    • D'autres processeurs tentent de lire ou de modifier cette variable doivent d'abord obtenir que cacheline en mode partagé ou exclusif, et de le faire communiquera avec ce processeur et recevoir la version mise à jour du cacheline. Une opération LOCKED, au contraire, ne peut coûter un manque de cache (parce que le cacheline sera demandé directement dans l'état exclusif).

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

Autres conseils

J'ai fait quelques profils avec la configuration suivante: La machine d'essai (AMD Athlon64 X2 3800+) a été démarré, passé en mode longue (interruptions désactivées) et l'instruction d'intérêt a été exécuté dans une boucle, 100 itérations déroulèrent et 1000 boucle cycles. Le corps de la boucle a été alignée à 16 octets. Le temps a été mesurée à l'aide d'une instruction rdtsc avant et après la boucle. En outre, une boucle factice sans instruction a été exécutée (qui mesurait 2 cycles par itération de la boucle et 14 cycles pour le repos) et le résultat a été soustrait du résultat du temps de profilage d'instruction.

Les instructions suivantes ont été mesurées:

  • "lock cmpxchg [rsp - 8], rdx" (les deux avec correspondance de comparaison et non-concordance),
  • "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 était d'environ +/- 8 cycles

est la valeur pour l'exécution répétée sur la même (en cache) mémoire. Avec un manque de cache supplémentaire, les temps sont considérablement plus élevés. Aussi cela a été fait avec un seul des 2 noyaux actifs, de sorte que le cache appartenait exclusivement, et pas synchonisation de cache était nécessaire.

Pour évaluer le coût d'une instruction verrouillé sur un défaut de cache, j'ai ajouté une instruction de wbinvld avant l'instruction verrouillé et mis le wbinvld plus un add [rsp - 8], rax dans la boucle de comparaison. Dans les deux cas, le coût était d'environ 80 000 cycles par paire d'instructions! En cas de blocage bts la différence de temps est d'environ 180 cycles par instruction.

Notez que ceci est le débit réciproque, mais étant donné que les opérations sont verrouillées opérations sérialisation, il n'y a probablement pas de différence de temps d'attente.

Conclusion: une opération de verrouillage est lourd, mais un manque de cache peut être beaucoup plus lourd. En outre: une opération de verrouillage ne provoque pas de manque de cache. Il ne peut provoquer un trafic de synchronisation du cache, lorsqu'un cacheline n'appartient pas exclusivement.

Pour démarrer la machine, j'ai utilisé une version 64 bits 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

Le SMP à base de bus, LOCK préfixe atomique n'assert (activer) un signal fil de bus LOCK#. Elle interdira d'autres unités centrales / périphériques sur le bus pour 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 = fausses pages 244-246

  

instructions sont Locked sérialisation, synchronisation opérations ....   / About Out-of-order / verrouillée RMW / lecture-modification-écriture lui-même = / instruction atomique en sorte que le processeur exécute toutes les instructions avant que l'instruction de verrouillage avant de l'exécuter.   / About mais pas rincée écrit / elle oblige tous affichés écrit dans le processeur pour être envoyé à la mémoire externe avant d'exécuter l'instruction suivante.

     

/ sur les SMP / sémaphores est en cache dans l'état S ... l'émission d'une lecture et d'invalider la transaction pour 0 octets de jour (ce qui est une mise à mort / des copies partagées de la ligne de cache dans les CPU adjacentes /)

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top