Классическая структура данных (набор, карта, двоичное дерево ...) для OpenCL

Question

Я открываю для себя OpenCL через PyOpenCL, но мне удобно заниматься программированием на низкоуровневом языке (C, Rust).

В моем ядре я хочу сравнить результат с существующими данными в set (ha sh set или tree set) перед его дальнейшей обработкой, вместо того, чтобы просматривать весь массив. Я бы хотел избежать этого в коде хоста, чтобы избежать слишком большого количества циклов обмена между хостом и устройством.

Я не хочу изменять содержимое набора, поэтому нет риска одновременного доступа со стороны рабочие элементы.

Мне не удается найти какую-то библиотеку "STL" для OpenCL или какую-то реализацию с открытым исходным кодом для структуры данных Set и Ha sh.

Я что-то пропускаю, это есть что-то подобное? Должен ли я сам реализовать структуру данных Set?

Или использование Ha sh или структуры данных Set в ядре OpenCL означает, что я делаю то, что несовместимо с целями OpenCL?

Answer 1

Ядра OpenCL обычно пишутся на C, а не на C ++; или, скорее, ядра C ++ являются необязательными, и я не знаю ни одной реализации, поддерживающей его.

Так что нет ничего сопоставимого с шаблонами C ++ для создания общих c структур данных, не говоря уже о чем-то вроде STL реализация. Кроме того, древовидные структуры данных в C ++ обычно не реализуются в непрерывной памяти, но используют много небольших выделений памяти, что не очень хорошо отображается в OpenCL, который ожидает, что данные будут в больших, «плоских» буферах. Он также не будет хорошо соответствовать шаблонам доступа к памяти, которые хорошо поддерживаются графическими процессорами.

Тем не менее, ничто не мешает вам создать ядро ​​OpenCL, которое выполняет поиск в таблице ha sh, или реализовать бинарный поиск для поиска в отсортированном массиве.

Операция поиска в обоих случаях очень проста, и, поскольку C не поддерживает общие c функции, это, вероятно, основная причина, по которой нет некоторых big go -to library.

Другая причина заключается в том, что ее эффективность будет во многом зависеть от характера ваших данных и оборудования, на которое вы нацеливаетесь, поэтому вам почти наверняка придется приложить немало усилий - настройка, чтобы сделать это быстро. Опять же, библиотека, вероятно, будет больше мешать, чем полезна.