We design new serial and parallel approximation algorithms for computing a maximum weight $b$-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 submodular $b$-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.


翻译:我们设计了新的序列算法和平行近似算法,用于在边缘加权图中计算最大重量($b$-匹配)和子模量目标函数。这是个问题;新算法是硬的;新算法是近似比率1/3美元,是贪婪算法的放松,仅依靠图中的地方信息,使其可以平行。我们设计并实施了用于系列计算机和平行计算机的本地Lazy贪婪算法。我们应用了近似亚模值($b$-匹配算法)来分配处理器在平行计算机量子化学中计算Fock矩阵时的任务。任务的目的是通过平衡处理器的计算负荷和将每个处理器发送的信息数捆绑来缩短运行时间。我们显示,对处理器的新任务指派为处理器提供了目前用于NWChemeEx软件的8000美元高级处理器在Oak Ridge National Lab的顶峰超级计算机上使用的四倍速度。

0
下载
关闭预览

相关内容

机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
斯坦福2020硬课《分布式算法与优化》
专知会员服务
118+阅读 · 2020年5月6日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
人工智能 | UAI 2019等国际会议信息4条
Call4Papers
6+阅读 · 2019年1月14日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
深度文本匹配开源工具(MatchZoo)
中国科学院网络数据重点实验室
7+阅读 · 2017年12月5日
【推荐】SLAM相关资源大列表
机器学习研究会
10+阅读 · 2017年8月18日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年9月13日
Arxiv
0+阅读 · 2021年9月13日
Arxiv
0+阅读 · 2021年9月10日
Arxiv
0+阅读 · 2021年9月9日
VIP会员
相关资讯
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
人工智能 | UAI 2019等国际会议信息4条
Call4Papers
6+阅读 · 2019年1月14日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
深度文本匹配开源工具(MatchZoo)
中国科学院网络数据重点实验室
7+阅读 · 2017年12月5日
【推荐】SLAM相关资源大列表
机器学习研究会
10+阅读 · 2017年8月18日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员