-
本次课程项目通过对埃拉托斯特尼筛法的原理分析,将其与MPI并行运算结合,大大降低了运算时间和时间复杂度。埃拉托斯特尼筛法(sieve of Eratosthenes),简称埃氏筛,也称素数筛,是简单且历史悠久的筛法,用来找出一定范围内所有素数。在寻找整数N以内的素数时,古希腊数学家埃拉托斯特尼采用了一种与众不同的方法:先将2-N的各数写在纸上:在2的上面画一个圆圈,然后划去2的其他倍数;第一个既未画圈又没有被划去的数是3,将它画圈,再划去3的其他倍数;现在既未画圈又没有被划去的第一个数是5,将它画圈,并划去5的其他倍数…… 依此类推,一直到所有小于或等于N的各数都画了圈或划去为止。这时,画了圈的以及未划去的那些数正好就是小于N的素数。以25为例,详细列出算法如下:列出2以后所有数: 2, 3 ,4 ,5, 6 ,7 ,8 ,9 ,10 ,11 ,12 ,13 ,14 ,15 ,16 ,17 ,18 ,19, 20 ,21 ,22, 23, 24 ,25标记第一个质数2标记2的倍数如果最大数不大于最后一个标出的素数的平方,那么剩下的所有的数都是质数,否则回到第二步本例中,25大于2的平方,返回第二步;2之后第一个质数是3,标记3的倍数;得到的质数是2、3,25仍大于3的平方,再次返回第二步;3之后第一个质数是5,标记5的倍数;得到的质数是2、3、5,25是5的平方,筛选完毕。去掉标记的数,25以内的质数是$$ 2\text{,}3\text{,}5\text{,}7\text{,}11\text{,}13\text{,}17\text{,}19\text{,}23 $$给出其C语言串行实现:int prime[100005]; bool is_prime[1000005]; int eratosthenes(int n) { int p = 0; for (int i = 0; i <= n; i++) { is_prime[i] = true; } is_prime[0] = is_prime[1] = 0; for (int i = 2; i <= n; i++) { if (is_prime[i]) { prime[p++] = i; if (1ll * i * i <= n) { for (int j = i * i; j <= n; j += i) { is_prime[j] = 0; } } } } return p; }下面使用并行计算加快这一筛法将数组分为p个连续的块,每个块大小基本相等。平衡负载要给每个进程分配$ \lfloor \frac{n}{p} \rfloor $或$ \lceil \frac{n}{p} \rceil $ 个元素,我们考虑下面这种不同的实现方法:进程i控制的第一个元素是$ \lfloor in/p \rfloor $,最后一个元素是 $ \lfloor \left( i+1 \right) n/p \rfloor -1 $,对于特定元素j,控制他的进程是$ \lfloor \left( p\left( j+1 \right) -1 \right) /n \rfloor $。我们将数组2,3,……n 分配给p个进程,令$$ low_value=2+\lfloor id*\left( n-1 \right) /p \rfloor $$ $$ high_value=1+\lfloor \left( id+1 \right) *\left( n-1 \right) /p \rfloor $$我们用进程0来储存步骤中用于筛选的k(即2到$\sqrt{n}$的质数),所以程序运行的前提必须要求$$ 2+proc0_size>=(int)sqrt((doubt)n) $$ 对每一个进程都要提供一个marked[size]这样的数组,prime保存当前用于筛选的质数,first表示进程id中第一个要被筛掉的数对应的marked数组的下标。index用于步骤中找到比prime大的未被标记的数中最小的那个数,index为0进程专属。核心部分的程序为:if(!id) index=0;//0进程专属 prime=2;//最开始用2去筛选 do{ //找到第一个被prime筛掉的数 if(prime*prime>low_value) first=prime*prime-low_value; else if(!(low_value%prime)) first=0; else first=prime-(low_value%prime); //筛数,筛掉的数对应marked数组相应位置赋值为1,做标记 for(i=first;i<size;i+=prime) marked[i]=1; //在0进程中找到比prime大的未被标记的数中最小的那个数,用这个质数做新的prime去筛选。 if(!id){ while(marked[++index]); prime=index+2;//marked[0]对应自然数2 } //把0进程找到的新的prime更新其他进程的prime的值 MPI_Bcast(&prime,1,MPI_INT,0,MPI_COMM_WORLD); }while(prime*prime<=n);结合MPI并行运算分析可能的几种并行化改造方案:特定线程剔除特定数:优点:直观;缺点:2的倍数最多,3的倍数次多,前几个 进程几乎决定了总的运算时间,成为瓶颈。按照可用进程数分段: 将待筛选的数字分为不同的段,每个段包含连续的一部分数字。 首先,每个进程独立地筛选其分配到的段中的素数。 接下来,进程间进行通信,共享各个进程的筛选结果,以便确定进一步筛选的范围。重复上述步骤,直到完成筛选过程。在此基础上,我们又将时间复杂度具体化,分析了各部分对于时间复杂度的影响,由此提出了删除偶数和消除广播两种降低时间复杂度的方法,在1E5、1E7、1E9、1E10四个量级的数据上基本都能降低一半的运行时间。根据最终运行时间图像可以发现,在一定规模的数据量下,随着进程数量的增加,运行时间是逐渐减小的,同时在1E9和1E10规模的图像中发现,去除偶数的算法耗费的时间略高于优化通信的时间,说明任务在线程中通信花费的时间较多,在1E5规模下时间随进程增大也能说明这一结论。
-
我们现在使用MDC300去开发环视算法,使用OpenGL ES渲染1.MDC610是有使用GPU加速OpenGL ES?2.MDC300没有GPU,是不是就只能使用host芯片自带CPU跑?,我理解mini芯片的NPU是加速AI相关的,应该无法用来搞这方面的那岂不是说使用MDC300开发OpenGL渲染相关的会很吃力,毕竟MDC610也使用GPU加速渲染?请帮忙再回答一下,万分感谢!!!
-
#include <stdio.h>#include <string.h>#include <unistd.h>#include "ohos_init.h"#include "cmsis_os2.h"#include "wifiiot_gpio.h"#include "wifiiot_gpio_ex.h"uint32_t real ;osThreadId_t threadID ;void my_timer(void* arg){ (void)arg; printf("Timer runs\r\n"); GpioInit(); IoSetFunc(WIFI_IOT_IO_NAME_GPIO_2, WIFI_IOT_IO_FUNC_GPIO_2_GPIO); GpioSetDir(WIFI_IOT_IO_NAME_GPIO_2, WIFI_IOT_GPIO_DIR_OUT); GpioSetOutputVal(WIFI_IOT_IO_NAME_GPIO_2,1); usleep(10000000); GpioSetOutputVal(WIFI_IOT_IO_NAME_GPIO_2,0);}//创建任务static void my_thread(void){ osTimerId_t id1;//创建定时器的ID uint32_t timerDelay;//创建定时器的锁定时间的变量 osStatus_t status;//创建一个枚举变量,用来存储运行状况 real = 1U; id1 = osTimerNew(my_timer,osTimerPeriodic,&real,NULL); if (id1 != NULL) { timerDelay = 200U;//设延时时间为2秒 status = osTimerStart(id1,timerDelay);//用status记录osTimerStart运行结果 if (status != osOK) { printf("Timer Start failed"); } }}APP_FEATURE_INIT(my_thread);运行结果如下ready to OS startsdk ver:Hi3861V100R001C00SPC025 2020-09-03 18:10:00formatting spiffs...FileSystem mount ok.wifi init success!00 00:00:00 0 196 D 0/HIVIEW: hilog init success.00 00:00:00 0 196 D 0/HIVIEW: log limit init success.00 00:00:00 0 196 I 1/SAMGR: Bootstrap core services(count:3).00 00:00:00 0 196 I 1/SAMGR: Init service:0x4aeaec TaskPool:0xfa22400 00:00:00 0 196 I 1/SAMGR: Init service:0x4aeb10 TaskPool:0xfa89400 00:00:00 0 196 I 1/SAMGR: Init service:0x4aec20 TaskPool:0xfaa5400 00:00:00 0 228 I 1/SAMGR: Init service 0x4aeb10 <time: 0ms> success!00 00:00:00 0 128 I 1/SAMGR: Init service 0x4aeaec <time: 0ms> success!00 00:00:00 0 72 D 0/HIVIEW: hiview init success.00 00:00:00 0 72 I 1/SAMGR: Init service 0x4aec20 <time: 0ms> success!00 00:00:00 0 72 I 1/SAMGR: Initialized all core system services!00 00:00:00 0 128 I 1/SAMGR: Bootstrap system and application services(count:0).00 00:00:00 0 128 I 1/SAMGR: Initialized all system and application services!00 00:00:00 0 128 I 1/SAMGR: Bootstrap dynamic registered services(count:0).Timer runs**********watchdog isr********************syserr info start**********kernel_ver : Hi3861V100 R001C00SPC025,2020-09-03 18:10:00**********Exception Information**********PC Task Name : IdleCorePC Task ID = 1Cur Task ID = 1Task Stack Size = 0x400Exception Type = 0x80000021**********reg info**********mepc = 0xd99ecmstatus = 0x1880mtval = 0x0mcause = 0x80000021ccause = 0x0ra = 0xd99c8sp = 0xeab70gp = 0x11a9c0tp = 0xe4d80591t0 = 0x4231c4t1 = 0x3fa9a0t2 = 0x28282828s0 = 0xe8460s1 = 0x14141414a0 = 0x0a1 = 0x0a2 = 0x0a3 = 0x0a4 = 0x23232323a5 = 0x0a6 = 0x21212121a7 = 0x20202020s2 = 0x13131313s3 = 0x12121212s4 = 0x11111111s5 = 0x10101010s6 = 0x9090909s7 = 0x8080808s8 = 0x7070707s9 = 0x6060606s10 = 0x5050505s11 = 0x4040404t3 = 0x19191919t4 = 0x18181818t5 = 0x17171717t6 = 0x16161616**********memory info**********Pool Addr = 0xe8300Pool Size = 0x302c0Fail Count = 0x0Peek Size = 0x13fe0Used Size = 0x101c0**********task info**********Name : IdleCoreID = 1Status = 0x14Stack Index = 0x8Stack Peak = 0x124Stack Size = 0x400SP = 0x119880Stack : 0xea840 to 0xeac40Real SP = 0xeab70Stack Overflow = 0**********track_info**********current_item:0x4item_cnt:10Index TrackType TrackID CurTime Data1 Data20001 0065 0006 0x389 0xd99ec 0x3f5e780002 0065 0001 0x389 0x3f5e78 0xd99ec0003 0016 0007 0x389 0xd99ec 0x00004 0016 0007 0x38a 0xd99ec 0x00005 0016 0007 0x383 0xd99ec 0x00006 0016 0007 0x384 0xd99ec 0x00007 0016 0007 0x385 0xd99ec 0x00008 0016 0007 0x386 0xd99ec 0x00009 0016 0007 0x387 0xd99ec 0x00010 0016 0007 0x388 0xd99ec 0x0**********Call Stack**********Call Stack 0 -- 3f6cf8 addr:eac1cCall Stack 1 -- 3f78c0 addr:eac2cCall Stack 2 -- 3f5e24 addr:eac3c**********Call Stack end**********ready to OS startsdk ver:Hi3861V100R001C00SPC025 2020-09-03 18:10:00FileSystem mount ok.wifi init success!00 00:00:00 0 196 D 0/HIVIEW: hilog init success.00 00:00:00 0 196 D 0/HIVIEW: log limit init success.00 00:00:00 0 196 I 1/SAMGR: Bootstrap core services(count:3).00 00:00:00 0 196 I 1/SAMGR: Init service:0x4aeaec TaskPool:0xfa22400 00:00:00 0 196 I 1/SAMGR: Init service:0x4aeb10 TaskPool:0xfa89400 00:00:00 0 196 I 1/SAMGR: Init service:0x4aec20 TaskPool:0xfaa5400 00:00:00 0 228 I 1/SAMGR: Init service 0x4aeb10 <time: 0ms> success!00 00:00:00 0 128 I 1/SAMGR: Init service 0x4aeaec <time: 0ms> success!00 00:00:00 0 72 D 0/HIVIEW: hiview init success.00 00:00:00 0 72 I 1/SAMGR: Init service 0x4aec20 <time: 0ms> success!00 00:00:00 0 72 I 1/SAMGR: Initialized all core system services!00 00:00:00 0 128 I 1/SAMGR: Bootstrap system and application services(count:0).00 00:00:00 0 128 I 1/SAMGR: Initialized all system and application services!00 00:00:00 0 128 I 1/SAMGR: Bootstrap dynamic registered services(count:0).然后就是这部分内容一直重复我想知道是哪里的问题
-
您好!我目前需要在MDC300中部署我们的360环视算法,直接在MDC里运行OpenGL的一个小demo,无法调用Opengl的窗口在上位机Ubuntu系统显示,也无法直接在MDC端可视化。请问是因为可视化一定需要通过ROS转发,然后通过MDC的Mviz工具进行显示吗?Mviz如何和OpenGL配合实现交互式的可视化?有没有其他的可视化办法?我看MDC里没有OpenGL相关示例,请问有在MDC开发360环视算法或者OpenGL的示例或者其他资料吗?
上滑加载中
推荐直播
-
华为云码道 × 仓颉编程:工程化AI编码探索2026/05/27 周三 19:00-21:00
刘俊杰-华为云仓颉语言专家/李炎-华为云码道技术专家/王智鹏-OpenCangjie开源社区发起人
本场直播围绕华为云仓颉语言与华为云码道的深度结合,展示华为云智能编程从零基础到高效落地的完整生态能力。以华为云码道为引擎,仓颉语言为载体,带给大家日常提效、趣味创新到极速量产的开发体验。
回顾中 -
一个AI团队帮你写代码:华为云码道Agent Space实战2026/06/25 周四 19:00-21:00
张翰文-华为云码道工程师/郭英旭-青软创新科技集团股份有限公司 软件架构师
本场直播聚焦华为云码道Agent Space两大模式:研发办公、代码开发,亲身体验从需求到代码的AI自动化能力。实操演示基于华为 CodeArts CLI,依托 OpenSpec 规格体系从零搭建业务项目。
回顾中
热门标签