一种分布式并行空间可视域分析方法

摘要

本发明涉及一种分布式并行空间可视域分析方法，使用数字高程模型数据并行动态划分模块，快速完成串行算法的并行化与数据调度，并运用不规则数据划分与视线区域的冗余机制，保证了从节点在分布式计算环境下，能够访问到目标栅格点区域所对应的数字高程模型数据，其中，不规则数据并行策略针对不同实现方式的可视域算法，具有重要的指导意义，并且结合缓冲区机制，有效保证了不同依赖程度算法的正确操作，提升了从节点的资源使用效率，具有广泛的工业化应用前景。

主权项

一种分布式并行空间可视域分析方法，基于主节点和至少一个从节点，实现分布式并行空间可视域分析方法，其中，各从节点彼此具有相等的软硬件配置；其特征在于，分布式并行空间可视域分析方法包括如下步骤：步骤001.主节点读取数字高程模型数据，并获取从节点的个数MPISize，以及单个从节点的内存大小MemSize，进入步骤002；步骤002.主节点将数字高程模型数据转化为与之相对应的数字高程模型栅格图，并获取数字高程模型栅格图中栅格点的总个数GlobalSize；其中，数字高程模型栅格图的各个栅格点分别存储数字高程模型数据中相对应的高程值，且单个栅格点存储高程值所占空间大小为NByte，然后进入步骤003；步骤003.主节点根据单个从节点的内存大小MemSize，根据预设存储处理比例系数a，获得单个从节点的单次最大数据块处理能力DataVol＝MemSize×a，其中0＜a＜1；并根据单个从节点的单次最大数据块处理能力DataVol，以及单个栅格点存储高程值所占空间大小为NByte，获得单个从节点单次最大数据块处理能力所对应的栅格点个数PixelNum，然后定义整数参数i＝1，并进入步骤004；步骤004.主节点获得所有从节点，单次最大数据块处理能力所对应的总栅格点个数为PixelNum×MPISize，并判断PixelNum×MPISize是否大于等于GlobalSize，是则进入步骤005；否则进入步骤006；步骤005.主节点将数字高程模型栅格图中的所有栅格点平均分别给各个从节点，作为主节点针对数字高程模型栅格图中栅格点的第i次分配，其中，各个从节点分别所获栅格点的个数并进入步骤007；步骤006.主节点针对数字高程模型栅格图中的栅格点，向各个从节点进行第i次分配，其中，分别向各个从节点分配的栅格点的个数n_i＝PixelNum，并进入步骤007；步骤007.主节点根据第i次栅格点分配过程中，各个从节点所获栅格点的个数n_i，以及预设数字高程模型属性参数，针对数字高程模型栅格图进行划分，获得各个从节点在数字高程模型栅格图中分别所对应的目标栅格点区域，且各个从节点分别所对应目标栅格点区域中栅格点的个数等于n_i，并进入步骤008；步骤008.主节点在数字高程模型栅格图中，分别为各个从节点所对应的目标栅格点区域设置预设大小的缓冲区，各个缓冲区分别与对应目标栅格点区域的边界外侧相邻，各个从节点所对应的目标栅格点区域和缓冲区构成从节点所对应的访问区域，且主节点分别获得各个从节点所对应访问区域的顶点序列，并分别发送给对应从节点，然后进入步骤009；步骤009.主节点分别针对各个从节点所对应访问区域中的栅格点，建立各个从节点所对应的栅格点集合，然后，主节点分别针对各个从节点，建立从节点所对应栅格点集合与数字高程模型栅格图中栅格点之间的索引，并分别发送给对应从节点，然后进入步骤010；步骤010.各从节点分别根据所对应的访问区域的顶点序列，以及从节点所对应栅格点集合与数字高程模型栅格图中栅格点之间的索引，获取其访问区域所对应的数字高程模型数据，并进入步骤011；步骤011.各从节点分别基于其访问区域所对应的数字高程模型数据，根据预设可视域分析算法属性参数，针对其访问区域中目标栅格点区域所对应的数字高程模型数据执行可视域分析，获得对应第i次栅格点分配，各从节点的可视域分析结果，并返回给主节点；同时，获得对应第i次栅格点分配，各从节点分别执行可视域分析的分析时间集合{t_i}，返回给主节点，然后判断i是否大于1，是则进入步骤017，否则进入步骤012；步骤012.主节点判断PixelNum×MPISize是否大于等于GlobalSize，是则进入步骤021；否则进入步骤013；步骤013.主节点判断GlobalSize是否大于2×PixelNum×MPISize，是则进入步骤014，否则进入步骤015；步骤014.主节点根据第i次针对各个从节点所分配的栅格点个数n_i，按预设分配优化比例b，针对数字高程模型栅格图中未分配的栅格点进行第i+1次分配，且第i+1次针对各个从节点所分配的栅格点个数n_i+1＝n_i×b，b＜1，然后进入步骤016；步骤015.主节点根据第i次针对各个从节点所分配的栅格点个数n_i，针对数字高程模型栅格图中未分配的栅格点进行第i+1次分配，且第i+1次针对各个从节点所分配的栅格点个数$n_{i+1}=\frac{GlobalSize-n_i\times MPISize}{MPISize},$然后进入步骤016；步骤016.将i+1的值赋给i，并返回步骤007；步骤017.主节点判断数字高程模型栅格图中是否存在未分配的栅格点，是则进入步骤018，否则进入步骤021；步骤018.主节点根据获得对应第i‑1次栅格点分配的从节点的效率ParaEff(i‑1)，以及根据获得对应第i次栅格点分配的从节点的效率ParaEff(i)，然后主节点判断ParaEff(i)是否大于ParaEff(i‑1)，是则进入步骤019；否则进入步骤020；步骤019.判断n_i×b×MPISize是否大于数字高程模型栅格图中未分配的栅格点的数目，是则主节点针对数字高程模型栅格图中未分配的栅格点进行第i+1次分配，将数字高程模型栅格图中未分配的栅格点平均分配给各个从节点，获取第i+1次针对各个从节点所分配的栅格点个数n_i+1，并返回步骤016；否则返回步骤014；步骤020.判断n_i‑1×MPISize是否大于数字高程模型栅格图中未分配的栅格点的数目，是则主节点针对数字高程模型栅格图中未分配的栅格点进行第i+1次分配，将数字高程模型栅格图中未分配的栅格点平均分配给各个从节点，获取第i+1次针对各个从节点所分配的栅格点个数n_i+1，并返回步骤016；否则主节点针对数字高程模型栅格图中未分配的栅格点进行第i+1次分配，且第i+1次针对各个从节点所分配的栅格点个数n_i+1等于n_i‑1，并返回步骤016；步骤021.主节点将针对数字高程模型数据，将所接收到的可视域分析结果合并生成结果文件进行输出，即获得分布式并行空间可视域分析方法的结果。