Почему ускорение матрицы умножается медленнее, чем мое?

Я реализовал одно матричное умножение с boost::numeric::ublas::matrix (см. мой полный рабочий код повышения)

Result result = read ();

boost::numeric::ublas::matrix<int> C;
C = boost::numeric::ublas::prod(result.A, result.B);

и еще один со стандартным алгоритмом (см. полный стандартный код):

vector< vector<int> > ijkalgorithm(vector< vector<int> > A, 
                                    vector< vector<int> > B) {
    int n = A.size();

    // initialise C with 0s
    vector<int> tmp(n, 0);
    vector< vector<int> > C(n, tmp);

    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            for (int j = 0; j < n; j++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

Вот как я проверяю скорость:

time boostImplementation.out > boostResult.txt
diff boostResult.txt correctResult.txt

time simpleImplementation.out > simpleResult.txt
diff simpleResult.txt correctResult.txt

Обе программы считывают жестко закодированный текстовый файл, который содержит две матрицы 2000 x 2000. Обе программы были скомпилированы с этими флагами:

g++ -std=c++98 -Wall -O3 -g $(PROBLEM).cpp -o $(PROBLEM).out -pedantic

Я получил 15 секунд для моей реализации и более 4 минуты для повышения производительности!

edit: после компиляции с помощью

g++ -std=c++98 -Wall -pedantic -O3 -D NDEBUG -DBOOST_UBLAS_NDEBUG library-boost.cpp -o library-boost.out

Я получил 28.19 секунд для ikj-алгоритма и 60.99 секунд для Boost. Таким образом, Boost все еще значительно медленнее.

Почему так значительно медленнее, чем моя реализация?

Ответ 1

Более низкая производительность версии uBLAS может быть частично объяснена функциями отладки последнего, как было указано TJD.

Здесь время, затраченное версией uBLAS с отладкой:

real    0m19.966s
user    0m19.809s
sys     0m0.112s

Здесь время, затраченное версией uBLAS с отладкой (-DNDEBUG -DBOOST_UBLAS_NDEBUG добавлены флаги компилятора):

real    0m7.061s
user    0m6.936s
sys     0m0.096s

Таким образом, при отладке версия uBLAS почти в 3 раза быстрее.

Оставшуюся разницу в производительности можно объяснить, указав следующий раздел часто задаваемые вопросы uBLAS "Почему uBLAS намного медленнее, чем (атлас-) BLAS"

Важная цель дизайна ublas должна быть как можно более общей.

Эта общность почти всегда идет со стоимостью. В частности, шаблон функции prod может обрабатывать различные типы матриц, такие как разреженные или треугольные. К счастью, uBLAS предоставляет альтернативы, оптимизированные для плотного умножения матриц, в частности axpy_prod и block_prod. Ниже приведены результаты сравнения различных методов:

ijkalgorithm   prod   axpy_prod  block_prod
   1.335       7.061    1.330       1.278

Как вы можете видеть, как axpy_prod, так и block_prod несколько быстрее, чем ваша реализация. Измерение только времени вычисления без ввода-вывода, удаление ненужного копирования и тщательный выбор размера блока для block_prod (я использовал 64) могут сделать разницу более глубокой.

См. также uBLAS FAQ и Эффективная uBlas и общая оптимизация кода.

Ответ 2

Я считаю, что ваш компилятор недостаточно оптимизирован. uBLAS-код сильно использует шаблоны, а шаблоны требуют интенсивного использования оптимизаций. Я запустил ваш код через компилятор MS VC 7.1 в режиме выпуска для матриц 1000x1000, он дает мне

10.064 для uBLAS

7.851 для вектора

Разница все еще существует, но отнюдь не подавляющая. Основная концепция uBLAS - это ленивая оценка, поэтому prod(A, B) оценивает результаты только при необходимости, например. prod(A, B)(10,100) будет выполняться в мгновение ока, поскольку только тот один элемент будет фактически вычислен. Как таковой фактически ~~нет выделенного алгоритма для полного умножения матрицы, который можно было бы оптимизировать~~ (см. Ниже). Но вы можете немного помочь библиотеке, объявив

matrix<int, column_major> B;

сократит время выполнения до 4.426, которое будет бить вашу функцию одной рукой. Это объявление делает доступ к памяти более последовательным при умножении матриц, оптимизируя использование кеша.

P.S. Прочитав документацию uBLAS до конца;), вы должны были обнаружить, что на самом деле есть специальная функция для умножения целых матриц сразу. 2 функции - axpy_prod и opb_prod. Так

opb_prod(A, B, C, true);

даже в неоптимизированной строке row_major B выполняется в 8.091 sec и находится наравне с вашим векторным алгоритмом

P.P.S. Там еще больше оптимизаций:

C = block_prod<matrix<int>, 1024>(A, B);

выполняется в 4.4 s, независимо от того, является ли B столбец_ или row_ major. Рассмотрим описание: "Функция block_prod предназначена для больших плотных матриц." Выберите конкретные инструменты для выполнения определенных задач!

Ответ 3

Я создал небольшой веб-сайт Матричные матричные эксперименты с uBLAS. Это о интеграции новой реализации матрично-матричного продукта в uBLAS. Если у вас уже есть библиотека boost, она состоит только из 4 файлов. Таким образом, он довольно самодостаточен.

Мне было бы интересно, если бы другие могли запускать простые тесты на разных машинах.