论文研究-基于图模型的多边形自动并行构建算法.pdf

所需积分/C币:7 2019-07-22 18:53:08 1.48MB .PDF

目前GIS基础算法并行化成为高性能GIS进一步深入的前提, 作为GIS空间分析基础算法的重点, 有必要对多边形构建提出一种自动并行算法。为此, 提出基于图模型的多边形自动并行构建算法。该算法根据图模型中有向闭合环的特点对一组线段的集合进行多边形构建, 能有效提高多边形构建的自动化程度。将搜索、排序等耗时较多的操作进行并行化处理, 能有效减少全局搜索次数及整体排序和逻辑操作时间。实验表明, 在对大规模线性数据生成区域时, 该算法能有效地实现效率提升, 达到良好的效果。
1636 计算机应用研究 第29卷 通过改进计算的某一部分,所得到的性能提升可以用An dahl定律定量地反映出来。 Amdahl定律定义了采用某种优化 或者并行方案所取得的加速比。 并行加速比(cdp)=并行前整个任务的运行时间 运仃 子边國"口叫--- lhdl23323214s4545 通过加速比公式,可以得到实验结果加速比的折线图如图 7所示。 图5标志 标记每条子边的目的是得到特殊标记线,特殊标记线指的 15 是属于同一条父边且具有相同 label的子边,并将这些特殊标 上加速比」 0.5 记线删除。删除标记线主要有三个步骤,都是并行扫描模型中 的基本操作:a)向前独占扫描;b)逻辑减;ε)排序。 0单核双核四核入核八核 图7加速比折线图 2.3生成有效环 由折线图可以看到,在四核的情况下加速比是最高的,达 根据边的存储关系生成环,闭合的环才是有效环,判断是到了1.875,们在六核和八核的情况下,加速比降低到1.66,这 否闭合主要是判断环的首边和尾边是否相同,首尾边相同的环说明了并行屮使用的核越多,额外开销也越多。但在总体上并 即是闭合环。个多边形至少有两个环,因此需要进行判淅的行加速比是相当不错的,达到了提高效率的目的。因此,可以 环的数目至少是多边形数目的两倍,这一判断过程耗时较长。认为在并行条件下进行多边形构建是提高效率的有效途径。 在并行构建中,根据可用处理器数目,将所有环分配到各个处4结束语 理器中,每个处理器处理一组相邻接的环,并行操作使得判断 时间可以大为缩减。最后再根据每组的处理结果,保留有效 本文提出了一种基于图模型进行多边形白动构建的并行 环删除无效环。图2共生成六个环,执行判断操作后留下的算法,使得空间分析的基层运算效率得到提升。本文算法是将 环都是有效的,生成的有效环如图6所示。 运算中对杳询、排列等消耗时间的基本操作并行化以提高运行 父边四区区么团 效率,在此基础上考虑空间数据分布的邻近性及并行节点间的 负载均衡。为了求证以上并行构建的可行性和有效性,本文进 行了测试实验,由实验结果可知基于图模型的多边形自动构建 编号 并行算法在效率上达到了预期效果,证明这一算法是可行的。 (l 未来的硏宄方向主要是增强扩展性和提高加速比,同时实现 4+2 些其他操作,如空间相交。 Lia PlI nio 书17151 参考文献 图6生成有效环 L1 GUTING R IL, PAPADIAS D. Advances in spatial databases [C// 构建多边形过程的最后一步是,根据有效环的的方向来判 Proc of the 6th Internat ional Symposium on SSD. 1999 断该环是壳或老是洞,环的方向是逆时针就是洞,顺时针即是[2 SCHOLL M. Advances in spatial databases[C]// Proc of the 5th In 壳。此判断过程与判断有效环一样需婁耗费大量时间,因此使 ternational Symposium on SED. 1997 用与上述判断同样的方法,根据处理器个数将坼分组,然后对3』闫浩文,陈全功基于方位角计算的拓扑多边形自动构建快速算 所有环组进行并发判断。上述有效环最后生成的洞和壳如表 法[J.中国图象图形学报,2000,5(7):563-5 2所小 [4』李大军,刘波,赵宝贵,等,拓扑多边形自动构建的一种改迂算法 「J.计算杌工程和应用,2005,41(16):80-82 表2洞和亮 [5」王杰臣.多边形拓扑关系构建的栅格算法[冂.测绘学报,2002 31(3):249-254. [6]罗芳,艾廷华,王洪.闭合坐标链多边形数据的拓扑关系快速构建 3-5-t63 U11-12-711-+1 「J.武汉大学学报:信息科学版,2004,29(6):558-561 110-+14-1-l [7]陈占龙,吴信才,吴亮.基于单调链和STR树的简单要素模型多 边形叠置分析算法LJ.测绘学报,2010,39(1):l02-108. 3实验及性能分析 [8 BESTUL T. Parallel paradigms and practices for spatial data[D.Col- 在保持正确性的前提下,多边形并行构建的最终目的是对[9 BLELLOCH G H. Scans as primitive parallel operations [ J.EE 一定规模的空间数据进行多边形构建运算时,运算速度可以得 Trans on Computers, 1989, 38(11): 1526-1538 到显著的提高。表3描述了在不同的核个数下,对规模为101 LINDENBAUM M, SAMET H, HJALTASON G R. a probabilistic 93664个对象的线数据进行并行多边形构建的运算时间。 analysis of trie-based sorting of large collections of line segments, CS 表3不同核数量下的实验结果 TR-3455 R. College Park: University of Maryland, 1995 核数 线的个数 [11] HOEL E G, SAMET H. Data-parallel polygonization[ J]. Parallel 成区个数 Computing,2003,29(10):1381-1401 93664 34123 12] BLELLOCH GE, LITTLE JJ Parallel solutions to geometric problems 93664 34123 on the scan model of computation, AIM-952 R 1. Cambridge, MA 34123 MII,1988 93664 L 13 SCIIWARTZ J T. Lltracumputers J. ACM Trans on Programming 18 93664 34123 Languages and Systems, 1980, 2(4):484-521

...展开详情
img

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐