bitonic双调排序c代码和verilog实现

2024-04-04 18:18

本文主要是介绍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实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/876507

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n