159.735 - Assignment 3

To be submitted by 25th May 2009

The aim of this assignment is to implement a parallel version of an algorithm for survey propagation.

Survey propagation is variation of belief propagation that uses messages sent between nodes in a graph to find solutions to very large NP complete problems. This assignment uses it to show satisfiability of logic expressions with large numbers of variables. All logic expressions can be written in 3 CNF form, that is a set of clauses ANDed together where each clause contains the ORed values of up to 3 variables and their negations.


This can be represented by the following graph:

Where A,B,C and D are the boolean variables and x,y and z are the 3 clauses in this expression. To show that this expression is satisfiable it is necessary to find a set of values for the variables that makes it true (for this example A=1,B=1,C=1).

The survey propagation algorithm assigns an initial random value to each edge in the graph and then passes messages between nodes to try to converge to a solution for the values of the variables. See http://arxiv.org/abs/cs/0212002 and http://www.americanscientist.org/issues/pub/on-the-threshold/ for details.

A simple sequential algorithm for survey propagation can be found on the web site and in /opt/examples on the iimscluster machine. This example uses 100000 variables and creates 410000 random clauses each with 3 variables. It should converge in 45 iterations.

Your task is to rewrite the sequential algorithm using MPI so that it can run on the immscluster machine. It does not matter if your program is not exactly the same as the sequential solution as long as it converges on a correct result. Try different values for the number of variables to see how your code scales.

Marks will be awarded for correct programs that perform as little communication as possible and run as fast as possible on many processors. The iimscluster machine has 8 processors but your code should also be able to run on larger machines.

This is an individual assignment, marks will be deducted for plagiarism and late submissions.

Programs that do not compile and run without modification will lose marks.

You should submit your program source code electronically from the paper web site.

M Johnson 2009