2

行数が非常に多いNx3ビットマトリックスを使用しています。 典型的なマトリックスは次のようになります N2^40

000
001
010
011
...

私はこのようなことをします

transform_row(5); //return 000
transform_row(10); //return 101
assemble_array(000,101); 
//return a 10x3 matrix, where:
//row 5: 000
//row 10: 101
//the other rows wait for the other iteration to be filled

...//repeat

initial_matrixmyとの両方のビット パターンtransformed_matrixは、非常に冗長であるか、非常に予備的です。たとえば、最初の列は のみで0ある場合もあれば、 の巨大なブロックが存在する場合もあります1。

この状況で組み立てて効率的に圧縮するためのオプションは何ですか?
独自のアセンブル アルゴリズムを使用する必要がありますか、それとも圧縮ライブラリを使用できますか?
このシーケンシャルな状況で圧縮ライブラリが効率的に機能するかどうかわからないため、自作を考えています。

assemble_arrayGPUで並列実行しています。
したがって、関数はスレッドセーフで、連想的で可換である必要があります。

bit_matrix_transform.cu

bit_matrix initial_matrix;
first=0;
last=2^40;
UnaryFunction bit_vector transform_row::operator(long row_index);
BinaryFunction bit_matrix assemble_array::operator(bit_array x, bit_array y);
bit_matrix transformed_matrix = thrust::transform_reduce(first, last, transform_row, init, assemble_array);
//a bit_array being either a bit_vector or a bit_matrix
4

1 に答える 1

1

配列の単純なランレングス表現から始めます。ここでは、2^40 ゼロのランとして初期化されます。(または、ゼロが空と異なる場合は、-1 または 8 を使用します。) 最初のランレングス表現は、単純に 2^40, 0 です。要素を挿入すると、ランが 2 つに分割されます。したがって、位置 n に 111 を配置するには (カウントをゼロから開始)、n, 0, 1, 7, 2^40-n-1, 0 を取得します。最初の 111 の隣に別の 111 を挿入すると、 a run: n, 0, 2, 7, 2^40-n-2, 0 など。

3 ビット レベルよりもビット レベルでより多くの相関がある場合は、これを 3 回 (ビットの列ごとに 1 回) 実行します。

于 2012-05-30T15:36:28.183 に答える