Почему транспонирование матрицы 512x512 намного медленнее, чем перенос матрицы 513x513?

Ответ 1

Объяснение исходит от Agner Fog в Оптимизация программного обеспечения на С++ и сводится к тому, как данные доступны и хранятся в кеше.

Для терминов и подробной информации см. запись wiki в кешировании, я собираюсь сузить ее здесь.

Кэш организован в наборах и строках. В то время используется только один набор, из которого может использоваться любая содержащаяся строка. Память линии может зеркально отражать количество строк, которые дают нам размер кеша.

Для определенного адреса памяти мы можем вычислить, какой набор он должен быть отражен с помощью формулы:

set = ( address / lineSize ) % numberOfsets

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

Ясно, что могут возникать перекрытия. В случае промаха в кеше память считывается в кеш, и старое значение заменяется. Помните, что в каждом наборе есть несколько строк, из которых наименее недавно использованная одна перезаписывается вновь прочитанной памятью.

Я попытаюсь несколько следовать примеру от Agner:

Предположим, что у каждого набора есть 4 строки, каждая из которых содержит 64 байта. Сначала мы попытаемся прочитать адрес 0x2710, который находится в наборе 28. Затем мы также пытаемся читать адреса 0x2F00, 0x3700, 0x3F00 и 0x4700. Все они принадлежат одному и тому же множеству. Перед чтением 0x4700 все строки в наборе были бы заняты. Чтение этой памяти вытесняет существующую строку в наборе, линию, которая изначально удерживала 0x2710. Проблема заключается в том, что мы читаем адреса, которые (для этого примера) 0x800 отделены друг от друга. Это критический шаг (опять же, для этого примера).

Критический шаг также можно вычислить:

criticaStride = numberOfSets * lineSize

Переменные с интервалом criticalStride или несколько раздельных сторонников для одинаковых строк кеша.

Это часть теории. Затем объяснение (также Агнер, я внимательно слежу за ним, чтобы избежать ошибок):

Предположим, что матрица 64x64 (помните, что эффекты различаются в зависимости от кеша) с кешем 8 КБ, 4 строки на каждый набор * размер строки 64 байта. Каждая строка может содержать 8 элементов в матрице (64-бит int).

Критическим шагом будет 2048 байт, которые соответствуют 4 строкам матрицы (которая непрерывна в памяти).

Предположим, что мы обрабатываем строку 28. Мы пытаемся взять элементы этой строки и поменять их на элементы из столбца 28. Первые 8 элементов строки составляют строку кэша, но они пойдут в 8 разных строк кеша в столбце 28. Помните, критический шаг состоит из 4 строк (4 последовательных элемента в столбце).

Когда элемент 16 достигнут в столбце (4 строки кэша в наборе и 4 строки в отдельности = проблема), элемент ex-0 будет выведен из кеша. Когда мы дойдем до конца столбца, все предыдущие строки кэша были бы потеряны и должны были перезагрузиться при доступе к следующему элементу (вся строка будет перезаписана).

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

Еще один отказ от ответственности - я только что обдумал объяснение и надеюсь, что я пригвоздил его, но я могу ошибаться. Во всяком случае, я жду ответа (или подтверждения) из Mysticial.:)

Ответ 2

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

В основном ваш алгоритм:

for (int i = 0; i < N; i++) 
   for (int j = 0; j < N; j++) 
        A[j][i] = A[i][j];

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

Можем ли мы сделать это лучше? Да, мы можем: общий подход к этой проблеме - кэшировать забытые алгоритмы, которые, как говорится в названии, избегают зависимости от конкретных размеров кеша [1]

Решение будет выглядеть так:

void recursiveTranspose(int i0, int i1, int j0, int j1) {
    int di = i1 - i0, dj = j1 - j0;
    const int LEAFSIZE = 32; // well ok caching still affects this one here
    if (di >= dj && di > LEAFSIZE) {
        int im = (i0 + i1) / 2;
        recursiveTranspose(i0, im, j0, j1);
        recursiveTranspose(im, i1, j0, j1);
    } else if (dj > LEAFSIZE) {
        int jm = (j0 + j1) / 2;
        recursiveTranspose(i0, i1, j0, jm);
        recursiveTranspose(i0, i1, jm, j1);
    } else {
    for (int i = i0; i < i1; i++ )
        for (int j = j0; j < j1; j++ )
            mat[j][i] = mat[i][j];
    }
}

Немного сложнее, но короткий тест показывает что-то довольно интересное на моем старом e8400 с выпуском VS2010 x64, тестовый код для MATSIZE 8192

int main() {
    LARGE_INTEGER start, end, freq;
    QueryPerformanceFrequency(&freq);
    QueryPerformanceCounter(&start);
    recursiveTranspose(0, MATSIZE, 0, MATSIZE);
    QueryPerformanceCounter(&end);
    printf("recursive: %.2fms\n", (end.QuadPart - start.QuadPart) / (double(freq.QuadPart) / 1000));

    QueryPerformanceCounter(&start);
    transpose();
    QueryPerformanceCounter(&end);
    printf("iterative: %.2fms\n", (end.QuadPart - start.QuadPart) / (double(freq.QuadPart) / 1000));
    return 0;
}

results: 
recursive: 480.58ms
iterative: 3678.46ms

Edit: О влиянии размера: он гораздо менее выражен, хотя и до сих пор заметен до некоторой степени, потому что мы используем итеративное решение как лист node вместо рекурсии до 1 (обычная оптимизация для рекурсивного алгоритмы). Если мы установим LEAFSIZE = 1, кеш не повлияет на меня [8193: 1214.06; 8192: 1171.62ms, 8191: 1351.07ms - что внутри поля ошибки флуктуации находятся в области 100 мс; этот "тест" не является чем-то, что мне было бы слишком комфортно, если бы мы хотели полностью точные значения])

[1] Источники для этого материала: Хорошо, если вы не можете получить лекцию от кого-то, кто работал с Лейсерсоном и сотрудничать с этим. Я полагаю, что их документы являются хорошей отправной точкой. Эти алгоритмы все еще довольно редко описываются - у CLR есть одна сноска о них. Тем не менее это отличный способ удивить людей.

Изменить (заметьте: я не тот, кто разместил этот ответ, я просто хотел добавить это):
Здесь полная версия С++ приведенного выше кода:

template<class InIt, class OutIt>
void transpose(InIt const input, OutIt const output,
    size_t const rows, size_t const columns,
    size_t const r1 = 0, size_t const c1 = 0,
    size_t r2 = ~(size_t) 0, size_t c2 = ~(size_t) 0,
    size_t const leaf = 0x20)
{
    if (!~c2) { c2 = columns - c1; }
    if (!~r2) { r2 = rows - r1; }
    size_t const di = r2 - r1, dj = c2 - c1;
    if (di >= dj && di > leaf)
    {
        transpose(input, output, rows, columns, r1, c1, (r1 + r2) / 2, c2);
        transpose(input, output, rows, columns, (r1 + r2) / 2, c1, r2, c2);
    }
    else if (dj > leaf)
    {
        transpose(input, output, rows, columns, r1, c1, r2, (c1 + c2) / 2);
        transpose(input, output, rows, columns, r1, (c1 + c2) / 2, r2, c2);
    }
    else
    {
        for (ptrdiff_t i1 = (ptrdiff_t) r1, i2 = (ptrdiff_t) (i1 * columns);
            i1 < (ptrdiff_t) r2; ++i1, i2 += (ptrdiff_t) columns)
        {
            for (ptrdiff_t j1 = (ptrdiff_t) c1, j2 = (ptrdiff_t) (j1 * rows);
                j1 < (ptrdiff_t) c2; ++j1, j2 += (ptrdiff_t) rows)
            {
                output[j2 + i1] = input[i2 + j1];
            }
        }
    }
}

Ответ 3

В качестве иллюстрации к объяснению в Luchian Grigore ответьте, вот что выглядит, как выглядит матричное кэширование для двух случаев 64x64 и 65x65 (см. ссылку выше для получения подробной информации о номерах).

Цвета в анимации ниже означают следующее:

• - не в кеше,
• - в кеше,
• - кэш,
• - просто прочитайте из ОЗУ,
• - пропустить кеш.

Случай 64x64:

Обратите внимание, что почти каждый доступ к новой строке приводит к пропуску кеша. И теперь, как он ищет нормальный случай, матрица 65x65:

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