本文主要是介绍bitonic双调排序c代码和verilog实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个算法除了两两比较和换位没有其他复杂操作，很适合在fpga上实现。
在fpga上如果需要排序的点比较多，实际应用就不能把这些点放到reg，只能放bram，而用bram，每个周期只能读写bram中的一项，现有网上的例子几乎所有都是资源不限制，纯仿真用不能实用的代码。
测试工程里点的个数是2048点，bram一项存两个点，每个点位宽是50bit，使用16个点的reg作为缓存，如果为加快速度，可以增加1项bram存的点个数，增加缓存点数，以资源为代价加快速度。
实际结果完成2048个点排序需要大约3万周期，在时钟跑150M情况下，大约需要200us。
可以在我的github页面下载
C程序，VS2013的工程：https://github.com/tishi43/bitonic_my
包括bitonic的两种实现函数，bitonic()和bitonic2()，以及bitonic_fpga，模拟fpga读入16个数到缓存。
verilog的modelsim仿真工程：https://github.com/tishi43/bitonic_verilog
这个链接跳转有问题，直接把上面这个https地址拷贝到浏览器的地址栏去访问
资源使用情况，用到4238个LUT和1860个reg,使用performance high的综合策略。
+-------------------------+------+-------+-----------+-------+
| Site Type | Used | Fixed | Available | Util% |
+-------------------------+------+-------+-----------+-------+
| Slice LUTs* | 4238 | 0 | 171900 | 2.47 |
| LUT as Logic | 4238 | 0 | 171900 | 2.47 |
| LUT as Memory | 0 | 0 | 70400 | 0.00 |
| Slice Registers | 1860 | 0 | 343800 | 0.54 |
| Register as Flip Flop | 1860 | 0 | 343800 | 0.54 |
| Register as Latch | 0 | 0 | 343800 | 0.00 |
| F7 Muxes | 0 | 0 | 109300 | 0.00 |
| F8 Muxes | 0 | 0 | 54650 | 0.00 |
+-------------------------+------+-------+-----------+-------+
最后贴两段C代码，两种bitonic的实现，看注释就知道原理了
// 5, 7, 15, 4, 0, 3, 11, 9, 12, 8, 1, 14, 13, 2, 6, 10//step 1: [5 7] [4 15] [0 3] [9 11] [8 12] [1 14] [2 13] [6 10]//step 1之后相邻两个一组，两两排序，两个里面都正序排列//step 2, 4个一组，//round 1，每4个1组里，第一个与最后一个比较，第二个与倒数第二个比较，如此，5和15比，7和4比,//round 2, 再两个1组两两比较//step 2之后相邻每四个一组，组内正序排列// ______// | |//round 1 [5 4 7 15] [0 3 9 11] [8 1 12 14] [2 6 13 10]// |_|//round 2 [4 5][7 15] [0 3][9 11] [1 8] [12 14] [2 6] [10 13]//step 3,round 1,8个1组比较，round 2, 4个1组比较，round 3，两个1组比较//round 1 第1个和倒数第一个比较，第二个和倒数第二个比较，round 2开始是间隔1个比较//step 3之后，相邻每8个一组，组内正序排列，// _______________// | |//round 1 [4 5 3 0 15 7 9 11] [1 8 6 2 14 12 10 13]// |__________|// ___// | |//round 2 [3 0 4 5] [9 7 15 11] [1 2 6 8] [10 12 14 13]// |___|//round 3 [0 3] [4 5] [7 9] [11 15] [1 2] [6 8] [10 12] [13 14]//step 4, round 1, 16个1组比较，round 2，8个1组比较，round 3，4个1组比较，round 4，2个1组比较//round 1 第1个和倒数第一个比较，第二个和倒数第二个比较，round 2开始是间隔1个比较// ____________________________________________________________// | |//round 1: [ 0 3 4 5 7 6 2 1 15 11 9 8 10 12 13 14 ]// |___________________________________________________|// _____________// | |//round 2 [ 0 3 2 1 7 6 4 5 ] [10 11 9 8 15 12 13 14]// |_____________|//round 3 [0 1 2 3] [4 5 7 6] [9 8 10 11] [13 12 15 14]//round 4 [0 1] [2 3] [4 5] [6 7] [8 9] [10 11] [12 13] [14 15]void bitonic(unsigned int *data, int N)
{int i;//遍历stepint j;//遍历roundint k; //遍历groupint l; //遍历group里每对数据int ii;int steps = log2(N);int groups;int rounds;int pairs; //一组有几对数据int M; //一组有几个数据,M=2*pairsfor (i = 1; i <= steps; i++){rounds = i;for (j = 0; j < rounds; j++){//step1,rounds=1,groups=1,//step2,rounds=2,j=0,groups=4,j=1,groups=8//step3,rounds=3,j=0,groups=2,j=1,groups=4,j=2,groups=8groups = N/(1<<(rounds-j));M = N/groups;pairs = M/2;for (k = 0; k < groups; k++){for (l = 0; l < pairs; l++){if (j == 0){if (data[k*M + l] >= data[(k + 1)*M - l-1]) //只有round 1 是组内第一点和最后一点，第二点和倒数第二点这样比较{int temp = data[k*M + l];data[k*M + l] = data[(k + 1)*M - l-1];data[(k + 1)*M - l-1] = temp;}}else{if (data[k*M + l] >= data[k*M +M/2+l]) //round 2之后都是间隔M/2-1点之间的比较{int temp = data[k*M + l];data[k*M + l] = data[k*M + M / 2 + l];data[k*M + M / 2 + l] = temp;}}}}printf("step %2d round %2d: ",i,j+1);for (ii = 0; ii < N; ii++){printf("%4d ",data[ii]);}printf("\n");}}
}
//另一种实现，和第一种区别是组内没有第一个与最后一个比较，第二个与倒数第二个比较，取数规律都是一样的,这种适合fpga实现//但是比较有正序和逆序// 5, 7, 15, 4, 0, 3, 11, 9, 12, 8, 1, 14, 13, 2, 6, 10// 正 逆 正 逆 正 逆 正 逆//step 1: [5 7] [15 4] [0 3] [11 9] [8 12] [14 1] [2 13] [10 6]//step 2, 4个数正，4个数逆，交替// 正 逆 正 逆//round 1 [5 4 15 7] [11 9 0 3] [8 1 14 12] [10 13 2 6]// 正 正 逆 逆 正 正 逆 逆//round 2 [4 5][7 15] [11 9][3 0] [1 8] [12 14] [13 10] [6 2]//step 3,8个数正，8个数逆// 正 逆//round 1 [4 5 3 0 11 9 7 15] [13 10 12 14 1 8 6 2]// 正 正 逆 逆//round 2 [3 0 4 5] [7 9 11 15] [13 14 12 10] [6 8 1 2]// 正 正 正 正 逆 逆 逆 逆//round 3 [0 3][4 5] [7 9][11 15] [14 13][12 10] [8 6][2 1]//step 4, 16个数正，16个数逆，也就是全部正//round 1: [ 0 3 4 5 7 6 2 1 14 13 12 10 8 9 11 15 ]//round 2 [ 0 3 2 1 7 6 4 5 ] [8 9 11 10 14 13 12 15]//round 3 [0 1 2 3] [4 5 7 6] [8 9 11 10] [12 13 14 15]//round 4 [0 1] [2 3] [4 5] [6 7] [8 9] [10 11] [12 13] [14 15]void bitonic2(unsigned int *data, int N)
{int i;//遍历stepint j;//遍历roundint k; //遍历groupint l; //遍历group里每对数据int ii;int steps = log2(N);int groups;int rounds;int pairs; //一组有几对数据int M; //一组有几个数据,M=2*pairsint ascend; //1=升序 0=降序for (i = 1; i <= steps; i++){rounds = i;//step 1,最大组2个数据，//step 2,最大组4个数据//...for (j = 0; j < rounds; j++){//step 1,rounds=1,groups=1,//step 2,rounds=2,j=0,groups=4,j=1,groups=8//step 3,rounds=3,j=0,groups=2,j=1,groups=4,j=2,groups=8groups = N / (1 << (rounds - j));M = N / groups;pairs = M / 2;for (k = 0; k < groups; k++){//round 1, k第0bit决定升降//round 2, k第1bit决定升降//...ascend = ((k >> j) & 0x1) ==0;for (l = 0; l < pairs; l++){int swap = ascend ? data[k*M + l] >= data[k*M + M / 2 + l] :data[k*M + l] <= data[k*M + M / 2 + l];if (swap){int temp = data[k*M + l];data[k*M + l] = data[k*M + M / 2 + l];data[k*M + M / 2 + l] = temp;}}}printf("step %2d round %2d: ", i, j + 1);for (ii = 0; ii < N; ii++){printf("%4d ", data[ii]);}printf("\n");}}
}
这篇关于bitonic双调排序c代码和verilog实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
