高性能空間疊加分析：理論、算法與實踐

目 錄
前言
第1 章 緒論 1
1.1 空間大數(shù)據(jù)及其挑戰(zhàn) 1
1.2 計算模式的發(fā)展 1
1.3 高性能計算技術(shù) 4
1.3.1 多核并行與線程模型 4
1.3.2 集群并行與分布式內(nèi)存模型 6
1.3.3 輔助處理器加速并行 8
1.3.4 混合架構(gòu)并行高性能計算 9
1.4 高性能GIS 及其發(fā)展 9
1.4.1 網(wǎng)格GIS 10
1.4.2 集群GIS 11
1.4.3 云GIS 12
1.5 空間疊加分析算法及其發(fā)展 13
1.5.1 空間分析 13
1.5.2 疊加分析 15
1.6 本章小結(jié) 20
參考文獻 20
第2 章 并行算法設(shè)計與優(yōu)化理論 24
2.1 并行化策略 24
2.2 數(shù)據(jù)分解方法 26
2.2.1 序列劃分 27
2.2.2 規(guī)則條帶/格網(wǎng)劃分 27
2.2.3 面向空間分布特征的數(shù)據(jù)劃分 28
2.3 任務(wù)調(diào)度策略 30
2.3.1 多核并行計算架構(gòu) 31
2.3.2 集群并行計算架構(gòu) 33
2.3.3 基于GPU 并行架構(gòu) 34
2.4 負載平衡策略 35
2.4.1 多核并行計算架構(gòu) 35
2.4.2 集群并行計算架構(gòu) 36
2.4.3 基于GPU 并行架構(gòu) 37
2.5 并行計算粒度 38
2.5.1 頂點級 38
2.5.2 幾何對象級 38
2.5.3 圖層級 38
2.6 本章小結(jié) 39
參考文獻 39
第3 章 空間疊加分析算法 42
3.1 疊加分析算法體系 42
3.1.1 空間疊加分析算法工具 42
3.1.2 視覺信息疊加分析 46
3.1.3 矢量數(shù)據(jù)的空間疊加分析 47
3.1.4 柵格數(shù)據(jù)的空間疊加分析 49
3.2 拓撲疊加分析 53
3.2.1 拓撲分析基本概念 53
3.2.2 拓撲疊加概念 56
3.3 非拓撲疊加分析 58
3.3.1 非拓撲疊加的數(shù)據(jù)模型與算法體系 58
3.3.2 多邊形裁剪算法及其發(fā)展 63
3.4 本章小結(jié) 72
參考文獻 73
第4 章 空間疊加分析算法并行化的關(guān)鍵問題 75
4.1 非拓撲疊加過程中圖層間要素的映射關(guān)系 75
4.1.1 “一對多”映射關(guān)系 75
4.1.2 “多對多”映射關(guān)系 76
4.2 拓撲疊加過程中的關(guān)鍵問題 76
4.2.1 拓撲疊加一致性 76
4.2.2 線要素多邊形化 85
4.2.3 拓撲錯誤檢查 90
4.2.4 實驗分析 94
4.3 拓撲疊加與非拓撲疊加并行化實現(xiàn)方式的比較 99
4.3.1 拓撲疊加的并行化 99
4.3.2 非拓撲疊加的并行化 101
4.4 本章小結(jié) 103
參考文獻 103
第5 章 并行空間數(shù)據(jù)域分解 105
5.1 基本概念 105
5.1.1 空間數(shù)據(jù)分解原則 107
5.1.2 分解粒度與方法 108
5.2 基于空間索引的劃分策略 110
5.2.1 四叉樹空間分解法 113
5.2.2 R-tree 分解策略 115
5.2.3 存在問題與改進分解方法 116
5.3 基于空間聚類規(guī)則的劃分策略 120
5.3.1 空間聚類策略選取 121
5.3.2 數(shù)據(jù)均衡化分解 122
5.4 多策略優(yōu)化的Hilbert 排序分解 123
5.4.1 Hilbert 排序 123
5.4.2 多策略的Hilbert 排序分解 127
5.5 數(shù)據(jù)I/O 與負載均衡 130
5.6 Hilbert 索引實驗與分析 133
5.7 本章小結(jié) 133
參考文獻 134
第6 章 多邊形并行疊加分析中的數(shù)據(jù)分解方法 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 數(shù)據(jù)劃分方法 147
6.3.2 并行任務(wù)映射 148
6.4 DWSI——基于R-tree 及雙向種子搜索方法的數(shù)據(jù)分解算法 148
6.4.1 并查集理論 148
6.4.2 DWSI 算法原理 149
6.4.3 DWSI 算法效率實驗分析 151
6.5 多核并行疊加聯(lián)合算法及其優(yōu)化 153
6.5.1 算法流程 153
6.5.2 并行實驗分析 154
6.5.3 DWSI 算法并行失效問題及其改進 156
6.5.4 數(shù)據(jù)劃分方法對比 158
6.6 本章小結(jié) 158
參考文獻 159
第7 章 多邊形并行疊加分析中的任務(wù)映射方法及算法優(yōu)化 160
7.1 多邊形疊加合并串行算法及其優(yōu)化 160
7.1.1 基于Vatti 算法的多邊形合并效率分析 160
7.1.2 多邊形合并過程中的頂點累積效應(yīng)及影響 162
7.1.3 基于分治法的多邊形“樹狀”合并方法 163
vi 高性能空間疊加分析——理論、算法與實踐
7.1.4 實驗分析與比較 165
7.1.5 效率提升評價模型 166
7.2 疊加分析中的任務(wù)映射關(guān)系 167
7.2.1 “一對多”映射 167
7.2.2 “多對多”映射 167
7.2.3 集群環(huán)境下的并行任務(wù)映射問題 167
7.3 多邊形集群并行疊加合并算法 168
7.3.1 集群并行高性能算法設(shè)計原則 168
7.3.2 并行策略與數(shù)據(jù)劃分方法 169
7.3.3 多邊形集群并行疊加合并算法流程 169
7.3.4 多邊形集群并行疊加合并算法任務(wù)映射方法 170
7.3.5 實驗分析與比較 173
7.4 本章小結(jié) 175
參考文獻 176
第8 章 多核環(huán)境下的算法并行化與算法優(yōu)化 177
8.1 多核疊加分析算法并行化 177
8.1.1 并行化分析 177
8.1.2 并行點面疊加 178
8.1.3 并行線面疊加 184
8.1.4 并行多邊形疊加 190
8.2 多種數(shù)據(jù)劃分方法下D8 算法的多核并行化實驗對比 194
8.2.1 D8 串行算法 195
8.2.2 D8 算法并行化設(shè)計 196
8.2.3 實驗分析與比較 198
8.3 GIS 典型幾何算法的并行化與算法優(yōu)化 201
8.3.1 算法內(nèi)容及流程 202
8.3.2 幾何計算的并行算法設(shè)計與優(yōu)化策略 203
8.3.3 實驗與分析 205
8.4 本章小結(jié) 208
參考文獻 209
第9 章 GPU 并行與CUDA 應(yīng)用 212
9.1 GPU 的并行計算技術(shù) 212
9.1.1 GPU 介紹 212
9.1.2 基于GPU 的并行計算 212
9.1.3 CUDA 并行程序設(shè)計模型 215
9.2 CUDA 并行計算模型 216
9.2.1 CUDA 的線程和內(nèi)存結(jié)構(gòu) 217
9.2.2 CUDA 的程序執(zhí)行方式 219
9.2.3 CUDA 執(zhí)行模型 219
9.2.4 單指令多線程模式SIMT 220
9.2.5 CUDA 計算的特點分析 221
9.3 GPU 的計算優(yōu)勢 222
9.4 RaPC 算法在GPU 并行環(huán)境下的應(yīng)用 223
9.4.1 RaPC 算法效率分析 223
9.4.2 基于RaPC 算法的GPU 并行多邊形求交算法 227
9.4.3 任務(wù)映射與數(shù)據(jù)拷貝 228
9.4.4 實驗分析與討論 230
9.5 本章小結(jié) 231
參考文獻 231
第10 章 高性能集群的并行疊加分析實驗 234
10.1 并行疊加分析系統(tǒng)設(shè)計 234
10.1.1 系統(tǒng)架構(gòu)與分析 234
10.1.2 微內(nèi)核工具集 236
10.1.3 軟硬件環(huán)境 237
10.1.4 數(shù)據(jù)模型設(shè)計 239
10.2 并行空間數(shù)據(jù)管理 242
10.2.1 讀寫分離的空間數(shù)據(jù)庫集群 243
10.2.2 空間數(shù)據(jù)的高效訪問實現(xiàn) 248
10.2.3 數(shù)據(jù)訪問沖突控制 252
10.3 并行方案分析 254
10.3.1 計算與存儲協(xié)同設(shè)計 254
10.3.2 并行疊加的MapReduce 特征分析 258
10.3.3 多路I/O 并行 258
10.4 任務(wù)管理與狀態(tài)監(jiān)控 260
10.4.1 作業(yè)管理 260
10.4.2 狀態(tài)監(jiān)控 262
10.5 并行系統(tǒng)疊加實驗 263
10.5.1 并行系統(tǒng)疊加擦除實驗 263
10.5.2 計算與存儲協(xié)同方法驗證 265
10.6 本章小結(jié) 267
參考文獻 267
第11 章 多邊形疊加算法應(yīng)用——以并行緩沖區(qū)生成算法為例 268
11.1 多邊形疊加算法應(yīng)用 268
11.1.1 緩沖區(qū)生成算法原理 269
11.1.2 串行算法性能分析 271
11.1.3 基于MPI 的并行緩沖區(qū)生成算法 273
11.2 緩沖區(qū)疊加合并并行優(yōu)化 274
11.2.1 緩沖與聯(lián)合 274
11.2.2 基于并行歸約的二叉樹合并 275
11.3 基于MPI 的并行緩沖區(qū)生成算法的優(yōu)化方法 283
11.3.1 并行緩沖區(qū)算法效率分析 284
11.3.2 應(yīng)用頂點數(shù)量指標的負載平衡方法 285
11.3.3 并行結(jié)果歸并優(yōu)化 286
11.4 本章小結(jié) 288
參考文獻 288
第12 章 高性能GIS 發(fā)展展望 290
參考文獻 296