硬件快速/面積優化排序（fpga）

Question

我想用vhdl對8位數字的數組進行排序。 我想找出一種優化延遲的方法，另一種方法會使用較少的硬件。

該數組的大小是固定的。但我也有興趣將功能擴展到可變長度。 我已經遇到3種算法迄今：

1. Bathcher平行
2. 法的綠色排序
3. 凡Vorris排序

哪種方式做了最好的工作嗎？我還有其他方法嗎？ 謝謝。

Answer 1

我在Knuth的一本書中閱讀了這本書，根據該書，Batcher的並行合併排序是最快的算法，也是最高效的硬件。

Answer 2

在這件事上有很多研究文章。你可以嘗試在網上搜索它。我搜索了「Sorting Networks」，並提出了很多不同算法的比較以及它們如何適合FPGA。

您選擇的算法在很大程度上取決於哪個參數對於優化，即等待時間，面積等最重要。另一個重要因素是值存儲在排序的開始和結束處的位置。如果它們被存儲在寄存器中，所有可能被一次訪問，但是如果你必須從寬度有限的存儲器中讀取它們，那麼你應該考慮在你的實現中，因爲那樣你將不得不對流中的值進行排序，並在將其保存回內存之前重新排列該流。我個人認爲像merge-sort這樣的時間常量，它有一個固定的時間來排序，所以你可以很容易地調度一個固定大小的數組。不過我不確定這個尺度如何擴展或適用於任意大小的數組。您可能必須設置數組大小的上限，並且如果所有數據都存儲在寄存器中，此方法的效果最佳。