Load Balancing in High Performance GIS: Declustering Polygonal Maps
Load Balancing in High Performance GIS: Declustering Polygonal Maps
复制标题
DOI：
10.1007/3-540-60159-7_13
复制
发表时间：
1995-08
期刊：
影响因子：
--
通讯作者：
S. Shekhar;S. Ravada;Vipin Kumar;Douglas Chubb;Greg Turner
中科院分区：
文献类型：
--
作者：
S. Shekhar;S. Ravada;Vipin Kumar;Douglas Chubb;Greg Turner
高性能的地理信息系统（GIS）是许多空间决策实时应用的核心组成部分。地理信息系统可能包含千兆字节的几何和特征数据（如位置、海拔、土壤类型等）。存储在存储器设备的层次结构上并表示为网格和大的多边形集合。数据通常通过范围查询（如多边形裁剪）和地图覆盖查询访问。例如，实时可视化程序通过范围查询检索模拟器当前位置周围的GIS数据的可见子集，每秒获取一百万个点。这样的性能可以得到只有利用并行和空间数据库技术的计算几何算法范围和地图覆盖queries.In本文中，我们开发和实验评估数据分区和负载平衡技术的范围查询在高性能GIS的重大进展。我们实现了静态和动态负载平衡方法的分布式内存并行机（Cray T3 D）的多边形数据，我们实验评估其性能。初步结果表明，静态和动态负载平衡方法是必要的，以提高性能，但本身是不够的。我们提出了一种新的准动态负载平衡（QDLB）技术，实现了更好的负载平衡和加速比比传统的方法。在16个处理器上，我们能够在0.12秒内处理329，296条边的地图的范围查询，其中范围查询大小为地图总面积的20-25%。我们还能够在16个处理器上实现14的平均加速比。
A high performance geographic information system (GIS) is a central component of many real-time applications of spatial decision making. The GIS may contain gigabytes of geometric and feature data (e.g. location, elevation, soil type etc.) stored on a hierarchy of memory devices and represented as grids and large sets of polygons. The data is often accessed via range queries (like polygon clipping) and map-overlay queries. For example, a real-time visualization program retrieves the visible subset of GIS data around the current location of simulator via range queries fetching a million points/second. Such performance can be obtained only with major advances in exploiting parallelism and spatial database techniques within the computational geometry algorithms for range and map-overlay queries.In this paper, we develop and experimentally evaluate data partitioning and load-balancing techniques for range queries in High Performance GIS. We implement static and dynamic load-balancing methods on a distributed memory parallel machine (Cray T3D) for polygon data, and we experimentally evaluate their performance. Preliminary results show that both the static and dynamic load-balancing methods are necessary for improved performance but are not sufficient by themselves. We propose a new quasi-dynamic load-balancing (QDLB) technique which achieves better load-balance and speedups than traditional methods. On 16 processors, we are able to process range queries in under 0.12 seconds for a map with 329,296 edges, where the range query size is 20–25% of the total area of the map. We are also able to achieve average speedups of 14 on 16 processors.