empaquetado de bits y compresión de estructuras de datos en informática científica

8

Recientemente me encontré con este artículo , que describe un esquema para ahorrar memoria al representar matrices dispersas. Un número entero de 32 bits puede almacenar números de hasta ~ 4 mil millones. Pero cuando resuelve un PDE, ha ido en paralelo y ha dividido el problema mucho antes de que el número de incógnitas se acerque a los 4 mil millones. Su idea es reordenar la matriz para un ancho de banda pequeño. En lugar de almacenar los índices jde todas las columnas distintas de cero en una fila dada i, almacenan el desplazamiento j - i, que tiende a ser de magnitud pequeña en virtud de la reordenación. Los desplazamientos se pueden almacenar utilizando menos bits que un entero de 32 bits. Hay más aritmética que hacer al iterar sobre las entradas distintas de cero de la matriz, pero los ahorros en menos caché pierden más que compensarlo. En este trabajoestaban buscando específicamente el uso de índices de 16 bits en un formato de matriz jerárquica, pero en última instancia, es una idea similar. También está la biblioteca zfp , que es más para comprimir datos de punto flotante.

Dado que los "flops son gratis" ahora y el cuello de botella es el acceso a la memoria, este tipo de trucos parecen realmente prometedores para hacer un mejor uso del caché de la CPU.

He revisado la mayoría de los trabajos citados / citados de estos dos artículos. Estoy buscando otras referencias sobre la efectividad del empaquetado de bits, la multiplicación escasa de vectores de matriz y cualquier otro problema en la ciencia computacional . Por ejemplo, imagino que podría diseñar estructuras de datos mucho más eficientes para gráficos o mallas no estructuradas utilizando esta idea.

Daniel Shapero
fuente

Respuestas:

7

Reducción de memoria para matrices dispersas

norte×nortenorte23×3

Puede encontrar una descripción más completa del formato aquí: http://www.netlib.org/utk/people/JackDongarra/etemplates/node375.html

Además, el almacenamiento de bloques densos en la matriz dispersa le permite vectorizar la multiplicación matriz-vector con instrucciones SSE o AVX, pero probablemente no verá una gran aceleración aquí porque, como notó, todavía estará vinculado a la memoria .

norte

https://bebop.cs.berkeley.edu/pubs/vuduc2005-ubcsr-split.pdf

Por supuesto, no hay nada que le impida jugar los juegos de empaquetado de bits con una matriz BCSR reordenada para reducir aún más el requisito de memoria, pero probablemente primero deba elegir la fruta más baja.

Empaque de bits en general

Si está específicamente interesado en aplicaciones de empaquetado de bits, esto se hace de manera agresiva en el proyecto LLVM. Una de sus ideas (¿inteligentes?) Es usar lo que llaman un PointerIntPair, que almacena un puntero y un entero pequeño juntos en el espacio de un solo puntero. La idea aquí es aprovechar el hecho de que (en los sistemas linux x64), los punteros devueltos por malloc están alineados a 16 bytes, lo que le da 4 bits en la parte inferior para hacer algo. Hacen todo tipo de locuras utilizando esta idea, construyendo estructuras de datos complejas que viven en el espacio de un solo puntero. Aquí hay una conferencia interesante dada hace unos años por uno de los optimizadores de LLVM. Comienza a hablar de esto a las 22:00. Sin embargo, una advertencia justa: esto fue en una conferencia de C ++, por lo que hay una gran cantidad de C ++ descaradamente complicado.

https://www.youtube.com/watch?v=vElZc6zSIXM&t=22m&ab_channel=CppCon

Tyler Olsen
fuente