compactação de bits e compactação de estruturas de dados em computação científica

8

Recentemente, me deparei com este artigo , que descreve um esquema para economizar memória na representação de matrizes esparsas. Um número inteiro de 32 bits pode armazenar números de até ~ 4 bilhões. Mas quando você resolve um PDE, fica paralelo e particiona o problema muito antes de o número de incógnitas chegar perto dos 4 bilhões. A idéia deles é reordenar a matriz para uma largura de banda pequena. Em vez de armazenar os índices jde todas as colunas diferentes de zero em uma determinada linha i, eles armazenam o deslocamento j - i, que tende a ser pequeno em magnitude em virtude da reordenação. As compensações podem ser armazenadas usando menos bits do que um número inteiro de 32 bits. Há mais aritmética a ser feita ao iterar sobre entradas diferentes de zero da matriz, mas a economia em menos cache perde mais do que compensando isso. No presente trabalhoeles estavam olhando especificamente para usar índices de 16 bits em um formato de matriz hierárquica, mas, no final das contas, é uma ideia semelhante. Há também a biblioteca zfp , que é mais para compactar dados de ponto flutuante.

Como os "fracassos estão livres" agora e o gargalo é o acesso à memória, esses tipos de truques parecem realmente promissores para um melhor uso do cache da CPU.

Examinei a maioria dos trabalhos citados / citados desses dois artigos. Estou procurando outras referências sobre a eficácia do empacotamento de bits, multiplicação esparsa de vetores matriciais e outros problemas da ciência computacional . Por exemplo, imagino que você poderia projetar estruturas de dados muito mais eficientes para gráficos ou malhas não estruturadas usando essa idéia.

Daniel Shapero
fonte

Respostas:

7

Reduzindo a memória para matrizes esparsas

n×nn23×3

Uma descrição mais completa do formato pode ser encontrada aqui: http://www.netlib.org/utk/people/JackDongarra/etemplates/node375.html

Além disso, o armazenamento de blocos densos na matriz esparsa permite vetorizar a multiplicação de vetores matriciais com instruções SSE ou AVX, mas você provavelmente não verá uma grande aceleração aqui porque, como observou, ainda estará vinculado à memória .

n

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

Obviamente, não há nada que o impeça de jogar os jogos de empacotamento de bits com uma matriz BCSR reorganizada para reduzir ainda mais os requisitos de memória, mas você provavelmente deve escolher primeiro os frutos mais baixos.

Empacotamento de bits em geral

Se você está especificamente interessado em aplicativos de empacotamento de bits, isso é feito de forma agressiva no projeto LLVM. Uma de suas idéias (inteligentes?) É usar o que chamam de PointerIntPair, que armazena um ponteiro e um pequeno número inteiro juntos no espaço de um único ponteiro. A idéia aqui é aproveitar o fato de que (nos sistemas linux x64), os ponteiros retornados pelo malloc são alinhados em 16 bytes, o que fornece 4 bits na parte inferior para fazer algo. Eles fazem todo tipo de coisa maluca usando essa idéia, construindo estruturas de dados complexas que vivem no espaço de um único ponteiro. Aqui está uma interessante conferência realizada há alguns anos por um dos otimizadores do LLVM. Ele começa a falar sobre isso às 22:00. Porém, um aviso justo: foi em uma conferência em C ++, portanto há uma grande quantidade de C ++ complicada descaradamente complicada.

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

Tyler Olsen
fonte