やりたい処理
skyは3種類のIR(中間表現)を駆使して、プロトコル処理で良く出てくるタイプの処理を最適化したい。
IRにはbit-IR(1bit単位の幅で構造体を表現する)、graph-IR(bit-IRで提供されるオブジェクトに対して演算や比較を提供する)、word-IR(CPUのword幅に合わせた演算を表現する)の3種類があり、最終的にアセンブラ(LLVM)に対してword-IRを変換して入力することでオブジェクトコードを得る。
要するにやることはFPGAとかで出てくるような論理合成と同じ。未使用やdon't careであるようなbitの刈り取りも行わなければならない。
やりたいことに新規性が無いだろというのは周囲から散々指摘がでているけれど、『これらの処理を想定してプロトコル記述言語を作る』という辺りが一応新規性。現実的な言語に落とし込むのは地味な作業であんまり面白い領域でもないが、研究のフレームワークを作るという意味では重要。。
並列bit演算の検出
並列bit演算というと仰々しいが、要するに、順序関係をもたないbit演算が無いかどうかを探索する。
例えば、32bit数値同士の比較について、大小関係に依存しない比較であればエンディアンの変換を省略できる。
通常の32bit整数同士の比較が、
(define p (neq a b)) ; a == bならp=0、そうでなければp=1
と表現されるとして、skyではこれらを全てunrollingして取り扱う。つまり、
(define p (par-and (neq a0 b0) (neq a1 b1) (neq a2 b2) ... (neq a31 b31) ))
par-で始まる関数は、引数の評価順が並列であることを示す。逆にseq-で始まる関数は直前ないし他のnamedパラメタの参照を許可している。
predicate-bitの導出
skyでは比較命令による分岐ではなく、比較演算として1bit値を返す関数を先に想定している。
これは、通常比較命令で行われるようなタイプの演算を、bit演算に落とし込む際にどうしても必要になる。ビットの選択代入などには専用の命令が有ったりとアーキテクチャ側でそれなりのケアが為されていることが多い。
静的分岐予測のプロファイリングによる付与
先行研究では20%の改善を出しているのでかなり効果は有るはず。
これをどのように表現するかは悩みどころで、例えば全てのビットの値に対して確率を上手く保持したまま処理が出来れば、データ構造や処理フローの選択に非常に有利になるように思える。
ただ、そのような情報を使って例えば"マルチスレッドにすべきかどうかを選択する"なんてことが可能なのかというのは想像が付かない。。
処理フローの選択は要するに特殊化を行うかどうかの選択となる。
