秦承志的科学网博客分享 http://blog.sciencenet.cn/u/qincz

博文

在数字地形分析并行算法设计方面取得的进展

已有 4112 次阅读 2012-2-28 00:15 |个人分类:科研进展|系统分类:科研笔记| 硕士生, 并行算法, 数字地形分析

数字地形分析算法常具有数据-计算密集型特点,一方面算法步骤常涉及迭代、递归等高复杂度的计算,另一方面其应用经常需面对大区域、高分辨率的大规模栅格数字高程模型(DEM)数据,在这种情况下传统以串行方式实现的数字地形分析算法以分钟、小时、乃至以天计的运行时间,显然难以满足用户的时间响应需求,因此迫切需要对算法运行效率进行改进,解决这一数字地形分析应用技术瓶颈。近年来,计算机领域不断发展的图形处理器(GPU)、集群等并行计算设备逐渐降低了应用门槛,但当前地理信息系统尚未充分利用这些先进计算设备所提供的高性能计算能力,地理计算算法并行化的研究也起步不久。在此背景下,我指导研究生基于GPU、集群等并行计算设备,选择具有典型计算特点的数字地形分析算法开展了并行化研发。

在实际计算单位汇水面积这一重要的区域地形属性时,常需用到具有迭代计算特点的DEM预处理算法和具有递归算法特点的多流向算法,我指导硕士生以这两个算法为代表,利用单台个人计算机中的GPU设备,基于图论提出了新的并行策略并研发了新的并行算法。实验结果表明,新建并行算法较串行算法的加速比分别达到~20倍(DEM预处理算法)、~10倍(多流向算法)。所提出的并行策略也适用于其他具有迭代、递归特点的数字地形分析算法的并行化设计。

该研究成果刚被《Computers & Geosciences》接收发表。

 

Qin C-Z, Zhan L-J. Parallelizing flow-accumulation calculations on Graphics Processing Units—from iterative DEM preprocessing algorithm to recursive multiple-flow-direction algorithm. Computers & Geosciences, 2012, 43: 7-16. doi: 10.1016/j.cageo.2012.02.022.

 

-------------------------------------------------------------

P.S. 之前的事:

这篇文章中的工作是我指导的2010年入学的硕士生在他入学第一学期中完成的,由于第一学年硕士生主要在玉泉路校区集中学习学位课程,所以他从2011年初根据确定的提纲开始写,拖到8月从玉泉路回所之后才完成了文章初稿。往复修改若干遍之后,在10月底投交《Computers & Geosciences》。今年1月中旬临近春节时我收到“minor revision”的修改意见,当天转给他让他先尝试修改。他节后回到所里才开始动手,再经讨论确定修改方案,由他完成第一遍修改并拟审稿意见回复,我改定之后投交了修改稿。一周后,收到文章接收通知。

现在中科院研究生院的课程学习越来越正规,好处是学生第一年被课程抓得很紧,各种作业、读文献、写报告很多,不好之处是这一年能用于真正开展硕士论文研究工作的时间很少。建议研究生院允许研究生入学后可以和导师共同提出申请,减轻一些课程报告的要求,代之以硕士研究工作的进展报告,这样可以增加学生真正用于硕士论文研究工作的时间——既然都是要进行科研能力锻炼,为什么不让学生直接选择“实战”题目来锻炼呢?这样写出的报告更可能成为硕士论文的一部分。

这次写文章的过程里,真有点“学生不急,急死老师”——这个学生刚来时喜欢编程,写东西就比较拖拉,我是心里着急,恨不得加班写完。但因为不喜欢强迫别人,所以不逼他写,只隔一段提醒一下:一个引言好像几个月都没变化了......好在这学生回所之后、等过完了暑假终于算是一鼓作气完成了初稿,后面进入了状态修改也比较自觉。包括这次“minor revision”,虽然学生让审稿意见休息了一整个春节,但他寒假过完回到所里之后也能很快修改完。这样,他在硕士论文开题前,收获了第一篇期刊论文(还是本领域不错的SCI期刊)。

导师和研究生之间,磨合很重要。象我这种不愿意催学生的,如果遇上学生自己不知道自觉的,很可能就会过程是烦恼,结果是遗憾。还好,目前招的几个学生略早略晚都能够开始自觉安排自己的科研工作了。这可能与我招的前三个学生都是推免生不无关系——通过指导他们本科论文来促进双方工作方式的磨合,让他们有时间来理解我希望的“自觉”、习惯我带学生的方式并提早进入角色。

其实做并行算法的这个学生,我指导他本科论文时定的是另一个研究方向,完成的也不错(从定量指标上看可能要略逊于高他一级的一个师兄和一个师姐——这两个学生研究生一入学,就分别以我指导完成的本科论文工作参加2009年中国地理学会年会并同时获得了年会“青年优秀学术论文”奖)。高他一级的师兄考虑硕士开题时,觉得更喜欢他做的这个方向,于是师兄师弟两人自己商量,正好这个师弟也对我刚启动的一个并行算法课题更有兴趣,就找我说要换题目。既然两厢情愿,这个师兄说的换题目之后的研究计划也能来得及毕业论文,于是就“乾坤大挪移”了。

本来是说研究进展的帖子,P.S.得有些远了。

 

P.S. 之后的事:

这篇文章之后还可以做什么工作呢?这里提出的利用单机GPU计算能力的并行策略也适用于其他具有迭代、递归特点的数字地形分析算法的并行化设计,举一反三去设计其他数字地形分析GPU并行算法是没问题的。但这样略显重复,我不打算让学生拿这个完成硕士论文。

这篇文章里提出的并行算法是运行于单机GPU的,所以能处理的DEM数据规模受限于GPU内存(实验环境的GPU内存是1G,运行该算法时能处理的最大栅格数大约5000*5000)。再想处理更大规模的DEM就要花钱换大内存的GPU了;大内存GPU还不够的话,就要砸钱(砸好多钱)换单机为集群了;换成集群后,这个算法又不适合这个硬件平台,又要重新设计代码了……难怪并行计算不够普及。针对这个问题我想还是可以做些工作的,于是就有了我这个学生的硕士论文开题的题目——祝他开题顺利,在这个新问题上有新的收获。

 



http://blog.sciencenet.cn/blog-65307-541968.html

上一篇:在坡位空间渐变信息实际应用方面取得的进展——英文稿
下一篇:中科院、地理所、GIS的研究生招生宣传这么薄弱吗?

0

该博文允许注册用户评论 请点击登录 评论 (2 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-10-24 09:01

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部