Улучшить производительность функции C с локальностью кэша?

Question

Я должен найти диагональную разницу в матрице, представленной в виде 2d-массива, и прототип функции:

int diagonal_diff(int x[512][512])

Я должен использовать 2d-массив, а данные - 512x512.Это проверено на машине SPARC: мое текущее время составляет 6 мс, но мне нужно быть меньше 2 мс.

Пример данных:

[3][4][5][9]
[2][8][9][4]
[6][9][7][3]
[5][8][8][2]

Разница:

|4-2| + |5-6| + |9-5| + |9-9| + |4-8| + |3-8| = 2 + 1 + 4 + 0 + 4 + 5 = 16

Для этого я использую следующий алгоритм:

int i,j,result=0;
for(i=0; i<4; i++)
    for(j=0; j<4; j++)
        result+=abs(array[i][j]-[j][i]);

return result;

Но этот алгоритм продолжает получать доступ к столбцу, строке, столбцу, строке и т. Д., Которые неэффективно используют кэш.

Есть ли способ улучшить мою функцию?

Answer 1

РЕДАКТИРОВАТЬ: Почему блок-ориентированный подход быстрее?Мы используем преимущества кэша данных процессора, гарантируя, что независимо от того, выполняем ли мы итерацию по блоку за строкой или по столбцу, мы гарантируем, что весь блок помещается в кэш.

Например, если у вас есть строка кэша32 байта и int - 4 байта, вы можете разместить матрицу 8x8 int в 8 строках кэша.Предполагая, что у вас достаточно большой кеш данных, вы можете выполнять итерацию по этой матрице либо по строке, либо по столбцу и быть уверенным, что кэш не будет перегружен.Еще один способ думать об этом - если ваша матрица помещается в кэш, вы можете перемещаться по ней любым нужным вам способом.

Если у вас матрица намного больше, например, 512x512, то вам нужно настроить матрицуобход такой, что вы не трогаете кеш.Например, если вы пересекаете матрицу в обратном порядке расположения матрицы, вы почти всегда будете пропускать кэш на каждом элементе, который вы посещаете.

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

Итак, если вы пытаетесь оптимизировать размер строки кэша компьютера, на котором вы работаетеВы можете перебирать матрицу в блочной форме и проверять каждый элемент матрицы только один раз:

int sum_diagonal_difference(int array[512][512], int block_size)
{
    int i,j, block_i, block_j,result=0;

     // sum diagonal blocks
    for (block_i= 0; block_i<512; block_i+= block_size)
        for (block_j= block_i + block_size; block_j<512; block_j+= block_size)
            for(i=0; i<block_size; i++)
                for(j=0; j<block_size; j++)
                    result+=abs(array[block_i + i][block_j + j]-array[block_j + j][block_i + i]);

    result+= result;

     // sum diagonal
    for (int block_offset= 0; block_offset<512; block_offset+= block_size)
    {
        for (i= 0; i<block_size; ++i)
        {
            for (j= i+1; j<block_size; ++j)
            {
                int value= abs(array[block_offset + i][block_offset + j]-array[block_offset + j][block_offset + i]);
                result+= value + value;
            }
        }
    }

    return result;
}

Вам следует поэкспериментировать с различными значениями для block_size.На моей машине 8 приводит к наибольшему ускорению (в 2,5 раза) по сравнению с block_size, равным 1 (и ~ 5x по сравнению с исходной итерацией по всей матрице).block_size в идеале должно быть cache_line_size_in_bytes/sizeof(int).

Answer 2

Если у вас есть хорошая библиотека векторов / матриц, такая как intel MKL, попробуйте векторизованный способ.

очень просто в Matlab: результат = сумма (сумма (абс (х-х ')));

Я воспроизвел метод Ганса и метод MSN в matlab, и результаты:

Elapsed time is 0.211480 seconds.  (Hans)

Elapsed time is 0.009172 seconds.  (MSN)

Elapsed time is 0.002193 seconds.  (Mine)

Answer 3

С одним незначительным изменением ваши циклы могут работать только с нужными индексами.Я только что изменил инициализацию цикла j.

int i, j, result = 0;
for (i = 0; i < 4; ++i) {
    for (j = i + 1; j < 4; ++j) {
        result += abs(array[i][j] - array[j][i]);
    }
}