Тесты реализации матрицы, стоит ли мне себя хлестать?

Question

Я пытаюсь найти в Интернете некоторые тесты умножения/инверсии матриц.Моя реализация на C++ в настоящее время может инвертировать матрицу 100 x 100 за 38 секунд, но по сравнению с этот тест, который я нашел, производительность моей реализации действительно отстойная.Я не знаю, является ли это чем-то сверхоптимизированным или действительно можно легко инвертировать матрицу 200 x 200 примерно за 0,11 секунды, поэтому я ищу больше тестов для сравнения результатов.У тебя есть какая-нибудь хорошая ссылка?

ОБНОВЛЯТЬЯ заметил ошибку в своем коде умножения, которая не влияла на результат, но приводила к бесполезным тратам цикла.Теперь моя инверсия выполняется за 20 секунд.Времени еще много, и любые идеи приветствуются.

Спасибо, ребята

Answer 1

Операции такого типа чрезвычайно чувствительны к кэшу.Вы хотите выполнять большую часть своей работы с переменными, которые находятся в вашем кеше L1 и L2.Ознакомьтесь с разделом 6 этого документа:

http://people.redhat.com/drepper/cpumemory.pdf

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

Answer 2

Проверьте, передаете ли вы огромные объекты матрицы по значению (поскольку это может быть дорогостоящим при копировании всей матрицы).
Если можно, передайте по ссылке.

Особенность матриц и C++ в том, что вы хотите по возможности избегать копирования.
Таким образом, ваш основной объект, вероятно, не должен содержать «данные матрицы», а скорее содержать метаданные о матрице и указатель (обернутый чем-то умным) на часть данных.Таким образом, при копировании объекта вы копируете только небольшой фрагмент данных, а не все целиком (пример см. в реализации строки).

Answer 3

Зачем вам вообще нужна реализация собственной библиотеки матриц?Как вы уже заметили, уже существуют чрезвычайно эффективные библиотеки, выполняющие то же самое.И хотя людям нравится думать о C++ как о языке производительности, это верно только в том случае, если вы Действительно хорош в языке.На C++ чрезвычайно легко написать ужасно медленный код.

Answer 4

Я не знаю, является ли это супер-оптимизированным что-то или, если действительно вы можете легко инвертировать матрицу 200 x 200 примерно за 0,11 секунд

MATLAB делает это, не особо беспокоясь.Вы реализуете ЛАПАК процедуры для обращения матрицы (например.LU-разложение)?

Answer 5

Вы пробовали профилировать?

Следуя этому бумага (pdf), для расчета матрицы 100x100 с LU-разложением потребуется 1348250 (операции с плавающей запятой).Ядро 2 может работать со скоростью около 20 Гфлопс (метрики процессора).Теоретически вы можете выполнить инверсию за 1 мс.

Без кода довольно сложно утверждать, в чем причина большого разрыва.Судя по моему опыту, использующему микрооптимизацию, такую ​​как развертывание цикла, кэширование значений, SEE, многопоточность и т. д., вы получите только прирост скорости, который в лучшем случае является лишь постоянным фактором вашего тока (чего, возможно, вам будет достаточно).

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

Answer 6

Тем ЛИНПАК тесты основаны на решении задач линейной алгебры.Они доступны для разных машин и языки.Возможно, они смогут помочь и вам.

Доступны библиотеки LINPACK C++. здесь, слишком.

Answer 7

На самом деле я выиграл около 7 секунд, используя **double**s вместо **long double**с, но это не так уж и много, поскольку я потерял половину своей точности.