Префиксный хеш-массив: понимание замедления OpenCL ⇐ C++

[Anonymous]

Я пытаюсь ускорить создание массива хеш-префиксов с помощью OpenCL 3.0.
Начиная с v = [v[0], v[1], v[2], ... ], я хочу построить:

Код: Выделить всё

pref = [v[0], B * v[0] + v[1], B**2 * v[0] + B * v[1] + v[2], ... ]

.
Мне не известна ни одна библиотечная функция (например, в boost.compute), которая могла бы добиться этого (сканирование префикса требует ассоциативного оператора).
Мой подход (~6 раз медленнее последовательного варианта) состоит из 4 ядер и использует 4 буфера (

Код: Выделить всё

v

(вход), pref (выход) и два блокнота, spad1 и spad2):

• < ли>

  Код: Выделить всё

  copy_spad

  : скопировать буфер устройства в другой буфер.

• Код: Выделить всё

  shr_spad

  : сдвиг вправо буфера устройства в другой буфер.

• Код: Выделить всё

  mul_spad

  : умножить каждый элемент в буфере устройства на число.

• Код: Выделить всё

  add_pref

  : добавьте буфер устройства в другой.

Например, если v будет иметь три элемента, моя реализация будет работать вот так:

Код: Выделить всё

pref : [v1, v2, v3]
spad1: [ ?,  ?,  ?]
spad2: [ ?,  ?,  ?]

Round 1:                                  |   Round 2:
|
copy_spad(pref, spad1):                   |   copy_spad(pref, spad1):
pref : [v1, v2, v3]                       |   pref : [v1,   B*v1 + v2,   B*v2 + v3]
spad1: [v1, v2, v3]                       |   spad1: [v1,   B*v1 + v2,   B*v2 + v3]
spad2: [ ?,  ?,  ?]                       |   spad2: [ 0,        B*v1,        B*v2]
|
shr_spad(2**0, spad1, spad2):             |   shr_spad(2**1, spad1, spad2):
pref : [v1, v2, v3]                       |   pref : [v1,   B*v1 + v2,   B*v2 + v3]
spad1: [v1, v2, v3]                       |   spad1: [v1,   B*v1 + v2,   B*v2 + v3]
spad2: [ 0, v1, v2]                       |   spad2: [ 0,           0,          v1]
|
mul_spad(B**1, spad2):                    |   mul_spad(B**2, spad2):
pref : [v1,   v2,   v3]                   |   pref : [v1,   B*v1 + v2,   B*v2 + v3]
spad1: [v1,   v2,   v3]                   |   spad1: [v1,   B*v1 + v2,   B*v2 + v3]
spad2: [ 0, B*v1, B*v2]                   |   spad2: [ 0,           0,     B**2*v1]
|
add_pref(spad2, pref):                    |   add_pref(spad2, pref):
pref : [v1,   B*v1 + v2,   B*v2 + v3]     |   pref : [v1,   B*v1 + v2,   B**2*v1 + B*v2 + v3]
spad1: [v1,          v2,          v3]     |   spad1: [v1,   B*v1 + v2,             B*v2 + v3]
spad2: [ 0,        B*v1,        B*v2]     |   spad2: [ 0,           0,               B**2*v1]
|

Фактически основная реализация выглядит так:

Код: Выделить всё

for (int i = 0; i < full_n; i += n) {
///we have multiple batches, each of size n.
queue.enqueueWriteBuffer(pref_d, CL_TRUE, 0, sizeof(int) * n, all_nos.data() + i);

B = 27;
for(int step = 1; step < n; step 

Подробнее здесь: [url]https://stackoverflow.com/questions/78611656/prefix-hash-array-understanding-opencl-slowdown[/url]