We describe version 0.1 of mts, a generic framework for parallelizing certaintypes of tree search programs using a single common wrapper. This complements aprevious tutorial that focused on using a preliminary version of mts. mtssupports sharing information between processes which is important forapplications such as satisfiability testing and branch-and-bound. Noparallelization is implemented in the legacy single processor code minimizingthe changes needed and simplying debugging. mts is written in C, uses MPI forparallelization and can be used on a network of computers. As examples weparallelize two simple existing reverse search codes, generating topologicalsorts and generating spanning trees of a graph, and two codes forsatisfiability testing. We give experimental results comparing the parallelcodes with other codes for the same problems.
展开▼
