导语

  

内容提要

  

    以地理信息系统中经典的几何分析算法——空间叠加分析为研究对象,结合不同计算环境下的多种算法并行化策略,对如何发展并行计算体系下高性能的空间叠置分析算法在原理、方法和应用实践等方面进行了系统的论述。主要内容包括并行算法的体系设计空间叠加分析算法并行化的关键问题、基于数据域分解的并行化,以及空间叠加分析算法在多核环境、GPU环境和集群环境下的并行化与实践等。
    本书可供地理信息学、地图学与地理信息系统和相关领域的本科生、研究生和学者参阅。

前言
第1章  绪论
  1.1  空间大数据及其挑战
  1.2  计算模式的发展
  1.3  高性能计算技术
    1.3.1  多核并行与线程模型
    1.3.2  集群并行与分布式内存模型
    1.3.3  辅助处理器加速并行
    1.3.4  混合架构并行高性能计算
  1.4  高性能GIS及其发展
    1.4.1  网格GIS
    1.4.2  集群GIS
    1.4.3  云GIS
  1.5  空间叠加分析算法及其发展
    1.5.1  空间分析
    1.5.2  叠加分析
  1.6  本章小结
  参考文献
第2章  并行算法设计与优化理论
  2.1  并行化策略
  2.2  数据分解方法
    2.2.1  序列划分
    2.2.2  规则条带/格网划分
    2.2.3  面向空间分布特征的数据划分
  2.3  任务调度策略
    2.3.1  多核并行计算架构
    2.3.2  集群并行计算架构
    2.3.3  基于GPU并行架构
  2.4  负载平衡策略
    2.4.1  多核并行计算架构
    2.4.2  集群并行计算架构
    2.4.3  基于GPU并行架构
  2.5  并行计算粒度
    2.5.1  顶点级
    2.5.2  几何对象级
    2.5.3  图层级
  2.6  本章小结
  参考文献
第3章  空间叠加分析算法
  3.1  叠加分析算法体系
    3.1.1  空间叠加分析算法工具
    3.1.2  视觉信息叠加分析
    3.1.3  矢量数据的空间叠加分析
    3.1.4  栅格数据的空间叠加分析
  3.2  拓扑叠加分析
    3.2.1  拓扑分析基本概念
    3.2.2  拓扑叠加概念
  3.3  非拓扑叠加分析
    3.3.1  非拓扑叠加的数据模型与算法体系
    3.3.2  多边形裁剪算法及其发展
  3.4  本章小结
  参考文献
第4章  空间叠加分析算法并行化的关键问题
  4.1  非拓扑叠加过程中图层间要素的映射关系
    4.1.1  “一对多”映射关系
    4.1.2  “多对多”映射关系
  4.2  拓扑叠加过程中的关键问题
    4.2.1  拓扑叠加一致性
    4.2.2  线要素多边形化
    4.2.3  拓扑错误检查
    4.2.4  实验分析
  4.3  拓扑叠加与非拓扑叠加并行化实现方式的比较
    4.3.1  拓扑叠加的并行化
    4.3.2  非拓扑叠加的并行化
  4.4  本章小结
  参考文献
第5章  并行空间数据域分解
  5.1  基本概念
    5.1.1  空间数据分解原则
    5.1.2  分解粒度与方法
  5.2  基于空间索引的划分策略
    5.2.1  四叉树空间分解法
    5.2.2  R-tree分解策略
    5.2.3  存在问题与改进分解方法
  5.3  基于空间聚类规则的划分策略
    5.3.1  空间聚类策略选取
    5.3.2  数据均衡化分解
  5.4  多策略优化的Hilbert排序分解
    5.4.1  Hilbert排序
    5.4.2  多策略的Hilbert排序分解
  5.5  数据I/O与负载均衡
  5.6  Hilbert索引实验与分析
  5.7  本章小结
  参考文献
第6章  多边形并行叠加分析中的数据分解方法
  6.1  “一对多”映射下的并行叠加分析
    6.1.1  多核并行叠加求差算法
    6.1.2  集群并行叠加求交算法
    6.1.3  多核并行与集群并行的比较
  6.2  “多对多”映射下的多边形相交蔓延性问题
  6.3  多边形叠加分析算法的并行化差异
    6.3.1  数据划分方法
    6.3.2  并行任务映射
  6.4  DWSI——基于R-tree及双向种子搜索方法的数据分解算法
    6.4.1  并查集理论
    6.4.2  DWSI算法原理
    6.4.3  DWSI算法效率实验分析
  6.5  多核并行叠加联合算法及其优化
    6.5.1  算法流程
    6.5.2  并行实验分析
    6.5.3  DWSI算法并行失效问题及其改进
    6.5.4  数据划分方法对比
  6.6  本章小结
  参考文献
第7章  多边形并行叠加分析中的任务映射方法及算法优化
  7.1  多边形叠加合并串行算法及其优化
    7.1.1  基于Vatti算法的多边形合并效率分析
    7.1.2  多边形合并过程中的顶点累积效应及影响
    7.1.3  基于分治法的多边形“树状”合并方法
    7.1.4  实验分析与比较
    7.1.5  效率提升评价模型
  7.2  叠加分析中的任务映射关系
    7.2.1  “一对多”映射
    7.2.2  “多对多”映射
    7.2.3  集群环境下的并行任务映射问题
  7.3  多边形集群并行叠加合并算法
    7.3.1  集群并行高性能算法设计原则
    7.3.2  并行策略与数据划分方法
    7.3.3  多边形集群并行叠加合并算法流程
    7.3.4  多边形集群并行叠加合并算法任务映射方法
    7.3.5  实验分析与比较
  7.4  本章小结
  参考文献
第8章  多核环境下的算法并行化与算法优化
  8.1  多核叠加分析算法并行化
    8.1.1  并行化分析
    8.1.2  并行点面叠加
    8.1.3  并行线面叠加
    8.1.4  并行多边形叠加
  8.2  多种数据划分方法下D8算法的多核并行化实验对比
    8.2.1  D8串行算法
    8.2.2  D8算法并行化设计
    8.2.3  实验分析与比较
  8.3  GIS 典型几何算法的并行化与算法优化
    8.3.1  算法内容及流程
    8.3.2  几何计算的并行算法设计与优化策略
    8.3.3  实验与分析
  8.4  本章小结
  参考文献
第9章  GPU并行与CUDA应用
  9.1  GPU的并行计算技术
    9.1.1  GPU介绍
    9.1.2  基于GPU的并行计算
    9.1.3  CUDA并行程序设计模型
  9.2  CUDA并行计算模型
    9.2.1  CUDA的线程和内存结构
    9.2.2  CUDA的程序执行方式
    9.2.3  CUDA执行模型
    9.2.4  单指令多线程模式SIMT
    9.2.5  CUDA计算的特点分析
  9.3  GPU的计算优势
  9.4  RaPC算法在GPU并行环境下的应用
    9.4.1  RaPC算法效率分析
    9.4.2  基于RaPC算法的GPU并行多边形求交算法
    9.4.3  任务映射与数据拷贝
    9.4.4  实验分析与讨论
  9.5  本章小结
  参考文献
第10章  高性能集群的并行叠加分析实验
  10.1  并行叠加分析系统设计
    10.1.1  系统架构与分析
    10.1.2  微内核工具集
    10.1.3  软硬件环境
    10.1.4  数据模型设计
  10.2  并行空间数据管理
    10.2.1  读写分离的空间数据库集群
    10.2.2  空间数据的高效访问实现
    10.2.3  数据访问冲突控制
  10.3  并行方案分析
    10.3.1  计算与存储协同设计
    10.3.2  并行叠加的MapReduce特征分析
    10.3.3  多路I/O并行
  10.4  任务管理与状态监控
    10.4.1  作业管理
    10.4.2  状态监控
  10.5  并行系统叠加实验
    10.5.1  并行系统叠加擦除实验
    10.5.2  计算与存储协同方法验证
  10.6  本章小结
  参考文献
第11章  多边形叠加算法应用——以并行缓冲区生成算法为例
  11.1  多边形叠加算法应用
    11.1.1  缓冲区生成算法原理
    11.1.2  串行算法性能分析
    11.1.3  基于MPI的并行缓冲区生成算法
  11.2  缓冲区叠加合并并行优化
    11.2.1  缓冲与联合
    11.2.2  基于并行归约的二叉树合并
  11.3  基于MPI的并行缓冲区生成算法的优化方法
    11.3.1  并行缓冲区算法效率分析
    11.3.2  应用顶点数量指标的负载平衡方法
    11.3.3  并行结果归并优化
  11.4  本章小结
  参考文献
第12章  高性能GIS发展展望
  参考文献