Оптимизация алгоритма при работе с изображениями в C (свертка изображения)

Question

Мне нужно написать программу, которая будет считывать изображение в массив, выполнять операцию свертки (резкость) и сохранять ее обратно в файл (ppm). Я написал стандартный алгоритм:

    unsigned char* imgBefore = malloc(height*(3*width)*sizeof(unsigned char));
    assert(fread(imgBefore, 3*width, height, inputFile) == height);
    unsigned char* imgAfter = malloc(height*(3*width)*sizeof(unsigned char));

    short ker[3][3] = {{0, -1, 0}, {-1, 5, -1}, {0, -1, 0}};

    unsigned char r, g, b;

    for(int y = 0; y < height; y++) {
        for(int x = 0; x < width; x++) {
            if(y == 0 || y == height-1 || x == 0 || x == width-1) {
                r = imgBefore[3*(width*y + x) + 0];
                g = imgBefore[3*(width*y + x) + 1];
                b = imgBefore[3*(width*y + x) + 2];
                imgAfter[3*(width*y + x) + 0]  = r;
                imgAfter[3*(width*y + x) + 1]  = g;
                imgAfter[3*(width*y + x) + 2]  = b;
                continue;
            }

            int rSum = 0, gSum = 0, bSum = 0, val;

            for(int dy = 0; dy < 3; dy++) { // kernels height
                int yy = 3*width*(y+dy-1);
                for(int dx = 0; dx < 3; dx++) { // kerenels width
                    int xx = 3*(x+dx-1);
                    val = ker[dy][dx];

                    rSum += val * imgBefore[yy + xx + 0];
                    gSum += val * imgBefore[yy + xx + 1];
                    bSum += val * imgBefore[yy + xx + 2];
                }
            }
            rSum = rSum < 0 ? 0 : (rSum > 255 ? 255 : rSum);
            gSum = gSum < 0 ? 0 : (gSum > 255 ? 255 : gSum);
            bSum = bSum < 0 ? 0 : (bSum > 255 ? 255 : bSum);

            imgAfter[3*(width*y + x) + 0] = rSum;
            imgAfter[3*(width*y + x) + 1] = gSum;
            imgAfter[3*(width*y + x) + 2] = bSum;
        }
    }

    fwrite(imgAfter, 3*width, height, outputFile);

Далее мне нужно оптимизировать его эффективность при взаимодействии с кешем. Мне кажется, что проблемная часть находится в этом фрагменте кода:

for(int dy = 0; dy < 3; dy++) { // kernels height
    int yy = 3*width*(y+dy-1);
    for(int dx = 0; dx < 3; dx++) { // kerenels width
        int xx = 3*(x+dx-1);
        val = ker[dy][dx];

        rSum += val * imgBefore[yy + xx + 0];
        gSum += val * imgBefore[yy + xx + 1];
        bSum += val * imgBefore[yy + xx + 2];
    }
}

, потому что он сначала загружает одну строку матрицы, использует только 3 (9) элемента, а затем переходит к следующей строке. Это кажется совершенно неэффективным в отношении кеша.

Что я могу сделать, чтобы это исправить?

Я также пытался повторно использовать отдельные пиксели или целые строки. Все это только ухудшило результат (есть большая вероятность, что я просто плохо реализовал структуры вроде FIFO или добавил и прочитал их в неправильных местах). Если программе это нужно, как она должна выглядеть? Для оценки я использую: valgrind --tool = cachegrind --I1 = 32768,8,64 --D1 = 32768,8,64 --LL = 1048576,16,64 ./a.out

I был бы признателен за любой совет

Answer 1

Способ доступа к данным не подходит для кэширования больших изображений. Это может быть улучшено (например, с использованием листов).

Имейте в виду, что время вычислений этой программы не ограничено иерархией памяти, но медленными последовательными вычислениями на основе скаляров, вызванными неэффективным размещением данных .

Вот результат анализа Valgrind для 10 вызовов функции трафарета с использованием 4608 x 3456 x 3 изображения:

--171871-- warning: L3 cache found, using its data for the LL simulation.
--171871-- warning: specified LL cache: line_size 64  assoc 12  total_size 9,437,184
--171871-- warning: simulated LL cache: line_size 64  assoc 18  total_size 9,437,184
==171871== 
==171871== I   refs:      30,437,416,378
==171871== I1  misses:               944
==171871== LLi misses:               938
==171871== I1  miss rate:           0.00%
==171871== LLi miss rate:           0.00%
==171871== 
==171871== D   refs:       7,526,412,742  (7,000,797,573 rd   + 525,615,169 wr)
==171871== D1  misses:        30,599,898  (   22,387,768 rd   +   8,212,130 wr)
==171871== LLd misses:        15,679,220  (    7,467,138 rd   +   8,212,082 wr)
==171871== D1  miss rate:            0.4% (          0.3%     +         1.6%  )
==171871== LLd miss rate:            0.2% (          0.1%     +         1.6%  )
==171871== 
==171871== LL refs:           30,600,842  (   22,388,712 rd   +   8,212,130 wr)
==171871== LL misses:         15,680,158  (    7,468,076 rd   +   8,212,082 wr)
==171871== LL miss rate:             0.0% (          0.0%     +         1.6%  )

Прежде всего, мы видим, что существует много D1 cache reference (47 на записанный пиксель из-за скалярного доступа).

Число D1 misses и D1 miss rate кажется очень маленьким, поэтому мы можем думать, что доступ к кешу хорош. Но это не тот случай. Результаты Valgrind вводят в заблуждение, потому что D1 cache reference работает с 1-байтовой скалярной гранулярностью, а D1 misses работает с 64-байтовой гранулярностью строки кэша.

Если мы посмотрим на анализ более тщательно, мы увидим, что почти все записанные данные приводят к отсутствию кэша D1. Кроме того, 20% данных, считанных из L1, необходимо (повторно) загрузить из LL C (для 7 ГБ, считанных из кэша D1, 1,43 ГБ загружаются из LL C).

Проблема связана с большими линиями изображения. Действительно, 1 строка изображения занимает 4608 * 3 = 13824 байтов, а 3 строки необходимы для записи одной строки. Таким образом, 41472 байта считываются из кэша D1 для записи 13824 байта. Теоретически, с достаточно большим кешем D1, 27648 следует повторно использовать из кеша D1. Однако кэш D1 слишком мал и не может вместить все данные для чтения / записи (примерно потому, что 41472+13824 > 32768).

Мы можем улучшить ситуацию, используя два метода:

• Tiling: идея состоит в том, чтобы установить x l oop, ограниченный небольшим фиксированным размером (например, 1024), чтобы он вычислял вертикальные блоки изображения, а затем добавить новый охватывающий xBlock l oop (который включает в себя циклы y и x), которые выполняют итерации по вертикальным блокам. Этот подход имеет преимущество, заключающееся в улучшении повторного использования кэша D1, но все же может вызвать некоторые ненужные ошибки кэша на современных процессорах (поскольку загруженные строки больше не являются смежными). Вы можете уменьшить это, выполнив мозаику по измерению y или адаптировав компоновку данных. Вот пример:

const int blockSize = 1024;
for(int xBlock = 0; xBlock < width; xBlock+=blockSize) {
    for(int y = 0; y < height; y++) {
        int xMax = xBlock + blockSize;
        if(xMax > width)
            xMax = width;
        for(int x = xBlock; x < xMax; x++) {
            // Unchanged part of the code
        }
    }
}

• Временные хранилища: запись данных в иерархию кеша приводит к загрязнению кеша, что приводит к дополнительным ошибкам в кеше (так как записанные данные требуют удаления ранее прочитанного кеша) линии). Это также может привести к увеличению нагрузки на некоторые архитектуры (например, как на процессорах Intel). Мы можем сказать процессору записывать данные прямо в память. Некоторые компиляторы предоставляют директивы #pragma для этого (выполнение этого вручную немного сложно в вашем коде). Это хорошо только в том случае, если изображение слишком велико, чтобы поместиться в кэш LL C, или не использовать его позже. См. здесь для получения дополнительной информации.

Вот результат Valgrind после применения метода листов:

==183432== D   refs:       7,527,450,132  (7,001,731,093 rd   + 525,719,039 wr)
==183432== D1  misses:        16,025,288  (    7,640,368 rd   +   8,384,920 wr)
==183432== LLd misses:        16,024,790  (    7,639,918 rd   +   8,384,872 wr)

Мы можем видеть, что теперь в 2 раза меньше пропусков кэша D1 (и в 3 раза меньше чтений).