kReese.net

Pipelining the A* Heuristic Search Algorithm

Here’s another paper that I worked on this last semester at UofL for my Parallel Programming class.  I took the A* Heuristic Search Algorithm and attempted to pipeline the algorithm using OpenMPI in C++.  The results of the experiments and comparisons were conducted on the Cardinal Research Cluster.

The paper discusses the implementation in a fairly straightforward manner.  The implementation is ultimately not very cost effective, but the implementation taught me a lot about Parallel techniques for Pipelining.  It does not include any sort of decomposition of the data.  Since the Algorithm uses a priority queue, we can simply pop items off the front of the queue and pass this information to slave processes which will do most of the heavy lifting.

One thing to especially take away from this paper is a method for polling on processes.  The sample below is an example of how you would poll on processes, written in C++:

if(process_id == 0)
{
	bool keep_alive = true;
 
	while (keep_alive)
	{
		if (MPI::COMM_WORLD.Iprobe(source_id, message_tag))
		{
			// Main Code Here
		}
	}
}

The main loop here keeps the process alive during the life of the program. This is necessary since MPI will kill the process once it reaches the end of the code. The next logic statement uses the MPI_Iprobe function which is a nonblocking test for a message. It takes two parameters, the source id from the message and the numeric tag of the message that we are looking for in the test.

One issue that this leads to is the processes staying alive forever, since we are essentially looping infinitely over the process. We can use this MPI_Iprobe function to kill the process when we send a message from the master node that will tell the program that it has reached an end. We do this with the MPI_Send function, simply sending a message, testing for it, and ending the loop when the process receives the message.

Below are the paper and the powerpoint for the project. Source code will be given in a later post.