bitslice

昨日の奴はbitsliceとも呼ばれているらしい。AJAXみたいに誰かbuzzwordを作ってくれるといいんだけど。
http://dsas.blog.klab.org/archives/51389536.html
bitsliceといってもAm2900でなく。少なくとも2000年代のテクニックではないよなVRAM操作的な意味で。
skyScheme的な興味は2つ。

これをC言語コンパイラに組み込んで自動化できるか

skySchemeは、これは実現不能だと思っている(C->skySchemeみたいな変換をするのは無しとして)。struct-reorgが可能かどうかも絶妙なところ。良いデータフロー解析によって実現できるかもしれない。けど、既存のソースコードをそのまま変換というスタイルでは難しいというのが仮説。
skySchemeのアプローチを言い換えると、良いAPIを作って、そのライブラリを使えばいいという考え方。ただAPIによる抽象化はこの手の目的にはむかないのでDSLにした。

n-bitでの処理はどの程度有効か

ステートマシンをN並列で行うことを考えると、ステートマシンを圧縮して、かつ、加算などの処理も活用することでlookupを減らせる可能性が有る。
単純に90度回転するだけは、加算などの処理の活用が難しい。1つのデータをn-bitで表し、1bitのスキマを設けることで加算や減算の処理を、限定付きのテーブルlookupとみなすことが出来る。単純な加減算に関しては自分でフラグを毎回*1セットすることで、n-bitの演算を並べるだけの並列化ができる。つまり、演算の最上位ビットをフラグだとみなす(普通の演算ではフラグは最終的には不要だから1bitのスキマになる)ことになる。
この手の最適化は人間には難しいが、8bit+8bitの真理値表は2^9の空間に収まるわけで、そこから欲しいものを探してくるのはそれほど難しいことでもないように思える。
ステートマシンの演算エンコードは分岐を減らせるので、例えばGPUでのデータ処理などにそれなりに有効と考えられる。
追記 : 真にパラレルなのはand, or, notのような演算だけで、加算は連鎖的にしか計算できないという問題には注意する必要が有る。加算は長くても64ビット程度の実装であることが普通。
あと、加算は情報量を減らす。1bitは無駄になるわけだが、これを1/2の無駄にするか1/64の無駄にするかはアルゴリズムに拠る。
一切の並列性に関する期待が無かったとしても、lookupを演算に置き換えることには価値が有る。殆どの場合カウンタで済み、例外的な状況はビット演算で済むようにステートマシンをエンコードすることを考える。

*1:まるで6502だ！