当前位置：
  1. 首页
  2. 可编辑器件

FPGA双调排序实现，精简指南，快速掌握排序新技巧！

2024-03-28

基于双调排序算法的蝶形图，我们可以得到地址的变化规律。这里以长度为16的双调序列为例，其地址变化规律入下图所示。由于长度为16，故总共需要4个Stage。图中每个Stage颜色的个数表明该Stage可分为的组数。例如Stage 0可分为1组，Stage 1可分为2组，Stage 2可分为4组，Stage 3可分为8组。
每组的起始地址和对应的Stage紧密相关，例如Stage 1第0组起始地址为0，即(16/2^1)*0，第1组起始地址为8，即(16/2^1)*1。每组的地址个数也由Stage决定。例如Stage 1每组地址长度为4，即16/2^(1+1)，Stage 2每组地址长度为2，即16/2^(2+1)。同一组内，相邻地址的间距为1，例如Stage 1第0组的4个地址为[0,1,2,3]，相邻地址间距为1，第1组的4个地址为[8,9,10,11]，相邻地址间距为1。
一旦确定了op1的地址就很容易确定op2的地址，因为两者之差（用diff表示）也是由Stage决定的。例如：Stage 0两者之差为8，即16/2^(0+1)，Stage 1两者之差为4，即16/2^(1+1)。
FPGA双调排序实现，精简指南，快速掌握排序新技巧！ (https://ic.work/) 可编辑器件 第1张
我们将地址规律总结为如下图所示形式。这里一个重要的数据是Stage，其与序列长度的关系可表示为Stage=log2(N)；另一个重要数据为diff，其与Stage关系可表示为diff=N/2^(Stage+1)。
FPGA双调排序实现，精简指南，快速掌握排序新技巧！ (https://ic.work/) 可编辑器件 第2张
在此基础上我们就很容易借助C++或Matlab生成两个操作数的地址。这里采用Matlab，相应的Matlab函数如下图所示。代码第5行用于判断序列长度是否为2的整数次幂。
FPGA双调排序实现，精简指南，快速掌握排序新技巧！ (https://ic.work/) 可编辑器件 第3张
有了地址关系也就有了数据之间的关系。通常情况下，数据是按时间顺序串行进入的，所以我们也期望每次排序之后也是串行输出的。根据数据流的关系，我们可以采用单路径延迟反馈（Single-pathDelay Feedback, SDF）运算单元流水结构，SDF单元如下图所示。
图中butterfly为蝶形运算单元，(2^P)D为延迟单元，延迟级数与所在Stage相关。仍以长度为16的双调序列为例，Stage 为0时，延迟级数为8，Stage 为1时，延迟级数为4，Stage为2时，延迟级数为2，Stage为3时延迟级数为1。图中sel为分频信号，仍与Stage相关，Stage为0时，sel为时钟的8分频信号，不难看出，分频系数与延迟级数是一致的。
FPGA双调排序实现，精简指南，快速掌握排序新技巧！ (https://ic.work/) 可编辑器件 第4张
在此基础上，将4个SDF相连即可实现串行输入/串行输出的双调排序。下图给出了Stage 0对应的SDF结构。
FPGA双调排序实现，精简指南，快速掌握排序新技巧！ (https://ic.work/) 可编辑器件 第5张
下图显示了相应的仿真结果。
FPGA双调排序实现，精简指南，快速掌握排序新技巧！ (https://ic.work/) 可编辑器件 第6张
 

文章推荐
Tags：

上一篇

下一篇

相关推荐