SSE2

| コメント(0)

例えば 128 ビットのキャリ付き整数加算ルーチンを x86 用の GCC で普通に書くとこんな感じです。

typedef struct {
  int dw[4];
} xmml;

int xmmladc(xmml *z, xmml *x, xmml *y, int c_in) {
  int c_out;
  asm volatile("negl    %0" : : "a" (c_in));  //下位からのキャリ
  asm volatile("movl    %0, %%eax" : : "m" (x->dw[0]) : "ax");
  asm volatile("adcl    %0, %%eax" : : "m" (y->dw[0]) : "ax");
  asm volatile("movl    %%eax, %0" : "=m" (z->dw[0]));
  asm volatile("movl    %0, %%eax" : : "m" (x->dw[1]) : "ax");
  asm volatile("adcl    %0, %%eax" : : "m" (y->dw[1]) : "ax");
  asm volatile("movl    %%eax, %0" : "=m" (z->dw[1]));
  asm volatile("movl    %0, %%eax" : : "m" (x->dw[2]) : "ax");
  asm volatile("adcl    %0, %%eax" : : "m" (y->dw[2]) : "ax");
  asm volatile("movl    %%eax, %0" : "=m" (z->dw[2]));
  asm volatile("movl    %0, %%eax" : : "m" (x->dw[3]) : "ax");
  asm volatile("adcl    %0, %%eax" : : "m" (y->dw[3]) : "ax");
  asm volatile("movl    %%eax, %0" : "=m" (z->dw[3]));
  asm volatile("setc    %%al" : : : "ax");
  asm volatile("movzbl  %%al, %0" : "=a" (c_out));  //上位へのキャリ
  return c_out;
}

同じ処理を 128 ビットの並列整数演算ができる SSE2(Pentium4 に実装されているストリーミング SIMD 拡張命令 2)を使って無理矢理書いたらこうなりました。

int xmmladc(xmml *z, xmml *x, xmml *y, int c_in) {
  int c_out;
  asm volatile("movdqa  %0, %%xmm0" : : "m" (*x));
  asm volatile("movdqa  %0, %%xmm1" : : "m" (*y));
  asm volatile("movdqa  %xmm0, %xmm2");
  asm volatile("pxor    %xmm1, %xmm2");  //xmm0^xmm1
  asm volatile("paddd   %xmm1, %xmm0");  //xmm0+xmm1
  asm volatile("movdqa  %xmm0, %xmm3");
  asm volatile("pandn   %xmm2, %xmm3");  //~(xmm0+xmm1)&(xmm0^xmm1)
  asm volatile("pandn   %xmm1, %xmm2");  //~(xmm0^xmm1)&xmm1
  asm volatile("por     %xmm3, %xmm2");  //~(xmm0^xmm1)&xmm1|~(xmm0+xmm1)&(xmm0^xmm1)
  asm volatile("psrad   $31, %xmm2");    //キャリ(0 or -1)
  asm volatile("movdqa  %xmm2, %xmm1");  //最上位のキャリを保存
  asm volatile("pslldq  $4, %xmm1");     //キャリを1つ上の位へ
  asm volatile("pxor    %xmm3, %xmm3");
  asm volatile("pinsrw  $0, %0, %%xmm3" : : "r" (c_in));  //下位からのキャリ
  asm volatile("psubd   %xmm3, %xmm1");  //下位からのキャリを合体
  asm volatile("psubd   %xmm1, %xmm0");  //キャリを加算
  asm volatile("pxor    %xmm3, %xmm3");
  asm volatile("pcmpeqd %xmm0, %xmm3");
  asm volatile("pand    %xmm3, %xmm1");  //キャリを加えた結果が0のところだけ-1 最大4個
  asm volatile("pmovmskb        %%xmm1, %%ecx" : : : "cx");  //xmm0!=0のところは0
  asm volatile("jecxz   skip");          //キャリがなくなったので終了
  asm volatile("movdqa  %xmm1, %xmm0");
  asm volatile("por     %xmm1, %xmm2");  //最上位のキャリを加算
  asm volatile("pslldq  $4, %xmm1");     //キャリを1つ上の位へ
  asm volatile("psubd   %xmm1, %xmm0");  //キャリを加算
  asm volatile("pxor    %xmm3, %xmm3");
  asm volatile("pcmpeqd %xmm0, %xmm3");
  asm volatile("pand    %xmm3, %xmm1");  //キャリを加えた結果が0のところだけ-1 最大3個
  asm volatile("por     %xmm1, %xmm2");  //最上位のキャリを加算
  asm volatile("pslldq  $4, %xmm1");     //キャリを1つ上の位へ
  asm volatile("psubd   %xmm1, %xmm0");  //キャリを加算
  asm volatile("pxor    %xmm3, %xmm3");
  asm volatile("pcmpeqd %xmm0, %xmm3");
  asm volatile("pand    %xmm3, %xmm1");  //キャリを加えた結果が0のところだけ-1 最大2個
  asm volatile("por     %xmm1, %xmm2");  //最上位のキャリを加算
  asm volatile("pslldq  $4, %xmm1");     //キャリを1つ上の位へ
  asm volatile("psubd   %xmm1, %xmm0");  //キャリを加算
  asm volatile("pxor    %xmm3, %xmm3");
  asm volatile("pcmpeqd %xmm0, %xmm3");
  asm volatile("pand    %xmm3, %xmm1");  //キャリを加えた結果が0のところだけ-1 最大1個
  asm volatile("por     %xmm1, %xmm2");  //最上位のキャリを加算
  asm volatile("skip:");
  asm volatile("psrldq  $12, %xmm2");    //最上位のキャリを最下位へ
  asm volatile("psrld   $31, %xmm2");    //キャリが確定
  asm volatile("movdqa  %%xmm0, %0" : "=m" (*z));
  asm volatile("pextrw  $0, %%xmm2, %0" : "=r" (c_out));  //上位へのキャリ
  return c_out;
}

あまり深く考えていないので無駄やバグがあると思いますが、最初に書いた x86 用のコードよりも速くすることはどうやっても不可能です。128 ビットすべてにデータを充填することを諦めればこれよりも少し速くできますが、それでも最初のコードには及びません。

SSE2 にはキャリ付き整数加算命令および符号なし整数比較命令が存在しないので、数倍から数十倍程度の多倍長整数演算に SSE2 はまったく役に立ちません。

コメントする

この記事について

このページは、kamadoxが2003年2月25日 12:01に書いた記事です。

ひとつ前の記事は「SSE2」です。

次の記事は「GMP-ECM 5.0」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ

ウェブページ

Powered by Movable Type 6.3.3