Parallel Beam Tracing and Visualization of 200 Million Sonar Points

-
For the final project in the UIC Spring 2013 Parallel Processing Class, I worked with a classmate to optimize our current implementation of a sonar beam tracer used for The NASA ENDURANCE Project.

The beam tracer is used to process the raw data collected by the ENDURANCE AUV in Lake Bonney, Antarctica, and correct sound beam paths using information about the water chemistry. The data is clustered and noise filtered to generate a final 3D Point cloud that can be visualized in our CAVE2 system.
The ENDURANCE Sonar data in CAVE2. Photo(c) Lance Long.

A lot of corrections and adjustments need to be applied to this data before the final results are acceptable. Some of the corrections derive from the sound speed estimation through the water column, AUV navigation corrections, water level changes and noise filtering thresholds. All this parameters influence the final result, and ideally researchers can tweak them and see the result of their actions in real time.
Given the size of the data (about 200 million unique sonar range returns), reprocessing the data sequentially using the ENDURANCE dttools (https://code.google.com/p/dttools/) takes about an hour.

The objective of our project was to use the computational power of the CAVE2 cluster to bring this time down as much as possible, with minimal changes to the tools themselves.

How Sound Travels Through Water

The basic measurement of most sonar systems is the time it takes a sound pressure wave, emitted from some source, to reach a reflector and return. The observed travel time is converted to distance using an estimate of the speed of sound along the sound waves travel path. The speed of sound in sea water is roughly 1500 meters/second. However the speed of sound can vary with changes in temperature, salinity and pressure. These variations can drastically change the way sound travels through water, as changes in sound speed between bodies of water, either vertically in the water column or horizontally across the ocean, cause the trajectory of sound waves to bend. Therefore, it is imperative to understand the environmental conditions in which sonar data is taken.The composite effects of temperature, salinity and pressure are measured in a vertical column of water to provide what is known as the "sound speed profile or SSP . The SSP shown below has been generated using a Chen/Millero sound speed model over real data collected during the ENDURANCE 2009 mission.

MPI dttools

The ENDURANCE sonar data processing pipeline: the AUV navigation and sonar data is raytraced to generate initial point clouds for each lake mission. The data for each mission is then merged, clustered and noise filtered to generate a full 3D point cloud covering the entire lake. The point cloud can optionally be send to a surface recontruction step to generate a 3D mesh representing the lake bathymetry.
To parallelize the generation of a lake 3d point cloud from the raw AUV sonar and navigation data, we targeted two of the major tools on the dttools distribution:
  • dtrt: the sonar beam tracer, adapted from the MB-System implementation.
  • dtmerge: point cloud merger, cleaner, and normal estimator.
Instead of modifying the original sequential implementations, we added two new tools to the dristribution: mpidtrt and mpidtmerge. We parallelized the code for both tools using the standard Message Passing Interface (MPI) API. We modified the dttools core library as little as possible, mostly just adding a few support methods. The core library has been kept independent from MPI.

We run both tools on the 36-node CAVE2 cluster for different numbers of nodes and measured the speedups compared to the sequential version of the code. The results were very satisfying:

Speedups for the beam tracing step. The best speedup (at 128 cores) is about 12x the sequential time. Execution times went from 45.5 minutes to 3.9 minutes. After 128 cores, speedup decrease is likely due to a data transfer bottleneck.

Speedups for the merge steps, using different custering voxel sizes. For 128 cores we reach a 40x speedup: the entire dataset can be reprocessed in 5 seconds. As for beam tracing, speedups decrease past 128 cores.
A full reprocessing of the data (beam tracing + merging) went from 1 hour to a little more than four minutes. We were not using the full parallel capacity of CAVE2 at this point (only ~4 cores out of 16 were used on each machine). Further improvements can be made by optimizing a few data access portions of the code, since at this point we are likely hitting a data transfer breakpoint when writing the intermediate and final outputs (these operations are mostly sequential).

Our next step will be integrating the data processor into our visualization tool, to let researchers control the processing pipeline directly within CAVE2.


You can access the dttools source code for mpidtrt and mpidtmerge
here
and here

Comments

Post a Comment

Popular posts from this blog

Parallel Gaussian Elimination Using MPI

-
Image
In this project, we had to implement a parallel solver for linear equation systems, using a technique known as Gaussian elimination (GE). As with many other algorithms for solving linear equation systems, GE is performed on the matrix representation of the system, Ax = b, where A is the coefficient matrix and b is the vector of known values. GE works by applying a set of elementary row operations (swapping rows, multiplying a row by a non-zero number, adding a multiple of one row to another) in order to turn the coefficient matrix into upper triangular form. The algorithm has been implemented in C, using the Message Passing Interface (MPI) API. The parallel GE program measured execution times for its four main components: data distribution, Forward Elimination , Pivot row identification, Back substitution. Read the full report here
Read more

Flickering 2D transform elements in Chrome: a simple fix

-
This quick post is to point out a fix to an issue I had to deal with a few weeks ago and was caused by a Chrome update. Components with absolute positioning and a 2D CSS transform started flickering when placed inside a scrollable component. A brief search online revealed several people with similar problems, but the suggested fixes were all very different. I tested several of them (including obvious changes to the z order) before finding the one that actually did the trick. What eventually worked for me was adding an empty 3D transform to the same elements with 2D transforms: transform:translate3d(0,0,0); I guess the reason why this works is that it forces elements to be drawn via a different rendering / compositing path than standard 2D elements.
Read more