快速、小区域和低延迟的部分排序算法

Question

我正在寻找一种快速的方式来部分排序81个数字 - 理想情况下，我希望提取最低的16个值（不需要16个值的准确顺序）。

这个目标是在FPGA的专用硬件上实现的 - 所以这稍微复杂了一些，因为我希望结果实现的面积尽可能小。我查看并实现了奇偶合并排序算法，但我理想地寻找任何对我的需求更有效的东西（通过交易算法实现大小，获得最低的16个值的部分排序，不一定是有序的，而不是完整的排序）

任何建议都将非常受欢迎

非常感谢

- trican

---

我可以接受一些较大的值 - 我可能只会取最低的24个值来进行补偿。 - trican

由于您要对少量元素进行排序，因此应考虑计数排序，该算法几乎可以在线性时间内完成。 - ylc

数字有多大？如果它们很小，使用基数为16的基数排序可能是一个不错的选择。我曾经在一个小于256个数字的列表（短整型）上使用过这样的排序算法。它只需要16个桶，可以放入SSE寄存器中，几乎完全消除了初始化开销。 - Gunther Piez

你的标题要求快速，但你的问题要求最小面积。你需要知道最小值的索引还是只需要最小值？所有数据是否一次性可用？ - user597225

是的，@Adam12，那就是我的意思，我想要相对较低的延迟 - 理想情况下可能在16个时钟周期左右，绝对不会是数百个时钟周期。 - trican

Answer 1

这可以在O（nlog_k）时间内完成，其中n=81，k=16。 这比O（nlog_n）更有效地处理大量元素。

算法如下：

1. 初始化最大堆数据结构。这个堆将包含您的前16个。这个堆的大小不会超过16，并且插入和删除具有log(k)。
2. 遍历n-数字列表。对于每个n：
   • 如果堆少于16个元素，则只需添加它
   • 如果堆有16个元素，则将n与堆中的最大值进行比较（如果它大于最大值，请跳过;如果小于最大值，请删除max并添加n）。

这样，在每次迭代时，您都可以跟踪当前处理部分列表的最小k个数字。

- mishadoff

---

你应该使用堆而不是排序列表，因为排序列表在插入时没有O(log k)的时间复杂度。 - Thomash

谢谢 - 再次听起来很有趣 - 尽管我认为目前快速排序对于硬件实现会更好。我需要进一步调查。 - trican

@trican：对于硬件实现来说，这个算法应该非常简单，特别是如果你可以并行进行几次比较。首先，你需要在数组的前16个元素上执行make_heap操作（实际上是八个堆操作）。然后，你遍历剩下的81-16个元素，忽略任何大于元素0的元素，并用元素0替换它们并重新进行堆排序（这与make_heap中的最后一个操作相同）。这样，你的堆大小就固定了，而且每个操作都变得更加简单。 - rici

Answer 2

这听起来像是某种信号处理内核。在不知道设计中确切数据流的情况下，很难回答这个问题。任何涉及排序的算法都有地址解码成本，因为您需要能够写入和读取一个包含81个元素的内存。如果这些数据已经在内存中，则已经支付了此成本，但如果它们在不同的寄存器中，则将它们写入会带来区域成本。

假设数据在内存中，您可以使用冒泡排序并选择底部16个值。以下代码假定存在双端口内存，但通过使用临时寄存器来存储写入值和写入索引，每个时钟周期交替读和写，也可以使用单个端口实现。对于仅有81个元素的内存而言，这种方法可能没有更高的区域效率。或者，源内存可以作为两个单端口内存实现，其中一个具有奇数索引，另一个具有偶数索引。

// Not working code 
reg [15:0] inData [80:0]; // Must be two-port
reg [3:0]  iterCount = 0;
reg [6:0]  index = 0;
reg sorting;

always @(posedge clk)
  begin
  // Some condition to control execution
  if(sorting)
    begin

    if(index == 80)
      begin 

      // Stop after 16 iterations
      if(iterCount == 15)
        begin
        sorting <= 0;
        iterCount <= 0;
        end
      else
        begin
        iterCount <= iterCount+1;
        index <= 0;
        end
      end 
    else
      begin
      // If this is smaller than next item
      if(inData[index] < inData[index+1])
        begin
        // Swap with next item
        inData[index+1] <= inData[index];
        inData[index]   <= inData[index+1];
        end
      index <= index + 1;
      end
    end
  end

编辑：如果您的延迟受限，只允许一个时钟域并且必须进行管道处理，则问题仅限于选择排序网络并将其映射到管道。您不能使用资源共享，因此在给定排序网络的情况下，面积是固定的。

• 为N = 81选择排序网络（比较困难）
• 构建代表排序网络的有向数据流图
• 删除除输出66-81所需节点之外的所有节点
• 确定一个比较节点的延迟L
• 使用ALAP调度将M个节点分配给每个时钟，其中M * L <1 / f
• 如果调度成功，请用HDL编写代码

- user597225

---

非常感谢您的建议，亚当。虽然我很欣赏这种方法可能代表了最小的区域，并且可能具有非常高的最大频率，但我的担忧是延迟是数百（或可能数千）个时钟周期 - 这是我无法承受的。正如您所怀疑的那样，这是用于信号处理应用程序，因此我每个时钟周期都会得到一个新的81个值的组来排序。因此，高效的流水线处理（在多个组同时进行排序的意义上）和短延迟至关重要。 - trican

一个偶奇合并排序或双调排序比冒泡排序具有更短的延迟，并且对于实现目的具有非常规则的数据流。当然，这种权衡是面临着更高的区域 - 我想这是一种微妙的平衡行为。 - trican

Answer 3

如果您正在寻找通用算法，则可以使用Quicksort的版本。 Quicksort围绕一个枢轴元素对值进行排序。您选择一个枢轴并对数组进行排序。然后，您获得x个小于枢轴的值和（n-x-1）个较大的值。根据x的大小，选择要继续处理的一个数组。如果x> 16，则知道您要查找的数字都在x数组中，因此可以继续对其进行排序。如果不是，则现在知道x最低，并且可以递归地在其他数组中查找其他16-x个。

Quicksort的结果数组未完全排序，您只知道它们比枢轴小或大。一些信息请参见wikipedia和a paper。

- Origin

---

这听起来是一个非常有趣的方法 - 我一定会阅读链接的论文并考虑其硬件实现 - 我需要使用固定数量的迭代来使其适合硬件。但我怀疑这不会太大程度上影响结果。 - trican

Answer 4

首先设置一个长度为16的数组，并使用类似于选择排序的方法：

1. 认为第一个值是数组中的最小值。
2. 比较第一个元素和第二个元素之类的值，直到找到一个更小的数。
3. 将该数视为新的最小值，并将其与下一个数字进行比较，直到找到一个更小的数。
4. 如果完成了整个数组的排序，则你得到的那个数就是最小值。将其保存在一个数组中，并从源数组中排除它，然后再次开始，直到填满解决方案数组的16个位置。

- Alberto Bonsanto

Answer 5

如果你想避免状态机和循环索引（伴随着大型多路复用器或RAM），那么一种硬件友好的方法可能是使用一个17项的排序网络（呕吐！）。从寄存器（最初为空）中提取16个项目，并从输入总线中提取1个项目，将其馈送到排序网络中。对于每个有效的输入总线周期，排序网络的输出是迄今为止最小的16个元素，新元素要么在结果中，要么在顶部（如果它更大）。然后将最小的16个元素锁存到寄存器中以供下一个周期使用，而排序网络的顶部输出则被忽略。

这将需要16 *（每个元素的n位）寄存器，以及一个深度为5个减法/比较块，宽度为8个的排序网络，总共有40个减法/完成块（每个块的最坏传播为n位）。如果您可以向输入总线施加反压力，则可以在阶段之间轻松地进行流水线处理。该解决方案在时间和空间上几乎是恒定的：每个输入一个周期，空间仅取决于输出而不是输入的数量。

- shuckc