In the first project, we are revisiting spatial data analytics on heterogeneous systems comprised of data processing units (DPU), GPUs and CPUs. The DPUs are a new class of programmable processors made by NVidia (and other manufacturers). Similar to a modern smart network interface card, DPUs can be used to filter unnecessary data from overwhelming the CPU and memory bandwidth. DPUs can be used by CPUs to offload computations; thereby reducing the load on CPU and increasing the capability of the compute node.
Second project is on “Nearest Neighbor Similarity Search for Polygons and Trajectories”.
Research thrust of the third project is to design communication-efficient spatial analytics algorithms for data-intensive computations by leveraging Processing-In-Memory (PIM) Paradigm. In this new computational model, code execution happens near DRAM memory instead of CPU.
Research publications are focused on leveraging GPUs and HPC compute clusters for speeding up geospatial analytics workloads like polygon overlay, spatial join, Voronoi diagram, geometric intersection, spatial autocorrelation, etc.
Grants
Communication-efficient and topology-aware designs for geo-spatial analytics on heterogeneous platforms , NSF, $511K, Duration: 2022 – 2027
Link to Project Page: DPU-based Hierarchical Filter and Refine Computation
Approximate Nearest Neighbor Similarity Search for Large Polygonal and Trajectory Datasets, NSF, $235K, Duration: 2023 – 2026 Link
Efficient Indexing and Similarity Searches Exploiting Processing-in-Memory Architectures for Memory-Bound Scientific Workloads. NSF, $303K, Duration: 2024 – 2027 .
MPI-ACC-GIS: Accelerating Geo-Spatial Computations on HPC Platform, $175K, 2018 – 2021, Link
Recent Publications
Extending Segment Tree for Polygon Clipping and Parallelizing using OpenMP and OpenACC Directives, International Conference on Parallel Processing (ICPP), Sweden, Aug. 2024. (Paper Link)
Geospatial Filter and Refine Computations on Nvidia Bluefield Data Processing Units (Extended Abstract and Research Poster), SC’23 Link
Efficient PRAM and Practical GPU Algorithms for Large Polygon Clipping with Degenerate Cases, 23rd IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGrid), May 2023. Acceptance rate 21%, Best Papers Finalist. Paper
Fine-grained Dynamic Load Balancing in Spatial Join by Work Stealing on Distributed Memory, November, ACM SIGSPATIAL 2022, Seattle, WA. Paper, Github Code
Accelerating Spatial Autocorrelation Computation with Parallelization, Vectorization and Memory Access Optimization, 22nd IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGrid), Italy, May 2022 (Paper, IEEE Link), Acceptance Rate 24% (75/302 submissions)
Teaching SIMD Instructions using Intel Intrinsics in Computer Organization Course, Lightning Talks of EduHPC 2021.
EduHPC-21 Workshop, EduHPC@SC 2021, November, 2021 Paper, Slides and Code on GitHub, Video
Efficient Filters for Geometric Intersection Computations using GPU, ACM SIGSpatial, 2020. Paper, Github Code, Slides, Video
Efficient Parallel and Adaptive Partitioning for Load-balancing in Spatial Join, IEEE IPDPS 2020. Paper link, Video, Slides
Hierarchical Filter and Refinement System over Large Polygonal Datasets on CPU-GPU, IEEE HiPC, 2019. Paper, Github Code, Slides
Current Research Assistants at Missouri S&T
- Alima Subedi (from Fall 2023), PhD Student – Shape Similarity Search.
- Oluwadamilola Durowoju (from Spring 2024), PhD Student – Nearest Neighbor Similarity Search.
- Nathan Tibbetts (from Spring 2024), PhD Student – Analytics on NVidia DPU and Hierarchical Data Visualization.
- Tasmia Jannat (from Fall 2024), PhD Student
- Sankalpa Pokharel (from Fall 2024), PhD Student
- Tanvi Purwar, MS Student, 2024
- Amulya Araveti, MS Student, 2024
- Leah Edwards (Fall 2023, Summer & Fall 2024), Undergraduate Student, Analytics on Processing in Memory devices.
Past Projects
In the past, our lab has worked on the following topics:
Parallelization of Computational Geometry Algorithms on Multi-cores and GPUs.
MPI-GIS: A Message Passing Interface based system for large-scale geospatial data (GitHub Code)
Parallel I/O and Partitioning for irregular variable-length data on parallel filesystems
Graduated Students
Buddhi Ashan (PhD Graduate, Summer 2024, Co-Advisor)
Title: Practical Parallel Algorithms over GIS Polygonal Datasets for Segment Tree-based Clipping and for Quad Tree-based Encoding to Search for Similar Shapes
Anmol Paudel (PhD Graduate, Spring 2022)
– Project: Acceleration of Computational Geometry Algorithms for High Performance Computing based Geo-Spatial Big Data Analysis
– Interned at Microsoft (Summer 2021), Oakridge National Lab, Tennessee (Summer 2020) and Lawrence Livermore National Lab, California (Summer 2019). These national labs are state-of-the-art HPC centers.
Jie Yang (PhD Graduate, Spring 2022)
– Project: Workload-aware Spatial Data Partitioning and Load Balancing Algorithms for Parallel Spatial Join by Work Stealing.
– Dissertation Title: Load Balancing Algorithms for Parallel Geo-Spatial Join on HPC Platforms
– Software Engineer, ByteDance. Interned at Argonne National Lab, Illinois (Summer 2021).
Yiming Liu (PhD Graduate, Spring 2021)
Phd Dissertation Title: Hierarchical and Adaptive Filter and Refinement Algorithms for Geometric Intersection Computations on GPU. Works in Energy Sector.
Undergraduate Students’ Project Supervision
Matt Schwennsen, Michigan Technological Univeristy, Michigan, REU Summer 2022, Now PhD student at University of Wisconsin, Madison.
– Project: Approximate Near Neighbor Query for geospatial data.
Jacqueline Gutierrez, Marquette University, Summer 2022
– Project: Using AVX-512 SIMD Intrinsics to speedup computational geometry algorithms.
Ulises Nevarez, Marquette University, Fall 2021
– Project: Using SIMD Intrinsics to speedup computational geometry algorithms.
Theresa Chen, Carleton College, Minnesota, REU Summer 2021, Now PhD student at University of Minnesota, Twin Cities.
– Project: Using Machine Learning to Predict Sea Ice Features from Remote Sensing Data. Poster
Erin Doyle, Saint Mary’s College, Indiana, REU Summer 2020
– Project: Modeling and Predicting Changes in Sea Ice Thickness from NASA’s ICESat-2 Launch. Poster
Acknowledgement
We gratefully acknowledge the support of NVIDIA Corporation with the donation of the two Titan Xp and one Titan V used for the lab’s research.
We also acknowledge NSF Career Grant (Link), NSF OAC 2024 (#2402987), NSF OAC 2023 (#2344585), and NSF CRII grants for support.
Publications
