FPGA篇（三）基于FPGA的几种排序算法
目錄
1??????冒泡法和比較排序法
1.1????????算法原理
1.2????????仿真結(jié)果
1.3????????算法優(yōu)缺點(diǎn)
2??????并行全比較排序法
2.1????????算法原理及Verilog實(shí)現(xiàn)
2.2????????仿真結(jié)果
2.3????算法優(yōu)缺點(diǎn)
3??????串行全比較排序法
3.1????????算法原理及Verilog實(shí)現(xiàn)
3.2???????仿真結(jié)果
3.3???????算法優(yōu)缺點(diǎn)
2??????總結(jié)
?
最近筆者在項(xiàng)目中正好遇到需要排序的情況，以前剛接觸C語(yǔ)言的時(shí)候排序的方法主要有冒泡排序、選擇排序等方法；于是就用Verilog實(shí)現(xiàn)了冒泡法，但是發(fā)現(xiàn)此方法和選擇排序法需要的時(shí)間周期太長(zhǎng)，比如16個(gè)數(shù)據(jù)差不多需要136個(gè)周期才能完成排序，于是筆者在網(wǎng)上找到了并行全比較排序法和改進(jìn)的串行全比較排序法；以下將一一介紹。
?
1??????冒泡法和比較排序法
?
1.1????????算法原理
?
這兩種方法比較容易理解，下面給出兩種排序方法的百科連接，大家可以自行百度。
冒泡排序：
https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F
?
?
選擇排序：
https://baike.baidu.com/item/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%E6%B3%95/2304587?fr=aladdin
?
1.2????????仿真結(jié)果
?
????????下面給出冒泡法的Verilog仿真結(jié)果，藍(lán)色箭頭是輸入的原始數(shù)據(jù)，紅色箭頭所指的是排完序的數(shù)據(jù)，黃色箭頭指的是排序所用的時(shí)間，仿真用的是100MHz的始終，所以冒泡總共需要136個(gè)周期。
?
1.3????????算法優(yōu)缺點(diǎn)
?
????選擇排序法和冒泡法屬于傳統(tǒng)的兩兩比較的算法，但是消耗的周期比較長(zhǎng)，在一些對(duì)實(shí)時(shí)性要求較高的情況下無(wú)法滿足要求。
?
2??????并行全比較排序法
2.1????????算法原理及Verilog實(shí)現(xiàn)
????????傳統(tǒng)的排序方式是以兩兩之間順序比較為基礎(chǔ)，而并行全比較實(shí)時(shí)排序算法是基于序列中任意兩個(gè)數(shù)并行比較實(shí)現(xiàn)。由于從原來(lái)的串行比較變成了并行比較，所以需要消耗比以前多的比較器，詮釋了FPGA中“用面積換速度”的思想。以序列長(zhǎng)度為m的數(shù)據(jù)為例：
A：????第一個(gè)時(shí)鐘周期：將其中一個(gè)數(shù)據(jù)和其他數(shù)據(jù)在一個(gè)周期中一一比較，比較器分三種情況：
????1.????????這個(gè)數(shù)據(jù)大于其他數(shù)據(jù)，則它的得分為0；
????2.????????這個(gè)數(shù)據(jù)等于其他數(shù)據(jù)，若它在這個(gè)序列中比和它相等的其他數(shù)據(jù)靠前，則它的得分為0，反之為1；
????3.????????這個(gè)數(shù)據(jù)小于其他數(shù)據(jù)，則它的得分為1；
//-------------------------- 計(jì)算得分 ----------------------------------generategenvar i;for(i=1;i<=COL_WIDTH;i=i+1)begin:unfold_ialways@(posedge clk or posedge rst)beginif(rst)begin comp_valid_i[i] <= 0;score_i[i] <= 0; endelse if(comp_valid_f)beginif(comp_data[col] > comp_data[i])score_i[i] <= 0;else if(comp_data[col] == comp_data[i])beginif(col <= i) //如果有兩個(gè)相同的數(shù)據(jù)，其中若輸入順序在前面則排序就靠前score_i[i] <= 0;elsescore_i[i] <= 1;endelse score_i[i] <= 1;comp_valid_i[i] <= comp_valid_f;endelsebeginscore_i[i] <= 0;comp_valid_i[i] <= 0;endendendendgenerate?
?
B：第二個(gè)時(shí)鐘周期：將每個(gè)數(shù)據(jù)和其他數(shù)據(jù)比較后的數(shù)據(jù)累加；
?
?
always@(posedge clk or posedge rst)beginif(rst)beginscore <= 0; // score_t[1]<=0; // score_t[2]<=0;location <= 0;add_cnt <= 0;data_o <= 0;valid_o <= 0;endelse if(comp_valid_j[1] == 1)beginadd_cnt <= 0; // add_cnt <= 1; // score_t[1] <= ( score_j[1]+score_j[2] ) + ( score_j[3]+score_j[4] ); // score_t[2] <= ( score_j[5]+score_j[6] ) + ( score_j[7]+score_j[8] );score <= ( ( score_j[1]+score_j[2] ) + ( score_j[3]+score_j[4] ) )+( ( score_j[5]+score_j[6] ) + ( score_j[7]+score_j[8] ) )+( ( score_j[9]+score_j[10] ) + ( score_j[11]+score_j[12] ) )+( ( score_j[13]+score_j[14] ) + ( score_j[15]+score_j[16] ) )+ 1;location <= {row[7:0],col[7:0]};//行,列data_o <= comp_data[col];//數(shù)據(jù)valid_o <= 1;end end?
C： 第三個(gè)時(shí)鐘周期：將每個(gè)數(shù)據(jù)根據(jù)自己的得分賦值給新的數(shù)組（若得分為1的就賦值給數(shù)組中的第一個(gè)數(shù)，2就賦值給新的數(shù)組中第二個(gè)數(shù)）；
?
//--------------------------------------------------------------------------------always@(posedge clk or posedge rst)beginif(rst)beginsort_done <= 0; //數(shù)據(jù)的坐標(biāo) endelse if(valid_o[1])beginchn[score[1]] <= data_o[1]; //重新排列的數(shù)據(jù) chn[score[2]] <= data_o[2]; //重新排列的數(shù)據(jù)chn[score[3]] <= data_o[3]; //重新排列的數(shù)據(jù)chn[score[4]] <= data_o[4]; //重新排列的數(shù)據(jù)chn[score[5]] <= data_o[5]; //重新排列的數(shù)據(jù)chn[score[6]] <= data_o[6]; //重新排列的數(shù)據(jù)chn[score[7]] <= data_o[7]; //重新排列的數(shù)據(jù)chn[score[8]] <= data_o[8]; //重新排列的數(shù)據(jù)chn[score[9]] <= data_o[9]; //重新排列的數(shù)據(jù)chn[score[10]] <= data_o[10]; //重新排列的數(shù)據(jù)chn[score[11]] <= data_o[11]; //重新排列的數(shù)據(jù)chn[score[12]] <= data_o[12]; //重新排列的數(shù)據(jù)chn[score[13]] <= data_o[13]; //重新排列的數(shù)據(jù)chn[score[14]] <= data_o[14]; //重新排列的數(shù)據(jù)chn[score[15]] <= data_o[15]; //重新排列的數(shù)據(jù)chn[score[16]] <= data_o[16]; //重新排列的數(shù)據(jù)sort_done <= 1;endelsebeginsort_done <= 0;endend?
D：? 第四個(gè)時(shí)鐘周期：將新數(shù)組輸出；
?
經(jīng)過(guò)以上四個(gè)步驟，即可將算法完成。
?
2.2????????仿真結(jié)果
?
????????如上圖所示，紅色箭頭代表著輸入數(shù)據(jù)，其中紅色的圈標(biāo)記出輸入相同的兩個(gè)數(shù)據(jù)；黃色箭頭為每個(gè)數(shù)據(jù)與別的數(shù)據(jù)比較后的得分，得分越小則代表這個(gè)數(shù)據(jù)越大，其中黃色部分是第一個(gè)數(shù)據(jù)和第二個(gè)數(shù)據(jù)的得分，這兩個(gè)數(shù)據(jù)的大小是一樣的，但是第一個(gè)數(shù)據(jù)輸入數(shù)組中比第二個(gè)數(shù)據(jù)靠前，所以它的得分低一分，這也驗(yàn)證了我們?cè)O(shè)計(jì)邏輯上在是正確的；藍(lán)色箭頭則代表的是排完序的輸出序列，經(jīng)觀察發(fā)現(xiàn)結(jié)果正確。
?
2.3????算法優(yōu)缺點(diǎn)
l? 優(yōu)點(diǎn)：并行比較排序方式在實(shí)時(shí)性上有明顯的優(yōu)勢(shì)，只需要四個(gè)時(shí)鐘周期就可以排序完成；
l? 缺點(diǎn)：
????????1.????????由于是并行比較消耗了較多的資源，而且在第二個(gè)時(shí)鐘周期（得分累加）需要大量的加法器級(jí)聯(lián)，考慮到路徑延遲、建立保持時(shí)間和時(shí)鐘抖動(dòng)，一個(gè)時(shí)鐘周期許多個(gè)加法器級(jí)聯(lián)會(huì)有問(wèn)題；
????????2.????????在代碼可移植性方面也有欠缺，比如若序列大小改變，在第二個(gè)和第三個(gè)時(shí)鐘周期的時(shí)候就需要人為修改多處代碼；
?
3??????串行全比較排序法
3.1????????算法原理及Verilog實(shí)現(xiàn)
????????串行全比較排序法在并行全比較排序法做了一些改進(jìn)，將原來(lái)并行全比較排序法的前三個(gè)周期由并行轉(zhuǎn)變?yōu)榇?#xff0c;但是可以在比較的同時(shí)將得分累加，所以串行全比較排序法排序需要的周期是2*m（m個(gè)序列）個(gè)周期。
//--------------------------------------------------------------------------------always@(posedge clk or posedge rst)beginif(rst)begincomp_cnt <= COL_WIDTH + 1;score <= 1;valid_o <= 0;endelse if(comp_cnt <= COL_WIDTH)begincomp_cnt <= comp_cnt + 1;if(comp_data[col] > comp_data[comp_cnt])score <= score;else if(comp_data[col] == comp_data[comp_cnt])beginif(col <= comp_cnt)score <= score;elsescore <= score + 1;endelse score <= score + 1;if(comp_cnt == COL_WIDTH) valid_o <= 1;else valid_o <= 0;endelse if(valid_r)begincomp_cnt <= 1;score <= 1;valid_o <= 0;endelsebegincomp_cnt <= comp_cnt;score <= score;valid_o <= 0;endend //-------------------------------------------------------------------------------- //--------------------------------------------------------------------------------always@(posedge clk or posedge rst)beginif(rst)beginsort_count <= COL_WIDTH + 1;sort_done <= 0;endelse if(sort_count <= COL_WIDTH)beginsort_count <= sort_count + 1;comp_data_index[score[sort_count]] <= comp_data[sort_count]; //這邊改成DPR_RAMif(sort_count == COL_WIDTH)sort_done <= 1;else sort_done <= 0;endelse if(valid_o[1])beginsort_count <= 1;sort_done <= 0;endelsebeginsort_count <= sort_count;sort_done <= 0;endend //--------------------------------------------------------------------------------3.2???????仿真結(jié)果
?
?
?
?
?
????????如上圖所示，紅色箭頭代表著輸入數(shù)據(jù)；黃色箭頭為每個(gè)數(shù)據(jù)與別的數(shù)據(jù)比較后的得分；藍(lán)色箭頭則代表的是排完序的輸出序列，經(jīng)觀察發(fā)現(xiàn)結(jié)果正確。
????????從圖中可以讀出排序需要的時(shí)間是330ns，由于仿真采用的時(shí)鐘是100MHz，所以串行全比較算法需要33個(gè)時(shí)鐘周期（大約2*n個(gè)周期）。
3.3???????算法優(yōu)缺點(diǎn)
串行全比較算法和并行全比較算法比較：
l? 優(yōu)點(diǎn)：
????????1.????????資源消耗的比較少；
????????2.????????代碼可移植性好，序列變化只需要改變幾個(gè)參數(shù)，不需要大規(guī)模修改代碼；
l? 缺點(diǎn)：
????????串行全比較算法所消耗的時(shí)間比并行全比較算法長(zhǎng)。
2??????總結(jié)
l? 代碼可移植性：傳統(tǒng)串行排序算法＞串行全比較排序法>并行全比較排序法
l??資源使用：傳統(tǒng)串行排序算法<串行全比較排序法<并行全比較排序法
l? 排序時(shí)間：并行全比較排序法＜串行全比較排序法＜傳統(tǒng)串行排序算法
?
總結(jié)
以上是生活随笔為你收集整理的FPGA篇（三）基于FPGA的几种排序算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： FPGA篇（一） 基于verilog
- 下一篇： Matlab篇（一）Matlab操作技巧