专栏首页CSDN技术头条大数据并行计算利器之MPI/OpenMP

大数据并行计算利器之MPI/OpenMP

1 背景

图像连通域标记算法是从一幅栅格图像(通常为二值图像)中,将互相邻接(4邻接或8邻接)的具有非背景值的像素集合提取出来,为不同的连通域填入数字标记,并且统计连通域的数目。通过对栅格图像中进行连通域标记,可用于静态地分析各连通域斑块的分布,或动态地分析这些斑块随时间的集聚或离散,是图像处理非常基础的算法。目前常用的连通域标记算法有1)扫描法(二次扫描法、单向反复扫描法等)、2)线标记法、3)区域增长法。二次扫描法由于简单通用而被广泛使用!

图1 连通域标记示意图

随着所要处理的数据量越来越大,使用传统的串行计算技术的连通域标记算法运行时间过长,难以满足实际应用的效率需求。随着并行计算技术的发展,利用不同的编程模型,许多数据密集型的计算任务可以被同时分配给单机多核或多机多处理器进行并行处理,从而有可能大幅度缩减计算时间。目前在集群计算领域广泛使用MPI来进行并行化,在单机领域广泛使用OpenMP进行化,本文针对基于等价对的二值图像连通域标记算法的进行了并行化设计,利用不同的并行编程模型分别实现了不同的并行算法,并通过实验对利用不同并行编程模型所实现的连通域标记算法进行了性能对比分析。

2 二次扫描串行算法思想

顾名思义,二次扫描串行算法步骤包含两部分。

2.1 第一次扫描

a)标记

b)等价关系建立

2.2 第二次扫描

利用并查集链表进行标记更新。

3 并行化策略

3.1 数据划分并行策略

二次扫描的串行算法中,非直接相邻的各像元数据之间是无关的,将图像分割为数据块后,对于各个数据块之间的主体运算也是独立无关的,可并行性较高,因此可通过对图像进行分块来加快计算时间、提高计算效率。

3.2 并行算法步骤

a)各个进程分别使用串行算法计算

b)各个进程将各块的标记值唯一化

c)生成等价对数组

d)主进程生成全局并查集链表

将1到n-1进程中比较获得的等价对数组统一发送给0进程,0进程生成并查集链表。

e)广播全局并查集链表,各进程更改标记值

主进程广播全局并查集链表,各进程接收后更新标记值。

4 程序实现

并行算法详细流程图。

MPI版本和OpenMP版本的并行算法。

5 测试准备

5.1 实验目的

a)正确性;

b)效率:测试不同连通域数目的数据、不同机器环境(单机和集群)、不同并行编程模型(MPI和OpenMP)对二次扫描并行算法效率的影响。

5.2 测试环境

a)单节点

CPU:两颗Intel(R) Quad Core E5645 Xeon(R) CPU,共12核;

内存:80GB ;操作系统:Linux CentOS 64位。

b)高性能集群(4个计算节点,1个存储节点)

CPU:两颗Intel(R) Quad Core E5645 Xeon(R) CPU,共12核;

内存:32GB;操作系统:Linux CentOS 64位;

节点间文件系统:Network File System (NFS)。

c)测试数据

两个相同数据量( 18640×22260 )的二值栅格图像,一个连通域为3个(简单图),一个连通域为10433个(复杂图)

6 效率测试结果

6.1 结果1:复杂图和简单图的运行时间

6.2 为什么复杂图计算时间更长?

6.3 结果2:单节点环境下,复杂图和简单图的加速比

6.4 问题1:为什么会出现超线性加速比?

原因:并查集链表的影响。

连通域标记算法很多时间用于对并查集链表进行大量查询和插入操作。

6.5 问题2:为什么复杂图比简单图加速比高?

6.6 结果3:集群环境下,复杂图和简单图的加速比

6.7 问题:为什么进程数超过12时,复杂图加速比不再上升,而简单图加速比继续上升?

6.8 结果4:OpenMP版本与MPI版本的比较?

6.9问题:为什么MPI 1个进程比OpenMP 1个线程更高效?

6.10 OpenMP开辟线程的开销?

6.11 OpenMP编译制导语句会影响编译结果?

OpenMP编译制导语句会影响编译结果,这也可以解释单线程OpenMP程序比串行程序慢这一现象。

参考文献

连通域标记算法的并行化研究,马益杭、占利军、谢传节、秦承志,《地理与地理信息科学》

附录

《GPU:并行计算利器》:

http://blog.jobbole.com/87849/

本文转载自伯乐在线,地址:http://blog.jobbole.com/88998/

本文分享自微信公众号 - CSDN技术头条(CSDN_Tech)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2015-08-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [访谈] Olivier Grisel谈scikit-learn和机器学习技术的未来

    几周前,我们的Florian Douetteau (FD)对Olivier Grisel(OG)进行了一次访谈,正好我得到这个机会去旁听。Olivier是sci...

    CSDN技术头条
  • 微软发布新的Visual C++代码优化器

    微软在5月4日发布了新的高级代码优化器,服务于Visual C++的后端编译器。提高了代码性能,可以压缩代码体积,将编译器带入了一个新的境界。 Visual C...

    CSDN技术头条
  • DNN的隐喻分析:“深度学习”,深在何处

    【编者按】DNN现在已经被互联网公司广泛使用,但大众对深度学习的理解水平并不一致。Nuance的这篇文章从另外一个角度来审视DNN技术的演进——分析隐喻如何作为...

    CSDN技术头条
  • HTML常用文本标记,超级链接和路径描述

    在body标记里写的文本内容会直接显示在页面上,但是这样直接写文本内容的方式不太好。我们在html里写文本内容的时候尽量使用标记套住内容,类似于声明这是一个文本...

    端碗吹水
  • 流媒体传输协议:RTMP、HLS和RTSP介绍

    流媒体传输协议经过几十年的发展,越来越丰富。近期的SRT、DASH、QUIC等都已经在实际中有所应用,但是这些协议里面应用最成熟,最广的协议还是RTSP/RTP...

    用户5796036
  • 中国首个开源协议“木兰宽松许可证”诞生?

    近日,中国开源云联盟官网上线了“木兰宽松许可证”(MulanPSL),这是中国首个开源协议。

    养码场
  • 11-通俗解释keystone

    如果把CTF比赛比作Project,参赛的选手就是User,CTF比赛可以提供交流学习、测评技能、学校之间交流合作等多种服务(Service);

    小朋友呢
  • 使用 PHP Masked Package 屏蔽敏感数据的实现方法

    Fuko Masked 是 Kaloyan Tsvetkov 的一个小型PHP库,用于通过用编辑后的元素替换列入黑名单的元素来屏蔽敏感数据。

    砸漏
  • nginx: [emerg] invalid log level “Files“ in C:\Program Files (x86)\phpstudy_pro\Extensions\Nginx1.16

    nginx: [emerg] invalid log level “Files” in C:\Program Files (x86)\phpstudy_pro\...

    韩旭051
  • 《从零开始做一个MEAN全栈项目》(4)

    欢迎关注本人的微信公众号“前端小填填”,专注前端技术的基础和项目开发的学习。  在上一篇中,我们讲了如何去构建第一个Express项目,总结起来就是使用两个核心...

    mukekeheart

扫码关注云+社区

领取腾讯云代金券