.png){kind=icon}
返回
Reduce Operations: Send Volume Balancing While Minimizing Latency
.png){kind=icon}
OA
AI
DOI：10.1109/TPDS.2020.2964536.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Communication hypergraph model was proposed in a two-phase setting for encapsulating multiple communication cost metrics (bandwidth and latency), which are proven to be important in parallelizing irregular applications. In the first phase, computational-task-to-processor assignment is performed with the objective of minimizing total volume while maintaining computational load balance. In the second phase, communication-task-to-processor assignment is performed with the objective of minimizing total number of messages while maintaining communication-volume balance. The reduce-communication hypergraph model suffers from failing to correctly encapsulate send-volume balancing. We propose a novel vertex weighting scheme that enables part weights to correctly encode send-volume loads of processors for send-volume balancing. The model also suffers from increasing the total communication volume during partitioning. To decrease this increase, we propose a method that utilizes the recursive bipartitioning framework and refines each bipartition by vertex swaps. For performance evaluation, we consider column-parallel SpMV, which is one of the most widely known applications in which the reduce-task assignment problem arises. Extensive experiments on 313 matrices show that, compared to the existing model, the proposed models achieve considerable improvements in all communication cost metrics. These improvements lead to an average decrease of 30 percent in parallel SpMV time on 512 processors for 70 matrices with high irregularity.
Keyword:
Communication hypergraph
communication cost
maximum communication volume
communication volume
latency
recursive bipartitioning
hypergraph partitioning
sparse matrix
sparse matrix-vector multiplication
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
5.2K
被引数:
1.1W
机构
引用论文
Plant science in forest canopies – the first 30 years of advances and challenges, (1980–2010).png)
IF0
PREAI
分享收藏A two-dimensional data distribution method for parallel sparse matrix-vector multiplicationSIAM REVIEWOAAI
SIAM REVIEWIF6.1
OAAI分享收藏分享收藏ON TWO-DIMENSIONAL SPARSE MATRIX PARTITIONING: MODELS, METHODS, AND A RECIPE关于二维稀疏矩阵分区: 模型，方法和配方
OAAI
OAAI分享收藏
查看更多内容