c++ - 在cuda中使用邻接表分配图形？

Question

我想使用邻接表分配一个图，即“V”指针数组，每个指针指向一个数组，该数组将具有相邻的顶点(这将是不相等的)所以

unsigned **d_ptr; 
cudaMalloc(&d_ptr, sizeof(unsigned *)*Count);
  for(int i=0;i<Count;i++)
  {   
     cudaMalloc(&temp, sizeof(unsigned)*outdegree(i));  
  }

我可以将临时指针复制到 d_ptr[i]，但是有更好的方法吗？

Answer 1

如果您想坚持自己的愿望，这似乎是每个顶点一个 CUDA 内存分配，您的方法是正确的，但效率低下且耗时。

这是低效的，因为每个 CUDA 分配都有对齐要求。 This post (加上 CUDA 文档本身)告诉任何 CUDA malloc 将消耗至少 256 字节的全局内存。因此，无论您的顶点的outdegree 有多小；使用您的方法保存指针将消耗每个顶点 256 个字节。随着图形大小的增加，这将导致内存很快耗尽。例如，假设在您的图中，每个顶点的 outdegree 都等于 4。虽然每个顶点的大小 required 都是 4*8=32(假设是 64 位寻址)，但每个顶点将消耗 256 字节，比需要的多 8 倍。请注意，对齐要求可能更高。因此，您建议的方法未充分利用可用的全局内存。

您的方法也很耗时。主机或设备代码中的内存分配和释放是耗时的操作。您正在为每个顶点分配一个内存区域。您还必须为每个顶点将 temp 复制到设备一次。因此，预计与一次分配内存区域相比，它会花费更多的时间。

如果你想用指向设备上顶点的指针填充你的d_ptr，而不是为每个顶点分配一个缓冲区，你可以计算outdegree的总数对于主机端的所有顶点，并使用它分配一个设备缓冲区。

// Allocate one device buffer for all vertices.
unsigned nOutEdges = 0;
for( int i=0; i < Count; i++ )
    nOutEdges += outdegree(i); // outdegree[ i ]??
unsigned* d_out_nbrs;
cudaMalloc( (void**)&d_out_nbrs, sizeof(unsigned) * nOutEdges );

// Collect pointers to the device buffer inside a host buffer.
unsigned** host_array = (unsigned**) malloc( sizeof(unsigned*) * Count );
host_array[ 0 ] = d_out_nbrs;
for( int i=1; i < Count; i++ )
    host_array[ i ] = host_array[ i - 1 ] + outdegree[ i - 1 ];

// Allocate a device buffer and copy collected host buffer into the device buffer.
unsigned **d_ptr; 
cudaMalloc( &d_ptr, sizeof(unsigned *) * Count );
cudaMemcpy( d_ptr, host_array , sizeof(unsigned*) * Count, cudaMemcpyHostToDevice );