Dies ist die Pseudodekodierung meiner Präsentation auf der !! Con 2019 .Die meisten heute verwendeten Prozessorarchitekturen verfügen über Anweisungen namens
popcount , kurz für "Population Count". Sie macht Folgendes: Zählt die Anzahl der in einem Maschinenwort gesetzten Bits. Beispiel: Nehmen wir zur Vereinfachung 8-Bit-Wörter.
popcount(00100110) ist 3 und
popcount(01100000) ist 2.
Es mag dich sehr überraschen, genau wie ich, aber das ist alles, was sie tut! Scheint nicht sehr hilfreich, oder?
Ich dachte, dies sei eine neue Ergänzung zu einigen hyperspezialisierten Anwendungsfällen, aber es ist tatsächlich seit mindestens 1961 in Prozessorarchitekturen vorhanden:
Also, was ist los?
NSA-Anweisung
popcount auch als "NSA-Anweisung" bekannt, und ein
sehr interessanter Thread auf comp.arch diskutiert seine Verwendung in der Kryptographie. Gerüchten zufolge wurde es ursprünglich auf Anfrage der NSA zum CPU-Befehlssatz hinzugefügt. Wie in
diesem archivierten Mail-Thread angegeben :
Es war fast Tradition, eines von jeder Charge schnellerer CDC-Autos an einen „guten Kunden“ zu senden - ein unbekannter LKW kam an und wurde nie wieder gehört.
Eine großartige Legende, aber warum haben sie sie benutzt?
Ein Maß für den Inhalt ist
Hammings Gewicht ,
dh die Anzahl der Zeichen ungleich Null in einer Zeichenfolge. Für eine binäre Zeichenfolge ist dies
popcount !
Wie
hier erläutert , erforderte die NSA eine Kryptoanalyse abgefangener Nachrichten, und da der CDC 6000 mit 60-Bit-Wörtern arbeitete, reichte ein Wort aus, um die meisten Alphabete zu speichern, die sie interessierten. Sie konnten:
- Nachricht in Zeilen aufteilen
- Setzen Sie ein Bit für jedes eindeutige Zeichen in einer Zeichenfolge
- Verwenden Sie
popcount um die Anzahl der verschiedenen Zeichen zu zählen
- Verwenden Sie den Zähler als Hash für die weitere Kryptoanalyse
popcount scheint
popcount zwischen Mitte der 1970er und Mitte der 2000er Jahre aus den Befehlssätzen verschwunden zu sein, daher sollte die Rückkehr durch etwas anderes als kryptografische Anwendungen erklärt werden. Wofür kann es noch verwendet werden?
Fehlerbehebung
Das Konzept des Hamming-Gewichts bezieht sich auf den
Hamming-Abstand ,
dh die Anzahl der verschiedenen Positionen zwischen zwei Linien gleicher Länge. Für zwei binäre Zeichenfolgen
x und
y ist dies nur
popcount nach XOR. Zum Beispiel:
00100110
01100000 ^
--------
01000110
Popcount (01000110) = 3
In Telekommunikationsanwendungen hilft dies bei der Berechnung der Signalentfernung, bei der ein bekanntes Wort entlang der Leitung übertragen wird und die Anzahl der geänderten Bits gezählt wird, um den Übertragungsfehler abzuschätzen.
Dann können wir den entsprechenden
Fehlerkorrekturcode entwerfen. Wenn eine Übertragung beispielsweise bis zu zwei modifizierten Bits standhalten muss, sollten sich die Codewörter in der Hamming-Entfernung um mindestens 5 unterscheiden.
Binäre Faltungs-Neuronale Netze
Und jetzt etwas ganz anderes: binäre Faltungs-Neuronale Netze! Aber zuerst, was ist es?
- Binär bedeutet, dass wir im Gegensatz zu 32-Bit-Gleitkommawerten nur Matrizen mit den Werten +1 (als 1 codiert) und -1 (als 0 codiert) verwenden.
- Bedeutet Faltung Matrixmultiplikation?
- Neuronale Netze sind Systeme, die vom Gehirn von Tieren inspiriert sind (hier schwimme ich ein wenig).
Wir müssen also die Multiplikation von Binärmatrizen durchführen. Aber was ist das Besondere an binären Matrizen?
Die konventionelle Matrixmultiplikation mit 32-Bit-Werten eignet sich gut für Desktop-Computer mit leistungsstarken CPUs und GPUs. Immer häufiger möchten wir jedoch nützliche Arbeiten an kleinen und einfachen Geräten wie Smartphones, Routern, Smartwatches usw. ausführen. Wir können diese zerlegen komplexere Matrizen für Schichten von Binärmatrizen, und es ist so einfacher, mit ihnen zu arbeiten und sie zu speichern, dass wir trotz der Zunahme der Anzahl der Schichten davon profitieren.
Hier kommt
popcount ins Spiel. Es wird verwendet, um das Skalarprodukt zweier binärer Matrizen zu berechnen:
a = xnor (x, y)
b = Popcount (a)
c = len (a)
Punkt (x, y) = 2 × b - c
Weitere Details finden Sie
hier und
hier .
Schachprogrammierung
Viele Schachprogramme speichern Daten in einer
Bitboard- Darstellung, die bequem in ein 64-Bit-Wort passt. Die Operation "
Population Count wurde für sinnvolle Operationen mit dieser Ansicht verwendet, z. B. zur Berechnung der
Mobilität einer Figur.
Molekularer Fingerabdruck
Dies hängt auch mit der Hamming-Distanz zusammen: Die Moleküle werden irgendwie gehasht und verglichen (unter Verwendung von
popcount ), um festzustellen, wie ähnlich sie sind. Weitere Details finden Sie hier.
Hash-Array-Mapping-Versuche (HAMT)
Hier habe ich zum ersten Mal etwas über
popcount gelernt! HAMT ist eine Datenstruktur (
zuerst von Phil Bagwell erstellt ), die eine sehr große Anzahl von Werten (normalerweise 32 oder 64) in einem Array auf jedem Trie-Knoten speichern kann. Das Zuweisen von Speicher für ein Array mit 32 oder 64 Elementen kann jedoch jedes Mal unglaublich verschwenderisch sein, insbesondere wenn das Array tatsächlich nur wenige Elemente enthält. Die Lösung besteht darin, eine Bitmaske hinzuzufügen, bei der die Anzahl der gesetzten Bits der Anzahl der Elemente im Array entspricht, wodurch das Array nach Bedarf wachsen und sich zusammenziehen kann. Die Indexberechnung für ein bestimmtes Element kann effektiv mit
popcount . In
meinem Blogbeitrag zur Implementierung von HAMT-Strukturen erfahren Sie mehr über deren Funktionsweise.
Komprimierte Datenstrukturen
Dies ist ein aufregendes neues Forschungsgebiet, das sich darauf konzentriert, wie Daten auf kleinstem Raum gespeichert werden können, ohne sie für nützliche Arbeiten auszupacken. Eine der Methoden besteht darin, in Arrays von Bits (Bitvektoren) zu denken, die in zwei Operationen angefordert werden können:
rank(i) zählt die Anzahl der Bits, die bis zum i-ten Index im Bitvektor abgegeben wurden
select(i) findet den Index, an dem das i-te Bit gesetzt ist
Um diese Operationen für große Bitvektoren effizient zu gestalten, müssen Sie einen Index erstellen und effektiv verwenden, in beiden Fällen mit
popcount . Hier ist eine gute Übersicht über den RRR-Index. Und soweit ich das beurteilen kann, wird der fortschrittlichste moderne Ansatz im Artikel
Platzsparende, leistungsstarke Rank & Select-Strukturen für unkomprimierte Bitsequenzen beschrieben .
Compiler-Optimierungen
popcount ist so weit verbreitet, dass sowohl
GCC als auch
Clang es erkennen und durch eine integrierte Anweisung ersetzen können. Stellen Sie sich diesen Clippy vor: "Oh, ich sehe, dass Sie versuchen, Popcount zu implementieren, lassen Sie mich rausgehen und es für Sie reparieren!" Der entsprechende LLVM-Code ist
hier . Daniel Lemyr führt es als Beispiel für den erstaunlichen Geist moderner Compiler an.
Fazit
Der zu Beginn seiner Geschichte geheimnisvolle Popcount-Befehl wurde überall verwendet, obwohl er ein etwas ungewöhnlicher CPU-Befehl blieb. Ich mag die Art und Weise, wie es so unterschiedliche Bereiche der Informatik verbindet, und ich frage mich, wie viele andere so seltsame Anweisungen existieren. Wenn Sie Ihren eigenen Favoriten haben, würde ich gerne von ihr hören!