sorting - 硬件中的快速/区域优化排序 (fpga)

Question

我正在尝试使用 vhdl 对一组 8 位数字进行排序。我试图找出一种优化延迟的方法和另一种使用更少硬件的方法。

数组的大小是固定的。但我也有兴趣将功能扩展到可变长度。到目前为止，我遇到了 3 种算法：

1. 巴彻平行
2. 方法绿色排序
3. 范沃里斯排序

其中哪一个会做得最好？我应该看看其他方法吗？谢谢。

Answer 1

在这方面有很多研究文章。您可以尝试在网上搜索它。我搜索了“排序网络”，并对不同算法进行了很多比较，以及它们在 FPGA 中的适配程度。

您选择的算法很大程度上取决于优化哪个参数最重要，即延迟、面积等。另一个重要因素是排序开始和结束时值的存储位置。如果它们存储在寄存器中，则可能会立即访问它们，但如果您必须从宽度有限的内存中读取它们，您也应该在实现中考虑这一点，因为这样您就必须对流中的值进行排序，并在将其保存回内存之前重新排列该流。

就个人而言，我会考虑一些时间恒定的东西，比如合并排序，它有一个恒定的排序时间，所以你可以很容易地为一个固定大小的数组安排排序。但是，我不确定这对任意大小的数组的扩展或使用效果如何。您可能必须设置数组大小的上限，如果所有数据都存储在寄存器中，这种方法效果最好。

Answer 2

我在 Knuth 的一本书中读到了这一点，根据那本书，Batcher 的并行合并排序是最快的算法，也是硬件效率最高的算法。