ファスト・イン・レジスタ・ソート・バイト？

4バイトのレジスタ（またはSIMDの場合は16ビット）を指定すると、いくつかの命令でレジスタをバイト単位でソートする効率的な方法が必要です。ファスト・イン・レジスタ・ソート・バイト？

ありがとうございます。

出典

2009-10-16 alecco

N =あなたが気にするバイト数（4または16）に対して効率的なsorting networkを探します。それを一連の比較および交換命令に変換する。（ただし、N = 16の場合は「少数」以上になります）

出典

2009-10-16 23:05:40

ありがとうございます。私は効率的なソリューションasmを探しています。ああ、私は「少数の命令」で「数サイクル」ではないと言っています;） – alecco

ああ、あなたがリンクしている論文はSSE2命令を使ってこのアプローチをとっていることがわかります。クール。 –

ええと、あまりにも冗長ではありませんでした。なぜなら、私はasmを使った何らかのハックの魔法を望んでいたからです。実際、私はこの「マルチコアSIMD CPUアーキテクチャでのソートの効率的な実装」（Chhugani、.. 2008）を探していましたが、アルゴリズムの指示には不満を持っていました： 1）a）長さKの並べ替えられたシーケンスを入手してください。 Intelの研究者にとっては、私はそうではないでしょうか？（私はまだレジスタを並べ替えるために、17-19の命令の手順全体を行っているかどうかはわかりません） [注意：申し訳ありませんが、カルマの不足のためにあなたをアップアップしませんでした] – alecco

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

私は、レジスタ内でバイトをソートするための組み込みメソッドを持つチップを見たことがありません。それが行われていないことを言っているわけではありませんが、私はそのような指示のために多くの用途を考えることはできません。

出典

2009-10-16 22:17:51 richardtallent

私はレジスタ内のバイトをソートすることを意味しましたが、少なくとももう1つのレジスタを使用する必要があります。誤解をおかけして申し訳ありません。 – alecco

実際には、xxレジスタを使ってCMPXCHGを使ってレジスタ内のソートを行い、それを回転させる方法があります。そこからの利益はほとんどありませんが、可能です。また、CMPXCHGはかなり遅いです。 – alecco

私が使用したすべてのSIMDアーキテクチャにこのような指示があります。 –

見つけました！ Furtak、Amaral、Niewiadomskiの2007年の論文「SIMDレジスタと命令を使用した命令レベルの並列処理のソートアルゴリズム」を参照してください。セクション4.

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

同じ論文には、SIMDでソートネットワークを動的に作成する優れた作業がいくつかあります。

出典

2009-10-17 01:05:02 alecco

PDFへのリンク：http://www.cs.ualberta.ca/~amaral/papers/furtak-spaa07.pdf – alecco

SSE2で16倍の2倍の配列をソート（ランキング）し、ビットニックソートを使用して2回の8回の実行と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）、ビート的なマージステップ（SSEのすべての方法に行きたい場合）：http://mischasan.wordpress.com/2012/11/04/sse2-odd-even-merge-the-last-step-in-sorting/が表示されます。私はqsortの一番下にある挿入の並べ替えをこの並べ替えに置き換えました。これはまっすぐなqsortの約5倍です。 HTH

私はUofA用紙を見たことがありませんでした。 bitonicロジックは、古い学校（CTM）のGPGPUプログラミングからです。

埋め込みリンク文字列についてはごめんなさい。私はコメントstackoverflowでクリック可能なリンクを追加する方法を知らない。

出典

2013-04-30 17:14:12 Mischa

ファスト・イン・レジスタ・ソート・バイト？

答えて

関連する問題