Почему мой множитель матрицы Штрассена такой быстрый?

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

https://github.com/wcochran/strassen_multiplier/blob/master/mm.c

К моему удивлению, это было намного быстрее для больших n. Например, для случая n=1024 при использовании обычного метода потребовалось 17,20 секунды, а при использовании метода Штрассена (2x2,66 ГГц Xeon) — всего 1,13 секунды. Что -- 15-кратное ускорение!? Это должно быть лишь незначительно быстрее. В самом деле, это казалось таким же хорошим даже для небольших матриц 32x32!?

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

Любые другие теории о том, почему это так быстро?


performance matrix strassen
person wcochran    schedule 19.10.2011    source источник

Ответы (3)


arrow_upward
3
arrow_downward

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

person user1188672    schedule 17.03.2012

arrow_upward
1
arrow_downward

Первый вопрос: «Правильны ли результаты?». Если это так, вполне вероятно, что ваш «обычный» метод не является хорошей реализацией.

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

Стандартные матричные библиотеки реализуют гораздо более дружественные к кэшу методы, учитывающие размер кэша данных.

Вы также можете реализовать рекурсивную версию стандартного матричного произведения (разделить на матрицу 2x2 матриц вдвое меньшего размера). Это даст что-то близкое к оптимальной производительности кеша, которую Strassen получает от рекурсии.

Так что либо вы делаете это неправильно, либо ваш обычный код не оптимизирован.

person phkahler    schedule 19.10.2011
comment
К моему удивлению, версия 1 заработала сразу же. У меня высокая уверенность в правильности. Следующее, что нужно проверить, это ваше предложение разделить стандартный алгоритм. Я также попробую трюк с транспонированием, чтобы сделать стандартный алгоритм более удобным для кэширования. Спасибо. - person wcochran; 20.10.2011

arrow_upward
0
arrow_downward

Каков порядок цикла в вашем обычном умножении? Если у вас есть

for (int i = 0; i < new_height; ++i)
{
    for (int j = 0; j < new_width; ++j)
    {
        double sum = 0.0;
        for (int k = 0; k < common; ++k)
        {
            sum += lhs[i * common + k] * rhs[k * new_width + j];
        }
        product[i * new_width + j] = sum;
    }
}

тогда вы не очень хорошо обращаетесь с кешем, потому что вы обращаетесь к правой матрице прерывистым образом. После повторного заказа на

for (int i = 0; i < new_height; ++i)
{
    for (int k = 0; k < common; ++k)
    {
        double const fixed = lhs[i * common + k];
        for (int j = 0; j < new_width; ++j)
        {
            product[i * new_width + j] += fixed * rhs[k * new_width + j];
        }
    }
}

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

Вы не указали язык, но что касается C++, продвинутые компиляторы даже распознают недружественный порядок циклов в некоторых конфигурациях и переупорядочивают их.

person primfaktor    schedule 18.11.2014