sorting - ハードウェア（fpga）での高速/エリア最適化ソート

Question

vhdlを使用して8ビットの数値の配列をソートしようとしています。遅延を最適化する方法と、ハードウェアの使用量を減らす方法を見つけようとしています。

配列のサイズは固定されています。しかし、機能を可変長に拡張することにも興味があります。私はこれまでに3つのアルゴリズムに出くわしました：

1. バッチャーパラレル
2. メソッドグリーンソート
3. ヴァンヴォリスソート

これらのどれが最高の仕事をしますか？私が見なければならない他の方法はありますか？ありがとう。

Answer 1

これについては、Knuth の本で読みました。その本によると、Batcher の並列マージ ソートは最速のアルゴリズムであり、ハードウェア効率も最も優れています。

Answer 2

この件に関しては、多くの研究論文があります。ウェブで検索してみてください。私は「Sorting Networks」を検索し、さまざまなアルゴリズムの多くの比較と、それらが FPGA にどれだけうまく適合するかを思いつきました。

選択するアルゴリズムは、最適化するのに最も重要なパラメータ (レイテンシ、面積など) によって大きく異なります。もう 1 つの重要な要素は、並べ替えの開始時と終了時に値が格納される場所です。それらがレジスタに格納されている場合は、すべてが一度にアクセスされる可能性がありますが、幅が制限されたメモリからそれらを読み取る必要がある場合は、ストリーム内の値を並べ替える必要があるため、実装でも考慮する必要があります。 、そのストリームをメモリに保存する前に並べ替えます。

個人的には、固定サイズの配列の並べ替えを簡単にスケジュールできるように、並べ替えに一定の時間がかかるマージ並べ替えのような時定数を検討します。ただし、これが任意のサイズの配列でどの程度スケーリングまたは機能するかはわかりません。おそらく、配列サイズに上限を設定する必要があります。また、このアプローチは、すべてのデータがレジスタに格納されている場合に最適です。