Как я могу оптимизировать интенсивную вычислением программу C++ с известным узким местом?

Разные мысли:

• Вы говорите, что вам удается достичь загрузки процессора только около 25%. Я могу придумать для этого две причины:
  1. Вы меняете местами. Какой размер у ваших матриц? Умещаются ли они полностью в физической памяти? Посмотрите на использование памяти вашим приложением и размер рабочего набора.
  2. Остальной код вашего приложения блокирует ввод-вывод. Выполняет ли код, окружающий вашу основную процедуру, какие-либо операции ввода-вывода? Это может быть блокировка там на большие промежутки времени, но, конечно, вы не видите этого, используя технику «пауза-когда-занято-и-проверяй», потому что всякий раз, когда процесс снова разблокируется, он возвращается прямо в ваше ядро, требующее интенсивных вычислений. рутина.
• Взгляните на ассемблерный код своей основной процедуры. Выглядит ли это разумно?
• Вам действительно нужно вычислять diffsum внутри цикла? Похоже, что вы могли бы сделать diffsum = sumA-sumB один раз вне цикла, но могут быть числовые соображения, которые не позволят вам сделать это.
• Как уже прокомментировал Реник, это выглядит как основная цель для оптимизации SSE. Опять же, вы должны убедиться, что компилятор генерирует разумный код сборки (если вы используете встроенные функции, а не пишете сборку самостоятельно).
• Если вы не хотите писать код SSE самостоятельно, по крайней мере убедитесь, что установлен флаг SSE вашего компилятора. Это позволит компилятору использовать модуль SSE вместо FPU для скалярных операций с плавающей запятой, что само по себе улучшит производительность, поскольку FPU на основе стека на x86, как известно, плохо подходит для генерации кода компилятора.

Вам следует попытаться избавиться от циклов и вместо этого попробовать векторизовать операции. Используя такую ​​библиотеку, как Eigen , ваш код будет выглядеть примерно так:

Eigen::MatrixXd matrixA(height, width);
Eigen::MatrixXd matrixB(height, width);
double sumA = matrixA.sum();
double sumAsq = matrixA.cwise().square().sum();
double sumB = matrixB.sum();
double sumBsq = matrixB.cwise().square().sum();

Eigen::MatrixXd diff = matrixA - matrixB;
double diffSum = diff.sum();
double diffSumSq = diff.cwise().square().sum();

return sumA + sumB / sumAsq + sumBsq * diffSum * diffSumSq;

«25% от своего предела и с относительно большими колебаниями, при которых я ожидал бы устойчивой, 100% -ной нагрузки, пока программа не завершится».

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

Я бы также рекомендовал использовать одну из математических библиотек, например Eigen , ATLAS или GSL

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

vala = *matrixA++; 
valb = *matrixB++; 

и, поскольку вы выполняете простые сложения и вычитания, посмотрите на SSE/SSE2 и т.д. в зависимости от возможностей вашего целевого процессора и вашей арифметики (целочисленной, с плавающей точкой и т.д.).

EDIT: MMX SSE2 intrinsics - это функции, которые отображаются один к одному с SIMD инструкциями CPU. Посмотрите эти страницы microsoft, чтобы начать, и дополнительно я советую заглянуть на сайт Intel для IA-32/ Intel64 руководства программиста или аналогичные руководства от AMD.

Я также очень рекомендую эту книгу по оптимизации для архитектур Intel. Она объяснит все скрытые возможности вашего процессора и компилятора.

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

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

Если бы я был на вашем месте, я бы попытался выяснить, что именно вызывает разницу в производительности между старым и новым кодом. Возможно, матрицы boost используют какое-то кэширование или ленивую/нетерпеливую оценку.

Сохранять матрицы с такими же параметрами вне цикла? Я думаю, что тебе нужно немного сэкономить.

TLDR: сначала оптимизируйте алгоритм умножения матриц, затем следите за количеством темпоралов, затем оптимизируйте внутренние распределения матриц.

Длинный ответ:

Я думаю, что наиболее важным моментом является оптимизация умножения матриц. Умножение матриц для самого интуитивного алгоритма - это O(n^3) (что огромно даже для маленьких матриц).

Для примера, для умножения матрицы 2x2 у вас есть 16 операций умножения ("мо"). Для умножения матрицы 3x3 у вас есть 27 mo, а для 4x4 - 64 mo.

Я не уверен, как это реализовано в вашем случае, но если это интуитивный алгоритм (как тройной for цикл), изменение этого алгоритма на матричное умножение с использованием LU-разложенных матриц должно резко увеличить вашу производительность.

Это связано с тем, что, получив разложенные матрицы, вы можете сильно оптимизировать алгоритм умножения (нет смысла перемножать строки и столбцы для нулевых элементов).

Далее, рассмотрите возможность использования кэшированных значений вместо повторения операций сложения в diffsumsq:

старый код:

diffsum+=valA-valB; // compute difference once
diffsumsq+=(valA-valB)*(valA-valB); // compute it two more times, then multiply

новый код:

diff = valA-valB; // compute difference once
diffsum+= diff; // use computed difference
diffsumsq+=diff*diff; // just multiply

Второй вариант в три раза быстрее на вычислении разности (два for цикла - операции x* y выполняются только один раз вместо трех).

Далее можно следить за количеством временных объектов: каждая бинарная операция создает временный объект (что означает выделение в памяти еще одной матрицы x*y и копирование значений). Например, выражение:

diffsumsq+=(valA-valB)*(valA-valB);

создает временный объект для разности в первой парантезе, затем еще один для разности во второй, затем еще один для произведения.

В моем примере лучше написать

diff = valA;
diff -= valB;

вместо

diff = valA - valB;

так как таким образом вы избежите выделения временного, которое присваивается diff (во втором варианте).

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

Я уверен, что есть и другие вещи, за которыми нужно следить.

Edit: Как вы можете умножать матрицы? Нужно, чтобы они сопоставлялись по столбцам x строкам. То есть, количество столбцов в valA должно быть равно количеству строк в valB (если я правильно помню свои умножения матриц).

Еще один момент:

Я сделал процедуру вычисления в виде многострочный макрос #define, чтобы обеспечить ее инлайнинг и чтобы избежать вызовов и возвратов функций.

Для оптимизации кода на C++ макросы не нужны. Чтобы избежать вызовов и возвратов функций, используйте встроенныефункции. Макросы имеют свои проблемы.

Вам также следует попробовать, если у вас нет возможности многопоточности цикла с помощью простой настройки, такой как OpenMP. использование ЦП на 25% звучит как четырехъядерный процессор, на котором работает один рабочий поток.