Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model
Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model
复制标题
DOI：
10.1007/s00224-010-9285-4
复制
发表时间：
2007-06
影响因子：
0.5
通讯作者：
M. A. Bender;G. Brodal;Rolf Fagerberg;R. Jacob;Elias Vicari
中科院分区：
文献类型：
--
作者：
M. A. Bender;G. Brodal;Rolf Fagerberg;R. Jacob;Elias Vicari
分析了I/O模型中稀疏矩阵密集向量乘法（SpMV）问题。SpMV的任务是计算：=Ax，其中A是稀疏NxN矩阵，xy是向量。这里，稀疏性由参数k表示，该参数k表示A总共最多有kN个非零，即，每列的平均knonzero数。参数k的极端选择是研究得很好的特殊情况，即fork=1置换和fork=Ndense矩阵向量乘法。我们研究了这个计算任务的最坏情况复杂度，即，取决于kandNonly的I/O数量的最佳可能上限是多少。我们确定这种复杂性的一个常数因子的大范围内的参数。通过我们的论证，我们发现大多数具有kNnonzeros的矩阵需要这个数量的I/O，即使程序可能依赖于矩阵的结构。计算下界的模型是Aggarwal和Vitter以及Hong和Kung的I/O模型的组合。我们研究了问题的两种变体，取决于A的存储器布局。如果A存储在列主布局中，SpMV的I/O复杂度为Θ（min{kNB（1+logM/BNmax{M，k}），kN}）fork≤N1-ε，且任何常数1> ε > 0。在可选择存储器布局的情况下，SpMV的I/O复杂度为Θ（min{kNB（1+logM/BNkM），kN]）fork≤3 <$N.在高缓存布局M ≥B1+ε的该高速缓存无关设置下，A在列优先布局下的I/O复杂度为O（kNB（1+logM/BNk））.
We analyze the problem of sparse-matrix dense-vector multiplication (SpMV) in the I/O-model. The task of SpMV is to computey:=Ax, whereAis a sparseNxNmatrix andxandyare vectors. Here, sparsity is expressed by the parameterkthat states thatAhas a total of at mostkNnonzeros, i.e., an average number ofknonzeros per column. The extreme choices for parameterkare well studied special cases, namely fork=1 permuting and fork=Ndense matrix-vector multiplication.We study the worst-case complexity of this computational task, i.e., what is the best possible upper bound on the number of I/Os depending onkandNonly. We determine this complexity up to a constant factor for large ranges of the parameters. By our arguments, we find that most matrices withkNnonzeros require this number of I/Os, even if the program may depend on the structure of the matrix. The model of computation for the lower bound is a combination of the I/O-models of Aggarwal and Vitter, and of Hong and Kung.We study two variants of the problem, depending on the memory layout ofA.IfAis stored in column major layout, SpMV has I/O complexity Θ(min{kNB(1+logM/BNmax{M,k}),kN}) fork≤N1-εand any constant 1> ε > 0. If the algorithm can choose the memory layout, the I/O complexity of SpMV is Θ(min{kNB(1+logM/BNkM),kN]) fork≤3√N.In the cache oblivious setting with tall cache assumptionM≥B1+ε, the I/O complexity is Ο(kNB(1+logM/BNk)) forAin column major layout.