tensorflow - Tensorflow 使用 CSR 以外的 COO 格式来处理稀疏矩阵是否有任何明显的原因？

Question

我正在尝试利用 Tensorflow 的内置稀疏矩阵乘法 API 的性能优势。
和 keveman推荐 tf.embedding_lookup_sparse 是正确的方法。

但是，似乎的表现embedding_lookup_sparse 对my experiments有些失望.尽管它执行了相当小的矩阵乘法，<1, 3196> 和 <3196, 1024>，但具有 0.1 稀疏度的稀疏 matmul 未能赢得密集矩阵乘法。

如果我的实现是正确的，我认为原因之一是 Tensorflow 使用 COO 格式保存所有索引非零对。我不是这个领域的专家，但是，CSR 格式在这种计算上的性能更高，难道不是众所周知的吗？ Tensorflow 在内部使用 COO 格式而不是 CSR 进行稀疏矩阵表示有什么明显的原因吗？

Answer 1

只是为了记录，你说矩阵乘法，但你的矩阵之一实际上是一个向量(1 x 3196)。所以这将使它成为矩阵向量乘法(不同的 BLAS 内核)。我假设你的意思是我的答案是矩阵向量乘法。

是的，对于矩阵向量乘法，CSR 理论上应该比 COO 更快；这是因为CSR格式的存储大小是O(2nnz + n)对比 O(3nnzs)并且稀疏矩阵向量乘法在许多情况下是内存限制的。

尽管基于问题大小、稀疏模式、数据类型和实现，与密集矩阵乘法相比，确切的性能差异会有所不同。很难说哪个应该更快，因为稀疏存储格式引入了间接性，这可能会导致局部性降低和算术单元的利用率低下(例如，不使用向量化)。

特别是当矩阵和向量的大小太小以至于几乎所有东西都适合缓存时，我预计性能优势有限。稀疏矩阵结构通常对真正的大矩阵更有用，范围从 10sK x 10sK 到 1B x 1B，使用密集表示甚至不适合主内存。对于小问题，根据我的经验，与密集格式相比，存储优势通常会被局部性和算术效率的损失所抵消。在某种程度上，这是通过混合存储格式(例如 Block CSR)来解决的，它试图两全其美，并且对某些应用程序非常有用(看起来不像 tensorflow 支持这一点)。

在 tensorflow ，我假设使用 COO 格式是因为它对其他操作更有效，例如它支持 O(1)数据结构中的更新、插入和删除。在稀疏矩阵向量乘法中牺牲 ~50% 的性能来提高这些操作的性能似乎是合理的。