C'est le pseudo décodage de ma présentation à !! Con 2019 .La plupart des architectures de processeur utilisées aujourd'hui ont des instructions appelées
popcount , abréviation de «population count». Elle fait ce qui suit: compte le nombre de bits définis dans un mot machine. Par exemple (prenons des mots de 8 bits pour simplifier),
popcount(00100110) est 3 et
popcount(01100000) est 2.
Cela peut vous surprendre énormément, tout comme moi, mais c'est tout ce qu'elle fait! Semble pas très utile, non?
Je pensais que c'était un ajout récent à certains cas d'utilisation hyperspécialisés, mais il est en fait présent dans les architectures de processeur depuis au moins 1961:
Alors qu'est-ce qui se passe?
Instruction NSA
popcount également connu comme «l'instruction NSA», et un
fil très intéressant sur comp.arch discute de son utilisation en cryptographie. La rumeur veut qu'il ait été initialement ajouté au jeu d'instructions CPU à la demande de la NSA. Comme indiqué dans
ce fil de discussion archivé :
C'était presque une tradition d'envoyer un de chaque lot de voitures CDC plus rapides à un «bon client» - un camion inconnu est arrivé et n'a plus jamais été entendu.
Une grande légende, mais pourquoi l'ont-ils utilisée?
Une mesure du contenu est
le poids de Hamming , qui est le nombre de caractères non nuls dans une chaîne. Pour une chaîne binaire, c'est
popcount !
Comme
expliqué ici , la NSA a exigé une cryptanalyse des messages interceptés, et puisque le CDC 6000 fonctionnait avec des mots de 60 bits, un mot était suffisant pour stocker la plupart des alphabets qui les intéressaient. Ils ont pu:
- Diviser le message en lignes
- Définissez un bit pour chaque caractère unique d'une chaîne
- Utilisez
popcount pour compter le nombre de caractères différents
- Utilisez le compteur comme hachage pour poursuivre la cryptanalyse
Curieusement,
popcount semble avoir disparu des jeux d'instructions entre le milieu des années 1970 et le milieu des années 2000, donc le retour devrait être expliqué par autre chose que des applications cryptographiques. À quoi d'autre peut-il servir?
Correction d'un bug
Le concept de poids de Hamming est lié à la
distance de Hamming , qui est le nombre de positions différentes entre deux lignes de même longueur. Pour deux chaînes binaires
x et
y , il s'agit juste d'un
popcount après XOR. Par exemple:
00100110
01100000 ^
--------
01000110
popcount (01000110) = 3
Dans les applications de télécommunication, cela aide à calculer la distance du signal, où un mot connu est transmis le long du fil et le nombre de bits modifiés est compté pour estimer l'erreur de transmission.
Ensuite, nous pouvons concevoir le
code de correction d'erreur approprié. Par exemple, si une transmission doit supporter jusqu'à deux bits modifiés, les mots de code doivent différer d'au moins 5 en distance de Hamming.
Réseaux de neurones convolutifs binaires
Et maintenant quelque chose de complètement différent: les réseaux de neurones convolutifs binaires! Mais d'abord, c'est quoi?
- Binaire signifie que nous n'utilisons que des matrices des valeurs +1 (codées en 1) et -1 (codées en 0), contrairement aux valeurs à virgule flottante 32 bits.
- La convolution signifie-t-elle une multiplication matricielle?
- Les réseaux de neurones sont des systèmes inspirés du cerveau des animaux (ici je nage un peu).
Ainsi, nous devons effectuer la multiplication des matrices binaires. Mais quelle est la particularité des matrices binaires?
La multiplication matricielle conventionnelle par des valeurs 32 bits est bien adaptée aux ordinateurs de bureau dotés de processeurs et de GPU puissants, mais nous souhaitons de plus en plus souvent effectuer des travaux utiles sur de petits appareils simples comme les smartphones, les routeurs, les montres intelligentes, etc. Nous pouvons les décomposer. des matrices plus complexes pour les couches de matrices binaires, et il est tellement plus facile de travailler avec elles et de les stocker que nous en bénéficions même malgré l'augmentation du nombre de couches.
C'est
popcount entre en jeu. Il est utilisé pour calculer le produit scalaire de deux matrices binaires:
a = xnor (x, y)
b = popcount (a)
c = len (a)
point (x, y) = 2 × b - c
Voir
ici et
ici pour plus de détails.
Programmation d'échecs
De nombreux programmes d'échecs stockent des données dans une représentation
bitboard , qui s'intègre facilement dans un mot 64 bits. L'opération
Population Count été utilisée pour des opérations significatives avec cette vue, telles que le calcul de la
mobilité d'une figure.
Empreinte moléculaire
Cela est également lié à la distance de Hamming: les molécules sont en quelque sorte hachées et comparées (à l'aide de
popcount ) pour déterminer leur similitude. Voir
ici pour plus de détails.
Essais mappés de tableau de hachage (HAMT)
C'est là que j'ai
popcount pour la première
popcount ! HAMT est une structure de données (d'
abord créée par Phil Bagwell ) qui peut stocker un très grand nombre de valeurs (généralement 32 ou 64) dans un tableau sur chaque nœud de trie. Cependant, l'allocation de mémoire pour un tableau de 32 ou 64 éléments peut être incroyablement inutile à chaque fois, surtout si le tableau ne contient en fait que quelques éléments. La solution consiste à ajouter un masque de bits dans lequel le nombre de bits défini correspond au nombre d'éléments dans le tableau, ce qui permet au tableau de croître et de se contracter selon les besoins. Le calcul de l'indice pour un élément donné peut effectivement être effectué à l'aide de
popcount . Dans
mon article de blog sur la mise en œuvre des structures HAMT, vous pouvez en savoir plus sur leur fonctionnement.
Structures de données compressées
Il s'agit d'un nouveau domaine de recherche passionnant qui se concentre sur la façon de stocker des données dans un espace minimal sans les déballer pour effectuer un travail utile. L'une des méthodes consiste à penser en termes de tableaux de bits (vecteurs de bits) qui peuvent être demandés en deux opérations:
rank(i) compte le nombre de bits abandonnés au i-ème indice dans le vecteur de bits
select(i) trouve l'indice auquel le i-ème bit est positionné
Pour rendre ces opérations efficaces sur des vecteurs de gros bits, vous devez créer un index et l'utiliser efficacement, dans les deux cas impliquant un
popcount . Voici un bon aperçu de l'indice RRR. Et, pour autant que je sache, l'approche moderne la plus avancée est décrite dans l'article
Structures de classement et de sélection performantes et peu encombrantes sur les séquences de bits non compressées .
Optimisations du compilateur
popcount est devenu si répandu que
GCC et
Clang sont capables de le détecter et de le remplacer par une instruction intégrée. Imaginez ce Clippy: "Oh, je vois que vous essayez d'implémenter
popcount , laissez-moi sortir et le réparer pour vous!" Le code LLVM correspondant est
ici . Daniel Lemyr le cite comme un exemple de l'esprit étonnant des compilateurs modernes.
Conclusion
Entourée de mystère au début de son histoire, l'instruction
popcount être utilisée partout, bien qu'elle soit restée un peu inhabituelle. J'aime la façon dont il relie ces différents domaines de l'informatique, et je me demande combien d'autres instructions étranges existent. Si vous avez votre propre favori, j'aimerais entendre parler d'elle!