快速排序法在FPGA中的实现
1. 算法概述
快速排序（Quick Sort）是一种分治排序算法，核心思想是：
- 选取一个基准值（pivot）
- 将序列分区为两部分：左侧小于等于 pivot，右侧大于 pivot
- 对左右子区间递归执行同样过程
平均时间复杂度为 O(NlogN)，最坏为 O(N^2)。
2. 为什么在FPGA上实现快速排序
适用场景：
- 包处理中的优先级重排
- 流式数据中的Top-K预处理
- 批量数据离线排序加速
优势：
- 高并行能力：比较、交换可流水化
- 低延迟路径：可定制数据宽度和存储结构
- 高吞吐：适合固定规模、重复执行场景
挑战：
- 递归在硬件上不自然，需改写为显式栈
- 随机访存对BRAM端口和调度要求高
- pivot选择会影响性能与最坏情况
3. FPGA实现总体架构
一个可落地的硬件架构通常包含：
- 数据存储模块：BRAM/URAM 保存待排序数组
- 分区执行模块：完成 i/j 扫描与交换
- 显式栈模块：保存待处理区间 (l, r)
- 控制状态机：驱动初始化、分区、入栈、出栈、结束
- 结果输出模块：排序完成后按地址读出
建议先做“单分区引擎 + 单栈 + 时分复用”，再扩展多引擎并行。
4. 快速排序硬件化步骤
4.1 递归改写为迭代
软件递归：quick_sort(l, r) 硬件改写：
- 用栈保存区间
- 每次弹出一个区间执行 partition
- 将两个子区间按有效性压栈
这样避免了函数调用与递归上下文。
4.2 分区逻辑（Hoare/Lomuto）选择
FPGA中常用 Hoare 风格：
- i 从左向右找 >= pivot
- j 从右向左找 <= pivot
- i < j 时交换
- i >= j 时返回分割点
优点是交换次数通常较少。
4.3 pivot选择策略
可选：
- 固定取左端点（简单）
- 取中间值（较稳）
- 三数取中（稳定性更好，逻辑稍复杂）
工程推荐：中间值起步，后续再优化。
4.4 时序与流水
关键时序路径：比较器 + 地址生成 + BRAM读写控制。
优化手段：
- 将读、比较、交换拆成多拍
- BRAM双端口并行读
- 交换写回放在独立阶段
5. 核心Verilog设计说明
下面代码给出“可综合的核心框架”，用于说明硬件实现方法。实际项目可按位宽、深度、接口协议扩展。
5.1 区间栈模块（核心）
module range_stack #(
parameter W = 10,
parameter DEPTH = 64
)(
input wire clk,
input wire rst_n,
input wire push,
input wire pop,
input wire [W-1:0] l_in,
input wire [W-1:0] r_in,
output reg [W-1:0] l_out,
output reg [W-1:0] r_out,
output wire empty,
output wire full
);
reg [W-1:0] l_mem [0:DEPTH-1];
reg [W-1:0] r_mem [0:DEPTH-1];
reg [$clog2(DEPTH):0] sp;
assign empty = (sp == 0);
assign full = (sp == DEPTH);
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
sp <= 0;
l_out <= 0;
r_out <= 0;
end else begin
if (push && !full) begin
l_mem[sp] <= l_in;
r_mem[sp] <= r_in;
sp <= sp + 1'b1;
end
if (pop && !empty) begin
l_out <= l_mem[sp-1'b1];
r_out <= r_mem[sp-1'b1];
sp <= sp - 1'b1;
end
end
end
endmodule
设计点：
- 用显式栈替代递归
- 每次弹出一个区间进入分区流程
- 栈深度决定可处理最大递归层级
5.2 分区状态机（核心思路）
localparam S_IDLE = 3'd0,
S_LOAD = 3'd1,
S_SCAN_I = 3'd2,
S_SCAN_J = 3'd3,
S_SWAP = 3'd4,
S_DONE = 3'd5;
reg [2:0] state;
reg [9:0] i, j, l, r;
reg [31:0] pivot, di, dj;
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
state <= S_IDLE;
end else begin
case (state)
S_IDLE: begin
// 等待新的区间
end
S_LOAD: begin
// 读取 pivot，初始化 i/j
end
S_SCAN_I: begin
// i 向右扫描，直到 di >= pivot
end
S_SCAN_J: begin
// j 向左扫描，直到 dj <= pivot
end
S_SWAP: begin
// 若 i<j，交换 di/dj 并继续
// 否则进入 DONE
end
S_DONE: begin
// 产生分割点，回写子区间到栈
end
endcase
end
end
设计点：
- 分区过程做成多拍 FSM，保证时序稳定
- 读 BRAM 与比较错拍，减少关键路径
- DONE 状态统一处理“子区间入栈”
5.3 顶层控制流程（简化）
// 1) 初始压栈 [0, N-1]
// 2) 栈非空 -> 弹栈 -> 分区
// 3) 左区间长度>1 则压栈
// 4) 右区间长度>1 则压栈
// 5) 栈空则排序完成 done=1
6. 性能与资源估算方法
关注四类指标：
- 周期数：约等于各分区扫描与交换总拍数
- 频率 Fmax：取决于比较器、地址生成、BRAM控制
- 吞吐：每批 N 个元素排序完成时间
- 资源：LUT/FF/BRAM 使用率
粗估方法：
- 平均比较次数约 NlogN
- 每次比较若消耗 1~2 拍，总周期约 k*NlogN
7. 验证与测试建议
- 功能正确性：随机数组与软件排序结果对比
- 边界测试：空数组、全相等、逆序、重复值
- 压力测试：最大 N、连续批处理
- 时序收敛：检查分区状态机关键路径
- 一致性测试：不同 pivot 策略对延迟分布影响
8. 排序完成后的二分法查表实现
当表数据完成排序后，可在同一套 BRAM 数据上直接执行二分查找（Binary Search），用于快速定位目标值是否存在以及其索引位置。该流程非常适合 FPGA：
- 比较路径固定，控制逻辑简单
- 查询延迟稳定，复杂度为 O(logN)
- 可与排序模块复用存储资源，降低面积
8.1 适用场景
- 黑白名单匹配（IP/端口/ID）
- 分级阈值命中
- 固定字典查表（数值 -> 索引/标签）
- 排序后数据的快速 membership 查询
8.2 接口与前提条件
前提：
- 排序阶段
sort_done=1 - 数据按升序存储在
mem[0..N-1]
建议查表接口：
lookup_req：查表请求有效lookup_key：待查值lookup_busy：查找进行中lookup_done：本次查询结束脉冲lookup_hit：命中标志lookup_idx：命中索引（未命中可置 0 或保留）
8.3 二分查找硬件流程
- 初始化边界：
low=0，high=N-1 - 计算中点：
mid=(low+high)>>1 - 读取
mem[mid]与lookup_key比较 - 若相等，命中结束
- 若
mem[mid] < key，令low=mid+1 - 否则令
high=mid-1 - 当
low>high时未命中结束
硬件实现建议采用 FSM 多拍执行：
S_BS_IDLE：等待请求S_BS_CALC：计算中点并发起 BRAM 读S_BS_CMP：比较并更新边界S_BS_DONE：拉高完成信号，输出结果
8.4 伪代码（软件等价逻辑）
function binary_search(mem[0..N-1], key):
low = 0
high = N - 1
while low <= high:
mid = (low + high) >> 1
v = mem[mid]
if v == key:
return (hit=1, idx=mid)
else if v < key:
low = mid + 1
else:
high = mid - 1
return (hit=0, idx=0)
若希望“命中第一个重复值”，可在命中后继续向左半区收敛；若希望“命中最后一个重复值”，则继续向右收敛。
8.5 Verilog 状态机参考框架
localparam S_BS_IDLE = 2'd0,
S_BS_CALC = 2'd1,
S_BS_CMP = 2'd2,
S_BS_DONE = 2'd3;
reg [1:0] bs_state;
reg [9:0] low, high, mid;
reg [31:0] key_reg, mid_data;
reg lookup_busy, lookup_done, lookup_hit;
reg [9:0] lookup_idx;
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
bs_state <= S_BS_IDLE;
lookup_busy <= 1'b0;
lookup_done <= 1'b0;
lookup_hit <= 1'b0;
lookup_idx <= 10'd0;
end else begin
lookup_done <= 1'b0; // done 采用单拍脉冲
case (bs_state)
S_BS_IDLE: begin
if (sort_done && lookup_req) begin
key_reg <= lookup_key;
low <= 10'd0;
high <= N-1;
lookup_busy <= 1'b1;
lookup_hit <= 1'b0;
bs_state <= S_BS_CALC;
end
end
S_BS_CALC: begin
if (low <= high) begin
mid <= (low + high) >> 1;
// 发起 mem[mid] 读请求（同步 BRAM 下一拍有效）
bs_state <= S_BS_CMP;
end else begin
bs_state <= S_BS_DONE; // 未命中
end
end
S_BS_CMP: begin
// mid_data 为上拍读出的 mem[mid]
if (mid_data == key_reg) begin
lookup_hit <= 1'b1;
lookup_idx <= mid;
bs_state <= S_BS_DONE;
end else if (mid_data < key_reg) begin
low <= mid + 1'b1;
bs_state <= S_BS_CALC;
end else begin
high <= mid - 1'b1;
bs_state <= S_BS_CALC;
end
end
S_BS_DONE: begin
lookup_busy <= 1'b0;
lookup_done <= 1'b1;
bs_state <= S_BS_IDLE;
end
endcase
end
end
实现注意：
N不是 2 的幂时也可直接工作- 为防止
mid-1下溢，需确保仅在mid>0且分支合法时更新 - 同步 BRAM 通常有 1 拍读延迟，FSM 必须显式留拍
8.6 与排序模块的集成方案
推荐增加一个上层仲裁状态：
MODE_SORT：仅允许排序读写 BRAMMODE_LOOKUP：排序完成后切换到查表模式
如果需要支持“持续查询 + 周期性重排”，建议采用双缓冲：
- Bank-A 在线查表
- Bank-B 后台重排
- 排序完成后进行 bank 切换
这样可以避免查表服务中断。
8.7 时延与吞吐估算
对于单次查询，周期数近似：
T_lookup ≈ c0 + c1 * ceil(log2(N))
其中 c1 与 BRAM 读延迟、比较拍数相关。若每轮迭代约 2~3 拍：
N=1024时，log2(N)=10- 单次查询约 20~30 拍 + 固定开销
在时钟 200MHz 下，单次查询延迟可做到亚微秒级。
8.8 验证用例补充
在原排序验证基础上增加以下查表用例：
- 命中测试：查询表内最小值、最大值、中间值
- 未命中测试：查询小于最小值、大于最大值、间隙值
- 重复值测试：验证返回索引策略（任意/首个/最后）
- 边界测试：
N=1、N=2、全相等数据 - 时序测试：排序结束到首次查表握手时序
9. 工程结论
快速排序在 FPGA 上可行，关键在于：
- 递归改写为显式栈
- 分区过程状态机化并流水化
- BRAM 访问调度与时序优化
对于固定规模中等数据集，能获得比通用 CPU 更稳定的时延表现。