concurrent data structures
OpenCL executes hundreds or thousands of individual kernel instances, so the processing and data structures must be parallelizable to that degree. This means you must use data structures that permit multiple data elements to be read and written simultaneously and independently. These are known as concurrent data structures.
Many common data structures are non-concurrent. This makes
parallelizing the code difficult. For example, the following data
structures are typically non-concurrent for writing data:
- Linked list.
- Hash table.
This does not mean you cannot use these data structures. For
example, these data structures can all be read in parallel without
Work-items can also write to these data structures, but you must be aware of
the following restrictions:
- Work-items can access any data structure
that is read-only.
- Work-items can write to any data structure if the
work-items write to different elements
Work-items can write to the same element in any
data structure if it is guaranteed that both work-items write the
same value to the element.
Alternatively, work-items can write different values to the
same element in any data structure if it does not matter in the
final output which of the values is correct. This is because either
of the values might be the last to be written.
- Work-items cannot change the links in the data structure
if they might impact other elements.
- Work-items can change the links in the data structure
with atomic instructions if multiple atomic instructions do not
access the same data.
There are parallel versions of many commonly used data structures.