大数据并行计算利器之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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SeanCheney的专栏

阿姆达尔定律和古斯塔夫森定律摘要背景建议使用指南更多资源

摘要 构建软件的并行版本可使应用在更短的时间内运行指定的数据集,在固定时间内运行多个数据集,或运行非线程软件禁止运行的大型数据集。 并行化的成功通常通过测量并行...

3166
来自专栏大数据智能实战

LargeVis可视化技术学习

大图可视化一直是大数据可视化领域的一个关键技术,当前有各种办法,但是今年出来了一个LargeVis的技术,因此对这个技术进行复现和学习一下。 前面有很多基础理论...

4297
来自专栏程序员宝库

使用机器学习预测天气(第一部分)

本章是使用机器学习预测天气系列教程的第一部分,使用Python和机器学习来构建模型,根据从Weather Underground收集的数据来预测天气温度。

5145

如何在Python中保存ARIMA时间序列预测模型

差分自回归移动平均模型(ARIMA)是时间序列分析和预测领域流行的一个线性模型。

2918
来自专栏数据魔术师

运筹学教学|Berders decomposition (二)应用实例及算法实现(附源代码及详细的代码注释)

我们在运筹学教学|Benders decomposition(一)技术介绍篇中已经介绍了Benders Decomposition的基本原理,下面为大家提供具体...

5407
来自专栏北京马哥教育

搭建python机器学习环境以及一个机器学习例子

作者 | hzyido 来源 | 简书 糖豆贴心提醒,本文阅读时间6分钟,文末有秘密! 这篇文章介绍了Python机器学习环境的搭建,我用的机器学习开...

60712
来自专栏新智元

【干货】神经增强:用 Python 实现深度学习超分辨率处理

【新智元导读】神经网络基于样本图像的训练为模糊图像补充细节,从而把模糊图像变高清。它不能把你的照片重建成一模一样的高清版。这只有好莱坞大片才有可能做到——但使用...

6835
来自专栏落花落雨不落叶

写了个学习正则的小工具

1283
来自专栏生信宝典

Seq logo 在线绘制工具——Weblogo

seqlogo图可以直观清晰的反应序列偏好特征,每个位置出现的碱基或氨基酸类型反映了该位置序列的偏好性,每个字母的大小与该碱基在该位置上的出现频率成正相关。

2032
来自专栏机器学习算法原理与实践

tensorflow机器学习模型的跨平台上线

    在用PMML实现机器学习模型的跨平台上线中,我们讨论了使用PMML文件来实现跨平台模型上线的方法,这个方法当然也适用于tensorflow生成的模型,但...

2182

扫码关注云+社区

领取腾讯云代金券