ビットスワップ

TAOCP V4F0にはビット交換の技法がいろいろ書いてある. その大方の仕掛けはδスワップだが, TAOCPのベースのRISCマシン, MMIXにはMORとMXORという大形命令が存在し, それを巧みに利用する例題も多い.

これらの命令の説明はややこしく, なかなか覚えられないが, 今回のブログはその機能を覚えるためのものでもある.

MORはmultiple orのことで, 命令MOR $X, $Y, $Zは, 64ビットのレジスタ$Yと$Zのビットに演算を施し, レジスタ$Xに置くものである. TAOCP V1F1では,

m($X) ← m($Z)^v_xm($Y)

と説明する. レジスタ$Zと$Yの順が命令での順と逆なことに注意. この演算は, 64ビットレジスタをそれぞれ8ビットの行が縦に8行並んだ8 × 8の行列とみて, 2つの行列の乗算のような演算をするのである.

行列の乗算では, 積のi,j要素は, 被演算子の左の行列のi行と, 右の行列のj列の要素を次々と掛けて全体を足すのであった. それを2つの行列の間の演算⁺_xで表わす.



今は要素は0か1である. それを次々と掛けて全体のor(v)を取るのである. MXOR命令は全体のxorを取る.

使い方の例として, TAOCPには
$Z = #0102040810204080
とすると, $Yのバイトの順が逆になるというのがある. つまり(abcdefgh)₂₅₆が(hgfedcba)₂₅₆になる. それを説明するのが, 次の図の上だ.



まず$Xの左上, X_0,0は, $Zの0行目, 000...01と$Yの0列目のそれぞれを掛けるが, 1が最後にしかないので, ここに来るのはhのバイトの左端のビットである. その右隣りX_0,1も, 同じ0行目と掛けるから, hのさっきのバイトの右隣りになる. 同様にした結果, $Xの0行目はhのバイトになる.

$Xの1行目は, $Zの1行目が000...10, つまり最後の1つ前にだけ1があるから, gの行が来る.

hの行が0行へ移った理由を再確認すると, Zの0行目の1が右端にあるからだ. つまり0行目へ置きたい$Yのバイトの位置を1にする. 赤矢印が0行目へ来るバイトの位置を示す.

そういう次第で, このパターンを使うと, $Yのバイトが逆転するのである.

下の図は左右逆転, つまりバイトの順は同じだが, バイトのビットを逆転する方法を示す. 上と同じで, $Xの0列目は, $Yの0列目の最後だけが1なので, hの各ビットが移動してきて, hになる. そして結局左からhgf...aと並ぶ.

ビット交換では, Yの0列の1の位置がXの0列に持ってきたいビットの位置である. (赤矢印)


これだけ分かると, V4F0にある完全シャッフルの問題(演習問題7.1.3-204)が解ける.

64ビットのレジスタzは

z = (x₃₁...x₁x₀y₃₁...y₁y₀)₂

である. それを

w = (x₃₁y₃₁...x₁y₁x₀y₀)₂

にしたい. ヒントがあって,

t = (x₃₁x₂₇x₃₀x₂₆x₂₉x₂₅x₂₈x₂₄y₃₁y₂₇y₃₀y₂₆y₂₉y₂₅y₂₈y₂₄...
    x₇x₃x₆x₂x₅x₁x₄x₀y₇y₃y₆y₂y₅y₁y₄y₀)₂

u = (y₂₇y₃₁y₂₆y₃₀y₂₅y₂₉y₂₄y₂₈x₂₇x₃₁x₂₆x₃₀x₂₅x₂₉x₂₄x₂₈...
    y₃y₇y₂y₆y₁y₅y₀y₄x₃x₇x₂x₆x₁x₅x₀x₄)₂

を中間結果とし, tとuを

MOR t,z,p; MOR t,q,t; MOR u,t,r; MOR u,r,u;

で作り,

PUT rM,m; MUX w,t,u;

とすると, 6命令で完全シャッフルが出来る. パターンp, q, r, mは何かという問題である.

このうちMUX命令は多重化マスクレジスタrMを見ながら, そのビットが1の所は$Yから, 0の所は$Zからデータを取る. PUT rM,mはパターンmをrMへ設定する命令だ. そうすると,

w₃₁はx₃₁にしたいからtから取る.
w₃₀はy₃₁にしたいからuから取る.
w₂₉はx₃₀にしたいからtから取る.
...
28まで行くと, 取るレジスタが交代する. 従って, 1010101001010101の繰り返しになるのだ. m = #aa55aa55aa55aa55


さて, zとtとの関係は, 次の図の上半分にある通り. バイトの交換とビットの交換をしている. 命令列の最初はMOR t,z,p;なので, $Zの方がパターンになり, バイトの交換だ. バイト位置の0,1,2,3,4,5,6,7に持ってきたいのは, それぞれ0,4,1,5,2,6,3,7だから, 下に示す行列のようになり, p = #8008400420021001でよかろう.



次の命令はパターンが$Yにあるから, ビット交換である. ビットの取り先は同じ関係だが, 縦と横が違うから転置のパターンにしなければならない.



q = #8020080240100401.

最後にtからuへの変換も, バイト交換とビット交換になっている. これはどちらも隣り同士の交換なので, パターンは同じである.

r = #4080102004080102.

TAOCPの演習問題には解答があるから覗いてみると, 正解であった.