Speed-Up of Grid Digital Elevation Model Construction -- David Wilikofsky (Danner)

Speed-Up of Grid Digital Elevation Model Construction

David Wilikofsky and Andy Danner

Grid Digital Elevation Models (DEMs) represent the height of Earth's surface as a regular 2D-array of height values. Using the lidar remote sensing method, scientists collect dense heterogeneous point clouds, which can then be used to create grid DEMs; however, the process of generating a DEM is very computationally intensive. Because LIDAR data sets often do not fit into the main memory of a computer, an I/O bottleneck often develops from moving points into and out of memory for analysis.

This summer Professor Danner and I worked on completing a system to speed up the generation of DEMs. The system was built on top of TerraStream, an implementation of scalable algorithms for large geographic data sets. TerraStream does its computations on a single host using the machine's CPU. Our system added two new layers to TerraStream: an MPI layer and a CUDA layer. MPI is an open-source message passing interface that allows us to distribute pieces of the computations to multiple CPUs on different machines. CUDA is a programming language for running general computation on the computer's graphics processing unit (GPU). It allows us to do our computations on the graphics card whose hardware is designed to quickly handle complex linear algebra computations.

Using both MPI and CUDA has led to significant speedups in computation time: a data set with one million points that took TerraStream forty five minutes to process on a single host took our system less than ten seconds on thirty MPI hosts with CUDA capable GPUs.