Почему мой множитель Strassen Matrix такой быстрый? - PullRequest
Новая
       25

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

1 голос
/ 20 октября 2011

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

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

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

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

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

Ответы [ 3 ]

3 голосов
/ 17 марта 2012

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

1 голос
/ 20 октября 2011

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

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

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

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

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

0 голосов
/ 18 ноября 2014

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

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 ++, в некоторых конфигурациях продвинутые компиляторы даже распознают недружественный порядок циклови изменить их порядок.

...