Parabix

http://parabix.costar.sfu.ca/
SIMDXMLパースやREマッチを行うもの。要するに1byteの処理を8本のbitstreamの処理に変換し、可能な限り並列にandとかorとかnotを取る。andやorはSIMD演算器の長いレジスタの中で完全に並列に求めることが出来る(cf http://d.hatena.ne.jp/mjt/20081107/p1 )
バイト列から、なにか1バイトを検索してくることを考える。1バイトの"00"(NUL)を考えよう。
バイト列の長さが128バイトなら、for文をiが128になるまで廻したくなる。当然、1度のオペレーションではひとつの比較しか行えない。
そこで、データを転置して128個の8bitデータを8個の128bitデータに変換することを考える。
そのように変換した後、"00"の位置を探すには、全てのデータをorして、依然0であるところを探せばよいことになる。ビットが立っていない位置に"00"がある。たった8回の演算で"00"の位置をあぶりだすことができる。もし、128bitの範囲に"00"が無いことだけを調べたいなら、全部のorをとった後all 1と一回比較すれば良いことになる。
もちろん"00"以外も同様にして探し出すことができる。(理由?)
今までskySchemeが構造体を1bit単位にバラしていた意義が微妙なところだったが、こういう転置の有効性を考え始めると、ついに、何か有用な利用方法が見つかるんじゃないかという気分になってくる。
...もっとも、これ別に64bitくらいのCPUであればSIMDじゃなくても同じ事になってしまうので何かキーアイデアの読み落としがあるような気がする。
データをbitごとに処理するのはHDLというか論理合成の世界では超当たり前のことなので、それほど新しいアイデアにも思えない。こういう一種の論理合成的な処理をさせるために言語の記述能力を制限する必要が有るのは、VHDLがAdaのフルセットでないことから容易にわかる。
例えば、1 bit CPUを想定してコンパイルした後、もういちど演算スケジューリングを行うことで今回の転置のような最適化を導けるだろうか?