《高性能空間疊加分析——理論、算法與實踐》是2021年科學出版社出版的圖書。
基本介紹
- 中文名：高性能空間疊加分析——理論、算法與實踐
- 作者：馬廷
- 出版社：科學出版社
- 出版時間：2021年3月1日
- 開本：16 開
- 裝幀：平裝
- ISBN：9787030682383
內容簡介,圖書目錄,
內容簡介
以地理信息系統中經典的幾何分析算法——空間疊加分析為研究對象，結合不同計算環境下的多種算法並行化策略，對如何發展並行計算體系下高性能的空間疊置分析算法在原理、方法和套用實踐等方面進行了系統的論述。主要內容包括並行算法的體系設計、空間疊加分析算法並行化的關鍵問題、基於數據域分解的並行化，以及空間疊加分析算法在多核環境、GPU 環境和集群環境下的並行化與實踐等。
圖書目錄
前言
第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
