Linked List in OpenCL

0
votes

I have 1000 float datas in an array. I want to separate into different classes, lets say 4 classes. Their sizes are unpredictable. I could easily hold them in a linked list in a CPU implementation, but in OpenCL kernel, is there an opportunity like that? In my mind there are 3 solution to this problem. First, arrays with length 1000 constructed in number of classes, which is memory costly. Second, I allocate an array with length 1000 and separate them into parts. However, I may transport the values from and index into different index, becuase I don't know the size of each classes and they may exceed the size which I provided for each.

Third, and better in my opinion, I get two different array with same length. One of them stores data, the other one stores pointers. For example, in i-th index of data array, the value is stored which belongs to 2nd class. Additionally in i-th index of pointer to the next data which belongs to 2nd class. But this is good for just atomic type (like int, float, char etc) linked lists.

I am new in OpenCL. I haven't known lots of features of it yet. If there is a better way, please don't share with me and others.

1
linked-listopencl
I know it may be too late to answer this question, but it still seems interesting to work with linked list in OpenCL, so I put here the link of a website about it. streamcomputing.eu/blog/2015-02-10/… and I quote "Shared Virtual Memory: host and device kernels can directly share complex, pointer-containing data structures such as trees and linked lists, providing significant programming flexibility and eliminating costly data transfers between host and devices." - Feng Shi

1 Answers

3
votes

Using pointers on GPU is usually very bad idea. Major amount of data resides in global memory, and to fetch it quickly the access should be coalesced. Using pointers breaks the access pattern totally, making it essentially random. It's not very good on CPUs too since it cause a lot of cache misses, but CPUs have larger caches and "smarter" internal logic, so it's usually not so important, but sometimes cache-aware memory access pattern can increase CPU application's speed by nearly order of magnitude. On GPUs coalesced global memory access is one of most important optimizations, and pointers can't provide it.

If you are not extremely short on memory, I'd suggest to use first way and preallocate arrays large enough to hold all data. If you are really short on memory, you could use textures to store your data and pointer arrays, but it depends on the algorithm whether it would provide any benefits or not.