A Parallel Approximation Algorithm for Maximizing Submodular b-Matching
A Parallel Approximation Algorithm for Maximizing Submodular b-Matching
复制标题
最大化子模b匹配的并行逼近算法
DOI：
10.1137/1.9781611976830.5
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Halappanavar, M.
中科院分区：
文献类型：
--
作者：
Ferdous, S;Pothen, A;Khan, A.;Panyala, A.;Halappanavar, M.
我们设计了新的串行和并行近似算法，用于计算具有子模目标函数的边加权图的最大权匹配。该问题是NP难的;新算法的近似比为1/3，是Greedy算法的放松，只依赖于图中的局部信息，使它们具有并行性。我们已经设计并实现了本地懒惰贪婪算法的串行和并行计算机。在量子化学中的Fock矩阵的并行计算中，我们应用了近似次模匹配算法来分配任务给处理器。分配试图通过平衡处理器上的计算负载和限制每个处理器发送的消息数量来减少运行时间。我们发现，新的任务分配给处理器提供了四倍的加速比目前使用的分配在NWChemEx软件上的8000个处理器的首脑会议超级计算机在橡树岭国家实验室。
We design new serial and parallel approximation algorithms for computing a maximum weightb-matching in an edge-weighted graph with a submodular objective function. This problem is NP-hard; the new algorithms have approximation ratio 1/3, and are relaxations of the Greedy algorithm that rely only on local information in the graph, making them parallelizable. We have designed and implemented Local Lazy Greedy algorithms for both serial and parallel computers. We have applied the approximate submodularb-matching algorithm to assign tasks to processors in the computation of Fock matrices in quantum chemistry on parallel computers. The assignment seeks to reduce the run time by balancing the computational load on the processors and bounding the number of messages that each processor sends. We show that the new assignment of tasks to processors provides a four fold speedup over the currently used assignment in the NWChemEx software on 8000 processors on the Summit supercomputer at Oak Ridge National Lab.
登录
查看更多内容
DOI：
10.1201/9781351236423-42
发表时间：
2018-05
期刊：
--
影响因子：
--
作者：
Niv Buchbinder;Moran Feldman
通讯作者：
Niv Buchbinder;Moran Feldman
DOI：
10.1609/aaai.v33i01.33011877
发表时间：
2018-11
期刊：
--
影响因子：
--
作者：
John P. Dickerson;Karthik Abinav Sankararaman;A. Srinivasan;Pan Xu
通讯作者：
John P. Dickerson;Karthik Abinav Sankararaman;A. Srinivasan;Pan Xu
DOI：
10.24963/ijcai.2020/1
发表时间：
2019-09
期刊：
--
影响因子：
--
作者：
Saba Ahmadi-;Faez Ahmed;John P. Dickerson;M. Fuge;S. Khuller
通讯作者：
Saba Ahmadi-;Faez Ahmed;John P. Dickerson;M. Fuge;S. Khuller
直接 SCF 程序中二电子积分评估的新变化
DOI：
--
发表时间：
1991
期刊：
影响因子：
--
作者：
T. Hamilton;H. Schaefer
通讯作者：
H. Schaefer
新的有效多线程匹配算法
DOI：
--
发表时间：
2014
期刊：
IEEE International Parallel and Distributed Processing Symposium
影响因子：
--
作者：
F. Manne;M. Halappanavar
通讯作者：
M. Halappanavar