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

Я реализовал одно матричное умножение с 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 файлов. Таким образом, он довольно самодостаточен.

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