Distributed Sum on a 2D mesh using MPI

-

For a recent class project, we had to implement an algorithm to sum an array of integers on a computer cluster. This problem is one of the easiest applications of the map-reduce approach: Since a sum is an associative operation, we can simply assign a portion of the array to each of our processing resources, and incrementally collect and merge all the partial sums until we get the final result. The Message Passing Interface (MPI) actually has primitives that support map-reduce algorithms directly.

To make the project a little more challenging, we had to implement our distributed algorithm considering this additional requirements:

  • We could only use MPI_Send and MPI_Recv primitives: in other words, all communication needed to be explicit, point-to-point messaging.
  • We had to assume our computational resources were organized as a 2D mesh: each computation element would have an index (i, j) and could only communicate with elements on its same row or column.
  • We wanted to minimize  the total distance traveled by messages (assuming each hop would have a cost): for instance, sending all partial sums in a row to the first element in the row is less efficient that summing neighbor nodes together iteratively (recursive halving)
We had to run the algorithm on a 16-node system and collect a few performance measures. An interesting (and expected) result is that depending on how many numbers we have to sum, distribution may or may not be convenient, due to message passing costs.

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

Parallel Beam Tracing and Visualization of 200 Million Sonar Points

-
Image
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
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