A Problem Shared is a Problem Halved (ignoring overhead)

An Introduction to Parallel Search

Since we know that the work which our sat solver does is contained in a stack we can now take the easy step of parallelising our solver by splitting up the stack and sharing it between two processes.

In this post we will cover this simple procedure and introduce and compare two approaches to parallel programming, namely synchronization (Java) based and message passing (Erlang) based.

The Trivial Act of Sharing Work

The act of splitting the work stack requires a donor process (roughly speaking Erlang has processes where Java has threads) who has work to give and a recipient process who has no work and recieves it from the donor.  Once the work has been shared each process can resume sequential work on their respective workstacks.

Message Passing Parallelism

Previous to this post we haven't mentioned any parallel aspects of our Sat Solver at all. So it seems like a good idea to take this opportunity to introduce Erlang paralellism (usually called message passing parallelism or the Actor model) as it is the core of the implementation of our distributed Sat Solver.  I will be using Java to compare Erlang with a more mainstream approach to parallelism.

In Java, two threads will usually coordinate their behaviour by calling synchronised methods on shared Objects.  For example; Imagine a scenario where threads could to share their workstack with other threads provided there was at least one other thread who had no work to do.  We would probably use a thread pool (like ExecutorService) whose methods would test the current count of working threads and see if there are any available.  These methods must clearly be synchronized to prevent multiple threads attempting to share work simultaneously.

By contrast, in Erlang two processes could not update a shared counter of since all data is immutable.  Instead processes communicate by sending messages to each other.  In this case we could recreate the 'thread pool' we used in the java example by creating a seperate process which accepts messages from workers and launches a new process if this is appropriate.  We should observe that this approach requires the process wishing to share its work to wait for a response from the 'thread pool' process to find out whether or not its work was shared and what work remains after sharing has taken place. 

This Erlang solution is simple to program because it has not tricky synchronisation but it does share with the Java approach one key feature, a single point of communication.  In the Java threads interact by passing through a synchronized block where only one thread may run at a time.  Similarly in Erlang we are passing all of our messages to one process and waiting for a response.  In both cases a large amount of simultaneous work sharing will create performance degrading contention in the java example and fill the mailbox of our 'thread pool' process in Erlang.

It is a very simple modification to the Erlang system to have each process individually track the number of processes currently running and spawn processes directly in order to share work.  This removes the bottleneck but introduces some other oddities which will be discussed in more detail in later posts.