2009年03月11日

bitsliceによる超高速ビット演算

はてなブックマークに登録

bitslice とは

Hack the Cell '09 に参加して知った、Cellに限らず一般的に使えるビット演算の高速化手法について紹介します。

Bitslice と呼ばれる手法では、ビット順を90度回転します。言葉で説明するよりもコードを見たほうが早いので、回転させるコードの例を見てください

int   x[32], y[32]; // x が元のデータ、y が回転後のデータ.
for (int i = 0; i < 32; ++i) {
    int t = 0;
    for (int j = 0; j < 32; ++j)
        t |= ((x[j] >> i) & 1) << j; // x[j] の i ビット目を
    y[i] = t;                        // y[i] の j ビット目にする
}

この変換をすることで、y[0] には x[0] - x[31] の最下位ビットが、 y[1] には 2番目のビットが格納されることになります。

回転することでビット演算が高速になる様を見てみます。

//--
// and 演算

// 通常
for (int i = 0; i < 32; ++i) {
    x[i] &= 3; // load, and, store, 各32回
}

// bitslice
for (int i = 2; i < 32; ++i) {
    y[i] = 0; // store 30回
}

//--
// xor 演算

// 通常
for (int i = 0; i < 32; ++i) {
    x[i] ^= 0xff; // load, xor, store, 各32回
}

// bitslice
for (int i = 0; i < 8; ++i) {
    y[i] = ~y[i]; // load, not, store 各8回
}

//--
// シフト演算
for (int i = 0; i < 32; ++i) {
    x[i] >>= 16; // load, 右シフト, store, 各32回
}

// bitslice
for (int i = 0; i < 16; ++i) {
    y[i] = y[i+16]; // load, store, 各16回
}

bitslice はなぜ速いか

無駄なビットに対する演算を省略できる

たとえば、 x ^= 1 (xは32bit整数) という演算は、最下位ビットを反転させているだけで、最下位以外の31bitにはまったく影響がありません。せっかくの32bit演算なのに、実質は1bit演算になってしまっているわけです。

bitslice なら最下位ビットだけを集めた32bitに対して演算するので、32bit演算の能力を無駄にすることがありません。

マスクがいらない

マスクは操作したくないビットを保護するためのものです。操作したいビットが集まっていれば、マスクが不要です。

マスク付きの通常ビット演算とbitsliceでの演算の対応は次のようになります。

  • and演算は、マスクビットが0の場所への 0 代入に
  • or演算は、マスクビットが1の場所への 1 代入に
  • xor演算は、マスクビットが1の場所への not 演算に

load が減る

普通の and や or 演算においてロードが必要なのは、操作しない(マスクされた)ビットを元の値にしておくためです。bitsliceでは全bitに1や0を代入できるので、不要な load を減らすことができます。

load が減るということは、単純に命令数が削減する以上の意味があります。一般的に言って、store命令は遅延して次の命令と並列に実行できるのに対して、load命令は完了するまでloadした値に依存する命令を実行できません。load命令が減ることで、パイプラインストールを減らすことができます。

工夫次第でさらに速く

先ほどの例では、通常のシフト演算を配列内での移動に置き換えていました。しかし、 y[i] = y[i+16] の代わりに y += 16 が許されるのであれば、シフト演算は完全に省略できることになります。

同じように or 演算でも、 y[i] = 0 をする代わりに、次に y[i] を参照する場所を 0 に置き換えることができるかもしれません。状況によって、いろいろな工夫が考えられます。

bitslice が苦手な計算

bitslice では各ビットがバラバラになっているので、ビット単位の演算は得意な代わりに、ビットをまたがる演算が苦手です。たとえば加算や減算は繰り上がりや繰り下がりがビットをまたぐので、bitsliceでは遅くなります。試しに加算を実装してみます

// 通常の演算
for (int i = 0; i < 32; ++i) {
    x[i] += z;
}

// bitslice
int carry = 0;
for (int i = 0; i < 32; ++i) {
    int c;
    c = (carry & y[i]) | (y[i] & z) | (z & carry);
    y[i] = carry ^ y[i] ^ z;
    carry = c;
}

ただし、特定の条件では通常の演算に近い速度が出せることもあります。次の例では、CPUに bitcnt() という bit が 1 になっている数を数える命令があると仮定して、配列の合計値を計算しています

// 通常の演算
int sum = x[0]; // load 1回
for (int i = 1; i < 32; ++i) {
    sum += x[i];  // load, add, 各31回
}

// bitslice
int sum = bitcnt(y[0]); // load, bitcnt, 各1回
for (int i = 1; i < 32; ++i) {
    sum += bitcnt(y[i]) << i; // load, bitcnt, shift, add 各31回
}

@methane
klab_gijutsu2 at 16:27│Comments(1)TrackBack(0)

トラックバックURL

この記事へのコメント

1. Posted by かたおか   2009年11月10日 14:06
C言語の規格では,右シフト演算は処理系依存ですので,例としては不適だと思いますし,挙げるにしても,上記は処理が不足していて,yがxの90度回転と同値になりません.
論理シフトが用いられる場合は,bitsliceのシフト演算の,
y[i] = y[i+16];
の後に,
y[i+16] = 0;
が必要です.
また,算術シフトが用いられる場合は,
y[i] = y[i+16];
の後に,
y[i+16] = y[31];
が必要です.

この記事にコメントする

名前:
URL:
  情報を記憶: 評価: 顔   
 
 
 
Blog内検索
Archives
このブログについて
DSASとは、KLab が構築し運用しているコンテンツサービス用のLinuxベースのインフラです。現在5ヶ所のデータセンタにて構築し、運用していますが、我々はDSASをより使いやすく、より安全に、そしてより省力で運用できることを目指して、日々改良に勤しんでいます。
このブログでは、そんな DSAS で使っている技術の紹介や、実験してみた結果の報告、トラブルに巻き込まれた時の経験談など、広く深く、色々な話題を織りまぜて紹介していきたいと思います。
最新コメント