Esta es la pseudo decodificación de mi presentación en !! Con 2019 .La mayoría de las arquitecturas de procesador en uso hoy en día tienen instrucciones llamadas
popcount , abreviatura de 'conteo de población'. Ella hace lo siguiente: cuenta el número de bits establecidos en una palabra de máquina. Por ejemplo (tomemos palabras de 8 bits por simplicidad),
popcount(00100110) es 3 y
popcount(01100000) es 2.
Puede sorprenderte mucho, como yo, ¡pero eso es todo lo que hace! Parece no muy útil, ¿verdad?
Pensé que esta era una adición reciente a algunos casos de uso hiperespecializados, pero en realidad ha estado presente en las arquitecturas de procesador desde al menos 1961:
Entonces, ¿qué está pasando?
Instrucción de la NSA
popcount también se conoce como la "instrucción NSA", y un
hilo muy interesante en comp.arch discute su uso en criptografía. Se rumorea que se agregó originalmente al conjunto de instrucciones de la CPU a pedido de la NSA. Como se indica en
este hilo de correo archivado :
Era casi una tradición enviar uno de cada lote de autos CDC más rápidos a un "buen cliente": llegó un camión desconocido y nunca más se supo de él.
Una gran leyenda, pero ¿por qué la usaron?
Una medida del contenido es
el peso de Hamming , que es el número de caracteres distintos de cero en una cadena. Para una cadena binaria, ¡esto es
popcount !
Como se
explica aquí , la NSA requirió criptoanálisis de mensajes interceptados, y dado que el CDC 6000 trabajó con palabras de 60 bits, una palabra fue suficiente para almacenar la mayoría de los alfabetos que les interesaban. Pudieron:
- Dividir mensaje en líneas
- Establecer un bit para cada personaje único en una cadena
- Use
popcount para contar la cantidad de caracteres diferentes
- Usa el contador como un hash para más análisis de criptoanálisis
Curiosamente,
popcount parece haber desaparecido de los conjuntos de instrucciones entre mediados de la década de 1970 y mediados de la década de 2000, por lo que el retorno debería explicarse por algo distinto a las aplicaciones criptográficas. ¿Para qué más se puede usar?
Corrección de errores
El concepto de peso de Hamming está relacionado con la
distancia de Hamming , que es el número de posiciones diferentes entre dos líneas de la misma longitud. Para dos cadenas binarias
x e
y , esto es solo
popcount después de XOR. Por ejemplo:
00100110
01100000 ^
--------
01000110
popcount (01000110) = 3
En aplicaciones de telecomunicaciones, esto ayuda a calcular la distancia de la señal, donde se transmite una palabra conocida a lo largo del cable y se cuenta el número de bits cambiados para estimar el error de transmisión.
Entonces podemos diseñar el
código de corrección de errores apropiado. Por ejemplo, si una transmisión debe soportar hasta dos bits modificados, las palabras de código deben diferir en al menos 5 en la distancia de Hamming.
Redes neuronales convolucionales binarias
Y ahora algo completamente diferente: ¡redes neuronales convolucionales binarias! Pero primero, ¿qué es?
- Binario significa que solo usamos matrices de valores +1 (codificados como 1) y -1 (codificados como 0), a diferencia de los valores de coma flotante de 32 bits.
- ¿La convolución significa multiplicación matricial?
- Las redes neuronales son sistemas inspirados en los cerebros de los animales (aquí estoy nadando un poco).
Por lo tanto, debemos realizar la multiplicación de matrices binarias. Pero, ¿qué tienen de especial las matrices binarias?
La multiplicación convencional de matrices por valores de 32 bits es muy adecuada para computadoras de escritorio con CPU y GPU potentes, pero cada vez más queremos hacer un trabajo útil en dispositivos pequeños y simples como teléfonos inteligentes, enrutadores, relojes inteligentes, etc. Podemos descomponerlos matrices más complejas para capas de matrices binarias, y es más fácil trabajar con ellas y almacenarlas que nos beneficiamos incluso a pesar del aumento en la cantidad de capas.
Aquí es
popcount entra en juego
popcount . Se utiliza para calcular el producto escalar de dos matrices binarias:
a = xnor (x, y)
b = popcount (a)
c = len (a)
punto (x, y) = 2 × b - c
Ver
aquí y
aquí para más detalles.
Programacion de ajedrez
Muchos programas de ajedrez almacenan datos en una representación de
tablero de bits , que se adapta convenientemente a una palabra de 64 bits. La operación
Population Count se utilizó para operaciones significativas con esta vista, como el cálculo de la
movilidad de una figura.
Huella molecular
Esto también está relacionado con la distancia de Hamming: las moléculas son de alguna manera desmenuzadas y comparadas (usando
popcount ) para determinar qué tan similares son. Ver
aquí para más detalles.
Intentos mapeados de matriz de hash (HAMT)
¡Aquí es donde aprendí por primera vez sobre
popcount ! HAMT es una estructura de datos (
creada por primera vez por Phil Bagwell ) que puede almacenar una gran cantidad de valores (generalmente 32 o 64) en una matriz en cada nodo trie. Sin embargo, asignar memoria para una matriz de 32 o 64 elementos puede ser un desperdicio increíble cada vez, especialmente si la matriz en realidad contiene solo unos pocos elementos. La solución es agregar una máscara de bits en la que el número de bits establecido corresponda con el número de elementos en la matriz, lo que permite que la matriz crezca y se contraiga según sea necesario. El cálculo del índice para un elemento dado se puede hacer efectivamente usando
popcount . En
mi publicación de blog sobre la implementación de estructuras HAMT, puede obtener más información sobre cómo funcionan.
Estructuras de datos comprimidos
Esta es una nueva área de investigación emocionante que se centra en cómo almacenar datos en un espacio mínimo sin desempacarlos para realizar un trabajo útil. Uno de los métodos es pensar en términos de matrices de bits (vectores de bits) que se pueden solicitar en dos operaciones:
rank(i) cuenta el número de bits dados hasta el índice i-ésimo en el vector de bits
select(i) encuentra el índice en el que se establece el bit i-ésimo
Para que estas operaciones sean eficientes en vectores de bits grandes, debe crear un índice y utilizarlo de manera efectiva, en ambos casos con
popcount . Aquí hay una buena descripción del índice RRR. Y, por lo que puedo decir, el enfoque moderno más avanzado se describe en el artículo
Estructuras de clasificación y selección de alto rendimiento y espacio eficiente en secuencias de bits sin comprimir .
Optimizaciones del compilador
popcount ha generalizado tanto que tanto
GCC como
Clang pueden detectarlo y reemplazarlo con una instrucción incorporada. Imagina este Clippy: "¡Oh, veo que estás intentando implementar
popcount , déjame salir y arreglarlo por ti!" El código LLVM correspondiente está
aquí . Daniel Lemyr lo cita como un ejemplo de la increíble mente de los compiladores modernos.
Conclusión
Envuelta en misterio al comienzo de su historia, la instrucción
popcount usarse en todas partes, aunque siguió siendo una instrucción de CPU un poco inusual. Me gusta la forma en que conecta áreas tan diferentes de la informática, y me pregunto cuántas instrucciones extrañas existen. Si tienes tu propio favorito, me gustaría saber de ella.