I'm currently working on a project that utilizes MPI in order to distribute
the calculating of a game tree across multiple MPI nodes. In order to do
this, we require the use of a backtracking algorithm. We've yet to find any
that support the parallelism of MPI and are wondering if there exists any
before we look towards implementing our own.
In essence, our code does the following:
RecursiveCall(GameTreeNode)
Create a set, S, of GameTreeNodes based on GameTreeNode (i.e. expand
the game tree)
For each GameTreeNode, N, in S
Find an idle processor
Execute RecursiveCall(N) on the selected processor
End
If there are no idle processors
Do calculation on current processor
End
End
We've reviewed "DIB - A Distributed Implementation of Backtracking"
by Raphael Finkel & Udi Manber, but that paper uses BSD sockets and we
couldn't easily see a way to reimplement it within MPI. We are wondering if
there exists a similar backtracking method that is already MPI-compatible.
Thanks.
Cheers,
Josh Vega
Computer Science, B.S., 2019
New Jersey Institute of Technology
