高性能空间叠加分析——理论、算法与实践

目 录
前言
第1 章 绪论 1
1.1 空间大数据及其挑战 1
1.2 计算模式的发展 1
1.3 高性能计算技术 4
1.3.1 多核并行与线程模型 4
1.3.2 集群并行与分布式内存模型 6
1.3.3 辅助处理器加速并行 8
1.3.4 混合架构并行高性能计算 9
1.4 高性能GIS 及其发展 9
1.4.1 网格GIS 10
1.4.2 集群GIS 11
1.4.3 云GIS 12
1.5 空间叠加分析算法及其发展 13
1.5.1 空间分析 13
1.5.2 叠加分析 15
1.6 本章小结 20
参考文献 20
第2 章 并行算法设计与优化理论 24
2.1 并行化策略 24
2.2 数据分解方法 26
2.2.1 序列划分 27
2.2.2 规则条带/格网划分 27
2.2.3 面向空间分布特征的数据划分 28
2.3 任务调度策略 30
2.3.1 多核并行计算架构 31
2.3.2 集群并行计算架构 33
2.3.3 基于GPU 并行架构 34
2.4 负载平衡策略 35
2.4.1 多核并行计算架构 35
2.4.2 集群并行计算架构 36
2.4.3 基于GPU 并行架构 37
2.5 并行计算粒度 38
2.5.1 顶点级 38
2.5.2 几何对象级 38
2.5.3 图层级 38
2.6 本章小结 39
参考文献 39
第3 章 空间叠加分析算法 42
3.1 叠加分析算法体系 42
3.1.1 空间叠加分析算法工具 42
3.1.2 视觉信息叠加分析 46
3.1.3 矢量数据的空间叠加分析 47
3.1.4 栅格数据的空间叠加分析 49
3.2 拓扑叠加分析 53
3.2.1 拓扑分析基本概念 53
3.2.2 拓扑叠加概念 56
3.3 非拓扑叠加分析 58
3.3.1 非拓扑叠加的数据模型与算法体系 58
3.3.2 多边形裁剪算法及其发展 63
3.4 本章小结 72
参考文献 73
第4 章 空间叠加分析算法并行化的关键问题 75
4.1 非拓扑叠加过程中图层间要素的映射关系 75
4.1.1 “一对多”映射关系 75
4.1.2 “多对多”映射关系 76
4.2 拓扑叠加过程中的关键问题 76
4.2.1 拓扑叠加一致性 76
4.2.2 线要素多边形化 85
4.2.3 拓扑错误检查 90
4.2.4 实验分析 94
4.3 拓扑叠加与非拓扑叠加并行化实现方式的比较 99
4.3.1 拓扑叠加的并行化 99
4.3.2 非拓扑叠加的并行化 101
4.4 本章小结 103
参考文献 103
第5 章 并行空间数据域分解 105
5.1 基本概念 105
5.1.1 空间数据分解原则 107
5.1.2 分解粒度与方法 108
5.2 基于空间索引的划分策略 110
5.2.1 四叉树空间分解法 113
5.2.2 R-tree 分解策略 115
5.2.3 存在问题与改进分解方法 116
5.3 基于空间聚类规则的划分策略 120
5.3.1 空间聚类策略选取 121
5.3.2 数据均衡化分解 122
5.4 多策略优化的Hilbert 排序分解 123
5.4.1 Hilbert 排序 123
5.4.2 多策略的Hilbert 排序分解 127
5.5 数据I/O 与负载均衡 130
5.6 Hilbert 索引实验与分析 133
5.7 本章小结 133
参考文献 134
第6 章 多边形并行叠加分析中的数据分解方法 136
6.1 “一对多”映射下的并行叠加分析 136
6.1.1 多核并行叠加求差算法 136
6.1.2 集群并行叠加求交算法 142
6.1.3 多核并行与集群并行的比较 145
6.2 “多对多”映射下的多边形相交蔓延性问题 147
6.3 多边形叠加分析算法的并行化差异 147
6.3.1 数据划分方法 147
6.3.2 并行任务映射 148
6.4 DWSI——基于R-tree 及双向种子搜索方法的数据分解算法 148
6.4.1 并查集理论 148
6.4.2 DWSI 算法原理 149
6.4.3 DWSI 算法效率实验分析 151
6.5 多核并行叠加联合算法及其优化 153
6.5.1 算法流程 153
6.5.2 并行实验分析 154
6.5.3 DWSI 算法并行失效问题及其改进 156
6.5.4 数据划分方法对比 158
6.6 本章小结 158
参考文献 159
第7 章 多边形并行叠加分析中的任务映射方法及算法优化 160
7.1 多边形叠加合并串行算法及其优化 160
7.1.1 基于Vatti 算法的多边形合并效率分析 160
7.1.2 多边形合并过程中的顶点累积效应及影响 162
7.1.3 基于分治法的多边形“树状”合并方法 163
vi 高性能空间叠加分析——理论、算法与实践
7.1.4 实验分析与比较 165
7.1.5 效率提升评价模型 166
7.2 叠加分析中的任务映射关系 167
7.2.1 “一对多”映射 167
7.2.2 “多对多”映射 167
7.2.3 集群环境下的并行任务映射问题 167
7.3 多边形集群并行叠加合并算法 168
7.3.1 集群并行高性能算法设计原则 168
7.3.2 并行策略与数据划分方法 169
7.3.3 多边形集群并行叠加合并算法流程 169
7.3.4 多边形集群并行叠加合并算法任务映射方法 170
7.3.5 实验分析与比较 173
7.4 本章小结 175
参考文献 176
第8 章 多核环境下的算法并行化与算法优化 177
8.1 多核叠加分析算法并行化 177
8.1.1 并行化分析 177
8.1.2 并行点面叠加 178
8.1.3 并行线面叠加 184
8.1.4 并行多边形叠加 190
8.2 多种数据划分方法下D8 算法的多核并行化实验对比 194
8.2.1 D8 串行算法 195
8.2.2 D8 算法并行化设计 196
8.2.3 实验分析与比较 198
8.3 GIS 典型几何算法的并行化与算法优化 201
8.3.1 算法内容及流程 202
8.3.2 几何计算的并行算法设计与优化策略 203
8.3.3 实验与分析 205
8.4 本章小结 208
参考文献 209
第9 章 GPU 并行与CUDA 应用 212
9.1 GPU 的并行计算技术 212
9.1.1 GPU 介绍 212
9.1.2 基于GPU 的并行计算 212
9.1.3 CUDA 并行程序设计模型 215
9.2 CUDA 并行计算模型 216
9.2.1 CUDA 的线程和内存结构 217
9.2.2 CUDA 的程序执行方式 219
9.2.3 CUDA 执行模型 219
9.2.4 单指令多线程模式SIMT 220
9.2.5 CUDA 计算的特点分析 221
9.3 GPU 的计算优势 222
9.4 RaPC 算法在GPU 并行环境下的应用 223
9.4.1 RaPC 算法效率分析 223
9.4.2 基于RaPC 算法的GPU 并行多边形求交算法 227
9.4.3 任务映射与数据拷贝 228
9.4.4 实验分析与讨论 230
9.5 本章小结 231
参考文献 231
第10 章 高性能集群的并行叠加分析实验 234
10.1 并行叠加分析系统设计 234
10.1.1 系统架构与分析 234
10.1.2 微内核工具集 236
10.1.3 软硬件环境 237
10.1.4 数据模型设计 239
10.2 并行空间数据管理 242
10.2.1 读写分离的空间数据库集群 243
10.2.2 空间数据的高效访问实现 248
10.2.3 数据访问冲突控制 252
10.3 并行方案分析 254
10.3.1 计算与存储协同设计 254
10.3.2 并行叠加的MapReduce 特征分析 258
10.3.3 多路I/O 并行 258
10.4 任务管理与状态监控 260
10.4.1 作业管理 260
10.4.2 状态监控 262
10.5 并行系统叠加实验 263
10.5.1 并行系统叠加擦除实验 263
10.5.2 计算与存储协同方法验证 265
10.6 本章小结 267
参考文献 267
第11 章 多边形叠加算法应用——以并行缓冲区生成算法为例 268
11.1 多边形叠加算法应用 268
11.1.1 缓冲区生成算法原理 269
11.1.2 串行算法性能分析 271
11.1.3 基于MPI 的并行缓冲区生成算法 273
11.2 缓冲区叠加合并并行优化 274
11.2.1 缓冲与联合 274
11.2.2 基于并行归约的二叉树合并 275
11.3 基于MPI 的并行缓冲区生成算法的优化方法 283
11.3.1 并行缓冲区算法效率分析 284
11.3.2 应用顶点数量指标的负载平衡方法 285
11.3.3 并行结果归并优化 286
11.4 本章小结 288
参考文献 288
第12 章 高性能GIS 发展展望 290
参考文献 296