Classical data structure (set, map, binary tree ...) for OpenCL

user_757293 0
Viewed 204

I am discovering OpenCL through PyOpenCL, but I am confortable in doing some low level language programming (C, Rust).

In my kernel, I want to compare a result with existing data in a set (hash set or tree set) before processing it further, instead of having to browse a whole array. I would like to avoid doing that in the host code to avoid too many round trips between the host and the device.

I do not want to change the content of the set, so no risk of concurrent access by the work items.

I have trouble finding some kind of "STL" library for OpenCL, or some open source implementation for Set and Hash data structure.

Do I miss something, is there something like that? Am I supposed to implement a Set data structure myself?

Or is using Hash or Set data structure in an OpenCL kernel the sign I am doing things that are not compatible with OpenCL goals?

opencl data-structures
1 Answers

OpenCL kernels are generally written in C, not C++; or rather, C++ kernels are optional, and I'm not aware of any implementations that support it.

So there is nothing comparable to C++ templates for building generic data structures, let alone something like an STL implementation. Additionally, tree-based data structures in C++ are typically not implemented on contiguous memory, but use lots of small memory allocations, which isn't something that maps very well to OpenCL, which expects data to be in large, "flat" buffers. It also wouldn't map well to memory access patterns which are well supported by GPUs.

That said, there is nothing stopping you from building an OpenCL kernel which performs lookup in a hash table, or implementing binary search for lookup in a sorted array.

The lookup operation in both cases is very straightforward, and with C not supporting generic functions, this is probably the main reason why there isn't some big go-to library.

Another reason is that making it efficient will very much depend on the nature of your data and the hardware you are targeting, so you would almost certainly need to do lots of hand-tweaking to make it fast. Again, a library would probably get in the way more than it is helpful.

user_486600
Related