Как выполнить реляционное соединение двух контейнеров данных на графическом процессоре (предпочтительно 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 не всегда будет последовательностью. Во время выполнения возможно удаление элементов из родительских векторов. Вновь добавленные родительские элементы всегда будут добавляться с идентификатором, который отображается из идентификатора последнего элемента. С учетом сказанного, я понимаю, что это означает, что дочерние элементы могут быть осиротевшими, но я не рассматриваю решение для этого здесь.

3

Решение

Это выглядит как простое поэлементное умножение между элементами 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, ...


При условии, что

  1. нет ребенка-сироты;
  2. Parent_IDs неупорядочен и уникален;
  3. 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 необходимо воссоздавать каждый раз при изменении родительского вектора.

1

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector