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

Question

Почему сложение матрицы занимает намного больше времени, чем умножение матрицы на вектор?

Matrix Add только стоит n ^ 2 add, тогда как Matrix-Vector Multiplication принимает n * (n-1) add и n ^ 2 умножение.

Однако в Eigen Matrix Add занимает вдвое больше времени, чем Matrix-Vector умножение.Существует ли какая-либо опция для ускорения операции Matrix Add в Eigen?

#include <eigen3/Eigen/Eigen>
#include <iostream>
#include <ctime>
#include <string>
#include <chrono>
#include <fstream>
#include <random>
#include <iomanip>

using namespace Eigen;
using namespace std;

int main()
{
const int l=100;
MatrixXf m=MatrixXf::Random(l,l);
MatrixXf n=MatrixXf::Random(l,l);
VectorXf v=VectorXf::Random(l,1);

MatrixXf qq=MatrixXf::Random(l,1);
MatrixXf pp=MatrixXf::Random(l,l);

auto start = chrono::steady_clock::now();
for(int j=0;j<10000;j++)
qq=m*v;
auto end = chrono::steady_clock::now();
double time_duration=chrono::duration_cast<chrono::milliseconds>(end - start).count();
std::cout << setprecision(6) << "Elapsed time in seconds : "<< time_duration/1000<< "s" << std::endl;
auto start1 = chrono::steady_clock::now();
for(int j=0;j<10000;j++)
pp=m+n;
auto end1 = chrono::steady_clock::now();
double time_duration1=chrono::duration_cast<chrono::milliseconds>(end1 - start1).count();
std::cout << setprecision(6) << "Elapsed time in seconds : "<< time_duration1/1000<< "s" << std::endl;
}

Тест 1: Без оптимизации:

команда компиляции: g ++ - 8 -test.cpp -o test

команда запуска: ./test

Истекшее время в секундах: 0,323 с

Истекшее время в секундах: 0,635 с

Тест 2: с -march =собственная оптимизация:

g ++ - 8 test.cpp -march = native -o test

команда запуска: ./test

истекшее время в секундах: 0,21 с

Истекшее время в секундах: 0,372 с

Тест 3: с оптимизацией -O3:

команда компиляции: g ++ - 8 -test.cpp -O3 -o тест

команда запуска: ./test

Истекшее время в секундах: 0,009 с

Прошедшее время в секундах: 0,016 с

Тест 4: с -march = native, -O3оптимизация:

команда компиляции: g ++ - 8 -test.cpp -march = native -O3 -o test

команда запуска: ./test

Истекшее время в секундах:0,008 с

Истекшее время в секундах: 0,016 с

==============

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

#include <eigen3/Eigen/Eigen>
#include <iostream>
#include <ctime>
#include <string>
#include <chrono>
#include <fstream>
#include <random>
#include <iomanip>

using namespace Eigen;
using namespace std;

int main()
{
const int l=1000;
MatrixXf m=MatrixXf::Random(l,l);
MatrixXf n=MatrixXf::Random(l,l);
VectorXf v=VectorXf::Random(l,1);

MatrixXf qq=MatrixXf::Random(l,1);
MatrixXf pp=MatrixXf::Random(l,l);

auto start = chrono::steady_clock::now();
qq=m*v;
auto end = chrono::steady_clock::now();
double time_duration=chrono::duration_cast<chrono::microseconds>(end - start).count();

auto start1 = chrono::steady_clock::now();
pp=m+n;
auto end1 = chrono::steady_clock::now();
double time_duration1=chrono::duration_cast<chrono::microseconds>(end1 - start1).count();
std::cout << setprecision(6) << "Elapsed time in microseconds : "<< time_duration<< "us" << std::endl;
std::cout << setprecision(6) << "Elapsed time in microseconds : "<< time_duration1<< "us" << std::endl;
}

Тест 1: Без какой-либо оптимизации:

команда компиляции: g ++ - 8 -test.cpp -o test

команда запуска: ./test

Истекшее время в микросекундах: 3125us

Истекшее время в микросекундах: 6849us

Тест 2: -March = собственная оптимизация:

g ++ - 8 test.cpp -march = собственная -o test

команда запуска: ./test

Истекшее время в микросекундах:1776us

Истекшее время в микросекундах: 3815us

Тест 3: с оптимизацией -O3:

команда компиляции: g ++ - 8 -test.cpp -O3 -o тест

команда запуска: ./test

Истекшее время в микросекундах: 449us

Истекшее время в микросекундах: 760us

Тест 4: с -march = native, -Оптимизация O3:

команда компиляции: g ++ - 8 -test.cpp -march = native -O3 -o test

команда запуска: ./test

Истекшее время в ммикросекунды: 351us

Истекшее время в микросекундах: 871us

Answer 1

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

Прежде всего, практическое количество операций одинаково для обеих операций, потому что современные процессоры могут выполнять одно независимое сложение и умножение одновременно.Два последовательных типа mul / add типа x*y+z могут даже объединяться в одну операцию с той же стоимостью, что и 1 сложение или 1 умножение.Если ваш процессор поддерживает FMA, это то, что происходит с -march=native, но я сомневаюсь, что FMA играет здесь какую-то роль.

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

Для сложения это просто: у нас есть 2*n^2 загрузки с большим количеством пропусков кэша,хранится в плюс n^2.

Для произведения матрицы-вектора с матрицей основного столбца входной вектор читается только один раз, поэтому n^2+n загружается для входных данных, а столбцы обрабатываются блоком.из 4 столбцов одновременно мы имеем n^2/4 чтение-запись в выходной вектор, но с почти нулевым отсутствием кэша, потому что он помещается в кэш L1.Таким образом, в целом у вас почти вдвое дороже загружается память для сложения, чем для матрично-векторного произведения, и поэтому коэффициент скорости x2 не является ненормальным.

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