OpenCL: implement tile-based element-wise mult of two sorted key-value arrays (Set intersection)

[EgorOrachyov]

Signature

void cl_intersect(cl::Queue, 
cl::Buffer a_keys, cl::Buffer a_values, uint a_size, 
cl::Buffer b_keys, cl::Buffer b_values. uint b_size,
cl::Buffer& r_keys, cl::Buffer& r_values, uint &r_size,
...)

Intpu: two sorted key-value arrays

A

uint a_size
uint a_keys[a_size] -- sorted, all keys unique, no duplicates
T a_values[a_size]

B

uint b_size
uint b_keys[b_size] -- sorted, all keys unique, no duplicates
T b_values[b_size]

Function

lambda func f: T x T -> T

Result: logical intersection of keys a and keys b

r_size <= min(a_size, b_size)

uint r_keys[r_size]
T r_values[r_size]

Example

a_keys [0, 1, 4, 7]
a_values [10, 10, 5, 30]

b_keys [2, 4, 5, 7, 8]
b_values [20, 2, 2, 2, 30]

f = (x, y) -> x + y

r_keys = [4, 7]
r_values = [7, 32]

Resources and links

• Boost compute implementation set intersection (but without values)