Spatial computations are at the heart of topological and geometric analysis used in many science and engineering applications. Spatial data is used in mapping applications for navigation. Government agencies in public health, urban planning, transportation, scientific communities and private sector depend on spatial data mining and analysis to gain insights and produce actionable plans. However, with the increase in the size and complexity of spatial data, traditional desktop-based analysis is inadequate for the task, and there is a need to accelerate compute-intensive spatial applications on modern computers and supercomputers to get results in real-time. This requires new software design and implementation, as well as efficient algorithms for spatial query, join and overlay that can scale with the data and the available hardware resources. The first objective of this project is to develop practical parallel algorithms based on plane sweep for computational geometry problems. The second objective is to inject spatial data awareness into the existing Message Passing Interface (MPI)-based Geographic Information System (GIS), and incorporate new features to leverage high performace computing resources by using specialized software packages. A new load balancing technique will be developed that works during the file partitioning phase by non-contiguous file reading supported by the MPI library.
The MPI-Vector-IO library will enable efficient parallel input/output on large polygonal datasets stored on parallel filesystems, thus improving the state-of-the-art. The MPI-ACC-GIS software will enable existing sequential tools to be used in a high performance computing environment with thousands of cores. Parallelization of plane sweep algorithm based on concurrent data structures on shared memory machines will impact many computational geometry algorithms that rely on plane sweep for efficient implementation. Development of MPI-ACC-GIS software will be useful to geo-spatial data scientists. In addition, the project has a broader impact in training undergraduate and graduate students to perform research in high performance computing.
MPI-ACC-GIS software implementing new algorithms and methodologies along with test data, results and benchmarks will be made publicly available on a website hosted at the university.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
