基于FPGA的几种排序算法总结

目录

1      冒泡法和比较排序法

1.1        算法原理

1.2        仿真结果

1.3        算法优缺点

2      并行全比较排序法

2.1        算法原理及Verilog实现

2.2        仿真结果

2.3    算法优缺点

3      串行全比较排序法

3.1        算法原理及Verilog实现

3.2       仿真结果

3.3       算法优缺点

2      总结

最近笔者在项目中正好遇到需要排序的情况，以前刚接触C语言的时候排序的方法主要有冒泡排序、选择排序等方法；于是就用Verilog实现了冒泡法，但是发现此方法和选择排序法需要的时间周期太长，比如16个数据差不多需要136个周期才能完成排序，于是笔者在网上找到了并行全比较排序法和改进的串行全比较排序法；以下将一一介绍。

1      冒泡法和比较排序法

1.1        算法原理

这两种方法比较容易理解，下面给出两种排序方法的百科连接，大家可以自行百度。

冒泡排序：

https://baike.baidu.com/item/冒泡排序

选择排序：

https://baike.baidu.com/item/选择排序法/2304587?fr=aladdin

1.2        仿真结果

下面给出冒泡法的Verilog仿真结果，蓝色箭头是输入的原始数据，红色箭头所指的是排完序的数据，黄色箭头指的是排序所用的时间，仿真用的是100MHz的始终，所以冒泡总共需要136个周期。

1.3        算法优缺点

选择排序法和冒泡法属于传统的两两比较的算法，但是消耗的周期比较长，在一些对实时性要求较高的情况下无法满足要求。

2      并行全比较排序法

2.1        算法原理及Verilog实现

传统的排序方式是以两两之间顺序比较为基础，而并行全比较实时排序算法是基于序列中任意两个数并行比较实现。由于从原来的串行比较变成了并行比较，所以需要消耗比以前多的比较器，诠释了FPGA中“用面积换速度”的思想。以序列长度为m的数据为例：

A：    第一个时钟周期：将其中一个数据和其他数据在一个周期中一一比较，比较器分三种情况：

1.        这个数据大于其他数据，则它的得分为0；

2.        这个数据等于其他数据，若它在这个序列中比和它相等的其他数据靠前，则它的得分为0，反之为1；

3.        这个数据小于其他数据，则它的得分为1；

//--------------------------计算得分----------------------------------generategenvar i;for(i=1;i<=COL_WIDTH;i=i 1)begin:unfold_ialways@(posedgeclkorposedgerst)beginif(rst)begincomp_valid_i[i] <= 0;score_i[i] <= 0;endelseif(comp_valid_f)beginif(comp_data[col] > comp_data[i])score_i[i] <= 0;elseif(comp_data[col] == comp_data[i])beginif(col <= i) //如果有两个相同的数据，其中若输入顺序在前面则排序就靠前score_i[i] <= 0;elsescore_i[i] <= 1;endelsescore_i[i] <= 1;comp_valid_i[i] <= comp_valid_f;endelsebeginscore_i[i] <= 0;comp_valid_i[i] <= 0;endendendendgenerate

B：第二个时钟周期：将每个数据和其他数据比较后的数据累加；

  1. always@(posedge clk or posedge rst)

  2. begin

  3. if(rst)

  4. begin

  5. score <= 0;

  6. // score_t[1]<=0;

  7. // score_t[2]<=0;

  8. location <= 0;

  9. add_cnt <= 0;

  10. data_o <= 0;

  11. valid_o <= 0;

  12. end

  13. else if(comp_valid_j[1] == 1)

  14. begin

  15. add_cnt <= 0;

  16. // add_cnt <= 1;

  17. // score_t[1] <= ( score_j[1] score_j[2] ) ( score_j[3] score_j[4] );

  18. // score_t[2] <= ( score_j[5] score_j[6] ) ( score_j[7] score_j[8] );

  19. score <= ( ( score_j[1] score_j[2] ) ( score_j[3] score_j[4] ) )

  20. ( ( score_j[5] score_j[6] ) ( score_j[7] score_j[8] ) )

  21. ( ( score_j[9] score_j[10] ) ( score_j[11] score_j[12] ) )

  22. ( ( score_j[13] score_j[14] ) ( score_j[15] score_j[16] ) ) 1;

  23. location <= {row[7:0],col[7:0]};//行,列

  24. data_o <= comp_data[col];//数据

  25. valid_o <= 1;

  26. end

  27. end

C： 第三个时钟周期：将每个数据根据自己的得分赋值给新的数组（若得分为1的就赋值给数组中的第一个数，2就赋值给新的数组中第二个数）；

//--------------------------------------------------------------------------------always@(posedgeclkor posedgerst)beginif(rst)beginsort_done <= 0; //数据的坐标endelseif(valid_o[1])beginchn[score[1]] <= data_o[1]; //重新排列的数据chn[score[2]] <= data_o[2]; //重新排列的数据chn[score[3]] <= data_o[3]; //重新排列的数据chn[score[4]] <= data_o[4]; //重新排列的数据chn[score[5]] <= data_o[5]; //重新排列的数据chn[score[6]] <= data_o[6]; //重新排列的数据chn[score[7]] <= data_o[7]; //重新排列的数据chn[score[8]] <= data_o[8]; //重新排列的数据chn[score[9]] <= data_o[9]; //重新排列的数据chn[score[10]] <= data_o[10]; //重新排列的数据chn[score[11]] <= data_o[11]; //重新排列的数据chn[score[12]] <= data_o[12]; //重新排列的数据chn[score[13]] <= data_o[13]; //重新排列的数据chn[score[14]] <= data_o[14]; //重新排列的数据chn[score[15]] <= data_o[15]; //重新排列的数据chn[score[16]] <= data_o[16]; //重新排列的数据sort_done <= 1;endelsebeginsort_done <= 0;endend

D：  第四个时钟周期：将新数组输出；

经过以上四个步骤，即可将算法完成。

2.2        仿真结果

如上图所示，红色箭头代表着输入数据，其中红色的圈标记出输入相同的两个数据；黄色箭头为每个数据与别的数据比较后的得分，得分越小则代表这个数据越大，其中黄色部分是第一个数据和第二个数据的得分，这两个数据的大小是一样的，但是第一个数据输入数组中比第二个数据靠前，所以它的得分低一分，这也验证了我们设计逻辑上在是正确的；蓝色箭头则代表的是排完序的输出序列，经观察发现结果正确。

2.3    算法优缺点

l  优点：并行比较排序方式在实时性上有明显的优势，只需要四个时钟周期就可以排序完成；

l  缺点：

1.        由于是并行比较消耗了较多的资源，而且在第二个时钟周期（得分累加）需要大量的加法器级联，考虑到路径延迟、建立保持时间和时钟抖动，一个时钟周期许多个加法器级联会有问题；

2.        在代码可移植性方面也有欠缺，比如若序列大小改变，在第二个和第三个时钟周期的时候就需要人为修改多处代码；

3      串行全比较排序法

3.1        算法原理及Verilog实现

串行全比较排序法在并行全比较排序法做了一些改进，将原来并行全比较排序法的前三个周期由并行转变为串行，但是可以在比较的同时将得分累加，所以串行全比较排序法排序需要的周期是2*m（m个序列）个周期。

//--------------------------------------------------------------------------------always@(posedgeclkor posedgerst)beginif(rst)begincomp_cnt <= COL_WIDTH   1;score <=1;valid_o <=0;endelseif(comp_cnt <= COL_WIDTH)begincomp_cnt <= comp_cnt   1;if(comp_data[col] > comp_data[comp_cnt])score <= score;elseif(comp_data[col] == comp_data[comp_cnt])beginif(col <= comp_cnt)score <= score;elsescore <= score   1;endelsescore <= score   1;if(comp_cnt == COL_WIDTH)valid_o <=1;elsevalid_o <=0;endelseif(valid_r)begincomp_cnt <= 1;score <= 1;valid_o <=0;endelsebegincomp_cnt <= comp_cnt;score <= score;valid_o <=0;endend//--------------------------------------------------------------------------------

  1. //--------------------------------------------------------------------------------

  2. always@(posedge clk or posedge rst)

  3. begin

  4. if(rst)

  5. begin

  6. sort_count <= COL_WIDTH 1;

  7. sort_done <= 0;

  8. end

  9. else if(sort_count <= COL_WIDTH)

  10. begin

  11. sort_count <= sort_count 1;

  12. comp_data_index[score[sort_count]] <= comp_data[sort_count]; //这边改成DPR_RAM

  13. if(sort_count == COL_WIDTH)

  14. sort_done <= 1;

  15. else

  16. sort_done <= 0;

  17. end

  18. else if(valid_o[1])

  19. begin

  20. sort_count <= 1;

  21. sort_done <= 0;

  22. end

  23. else

  24. begin

  25. sort_count <= sort_count;

  26. sort_done <= 0;

  27. end

  28. end

  29. //--------------------------------------------------------------------------------

3.2       仿真结果

如上图所示，红色箭头代表着输入数据；黄色箭头为每个数据与别的数据比较后的得分；蓝色箭头则代表的是排完序的输出序列，经观察发现结果正确。

从图中可以读出排序需要的时间是330ns，由于仿真采用的时钟是100MHz，所以串行全比较算法需要33个时钟周期（大约2*n个周期）。

3.3       算法优缺点

串行全比较算法和并行全比较算法比较：

l  优点：

1.        资源消耗的比较少；

2.        代码可移植性好，序列变化只需要改变几个参数，不需要大规模修改代码；

l  缺点：

串行全比较算法所消耗的时间比并行全比较算法长。

2      总结

l  代码可移植性：传统串行排序算法＞串行全比较排序法>并行全比较排序法

l  资源使用：传统串行排序算法<串行全比较排序法<并行全比较排序法

l  排序时间：并行全比较排序法＜串行全比较排序法＜传统串行排序算法

来源：https://www.icode9.com/content-1-814801.html

赞 (0)

相关推荐