在CUDA中实现用于RDF三元组的大的布尔稀疏矩阵（可能具有1000万条目） [英] implementing in CUDA a large boolean sparse matrix (having possibly 10 million entries) for RDF triples

问题描述

我正在寻找一个合适的矩阵格式来表示一个非常大的布尔稀疏矩阵（只包含0和1）在CUDA。我一直在阅读 CUSPARSE文档，并找到了几种格式，如压缩稀疏行（CSR），压缩稀疏列（CSC）等。由于矩阵非零元素都是1，哪个特定格式应该是完美的选择？矩阵中的操作基本上是基于某些条件将0转换为1的写操作。主要目的是查询特定行中每个1的（row，col）对的矩阵。欢迎对矩阵格式和搜索效率的任何洞察。

I am looking for a suitable matrix format to represent a very large boolean sparse matrix (containing only 0's and 1's) in CUDA. I have been reading the CUSPARSE documentation and found several formats such as Compressed Sparse Row (CSR), Compressed Sparse Column (CSC), etc. Since the matrix non-zero elements are all 1, which particular format should be the perfect choice? The operations in matrix are basically writes that convert 0 to 1 based on some condition. The main aim is to query the matrix for the (row,col) pair for each 1's in a particular row. Any insight into matrix formats and efficiency of search row-wise shall be welcome.

@Robert Crovella：非常感谢您澄清问题。我知道CUDA没有太多的角色，除非我们决定在不同的行同时搜索1（非零值），当然没有在矩阵上写。这可以按照您所描述的搜索第二行（== 1）中的所有1来完成。每个线程然后可以为非零值（在我们的例子中为1）异步地搜索单独的行。只需要提及，并希望看看你是否可以删除值向量，因为它包含所有的。我们将节省空间复杂度（虽然它不会是空间方面的主要因素）。空间需求将是nnz + n + 1，而不是2nnz + n + 1。

@Robert Crovella: Many thanks for clarifying the issue. I understand CUDA does not has much role to play unless and until we decide to search for 1's (non-zero values) on different rows simultaneously, of course no writes on the matrix. This may be done as described by you for the search of all 1's in the second row (==1). Each thread can then search for a separate row asynchronously for non-zero values (in our case 1's). Just need to mention and would like to take your view on whether we can drop the values vector as it contains all ones. We will save on the space complexity a bit(though it will not be a major factor in terms of space). The space requirements will be nnz+n+1 instead of 2nnz+n+1.

推荐答案

问题与CUDA无关。你只需要一个关于稀疏矩阵压缩存储格式的教程。我会建议你google的（这里是一个例子，但我会尝试回答这个问题：

As near as I can tell your question has nothing to do with CUDA. You just need a tutorial on sparse matrix compressed storage formats. I'll suggest you google for that (here's one example, but I will attempt to answer this question:

我渴望知道一个合适的搜索操作，用于在给定行中找到数百万的相关列， 1。

I was keen to know of a suitable search operation for finding the relevant columns among millions across a given row that have the value 1.

或：

(how) to query the matrix for the (row,col) pair for each 1's in a particular row.

如果你有一个矩阵在CSR格式中，您将有一个行指针序列和每个（非零）元素的一组列索引。假设我有以下稀疏矩阵：

If you have a matrix in CSR format, you will have a sequence of row pointers, and a set of column indices for each (non-zero) element. Suppose I have the following "sparse" matrix:

0   1   0
1   0   1 
0   1   0

CSR表示为：

index:           0    1    2    3     
values:          1    1    1    1
column indices:  1    0    2    1
row pointers:    0    1    3    4

如果我有一个CSR表示，并且我想回答第二行的哪些列有非零条目的问题，这是一个简单的问题，从第二行的行指针开始（== 1），继续到下一行指针（3）之前的最后一个元素，并读出相应的列索引。在这种情况下，有两个列索引：0和2.因此，第1行有两个非零元素，第0和2列。

If I have therefore a CSR representation, and I want to answer the question "Which columns for the second row have non-zero entries" it's a simple matter of starting with the row pointer for the second row (== 1), proceeding to the last element before the next row pointer (3), and reading off the respective column indices. In this case there are two column indices: 0 and 2. Therefore, row 1 has two non-zero elements, in columns 0 and 2.

要增加CUDA代码中第2行的每个非零元素，我可以：

Programmatically, if I wanted to increment each non-zero element in row 2 in CUDA code, I could:

int idx = threadIdx.x+blockDim.x*blockIdx.x;
if (idx < rowPtr[2] - rowPtr[1]) 
  values[idx + rowPtr[1]]++;

CUSPARSE 和 CUSP 提供许多有用的稀疏矩阵处理函数。

CUSPARSE and CUSP provide many useful sparse matrix manipulation functions.

这篇关于在CUDA中实现用于RDF三元组的大的布尔稀疏矩阵（可能具有1000万条目）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！