- 快速排序（QuickSort）及 HLS 实现解析
1. 快速排序简介
1.1 算法概述
快速排序（QuickSort）是一种基于分治（Divide and Conquer）思想的排序算法，平均时间复杂度为 O(n log n)，最坏情况下为 O(n²)，但通常情况下性能优越。其基本思想是：
- 选择一个基准值（Pivot），通常是数组的最后一个元素。
- 通过 分区（Partition） 操作，将数组分成两部分，使得左侧元素小于 Pivot，右侧元素大于 Pivot。
- 递归地对左右子数组进行快速排序。
1.2 Hoare 分区方案
本实现采用 Hoare 分区方案，将数组划分成两部分，并返回 Pivot 的最终位置。该方案在遍历过程中进行元素交换，以确保所有小于 Pivot 的元素位于左侧，而所有大于 Pivot 的元素位于右侧。
2. 快速排序的分步解析
假设我们有以下输入数组：
arr = [10, 7, 8, 9, 1, 6]
我们使用最后一个元素作为 Pivot（即 6），然后进行 分区。
2.1 第一次分区（Pivot = 6）
原始数组: [10, 7, 8, 9, 1, 6]
Pivot选取: 6
|
i |
j |
arr[j] |
操作 |
结果 |
|
-1 |
0 |
10 |
- |
无交换 |
|
-1 |
1 |
7 |
- |
无交换 |
|
-1 |
2 |
8 |
- |
无交换 |
|
-1 |
3 |
9 |
- |
无交换 |
|
-1 |
4 |
1 |
交换(1↔10) |
|
最终，将 Pivot（6）放到正确位置（索引 1）：
[1, 6, 8, 9, 10, 7]
Pivot 6 位置索引为 1，接下来递归对 [1] 和 [8, 9, 10, 7] 进行排序。
2.2 第二次分区（子数组 [8, 9, 10, 7]，Pivot = 7）
原数组: [8, 9, 10, 7]
Pivot选取: 7
|
i |
j |
arr[j] |
操作 |
结果 |
|
-1 |
0 |
8 |
- |
无交换 |
|
-1 |
1 |
9 |
- |
无交换 |
|
-1 |
2 |
10 |
- |
无交换 |
最终，交换 Pivot 7 到正确位置：
[7, 8, 9, 10]
Pivot 7 位置索引为 0，继续对子数组 [8, 9, 10] 进行排序。
2.3 第三次分区（子数组 [8, 9, 10]，Pivot = 10）
原数组: [8, 9, 10]
Pivot选取: 10
所有元素均小于 Pivot，无需交换，排序完成。
最终结果：
[1, 6, 7, 8, 9, 10]
3. 硬件加速（HLS）实现
3.1 代码解析
以下代码使用 HLS 进行快速排序，主要优化点如下：
swap使用#pragma HLS INLINE进行内联，减少函数调用开销。partition使用#pragma HLS PIPELINE II=1以流水线方式处理数据，提高吞吐率。quicksort使用非递归方式，并使用stack模拟递归过程，确保 HLS 兼容性。#pragma HLS ARRAY_PARTITION variable=stack cyclic factor=2 dim=1进行部分数组分区，提高访问效率。
#include <ap_int.h>
#define data_number 1000
inline void swap(ap_int<64> &a, ap_int<64> &b) {
#pragma HLS INLINE
ap_int<64> temp = a;
a = b;
b = temp;
}
int partition(ap_int<64> arr[], int low, int high) {
ap_int<64> pivot = arr[high];
int i = low - 1;
Partition_Loop:
for (int j = low; j < high; j++) {
#pragma HLS PIPELINE II=1
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
void quicksort(ap_int<64> arr[], int low, int high) {
int stack[data_number];
#pragma HLS ARRAY_PARTITION variable=stack cyclic factor=2 dim=1
int top = -1;
stack[++top] = low;
stack[++top] = high;
QuickSort_Loop:
while (top >= 0) {
#pragma HLS PIPELINE II=1
high = stack[top--];
low = stack[top--];
int pivot = partition(arr, low, high);
if (pivot - 1 > low) {
stack[++top] = low;
stack[++top] = pivot - 1;
}
if (pivot + 1 < high) {
stack[++top] = pivot + 1;
stack[++top] = high;
}
}
}
void hls_quicksort(ap_int<64> arr[data_number]) {
#pragma HLS INTERFACE mode=ap_memory port=arr
#pragma HLS BIND_STORAGE variable=arr type=RAM_1P impl=BRAM
quicksort(arr, 0, data_number-1);
}
3.2 代码优化点
- 数据流优化：使用
#pragma HLS PIPELINE II=1进行流水线优化，加速分区过程。 - 存储优化：
arr绑定到 Block RAM (#pragma HLS BIND_STORAGE variable=arr type=RAM_1P impl=BRAM)，提高 FPGA 访问速度。 - 循环展开：使用
#pragma HLS ARRAY_PARTITION进行栈优化，提高并行性。
4. 结论
- 快速排序 通过分区和递归实现高效排序，适用于 FPGA 设计。
- HLS 优化 采用流水线、RAM 绑定等方法，提高计算效率。
- 硬件友好设计 采用非递归实现，避免 HLS 递归限制。
此方案适用于 FPGA 高速数据处理，如金融分析、图像处理等领域。