単純な遷移ルールによる2次元セル・オートマトンである Conway's Game of Life（ライフ・ゲーム）の次世代状態計算を行う高速なアルゴリズムを調査・考案・実装・評価した。
ビットボード演算により８近傍のON状態数をカウントすることで、条件分岐をまったく使用せず多くのビットをパラレルに処理することができる。
本稿では32ビット長までの実装・計測を行なったが、レジスタのビット数に比例した処理速度を得ることが出来るので、
SSE の128ビットレジスタを使用すれば、テーブルを引く方法のように多量のメモリを使用することもなく、さらに4倍程度の高速化も可能である。
bd' = (bd & s2) | s3 （※ s2は8近傍の生きているセル数が2、s3 は 3）
┏━━━━━━━━━━━┓
┃ 番人 ┃
┃ ┌────────┬┨
┃ │・(0, 0) │┃パディング
┃ │ │┃(w が T のサイズの倍数で無い場合）
┃ │ │┃
┃ │ (w-1,h-1)・│┃
┃ └────────┴┸━┓
┃ 番人 ┃
┗━━━━━━━━━━━━━┛
← hSize →
int offset = (x + 1) / 8 + (y + 1) * hSize;
int mask = 0x80 >> (x & 7);
std::vector<byte> buffer2; // 結果を一時的に保存するバッファ（予め作成しておく）
for(int y = 0; y < h; ++y) {
for(int x = 0; x < w; ++x) {
const int cnt = // 8近傍の状態がONのセル数を求める
(pixel(x - 1, y - 1) ? 1: 0) +
(pixel(x, y - 1) ? 1: 0) +
(pixel(x + 1, y - 1) ? 1: 0) +
(pixel(x - 1, y) ? 1: 0) +
(pixel(x + 1, y) ? 1: 0) +
(pixel(x - 1, y + 1) ? 1: 0) +
(pixel(x, y + 1) ? 1: 0) +
(pixel(x + 1, y + 1) ? 1: 0);
bool b = cnt == 3 || cnt == 2 && pixel(x, y);
setPixel2(x, y, b); // 結果を buffer2 に設定
}
}
buffer.swap(buffer2); // バッファを交換
8ビットまとめて計算すれば、単純に言えば8倍高速になる。64ビット や 128ビットまとめて計算すれば、恐ろしく高速になる。 （※ 実際には余分な処理が入るので、単純にビット数倍高速にはならない）
０│０１１０００１０│１
─┼────────┼─
０│０１００１１００│０ // 注目箇所・周辺の生データ
─┼────────┼─
０│１０１１００００│１
↓ ８近傍データに変換
ａ: ００１１０００１
ｂ: ０１１０００１０
ｃ: １１０００１０１
ｄ: ００１００１１０
ｅ: １００１１０００
ｆ: ０１０１１０００
ｇ: １０１１００００
ｈ: ０１１００００１
＋ ----------------
３４５４２２２３ // ビットごとの１の数
↓
s0: ００００００００
s1: ００００００００
s2: ００００１１１０
s3: １００００００１
s4: ０１０１００００
s5: ００１０００００
s6: ００００００００
s7: ００００００００
s8: ００００００００
↓ s3 | (bd & s2)
bd: １０００１１０１
s2 = a & b;
s1 = a ^ b;
s0 = ~(a | b); // a と b の加算、論理演算回数：４
s3 = s2 & c;
s2 = (s2 & ~c) | (s1 & c);
s1 = (s1 & ~c) | (s0 & c);
s0 &= ~c; // c を加算、論理演算回数：１１（９）
s3 = (s3 & ~d) | (s2 & d);
s2 = (s2 & ~d) | (s1 & d);
s1 = (s1 & ~d) | (s0 & d);
s0 &= ~d; // d を加算、論理演算回数：１４（１１）
s3 = (s3 & ~e) | (s2 & e);
s2 = (s2 & ~e) | (s1 & e);
s1 = (s1 & ~e) | (s0 & e);
s0 &= ~e; // e を加算、論理演算回数：１４（１１）
s3 = (s3 & ~f) | (s2 & f);
s2 = (s2 & ~f) | (s1 & f);
s1 = (s1 & ~f) | (s0 & f);
s0 &= ~f; // f を加算、論理演算回数：１４（１１）
s3 = (s3 & ~g) | (s2 & g);
s2 = (s2 & ~g) | (s1 & g);
s1 = (s1 & ~g) | (s0 & g);
//s0 &= ~g; // g を加算、論理演算回数：１２（１０）
s3 = (s3 & ~h) | (s2 & h);
s2 = (s2 & ~h) | (s1 & h);
//s1 = (s1 & ~h) | (s0 & h);
//s0 &= ~h; // h を加算、論理演算回数：８（７）
template<typename T>
T nextGeneration(byte UL, T U, byte UR, byte L, T bd, byte R, byte DL, T D, byte DR)
{
const int MSB = 0x80 << (sizeof(T)*8 - 1);
T a = (U >> 1) | (!(UL & 0x01) ? 0 : MSB);
T b = U;
T c = (U << 1) | (!(UL & 0x80) ? 0 : 1);
T d = (bd >> 1) | (!(L & 0x01) ? 0 : MSB);
T e = (bd << 1) | (!(L & 0x80) ? 0 : 1);
T f = (D >> 1) | (!(DL & 0x01) ? 0 : MSB);
T g = D;
T h = (D << 1) | (!(DL & 0x80) ? 0 : 1);
a～h から s2, s3 を計算;
return (bd & s2) | s3;
}
┏━━━━━━━━━━━━━┓
┃ 番人 ┃
┃ ┌──────────┬┨
┃ │ ┌─┬───┬─┐ │┃
┃ │ │UL│ U │UR│ │┃
┃ │ ├─┼───┼─┤ │┃
┃ │ │L │ bd │R │ │┃
┃ │ ├─┼───┼─┤ │┃
┃ │ │DL│ D │DR│ │┃
┃ │ └─┴───┴─┘ │┃
┃ └──────────┴┸━┓
┃ 番人 ┃
┗━━━━━━━━━━━━━━━┛
s2 = ~b3 & ~b2 & b1 & ~b0;
s3 = ~b3 & ~b2 & b1 & b0;
ａ: ００１１０００１
ｂ: ０１１０００１０
ｃ: １１０００１０１
ｄ: ００１００１１０
ｅ: １００１１０００
ｆ: ０１０１１０００
ｇ: １０１１００００
ｈ: ０１１００００１
＋ ----------------
３４５４２２２３ // ビットごとの１の数
↓
b2: ０１１１００００
b1: １０００１１１１
b0: １０１００００１
↓
s2: ００００１１１０
s3: １００００００１
b0 = a ^ b; b1 = a & b; b2 = 0; // a と b を加算、論理演算回数：２ x = b0 & c; // 桁上り b0 ^= c; b2 ^= b1 & x; b1 ^= x; // c を加算、論理演算回数：５ x = b0 & d; b0 ^= d; b2 ^= b1 & x; b1 ^= x; // d を加算、論理演算回数：５ x = b0 & e; b0 ^= e; b2 ^= b1 & x; b1 ^= x; // e を加算、論理演算回数：５ x = b0 & f; b0 ^= f; b2 ^= b1 & x; b1 ^= x; // f を加算、論理演算回数：５ x = b0 & g; b0 ^= g; b2 ^= b1 & x; b1 ^= x; // g を加算、論理演算回数：５ x = b0 & h; b0 ^= h; b2 ^= b1 & x; b1 ^= x; // h を加算、論理演算回数：５ x = ~b2 & b1; // 共通部分 s2 = x & ~b0; s3 = x & b0; // s2, s3 を計算、論理演算回数：５
// a + b → (xab a), c + d → (xcd c),… を計算、論理演算回数：２＊４＝８ xab = a & b; // a + b の上位ビット a ^= b; xcd = c & d; c ^= d; xef = e & f; e ^= f; xgh = g & h; g ^= h; // (xab a) + (xcd c) → (c b a) 論理演算回数：５ d = a & c; a ^= c; c = xab & xcd; // b2 が１になるのは (1 0) + (1 0) の時のみ b = xab ^ xcd ^ d; // (xef e) + (xgh g) → (g f e) 論理演算回数：５ h = e & g; e ^= g; g = xef & xgh; // b2 が１になるのは (1 0) + (1 0) の時のみ f = xef ^ xgh ^ h; // (c b a) + (g f e) → (c b a) 論理演算回数：９ d = a & e; a ^= e; h = b & f; b ^= f; h |= b & d; // d は b0 からの桁上り b ^= d; c ^= g ^ h; // 論理演算回数：５ x = ~c & b; s2 = x & ~a; s3 = x & a;
ａ: ００１１０００１
ｂ: ０１１０００１０
ｃ: １１０００１０１
ｄ: ００１００１１０
ｅ: １００１１０００
ｆ: ０１０１１０００
ｇ: １０１１００００
ｈ: ０１１００００１
↓ ビットごとにソート
ａ: ００００００００
ｂ: ００００００００
ｃ: ００００００００
ｄ: ００１０００００
ｅ: ０１１１００００
ｆ: １１１１０００１
ｇ: １１１１１１１１
ｈ: １１１１１１１１
x = a & ~b; // a == 1, b == 0 の場合のみ 1 とする
a ^= x;
b ^= x; // 論理演算回数：４回
| 方式 | 処理時間（ミリ秒） |
|---|---|
| 定義通りに処理 1ピクセル単位 | 24 (total: 97, iterations: 4) |
| 8近傍→s3～s0（順次計算） ８bit単位 | 5.4 (total: 87, iterations: 16) |
| 8近傍→b2～b0（分割計算）→s3,s2 ８bit単位 | 4.7 (total: 76, iterations: 16) |
| 8近傍→b2～b0（分割計算）→s3,s2 32bit単位 | 1.0 (total: 69, iterations: 64) |
┌────────┐ １セルごとに定義どおりに処理（非ビットボード）約72命令/pixel
│１次元配列データ│─────────────────────────────────┐
└────────┘ │
│ │
│各配列要素について処理 │
↓ │
┌───────────────┐ │
│UL, U, UR, L, bd, R, DL, D, DR│注目データの８近傍生データ │
└───────────────┘ │
│ │
│シフト（6）と論理演算（18） │
↓ │
┌───────────┐ │
│a, b, c, d, e, f, g, h│各ビットごとの８近傍データ │
└───────────┘ │
│ │
│ビットごとに直接加算 │
├────────────────────────────────┐ │
│ │ │
│s2, s3 のみを直接的に計算 │ │
├───────────────────────────────→│ │
│ │ │
│s0～s3 (s4～s8) を順に計算（63論理演算） │ │
├───────────────────────────────→│ │
│ │ │
│b0～b2 を ((…(a+b)+c)+d)+… で計算（32論理演算） │ │
├────────────────────┐ s2=~b2&b1&~b0 │ │
│ │ s3=~b2&b1&b0 │ │
│ │ （5論理演算） ↓ │
│b0～b2 を ((a+b)+(c+d))+… で計算（27） ↓ ┌───┐ ┌───┐ │
├─────────────────────→│b0～b2│──→│s2, s3│ │
│ └───┘ ↑ └───┘ │
│ビットごとにソート（4論理演算/比較交換） │ │ │
↓ │ │s3|(bd&s2) │
┌────────┐ s2 = g & ~f, s3 = f & ~e （4論理演算） │ ↓（2論理演算）│
│ソート済み a～h │──────────────────────┘ ┌───┐ │
└────────┘ │ bd' │ │
└───┘ │
│ │
│ ←─────┘
↓
┌────────┐
│１次元配列データ│
└────────┘
template<typename T>
T nextGeneration(byte UL, T U, byte UR, byte L, T bd, byte R, byte DL, T D, byte DR)
{
if( !U && !L && !bd && !R && !D ) return 0;
const int MSB = 0x80 << (sizeof(T)*8 - 1);
.....
return (bd & s2) | s3;
}