Declustering and Load-Balancing Methods for Parallelizing Geographic Information Systems
Declustering and Load-Balancing Methods for Parallelizing Geographic Information Systems
复制标题
DOI：
10.1109/69.706061
复制
发表时间：
1998-07
期刊：
影响因子：
--
通讯作者：
S. Shekhar;S. Ravada;Vipin Kumar;Douglas Chubb;Greg Turner
中科院分区：
文献类型：
--
作者：
S. Shekhar;S. Ravada;Vipin Kumar;Douglas Chubb;Greg Turner
分布式和负载均衡是设计高性能地理信息系统的重要问题，而地理信息系统是实时地形可视化等交互应用的核心组件。目前的文献为空间点数据的去聚提供了有效的方法。然而，对于扩展对象的集合，如线段链和多边形链，开发有效的去聚方法的工作很少。我们将重点介绍数据分区方法，以实现GIS操作的并行化。通过识别以下关键问题：(1)工作负载度量；(2)工作负载的空间范围；(3)工作负载在空间范围上的分布；(4)分离方法，提供了一个用于对扩展空间对象集合进行去聚的框架。我们确定并在实验中评估这些问题的每个替代方案。此外，我们还提供了一个在不同处理器之间动态平衡负载的框架。我们在分布式内存MIMD机器(Cray T3D)上对所提出的去集群和负载均衡方法进行了实验评估。实验结果表明，空间范围和工作负载度量是开发去聚方法的重要问题。实验还表明，由于本地处理的开销通常小于扩展空间对象的数据传输开销，因此通常需要复制数据以促进动态负载平衡。此外，我们还证明了动态负载均衡技术的有效性可以通过使用去簇方法来确定在运行时要传输的空间对象的子集来提高。
Declustering and load balancing are important issues in designing a high performance geographic information system (HPGIS), which is a central component of many interactive applications such as real time terrain visualization. The current literature provides efficient methods for declustering spatial point data. However, there has been little work toward developing efficient declustering methods for collections of extended objects, like chains of line segments and polygons. We focus on the data partitioning approach to parallelizing GIS operations. We provide a framework for declustering collections of extended spatial objects by identifying the following key issues: (1) work load metric; (2) spatial extent of the work load; (3) distribution of the work load over the spatial extent; and (4) declustering method. We identify and experimentally evaluate alternatives for each of these issues. In addition, we also provide a framework for dynamically balancing the load between different processors. We experimentally evaluate the proposed declustering and load balancing methods on a distributed memory MIMD machine (Cray T3D). Experimental results show that the spatial extent and the work load metric are important issues in developing a declustering method. Experiments also show that the replication of data is usually needed to facilitate dynamic load balancing, since the cost of local processing is often less than the cost of data transfer for extended spatial objects. In addition, we also show that the effectiveness of dynamic load balancing techniques can be improved by using declustering methods to determine the subsets of spatial objects to be transferred during runtime.