硬件快速/面积优化排序（fpga）

Question

我想用vhdl对8位数字的数组进行排序。 我想找出一种优化延迟的方法，另一种方法会使用较少的硬件。

该数组的大小是固定的。但我也有兴趣将功能扩展到可变长度。 我已经遇到3种算法迄今：

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

哪种方式做了最好的工作吗？我还有其他方法吗？ 谢谢。

Answer 1

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

Answer 2

在这件事上有很多研究文章。你可以尝试在网上搜索它。我搜索了“Sorting Networks”，并提出了很多不同算法的比较以及它们如何适合FPGA。

您选择的算法在很大程度上取决于哪个参数对于优化，即等待时间，面积等最重要。另一个重要因素是值存储在排序的开始和结束处的位置。如果它们被存储在寄存器中，所有可能被一次访问，但是如果你必须从宽度有限的存储器中读取它们，那么你应该考虑在你的实现中，因为那样你将不得不对流中的值进行排序，并在将其保存回内存之前重新排列该流。我个人认为像merge-sort这样的时间常量，它有一个固定的时间来排序，所以你可以很容易地调度一个固定大小的数组。不过我不确定这个尺度如何扩展或适用于任意大小的数组。您可能必须设置数组大小的上限，并且如果所有数据都存储在寄存器中，此方法的效果最佳。