Hokkaido University Collection of Scholarly and Academic Papers >
Graduate School of Information Science and Technology / Faculty of Information Science and Technology >
Peer-reviewed Journal Articles, etc >
mts: a light framework for parallelizing tree search codes
Title: | mts: a light framework for parallelizing tree search codes |
Authors: | Avis, David Browse this author →KAKEN DB | Jordan, Charles Browse this author |
Keywords: | Reverse search | parallel processing | topological sorts | spanning trees | triangulations | satisfiability testing |
Issue Date: | 9-Mar-2021 |
Publisher: | Taylor & Francis |
Journal Title: | Optimization methods and software |
Volume: | 36 |
Issue: | 2-3 |
Start Page: | 279 |
End Page: | 300 |
Publisher DOI: | 10.1080/10556788.2019.1692344 |
Abstract: | We describe mts, a generic framework for parallelizing certain types of tree search programmes including reverse search, backtracking, branch and bound and satisfiability testing. It abstracts and generalizes the ideas used in parallelizing lrs, a reverse search code for vertex enumeration. mts supports sharing information between processes which is important for applications such as satisfiability testing and branch-and-bound. No parallelization is implemented in the legacy single processor programmes minimizing the changes needed and simplifying debugging. mts is written in C, uses MPI for parallelization and can be used on a network of computers. We give four examples of reverse search codes parallelized by using mts: topological sorts, spanning trees, triangulations and Galton-Watson trees. We also give a parallelization of two codes for satisfiability testing. We give experimental results comparing the parallel codes with other codes for the same problems. |
Rights: | This is an Accepted Manuscript of an article published by Taylor & Francis in Optimization methods and software on 22 Nov 2019, available online: http://www.tandfonline.com/10.1080/10556788.2019.1692344. |
Type: | article (author version) |
URI: | http://hdl.handle.net/2115/79776 |
Appears in Collections: | 情報科学院・情報科学研究院 (Graduate School of Information Science and Technology / Faculty of Information Science and Technology) > 雑誌発表論文等 (Peer-reviewed Journal Articles, etc)
|
Submitter: Charles Jordan
|