Processing Lidar with MPI - Liblas + MPICH2

I did some work in the last company for processing and reclassifying Lidar points using Liblas. The first Python implementation had lots of point-in-polygon queries and even with prepared geometries in GEOS took a few hours. We improved the execution of this by rasterizing the polygons, while polygons in theory have arbitrary precision and rasters are limited to the spacing they are gridded at, in this case the polygons were derived by classifying a rasterized version of the Lidar and the raster mask should have the same degree of precision.

The mask is overly generous in classes at times, considering each class as a local surface. A piecewise interpolation model can often be used to identify disparate points in context and perform class switching. In unordered Lidar data this may lead to many passes through the data generating neighbourhood class relationships if an index has not been built e.g. Octree.

I decided to adopt the Google philosophy of scale solves everything - and implemented the Lidar processing using MPI (Specifically MPICH2). The solution is implemented with task queues.

1. Read all data on all nodes except last
2. Node 0 makes a pass through all data sending each point in round robin to intermediate nodes
3. Intermediate nodes receive a point and make another pass through all data identifying nearby points and using them in an IDW2 estimate
4. Intermediate nodes message with IDW2 estimate to last node in the set (in charge of serializing) which makes various comparisons against classification masks (e.g. SRTM Water Boundary mask) and geo-statistical surface consistency before reclassifying and serializing to an output LAS file.

The task is essentially O(n^2) but with sufficient nodes we can bring it down to O(n*n/M+M*overheads) where M is the number of nodes. If the dataset is large enough and M is suitably chosen we gain significant speed increases. I got so carried away with Lidar + MPI ( and since I don't want to mix it with my PhD stuff) I started a small code dump on Google Code. Use CMake and see if you can build it. Lots of sample Lidar here.

MPICH2 - Joys of windows MPI

LAM/MPI is showing its age on our Ubuntu cluster. LAMD dies at times and we always seem to have more windows machines than linux pxeboot boxes. MPICH2 may allow heterogenous clusters. Here are runtimes with different communication protocols on MPICH2 and LAM with the trivial prime tutorial.

MPICH2 : [FAQ]
sock: 4.562287
nemesis: 0.403781
ssm: 0.641682
mt: 4.793552
default: 4.489148
auto: 4.200369


LAM/MPI : [FAQ]
usysv: 0.260094
sysv: 1.899345
tcp: 1.965503
crtcp: 2.089337

The test app was built with CMake and the very handy MPI detection with MPI choice options.

On the other hand the CMake setup for polsarprosim is progressing very quickly thanks to the experience with Qgis, OTB and lots of advice from Norman and Emmanuel. Here is a what the automated testing says:

Test project C:/Program Files (x86)/PolSARpro_v4.1.5/Soft/build
 Start 1: compareOutput
1/2 Test #1: compareOutput ....................   Passed    0.07 sec
  Start 2: runSim
2/2 Test #2: runSim ...........................   Passed  3919.94 sec
100% tests passed, 0 tests failed out of 2
Total Test time (real) = 3920.05 sec


Now need to try some MPI to speed up the simulation time a bit and put the simulation run and output comparison to a standard in the proper order.

Alternative power from an Alternator - figuring out wiring

I had a minor mishap with my car, a broken tail light - some angry kid smashed a bin onto it. So I went to the wreckers and picked up a tail light. They had lots of alternators on the shelf, so I got one for the power generation gym project ( stationary excercise bikes hooked up to produce electricity, instead of consuming). A pilot has already been done in HongKong along these lines.

The trick with alternators as opposed to permanent magnet brushless motor I used in the past is that the field windings for the alternator need to be excited with a battery before it can produce enough power to be self exciting. This switchover can be done in theory using an Arduino to monitor the voltage levels, or something smarter to send the produced voltage out to the net.

Also exciting  was LAM-MPI based processing once I figured out how to give separate hostnames to machines booting from the same NFS root image. Here is a script that makes use of the /etc/hosts file in the NFS root to assign separate hostnames to slave nodes.

ipaddr=$(/sbin/ifconfig eth0|grep 192.168|sed "s/.*addr://"|sed "s/\sBcast.*//")
host_name=$(cat /etc/hosts|grep $ipaddr|sed "s/[0-9\.]* //")
sudo hostname $host_name

Here is another option for automatic hostnames. Ideally it should be run after the system completes booting or as part of the ssh profile to change the hostname, so that when LAM-MPI starts the lock-files etc do not conflict. More alternate naming the better.

PS: Here is a very useful link for newer alternators