10

我正在寻找一种快速的方法来对 81 个数字进行部分排序 - 理想情况下，我希望提取最低的 16 个值（16 个值没有必要以绝对正确的顺序排列）。

目标是 FPGA 中的专用硬件 - 所以这有点复杂，因为我希望最终实现的区域尽可能小。我查看并实现了奇偶合并排序算法，但理想情况下，我正在寻找任何可能对我的需求更有效的东西（交易算法实现大小以获得最低 16 的部分排序，不一定按顺序而不是全排序）

任何建议都会非常受欢迎

非常感谢

4

5 回答 5

8

这可以及时完成O(nlog_k)，在您的情况下，n = 81 和 k = 16。当您处理大量元素时，这比O(nlog_n).

算法如下：

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

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

于 2012-11-09T10:49:30.467 回答
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 选择一个排序网络（Bitonic、Pairwise 等）（不容易）
  • 构建表示排序网络的有向数据流图
  • 除输出 66-81 所需的节点外，删除所有节点
  • 确定一个比较节点的延迟 L
  • 使用 ALAP 调度为每个时钟分配 M 个节点，其中 M*L < 1/f
  • 如果调度成功，则将其编码为 HDL
于 2012-11-11T20:48:13.550 回答
1

如果您正在寻找通用算法，那么您可以使用 Quicksort 的一个版本。快速排序围绕枢轴元素对值进行排序。您选择一个枢轴并对您的数组进行排序。然后你会得到 x 值 < pivot 和 (nx-1) 更大的值。根据 x，您可以选择任一数组继续处理。如果 x>16，那么您知道您要查找的数字都在 x 数组中，您可以继续对其进行排序。如果不是，那么您知道 x 最低，现在可以递归地在另一个数组中查找 16-x 其他人。

快速排序的结果数组没有完全排序，您只知道它们小于或大于您的枢轴。维基百科上的一些信息和一篇论文。

于 2012-11-09T10:40:29.550 回答
0

也许修改的中位数选择是一种选择？否则，只求最少 16 次是否可行？

于 2012-11-09T10:40:08.790 回答
0

首先设置一个包含 16 个值的数组。并使用选择排序之类的东西：

  1. 您认为第一个值是数组中的最小值。
  2. 比较第一个元素的值，第二个，直到找到比它小的数字。
  3. 将其作为您的新最小值，并将其与下一个数字进行比较，直到找到一个低于它的数字。
  4. 如果你完成了数组，你拥有的数字是你的最小值，将它保存在一个数组中并将它从源数组中排除，然后重新开始，直到你填满解决方案数组的 16 个位置。
于 2012-11-09T10:44:59.340 回答