1

特定のビット表現のパリティを決定するMIPSの命令はありますか？「数値」が偶数パリティか奇数パリティかを判断するのは、バイナリ表現の個々のビットをXORすることですが、MIPS命令のセットでは、計算量が多いようです...これを行う必要がありますできるだけ早く。

また、私が働いている番号はグレイコードで表されています...それをそこに投げ込むだけです。それで、MIPSには「数値」のパリティを決定するための疑似命令がありますか、それとも手動で行う必要がありますか？

MIPS命令がない場合、それは非常にありそうもないと思われますが、手作業でそれを行う方法について何かアドバイスはありますか？

ありがとう、Hristo

フォローアップ：最適化を見つけましたが、実装が機能していません。

unsigned int v; // 32-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x11111111U) * 0x11111111U;
return (v >> 28) & 1;
4

1 に答える 1

3

パリティ命令を使用するMIPSバリアントを認識していませんが、32ビットのそれぞれを順番に実行する明白な方法よりも高速にパリティを計算するためのビットをいじるトリックがあります。Cの場合：

result = in ^ (in >> 16);
result ^= (result >> 8);
result ^= (result >> 4);
result ^= (result >> 2);
result ^= (result >> 1);
result &= 1;

  • 最初のステップの後、結果の下位16ビットには、入力のビットNとN + 16のパリティが含まれます。基本的に、パリティ計算の16ステップが一度に実行されます。result{N}「のビットN」を意味するように書くresult：

    result{0}  =  in{0} ^ in{16}
result{1}  =  in{1} ^ in{17}
result{2}  =  in{2} ^ in{18}
...
result{7}  =  in{7} ^ in{23}
result{8}  =  in{8} ^ in{24}
...
result{15} = in{15} ^ in{31}

    （そして、残りの上位16ビットはresult無視できるようになりました。これらは残りの計算では有用な目的を果たしません）。

  • 2番目のステップの後、の下位8ビットにresultは、元の入力のビットN、N + 8、N + 16、N+24のパリティが含まれます。

    result{0} = result{0} ^ result{8}  =  in{0} ^  in{8} ^ in{16} ^ in{24}
result{1} = result{1} ^ result{9}  =  in{1} ^  in{9} ^ in{17} ^ in{25}
...
result{7} = result{7} ^ result{15} =  in{7} ^ in{15} ^ in{23} ^ in{31}

    （繰り返しますが、残りのビットはここから無視できます）。

  • ...など、元の入力のすべてのビットのパリティが次の最後のビットになるまで続きますresult。

    result{0} = in{0} ^ in{1} ^ in{2} ^ ... ^ in{30} ^ in{31}

これは、MIPSアセンブリに直接変換するのは簡単です。それは11の指示です：

# input in $a0, output in $v0, $t0 corrupted
srl $t0, $a0, 16
xor $v0, $a0, $t0
srl $t0, $v0, 8
xor $v0, $v0, $t0
srl $t0, $v0, 4
xor $v0, $v0, $t0
srl $t0, $v0, 2
xor $v0, $v0, $t0
srl $t0, $v0, 1
xor $v0, $v0, $t0
and $v0, $v0, 1

考えられる改善点は、ルックアップテーブルを使用することです。たとえば、最初の2つの手順の後、次のようになります。

    result{0} =  in{0} ^  in{8} ^ in{16} ^ in{24}
    result{1} =  in{1} ^  in{9} ^ in{17} ^ in{25}
    ...
    result{7} =  in{7} ^ in{15} ^ in{23} ^ in{31}

したがって、この時点で256バイトのルックアップテーブルを使用できます。Cの場合：

result = in ^ (in >> 16);
result ^= (result >> 8);
result = lookup_table[result & 0xff];

lookup_table[n]事前に計算されている場所、例：

for (i = 0; i < 256; i++) {
    n = i ^ (i >> 4);
    n ^= (n >> 2);
    n ^= (n >> 1);
    lookup_table[i] = n & 1;
}

これは7つのMIPS命令であり、ルックアップテーブルのベースアドレスをレジスタにロードすることは含まれていません。

# input in $a0, lookup table address in $a1, output in $v0, $t0 corrupted
srl  $t0, $a0, 16
xor  $v0, $a0, $t0
srl  $t0, $v0, 8
xor  $v0, $v0, $t0
andi $v0, $v0, 0xff
addu $t0, $a1, $v0
lbu  $v0, 0($t0)

ただし、これはメモリアクセスを含む7つの命令であるのに対し、純粋にレジスタ操作である11の命令です。それは速いかもしれないし、そうでないかもしれません。（この種のマイクロ最適化は常にプロファイリングする必要があります！）

于 2010-04-11T16:52:46.873 に答える