New Effective Multithreaded Matching Algorithms
New Effective Multithreaded Matching Algorithms
复制标题
新的有效多线程匹配算法
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. Halappanavar
中科院分区：
文献类型：
--
作者：
F. Manne;M. Halappanavar
匹配是一个重要的组合问题，在社区检测、稀疏线性代数和网络对齐等领域有着广泛的应用。由于计算最佳匹配可能非常耗时，已经提出了几种快速近似算法，包括顺序和并行算法。给出最佳解的算法的共同之处在于它们本质上倾向于顺序的，而更适合于并行计算的算法给出的解质量较低。我们提出了一个新的简单的1/2近似算法的加权匹配问题。该算法在几乎所有输入上都比任何其他建议的顺序1/2近似算法快，并且在并行化时也比以前的多线程算法更好地扩展。我们进一步扩展到一个一般的可扩展的多线程算法，计算匹配的重量可比的最佳顺序确定性算法。所建议的算法的性能记录通过广泛的实验，不同的多线程架构。
Matching is an important combinatorial problem with a number of applications in areas such as community detection, sparse linear algebra, and network alignment. Since computing optimal matchings can be very time consuming, several fast approximation algorithms, both sequential and parallel, have been suggested. Common to the algorithms giving the best solutions is that they tend to be sequential by nature, while algorithms more suitable for parallel computation give solutions of lower quality. We present a new simple 1/2-approximation algorithm for the weighted matching problem. This algorithm is both faster than any other suggested sequential 1/2-approximation algorithm on almost all inputs and when parallelized also scales better than previous multithreaded algorithms. We further extend this to a general scalable multithreaded algorithm that computes matchings of weight comparable with the best sequential deterministic algorithms. The performance of the suggested algorithms is documented through extensive experiments on different multithreaded architectures.