4

スライディング対角ベクトルには 16 個の要素が含まれ、それぞれが 8 ビットの符号なし整数です。

SSE と少し単純化されていなければ、C では次のようになります。

int width=1000000; // a big number
uint8_t matrix[width][16];
fill_matrix_with_interesting_values(&matrix);

for (int i=0; i < width - 16; ++i) {
  uint8_t diagonal_vector[16];
  for (int j=0; j<16; ++j) {
    diagonal_vector[j] = matrix[i+j][j];
  }
  do_something(&diagonal_vector);
}

_mm_load_si128しかし、私の場合、組み込み関数を使用してマトリックスから列方向 (垂直方向) にのみロードできます。スライディング対角ベクトルは水平方向に移動するため、事前に 16 列ベクトルをロードし、それらの各列ベクトルから 1 つの要素を使用して対角ベクトルを作成する必要があります。

SSE を使用して、これを低メモリで高速に実装することは可能ですか?

2016 年 11 月 14 日更新:いくつかの詳細を提供します。私の場合、FASTA 形式のテキスト ファイルから 1 文字コードを読み取ります。各文字は特定のアミノ酸を表します。各アミノ酸には、それに関連付けられた特定の列ベクトルがあります。その列ベクトルは、定数テーブル ( BLOSUM行列) から検索されます。Cコードでは、次のようになります

while (uint8_t c = read_next_letter_from_file()) {
   column_vector = lookup_from_const_table(c)
   uint8_t diagonal_vector[16];
   ... rearrange the values from the latest column
       vectors into the diagonal_vector ...

   do_something(&diagonal_vector)
}
4

1 に答える 1

3

これから紹介する実装では、反復ごとに 1 つの列の読み込みのみが必要です。まず、いくつかの変数を初期化します

const __m128i mask1=_mm_set_epi8(0,0,0,0,0,0,0,0,255,255,255,255,255,255,255,255);
const __m128i mask2=_mm_set_epi8(0,0,0,0,255,255,255,255,0,0,0,0,255,255,255,255);
const __m128i mask3=_mm_set_epi8(0,0,255,255,0,0,255,255,0,0,255,255,0,0,255,255);
const __m128i mask4=_mm_set_epi8(0,255,0,255,0,255,0,255,0,255,0,255,0,255,0,255);
__m128i v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14, v15;

次に、各ステップで変数v_column_loadが次の列に読み込まれます。

v15 = v_column_load;
v7 = _mm_blendv_epi8(v7,v15,mask1);
v3 = _mm_blendv_epi8(v3,v7,mask2);
v1 = _mm_blendv_epi8(v1,v3,mask3);
v0 = _mm_blendv_epi8(v0,v1,mask4);
v_diagonal = v0;

次のステップではv0、v1、v3、v7、の変数名番号v15が 1 ずつ増分され、0 ～ 15 の範囲になるように調整されます。つまり、newnumber = ( oldnumber + 1 ) modulo 16 です。

v0 = v_column_load;
v8 = _mm_blendv_epi8(v8,v0,mask1);
v4 = _mm_blendv_epi8(v4,v8,mask2);
v2 = _mm_blendv_epi8(v2,v4,mask3);
v1 = _mm_blendv_epi8(v1,v2,mask4);
v_diagonal = v1;

16 回の反復の後v_diagonal、正しい対角値が含まれるようになります。

mask1、mask2、mask3、を見るとmask4、このアルゴリズムを他のベクトル長 (2^n) に一般化するために使用できるパターンがわかります。

たとえば、ベクトルの長さが 8 の場合、必要なマスクは 3 つだけで、反復ステップは次のようになります。

v7 = a a a a a a a a
v6 =
v5 =
v4 =
v3 =         a a a a
v2 =
v1 =             a a
v0 =               a

v0 = b b b b b b b b
v7 = a a a a a a a a
v6 =
v5 =
v4 =         b b b b
v3 =         a a a a
v2 =             b b
v1 =             a b

v1 = c c c c c c c c
v0 = b b b b b b b b
v7 = a a a a a a a a
v6 =
v5 =         c c c c
v4 =         b b b b
v3 =         a a c c
v2 =           a b c

v2 = d d d d d d d d
v1 = c c c c c c c c
v0 = b b b b b b b b
v7 = a a a a a a a a
v6 =         d d d d
v5 =         c c c c
v4 =         b b d d
v3 =         a a c d

v3 = e e e e e e e e
v2 = d d d d d d d d
v1 = c c c c c c c c
v0 = b b b b b b b b
v7 = a a a a e e e e
v6 =         d d d d
v5 =     a a c c e e
v4 =       a b b d a

v4 = f f f f f f f f
v3 = e e e e e e e e
v2 = d d d d d d d d
v1 = c c c c c c c c
v0 = b b b b f f f f
v7 = a a a a e e e e
v6 =     b b d d f f
v5 =     a b c d e f

v5 = g g g g g g g g
v4 = f f f f f f f f
v3 = e e e e e e e e
v2 = d d d d d d d d
v1 = c c c c g g g g
v0 = b b b b f f f f
v7 = a a c c e e g g
v6 =   a b c d e f g

v6 = h h h h h h h h
v5 = g g g g g g g g
v4 = f f f f f f f f
v3 = e e e e e e e e
v2 = d d d d h h h h
v1 = c c c c g g g g
v0 = b b d d f f h h
v7 = a b c d e f g h  <-- this vector now contains the diagonal

v7 = i i i i i i i i
v6 = h h h h h h h h
v5 = g g g g g g g g
v4 = f f f f f f f f
v3 = e e e e i i i i
v2 = d d d d h h h h
v1 = c c e e g g i i
v0 = b c d e f g h i  <-- this vector now contains the diagonal

v0 = j j j j j j j j
v7 = i i i i i i i i
v6 = h h h h h h h h
v5 = g g g g g g g g
v4 = f f f f j j j j
v3 = e e e e i i i i
v2 = d d f f h h j j
v1 = c d e f g h i j  <-- this vector now contains the diagonal

補足: Smith-Waterman アルゴリズムの実装に取り​​組んでいたときに、対角ベクトルをロードするこの方法を発見しました。古い SourceForge プロジェクトのWeb ページで、さらに詳しい情報を見つけることができます。

于 2013-03-04T09:12:42.957 に答える