assembly - バイトの高速レジスタ内ソート?

Question

レジスタが 4 バイト (SIMD の場合は 16 バイト) の場合、いくつかの命令でレジスタ内のバイトを効率的にソートする方法が必要です。

前もって感謝します。

Answer 1

それを見つけた！これは、Furtak、Amaral、および Niewiadomski による 2007 年の論文「Using SIMD Registers and Instructions to Enable Instruction-Level Parallelism in Sorting Algorithms」にあります。セクション 4。

4 つの SSE レジスタを使用し、12 のステップを持ち、ロードとストアを含む 19 の命​​令で実行されます。

同じ論文には、SIMD を使用したソーティング ネットワークの動的な作成に関する優れた研究がいくつかあります。

Answer 2

文字列のソートを高速化するために、SSE2 で double ごとに 7 バイトをパックし、16 個の double の配列をソート (ランキング) し、bitonic sort を使用して 8 の 2 つの実行を作成し、バイナリ マージを使用して 2 つの実行をマージしました。最初の部分はhttp://mischasan.wordpress.com/2011/07/29/okay-one-more-poke-at-sse2-sorting-doubles/ (asm) とhttp://mischasan で見ることができます。 wordpress.com/2011/09/02/update-on-bitonic-sse2-sort-of-16-doubles/ (C)、および bitonic マージ手順 (SSE に完全に移行したい場合) はこちら: http: //mischasan.wordpress.com/2012/11/04/sse2-odd-even-merge-the-last-step-in-sorting/ . qsort の一番下の挿入ソートをこのソートに置き換えたところ、そのままの qsort の約 5 倍高速になりました。HTH

私は UofA の論文を見たことがありませんでした。バイトニック ロジックは、古い学校 (CTM) GPGPU プログラミングからのものです。

埋め込まれたリンク文字列について申し訳ありません。コメントのスタックオーバーフローにクリック可能なリンクを追加する方法がわかりません。

Answer 3

すべての並べ替えアルゴリズムでは、値をある場所から別の場所に「交換」する必要があります。リテラルの CPU レジスタについて話しているので、スワップされるバイトを保持するための一時的な場所として使用する別のレジスタが必要になることを意味します。

レジスタ内のバイトをソートするための組み込みメソッドを備えたチップを見たことがありません。やったことがないとは言いませんが、そのような指示の用途はあまり思いつきません。