Dynamic data structures Dynamic data structures (such as Python's list) in OpenCL


Is it possible to define a dynamic data structure in OpenCL? I use PyOpenCL and need to populate a large sparse matrix. One way to do that would be to have three dynamic data structures (Lists) for R, C and V where (R,C) is the position in the matrix and V is the value at that position.


Define ‘dynamic’. The sizes of all buffers must be known at kernel launch so you need to know how much data your are going to write from your kernel, but once the buffer is there you are free to write data into these buffers however you want. Work groups could, for example, create a bunch of (R,C,V) triplets in local memory and then use atomic adds to allocate slots in the global buffers.

You can emulate the memory allocation as in usual memory, but it does not mean that it is a good practice. Most of people use OpenCL because they need performance that is obtained from the mass-parallel hardware. However, lists are not much a parallel data structure and iterating through them could deeply hurt your kernel’s performance.

Are the elements in the sparse matrix really random, or do they concentrate in some patterns (diagonals, columns, clusters…). If nothing of this is true but you have only integral values in the matrix, maybe you could represent each row/column just like a linear combination of several vectors.

Or a simpler solution, if you can populate the matrix row by row, you can have one buffer of (C,V) values and another one of R indices for each row into the first buffer.

All depends on your data, one sparse matrix is not like another sparse matrix.

Quite a bit of research has been done on sparse matrices on GPU, a recent paper that can be used as a starting point is mentioned here (gpgpu.org). Unfortunately, most publications only describe the memory layout of the matrices and possible some operations. Very few describe how to populate a matrix. Does anyone know of such a paper?