GPGPU: an effective way to handle 'irregular' transform?

On regular transform, every GPU-threads are expected to have same time complexity O. For example:

for i=0 to 10: c[i] = a[i]*b[i]

On irregular transform, it isn't:

for i=0 to len(arr)
    for k=0 to random()%100
        arr[i] += 1

which results an array like [2,50,32,77,1,5,66, ...] where each element indicates, roughly, a computational cost.

GPGPU programming is well suited to regular transforms like 'element-wise addition', 'matrix-multiplication', 'convolution', ... But how about irregular transforms? How to 'well' distribute GPU-threads? How to design a 'good' kernel? Is there a common methodology?

GPGPU: an effective way to handle 'irregular' transform?

1 Answers