醉染图书高能空间叠加分析——理论、算法与实践9787030683

前言

章 绪论 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.. 面向空间分布特征的数据划分 28

. 任务调度策略 30

..1 多核并行计算架构 31

..2 集群并行计算架构 33

.. 基于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.. 拓扑错误检查 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.. 存在问题与改进分解方法 116

5.3 基于空间聚类规则的划分策略 120

5.3.1 空间聚类策略选取 121

5.3.2 数据均衡化分解 122

5.4 多策略优化的Hilbert 排序分解 1

5.4.1 Hilbert 排序 1

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

7.1.4 实验分析与比较 165

7.1.5 效率提升评价模型 166

7.2 叠加分析中的任务映关系 167

7.2.1 “一对多”映 167

7.2.2 “多对多”映 167

7.. 集群环境下的并行任务映问题 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.. 实验分析与比较 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.. CUDA 执行模型 219

9.2.4 单指令多线程模式SIMT 220

9.2.5 CUDA 计算的特点分析 221

9.3 GPU 的计算优势 222

9.4 RaPC 算法在GPU 并行环境下的应用 2

9.4.1 RaPC 算法效率分析 2

9.4.2 基于RaPC 算法的GPU 并行多边形求交算法 227

9.4.3 任务映与数据拷贝 228

9.4.4 实验分析与讨论 0

9.5 本章小结 1

参考文献 1

0 章 高能集群的并行叠加分析实验 4

10.1 并行叠加分析系统设计 4

10.1.1 系统架构与分析 4

10.1.2 微内核工具集

10.1.3 软硬件环境

10.1.4 数据模型设计

10.2 并行空间数据管理 242

10.2.1 读写分离的空间数据库集群 243

10.2.2 空间数据的高效访问实现 248

10.. 数据访问控制 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

1 章 多边形叠加算法应用——以并行缓冲区生成算法为例 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

2 章 高能GIS 发展展望 290

参考文献 296