A Parallel Approach to Constructing Digital Elevation Models

A Parallel Approach to Constructing Digital Elevation Models

Jake Baskin and Andy Danner

Computational intensive interpolation methods convert large LIDAR point sets to more useful grid digital elevation models. Terrastream (archive provided by Wayback Machine) is an implementation of scalable algorithms for processing large LIDAR data sets containing billions of points. However, the process is done serially on a single machine and can sometimes run for days on large jobs.

This summer Jake and Professor Danner investigated using multiple computers at the same time to speed up part of terrastream. The improved algorithm farms groups of the points to be interpolated out to as many processors as are available and interpolates these groups in parallel, drastically reducing the runtime of the algorithm. Using MPI, a flexible framework for implementing parallel algorithms, the new code collects the results from each processor and writes a file that can be processed by GRASS, an open source GIS program. Although research is still ongoing, the data collected so far show a speed up proportional to the number of processors used from 3 up to the maximum number of processors we have been able to test (98). For an example of the speed up attained from parallelization, creating an image of 358 sq. miles of the Neuse river basin in North Carolina at 20 ft resolution took over 46 hours serially, but completed in under two hours using 98 processors.