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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

It is imperative that for scalable solutions of GIS computations the modern hybrid architecture comprising a CPU-GPU pair is exploited fully. The existing parallel algorithms and data structures port reasonably well to multi-core 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2nd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2013
PublisherAssociation for Computing Machinery
Pages65-72
Number of pages8
ISBN (Print)9781450325349
DOIs
StatePublished - Jan 1 2013
Event2nd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2013 - Orlando, FL, United States
Duration: Nov 4 2013Nov 4 2013

Publication series

NameProceedings of the 2nd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2013

Other

Other2nd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2013
CountryUnited States
CityOrlando, FL
Period11/4/1311/4/13

Keywords

  • CUDA-C
  • R-tree
  • SIMT
  • analytics
  • big data
  • ecological change
  • interesting subpath
  • polygon overlay

Fingerprint Dive into the research topics of 'GPGPU-accelerated interesting interval discovery and other computations on GeoSpatial datasets - A summary of results'. Together they form a unique fingerprint.

  • Cite this

    Prasad, S. K., Shekhar, S., McDermott, M., Zhou, X., Evans, M., & Puri, S. (2013). GPGPU-accelerated interesting interval discovery and other computations on GeoSpatial datasets - A summary of results. In Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2013 (pp. 65-72). (Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data, BigSpatial 2013). Association for Computing Machinery. https://doi.org/10.1145/2534921.2535837