Linux下一种多核网络服务器模型设计与实现

传统的基于Linux操作系统的网络服务器程序在高负载情况下不能充分利用多核服务器硬件资源,其原因主要在于没有找到一种高效的服务器编程解决方案.为了解决这一问题,在分析了线程池技术和linux 2.6内核下的I/O多路复用技术各自的优缺点的基础上,设计并实现了一种在多核服务器平台上结合线程池和I/O多路复用的高性能网络服务器编程模型.通过实验表明,新的编程模型相对于线程池模型和单纯的I/O多路复用模型,其任务平均响应时间只占其它两种模型的8%和29%,而其平均吞吐量则达到了其它两种模型的8.4倍和1.9倍.     

一种异构多核架构快速查询多边形图层间空间关系的方法

目前,空间关系查询中常用的Plane Sweep 算法是一种串行方法,而关于多核CPU的并行查询算法,在面对海量数据查询时,由于CPU核心数及线程数量的限制,其难以满足查询效率需求。针对该问题,本文提出了一种全新的异构多核架构多边形图层间空间关系查询的并行算法。首先,利用STR 树索引过滤不相交的多边形;然后,对过滤后多边形的线段构建四叉树索引,利用CPU+GPU架构并行计算线段的相交以判断多边形环间的拓扑关系;再根据环间的拓扑关系计算多边形间的维度扩展九交模型(DE-9IM)参数值,据此确定多边形间的空间关系;最后,通过实验验证了该算法的准确性和高效性。实验表明,本算法能有效缩短大数据量的空间查询时间。在实验中逐渐增加目标数据集和源数据集多边形的数量,当两数据集都为50 000 个多边形时,以包含关系为例,相比于ArcGIS,本文提出的算法可达到2 倍的加速比。     

全球六边形离散格网的矢量线数据绘制精度控制

全球离散格网系统是一种新型的地球空间数据模型,是平面格网模型在球面上的扩展。由于六边形的几何结构优势,经常被用于球面离散格网的构建。在平面格网向球面映射过程中,因球面的不可展性,格网上的距离和方向都会发生巨大变化,导致矢量数据球面格网化绘制的精度无法得到保证,这成为矢量数据在全球离散格网显示的一个重要瓶颈,直接制约了球面格网上空间度量关系的建立。本文针对全球六边形离散格网上矢量线数据的绘制问题,研究了平面-球面映射过程,对直线方向影响的统计变化规律,对矢量线数据的格网化表达进行了精度控制,使得平面格网上的矢量绘制方法,能在球面格网上进行高精度的绘制,并保证矢量数据的球面格网绘制误差严格控制在当前层次格网的一个单元内,为格网化数据的高精度显示和格网空间度量的建立奠定了理论基础。     

基于空间填充曲线排列码划分的并行缓冲区算法

缓冲区计算是地理信息系统空间分析的基本功能之一。在矢量缓冲区研究方面,以往大多聚焦缓冲区生成算法,这些优化方法在单机计算环境中针对大规模空间数量数据的计算效率提升是有限的,因而需要并行环境下的改进方法来进一步破解计算瓶颈。本文基于Map Reduce计算模型和分布式内存计算框架,提出了一种基于空间填充曲线排列码划分的并行缓冲区分析算法(SPBM),基于空间填充曲线编码进行数据排序和范围划分,对跨越网格的数据采用近似切分方法,在考虑负载均衡的前提下对任务并行分解,之后按照给定深度的"树状"方式进行结果合并。本文在单机和集群两种环境下利用实际道路网等数据进行了实验。同等环境下,相较于目前流行的GIS软件——QGIS和Post GIS计算性能提升明显,相较于现有其他并行优化方法效率提升超过50%。这样的优化分析方法对于GIS中其他矢量分析算法的并行算法也具有一定的借鉴意义。     

基于GPU的全球地形数据加速绘制技术研究

在对基于GPU大规模地形数据快速绘制方法的研究基础上,针对GPU的批量绘制的特点,提出了改进的几何体实例化方法,把它用在全球格网的快速绘制上。把地形数据通过重新编码存储在高度图中,再结合Shader Model 3.0引入的顶点纹理拾取技术,在GPU中进行解码,得到原始的DEM数据,避免了在CPU上执行顶点缓存的更新。实验证明该算法充分利用了新一代GPU的特性,降低了CPU的负担,能达到实时绘制的要求。     

多边形叠加Vatti算法的VCS优化方法与GPU并行化

Vatti算法是常用的矢量多边形裁剪算法之一,在其构建扫描束实现交点计算的过程中,二叉树的数据结构和递归计算方法导致其计算效率受矢量多边形边界顶点数量影响显著。本文针对Vatti算法执行过程中较为耗时的扫描束构建环节,提出了一种多边形边界顶点预排序的优化方法——VCS（Vertex Coordinate Pre-Sorting）方法,并基于该方法实现了对Vatti算法的GPU细粒度并行化。VCS方法使用双向链表对Vatti算法原有的二叉树数据结构进行了替换,以较小的额外存储空间取得了多边形边界顶点信息查找效率的明显提升。在GPU环境下采用双调排序算法对多边形边界顶点数组元素进行并行化排序并过滤出有效值,克服了原始算法使用二叉树存储导致效率低下的问题。实验结果表明,改进后的算法与原始算法相比,具有相同的计算精度;当多边形顶点数量为92万,CUDA每个线程块中的线程数量为32时,使用VCS优化方法,与采用CPU计算构建扫描束方法相比,GPU并行化方法获得了39.6倍的相对加速比,矢量多边形叠加分析算法效率总体上提升了4.9倍。     

矢量瓦片并行构建与分布式存储模型研究

矢量瓦片体积小、生成效率高、支持动态交互,较传统栅格瓦片有诸多优势,是下一代互联网地图服务研究的重点。为了解决当前矢量瓦片研究中处理速度慢,扩展性差等问题,本文利用并行计算框架Spark进行矢量瓦片快速构建,通过自定义转换函数,将原始矢量数据GeoJson转换成mvt瓦片集;对于生成的矢量瓦片集,本文基于分布式内存文件系统Alluxio设计一个瓦片存储模型-VectorTileStore,模型以键值对进行数据存储,瓦片元数据占据前八个键值对,单个瓦片占据一个键值对,在数据写入的同时,基于键构建一个哈希索引,用于快速访问,模型兼容海量瓦片的组织存储,具有很强的扩展性。通过实验结果表明,本文提出的矢量瓦片并行构建算法较单机构建算法运行时间平均减少49.6%,分布式存储模型VectorTileStore较传统方案更适合海量矢量瓦片存储,存取时间效率更高。     

球面线要素的多分辨率实时简化方法

在分析球面3维数据可视化特点的基础上,提出了视点相关的球面矢量数据LOD简化方法,基本原理是:以视点为基础在屏幕空间获取投影误差,反投影到模型空间得到动态简化阈值,并结合Douglas-Peucker算法,对矢量数据进行多分辨率实时简化表达.最后,开发实验系统并对相关方法进行了验证.结果表明:在不影响球面图形可视化效果下,数据量减少了约4～5倍,有效地提高了图形渲染速度和效率.     

林木多样性模型及生长模拟

林木生存环境复杂多变,导致林木形态千差万别,为了准确描述林木的形态多样性特征,提出了一种基于模型分解的林木生长模拟方法。首先构建多样性林木三维模型,使用林木形态的实际测量数据,基于B样条函数约束树干、树冠形态,依据削度方程模拟树干直径的变化趋势,利用Direct3D实现林木形态的三维建模;其次,按林木形态特征进行林木模型分解,将林木模型分为9个子模型;最后,使用场景节点按照拓扑结构关系对子模型进行动态组织,基于胸径、树高、枝下高、冠高和冠幅生长模型,使用多核CPU多线程并行的计算方式,获得各年龄阶段林木东、南、西、北方向形态参数,从而对子模型生长状态进行控制,实现林木不同方向生长变化的可视化模拟。结果表明：该方法可将林木三维模型与生长模型紧密结合起来,林木各方向的枝下高、冠高和冠幅严格按照生长模型进行生长,可有效模拟出林木各方向生长状态的多样性;三维场景渲染帧率（FPS）保持在25以上,平均FPS可以达到50,实现林木生长的方向异质性模拟。     

一种基于三维Arnold变换的矢量地理数据置乱加密方法

矢量地理数据具有位置精度高、语义丰富、空间关系明确等特点,易于同各类专题信息集成、融合使用,是地理信息系统的一类重要数据源.互联网和大数据背景下,矢量地理数据面临泄密、侵权、窃取等安全隐患日益凸显.为此,本文分析比较了几类主要的矢量空间数据安全技术,认为数据置乱技术具有较为均衡的安全防护性能,实际应用潜力大,将经典的图像数据置乱思路引入矢量地理数据,提出了一种基于三维Arnold变换的矢量地理数据置乱加密方法.实验表明,该方法简洁高效,具有置乱度高、保持原有数据结构、完全可逆和抗暴力攻击等特点.