GPGPU-accelerated Interesting Interval Discovery and other Computations on GeoSpatial Datasets – A Summary of Results

Sushil K. Prasad, Shashi Shekhar, Michael McDermott, Xun Zhou, Michael Evans, Satish Puri
Georgia State University, Atlanta, GA
2nd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial-2013), 2013


   title={GPGPU-accelerated Interesting Interval Discovery and other Computations on GeoSpatial Datasets–A Summary of Results},

   author={Prasad, Sushil K and Shekhar, Shashi and McDermott, Michael and Zhou, Xun and Evans, Michael and Puri, Satish},



Download Download (PDF)   View View   Source Source   



It is imperative that for scalable solutions of GIS computations the modern hybrid architecture comprising a CPUGPU pair is exploited fully. The existing parallel algorithms and data structures port reasonably well to multicore CPUs, but poorly to GPGPUs because of latter’s atypical fine-grained, single-instruction multiple-thread (SIMT) architecture, extreme memory hierarchy and coalesced access requirements, and delicate CPU-GPU coordination. Recently, our parallelization of the state-of-art interesting sequence discovery algorithms calculates one-dimensional interesting intervals over an image representing the normalized difference vegetation indices of Africa within 31 ms on an nVidia 480GTX. To our knowledge, this paper reports the first parallelization of these algorithms. This allowed us to process 612 images representing biweekly data from July 1981 through Dec 2006 within 22 seconds. We were also able to pipe the output to a display in almost real-time, which would interest climate scientists. We have also undertaken parallelization of two key tree-based data structures, namely R-tree and heap, and have employed parallel R-tree in polygon overlay system. These data structure parallelization are hard because of the underlying tree topology and the fine-grained computation leading to frequent access to such data structures severely stifling parallel efficiency.
No votes yet.
Please wait...

* * *

* * *

* * *

HGPU group © 2010-2022 hgpu.org

All rights belong to the respective authors

Contact us: