Как выполнить реляционное соединение двух контейнеров данных на графическом процессоре (предпочтительно CUDA)?
Что я пытаюсь сделать:
На GPU я пытаюсь имитировать соглашения, используемые SQL в реляционной алгебре для выполнения объединений в таблицах (например, Inner Join, Outer Join, Cross Join). В приведенном ниже коде я хочу выполнить Inner Join. Представьте себе две таблицы (контейнеры), где одна таблица является родительской / основной таблицей, а другая — дочерней. Отношение родителя к потомку равно 1 ко многим (или 1 к нулю, если в Child_ParentIDs нет элемента, который соответствует элементу в Parent_IDs).
Пример входных данных:
Parent_IDs: [1, 2, 3, 4, 5] ... 5 elements
Parent_Values: [0, 21, 73, 0, 91] ... 5 elements
Child_ParentIDs: [1, 1, 1, 2, 3, 5, 5] ... 7 elements
Child_Permanences: [120, 477, 42, 106, 143, 53, 83] ... 7 elements
Child_Values: [0, 0, 0, 0, 0, 0, 0] ... 7 elements
Работа как запрос SQL:
SELECT child.permanence * parent.value FROM child, parent WHERE child.parent_id = parent.id;
Описание операции:
Соедините Child_ParentID с Parent_ID для доступа к соответствующим Parent_Values. Используйте соответствующие Parent_Values для умножения на соответствующие Child_Permanences и поместите результат каждой операции в Child_Values.
Ожидаемый результат (Child_Values - единственный измененный вектор во время операции):
Child_ParentIDs: [1, 1, 1, 2, 3, 5, 5] ... 7 elements
Child_Permanences: [120, 477, 42, 106, 143, 53, 83] ... 7 elements
Child_Values: [0, 0, 0, 2226, 10439, 4823, 7553] ... 7 elements
Объяснение (если это не имеет смысла):
Значение 2226 получено умножением 106 и 21. 10439 было получено умножением 143 и 73. Также обратите внимание, что ВСЕ записи сохраняются в дочерних векторах (все 7 элементов все еще существуют в выходных данных, хотя обновлены отдельные элементы Child_Values). Родительские векторы не сохраняются в выходных данных (обратите внимание на то, что ParentID 4 отсутствует в списке векторов, и для него нет «фиктивного» заполнителя). Это поведение «внутреннего соединения».
Идеи элегантных решений, которые я не получил работать:
-Использование динамического параллелизма CUDA. Возможно, единственное решение во всем Интернете, которое я нашел, которое делает именно то, что я пытаюсь сделать, это здесь-часть 1 а также здесь-часть 2.
-Использование операций хеширования CUDPP;
-Аленка Д.Б.
И, наконец, мой вопрос повторился:
Существует ли какое-либо рабочее решение с точки зрения чисто графического процессора (предпочтительно с CUDA, но OpenCL также будет работать) для выполнения реляционных объединений в двух отдельных контейнерах данных, чтобы можно было осуществлять поиск данных и обновлять элементы параллельно через указанные объединения?
РЕДАКТИРОВАТЬ
Parent_IDs не всегда будет последовательностью. Во время выполнения возможно удаление элементов из родительских векторов. Вновь добавленные родительские элементы всегда будут добавляться с идентификатором, который отображается из идентификатора последнего элемента. С учетом сказанного, я понимаю, что это означает, что дочерние элементы могут быть осиротевшими, но я не рассматриваю решение для этого здесь.
Решение
Это выглядит как простое поэлементное умножение между элементами Child_Permanences и выбранные элементы из Parent_Values, С помощью нескольких ограничений это можно сделать одним thrust::transform,
thrust::transform(
Child_Permanences.begin(),
Child_Permanences.end(),
thrust::make_permutation_iterator(
Parent_Values.begin(),
thrust::make_transform_iterator(Child_ParentIDs.begin(),
_1 - 1)),
Child_Values.begin(),
_1 * _2);
Вы можете заметить, что Parent_IDs не используется Это ограничение вышеуказанного кода. Код предполагает, что Parent_IDs не может быть ничего, кроме 1-базовой последовательности. Вы найдете это thrust::make_transform_iterator не требуется, если Parent_IDs является 0-базовой последовательностью, или Child_ParentIDs это просто индекс родительского значения, как показано в следующем примере.
Child_ParentIDs: [0, 0, 0, 1, 2, 4, 4]
РЕДАКТИРОВАТЬ
Приведенный выше код предполагает, что 1) нет ребенка-сироты; и 2) Parent_IDs является фиксированной последовательностью на основе 1, как 1, 2, 3, ...
При условии, что
- нет ребенка-сироты;
Parent_IDsнеупорядочен и уникален;Child_ParentIDsне распечатан, но не уникален;
и тот факт, что ваш Parent_IDs имеет тип int16, вы можете создать таблицу индекса родительского значения для дочернего элемента, чтобы найти, когда диапазон Parent_IDs достаточно маленький.
Предполагая диапазон Parent_IDs [1, 32767], код решения может быть
thrust::device_vector<int> Parent_index(32768, -1);
thrust::scatter(thrust::make_counting_iterator(0),
thrust::make_counting_iterator(0) + Parent_IDs.size(),
Parent_IDs.begin(),
Parent_index.begin());
thrust::transform(
Child_Permanences.begin(),
Child_Permanences.end(),
thrust::make_permutation_iterator(
Parent_Values.begin(),
thrust::make_permutation_iterator(
Parent_index.begin(),
Child_ParentIDs.begin())),
Child_Values.begin(), _1 * _2);
Обратите внимание, что Parent_index необходимо воссоздавать каждый раз при изменении родительского вектора.
Другие решения
Других решений пока нет …