ワード内のパーミュテーション(ビット入れ換え)は、様々な処理で用いられる操作である。例えば、標準暗号として広く使用されているDES(Data Encryption Standard)の暗号化および復号の処理では、64ビットワード内のパーミュテーションが行われる。
現在の汎用プロセッサでワード内パーミュテーションを実行する場合、ワード内のビットを一つずつ取り出して処理する必要があり、シフトやビットワイズの論理演算をワード内のビット数分繰り返すことになる。このため、ワード内パーミュテーションは現在のプロセッサでは比較的時間のかかる処理となっている。
本論文では、マイクロプロセッサに専用回路を付加することにより、ワード内の任意のパーミュテーションを高速に行う方法を提案する。ワードのビット数をnとする場合、提案方法で用いる回路は任意のn入力のサブシャフル置換が実行可能な回路とn/2個のスイッチから成る。回路はnlog2n-n+2個の2入力1出力のマルチプレクサで構成され、ハードウェア量はn入力のバレルシフタと同程度である。 専用回路を用いてパーミュテーションを実行するために、高級言語向けのパーミュテーションの組み込み関数を提供し、コンパイル時に専用回路で使用する命令コード列を生成する方法を提案する。組み込み関数は、ワード内パーミュテーションの対象ワードとパーミュテーションを規定する定数行列を引数とするものである。コンパイラは、ソーティングネットワークの一種であり、サブシャフル置換と隣り合うビットの入れ換え操作のみで構成可能なバイトニックソータをシミュレートして、専用回路の入力コード列を生成する。これにより、nビットワード内のパーミュテーションの実行に必要な命令数は((log2n)2+log2n)/2となる。パーミュテーションが局所的なビット置換である場合等は、命令数は更に削減可能である。
1ワードのビット数nを64とすると、専用回路を構成するマルチプレクサの数は322となり、ワード内パーミュテーションの実行に必要な命令数は最大で21となる。