High-performance quadtree constructions on large-scale geospatial rasters using GPGPU parallel primitives

Abstract

The increasingly available graphics processing units (GPU) hardware and the emerging general purpose computing on GPU (GPGPU) technologies provide an attractive solution to high-performance geospatial computing. In this study, we have proposed a parallel, primitive-based approach to quadtree construction by transforming a multidimensional geospatial computing problem into chaining a set of generic parallel primitives that are designed for one-dimensional (1D) arrays. The proposed approach is largely data-independent and can be efficiently implemented on GPGPUs. Experiments on 4096*4096 and 16384*16384 raster tiles have shown that the implementation can complete the quadtree constructions in 13.33 ms and 250.75 ms, respectively, on average on an NVidia GPU device. Compared with an optimized serial CPU implementation based on the traditional recursive depth-first search (DFS) tree traversal schema that requires 1191.87 ms on 4096*4096 raster tiles, a significant speedup of nearly 90X has been observed. The performance of the GPU-based implementation also suggests that an indexing rate in the order of more than one billion raster cells per second can be achieved on commodity GPU devices.

Keywords:

• spatial indexing
• geographic information systems
• GPGPU
• parallel primitives
• high-performance computing

Acknowledgment

This work is supported in part by PSC–CUNY Grants #65692-00 43 and #66724-00 44, and NSF Grant IIS-1302423.

Notes

1. 1. http://en.wikipedia.org/wiki/Parallel_Random_Access_Machine

2. 2. http://www.cray.com/products/XMT.aspx

3. 3. http://www.goes-r.gov/

4. 4. http://en.wikipedia.org/wiki/Radeon

5. 5. http://developer.nvidia.com/cuda-gpus

6. 6. http://www.nvidia.com/object/io_1227008280995.html

7. 7. http://en.wikipedia.org/wiki/SIMD

8. 8. http://www.nvidia.com/object/cuda_home_new.html

9. 9. http://developer.amd.com/sdks/AMDAPPSDK/

10. 10. http://www.khronos.org/opencl/

11. 11. http://thrust.github.com/

12. 12. http://en.wikipedia.org/wiki/Generic_programming

13. 13. http://www.sgi.com/tech/stl/

14. 14. http://en.wikipedia.org/wiki/Message_Passing_Interface

15. 15. http://hadoop.apache.org/

16. 16. http://docs.oracle.com/html/B10827_01/geor_intro.htm

17. 17. http://www.postgresql.org/docs/9.1/static/ltree.html

18. 18. http://geoteci.engr.ccny.cuny.edu/geoteci/SPTestMap.html

19. 19. http://geoteci.engr.ccny.cuny.edu/rasterexplorer/comgeotiling/TestOverlay.html

20. 20. http://geoteci.engr.ccny.cuny.edu/primquad/primquad.htm

21. 21. http://biogeo.ucdavis.edu/data/climate/worldclim/1_4/grid/cur/prec_30s_bil.zip

22. 22. http://www.nvidia.com/object/product-quadro-6000-us.html

23. 23. http://en.wikipedia.org/wiki/PCI_Express

24. 24. Approximately calculated as |W|*|H|*|T|*|B|/R = (360*60)*(180*60)*(12*24)*16/(2^30) = 1001sec = 16.7min.

25. 25. http://www.nvidia.com/object/nvidia-kepler.html