Вычисление интегрального изображения на GPU действительно быстрее, чем на CPU?

Question

Я новичок в вычислениях на GPU, так что, возможно, это действительно наивный вопрос.
Я сделал несколько поисков, и кажется, что вычисление интегрального изображения на GPU - неплохая идея.
Однако, когда я действительно копаюсь в этом, я задаюсь вопросом, может быть, это не быстрее, чем процессор, особенно для большого изображения. Так что я просто хочу узнать ваши идеи об этом и некоторые объяснения, если GPU действительно быстрее.

Таким образом, предполагая, что у нас есть изображение MxN, для вычислений интегрального изображения на ЦП потребуется примерно 3xMxN сложения, то есть O(MxN).
На GPU, следуйте коду, предоставленному 6-й редакцией "OpenGL Super Bible", для этого потребуется некоторая операция KxMxNxlog2(N) + KxMxNxlog2(M), в которой K - это число операций для большого количества сдвига битов, умножения, прибавление...
Графический процессор может работать параллельно, скажем, 32 пикселя за один раз, в зависимости от устройства, но он все равно O(MxNxlog2(M)).
Я думаю, что даже при обычном разрешении 640x480 процессор все еще быстрее.

Я здесь не прав?
[Edit] Это код шейдера прямо из книги, идея состоит в том, чтобы использовать 2 прохода: вычислить интеграл по строкам, а затем вычислить интеграл столбца результата из прохода 1. Этот код шейдера предназначен для 1 прохода.

#version 430 core
layout (local_size_x = 1024) in;
shared float shared_data[gl_WorkGroupSize.x * 2];
layout (binding = 0, r32f) readonly uniform image2D input_image;
layout (binding = 1, r32f) writeonly uniform image2D output_image;
void main(void)
{
    uint id = gl_LocalInvocationID.x;
    uint rd_id;
    uint wr_id;
    uint mask;
    ivec2 P = ivec2(id * 2, gl_WorkGroupID.x);
    const uint steps = uint(log2(gl_WorkGroupSize.x)) + 1;
    uint step = 0;
    shared_data[id * 2] = imageLoad(input_image, P).r;
    shared_data[id * 2 + 1] = imageLoad(input_image,
    P + ivec2(1, 0)).r;
    barrier();
    memoryBarrierShared();
    for (step = 0; step < steps; step++)
    {
        mask = (1 << step) - 1;
        rd_id = ((id >> step) << (step + 1)) + mask;
        wr_id = rd_id + 1 + (id & mask);
        shared_data[wr_id] += shared_data[rd_id];
        barrier();
        memoryBarrierShared();
    }
    imageStore(output_image, P.yx, vec4(shared_data[id * 2]));
    imageStore(output_image, P.yx + ivec2(0, 1),
    vec4(shared_data[id * 2 + 1]));
}

Answer 1

Что вы подразумеваете под integral image?

Мое предположение суммирует K изображения одинакового разрешения MxN все вместе. в таком случае это O(K.M.N) на стенде CPU и GPU, но постоянное время может быть лучше на GPU, поскольку доступ к памяти gfx намного быстрее, чем на стороне процессора. Также обычно имеется больше ядер GPU, чем ядер CPU, которые предпочитают GPU для этого.

Если K слишком большой, чтобы поместиться в текстурные блоки GPU U сразу, чем вам нужно использовать несколько проходов, так O(K.M.N.log(K)/log(U)) K>U... где процессор может быть быстрее в некоторых случаях. Но, как и предыдущий комментарий, предложенный без теста, вы можете только догадываться. Вы также должны принять во внимание, что существуют такие вещи, как текстурные массивы и массивы текстур без привязки, которые позволяют делать это за один проход (но я не уверен, есть ли для этого какие-либо затраты на производительность).

[Edit1] после очистки того, что вы действительно хотите сделать

Для начала предположим, что для простоты мы получили квадратное входное изображение. NxN пиксели. Таким образом, мы можем разделить задачу на H-линии и V-линии отдельно (аналогично 2D FFT), чтобы упростить этот процесс. Кроме того, мы можем использовать подразделение каждой строки на группу M пиксели. Так:

N = M.K

куда N это разрешение, M это разрешение региона и K количество регионов.

1. Первый. проходить

   Рендеринг строки для каждой группы, чтобы мы получили K линии размера M, Использование фрагментного шейдера, который вычисляет интегральное изображение каждой области, выводя только какую-то текстуру. Это T(0.5*K*M^2*N) Все это можно сделать фрагментом, представленным одним квадром, покрывающим экран...

2. Второй. проходить

   Преобразование интегралов области в интегралы полного изображения. Так опять рендер K строки и во фрагмент добавьте все последние пиксели каждой предыдущей группы. Это T(0.5*K^3*N) Все это тоже можно сделать фрагментом, представленным одним квадром, покрывающим экран...

3. сделать #1,#2 на результат в направлении другой оси

Все это превращается в

T(2*N*(0.5*K*M^2+0.5*K^3))
T(N*(K*M^2+K^3))
O(N*(K*M^2+K^3))

Теперь вы можете настроить M для максимальной производительности на вашей установке... Если я переписать все это в M,N затем:

T(N*((N/M)*M^2+(N/M)^3))
T(N*(N*M+(N/M)^3))

Таким образом, вы должны минимизировать терм, поэтому я бы попытался использовать значения вокруг

N*M = (N/M)^3
N*M = N^3/M^3
M^4 = N^2
M^2 = N
M = sqrt(N) = N^0.5

Так что все это превращается в:

T(N*(N*M+(N/M)^3))
T(N*(N*N^0.5+(N/N^0.5)^3))
T(N^2.5+N^1.5)
O(N^2.5)

Который быстрее наивного O(N^4) Но вы правы, ЦП выполняет меньше операций O(N^2) для этого и не требуется копирование данных или несколько проходов, поэтому вы должны выяснить пороговое разрешение для конкретного HW для вашей задачи и выбрать в зависимости от измерений. PS Надеюсь, я не сделал глупой ошибки где-то в вычислениях. Кроме того, если вы делаете линии H и V отдельно на CPU, то сложность на стороне CPU будет O(N^3) и используя этот подход даже O(N^2.5) без необходимости 2 прохода на ось.

Взгляните на этот похожий QA:

• Как реализовать 2D лучевой эффект освещения в GLSL

Я думаю, что это хорошая отправная точка.