Experimental evaluation of efficient sparse matrix distributions
Experimental evaluation of efficient sparse matrix distributions
复制标题
有效稀疏矩阵分布的实验评估
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
J. Saltz
中科院分区：
文献类型：
--
作者：
M. Ujaldón;Shamik D. Sharma;E. Zapata;J. Saltz
稀疏矩阵问题很难在分布式内存机器上高效并行化，因为非零元素是不均匀分布的，并且通过多级间接访问。实现良好负载平衡和局部性的不规则分布难以计算，具有高内存开销，并且还导致在定位分布式数据时进一步间接。本文评估替代半定期分布策略，权衡质量的负载平衡和本地化较低的分解开销和有效的查找。所提出的技术进行比较，一个不规则的稀疏矩阵分区和每个分布方法的相对优点进行了概述。
Sparse matrix problems are difficult to parallelize efficiently on distributed memory machines since non-zero elements are unevenly scattered and are accessed via multiple levels of indirection. Irregular distributions that achieve good load balance and locality are hard to compute, have high memory overheads and also lead to further indirection in locating distributed data. This paper evaluates alternative semi-regular distribution strategies which trade off the quality of loadbalance and locality for lower decomposition overheads and efficient lookup. The proposed techniques are compared to an irregular sparse matrix partitioned and the relative merits of each distribution method are outlined.