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

Question

Я занимаюсь разработкой научного программного обеспечения для своего университета.Он написан на C ++ для Windows (VS2008).Алгоритм должен вычислять некоторые значения для большого числа пар матриц, то есть в ядре находится цикл, повторяющийся над матрицами и собирающий некоторые данные, например:

sumA = sumAsq = sumB = sumBsq = diffsum = diffsumsq = return = 0;
for (int y=0; y < height; ++y)
{
    for (int x=0; x < width; ++x)
    { 
        valA = matrixA(x,y);
        valB = matrixB(x,y);
        sumA+=valA;
        sumAsq+=valA*valA;
        sumB+=valB;
        sumBsq+=valB*valB;
        diffsum+=valA-valB;
        diffsumsq+=(valA-valB)*(valA-valB);
    }
}
return = sumA + sumB / sumAsq + sumBsq * diffsum * diffsumsq

Эта процедура выполняется миллионы раздля разных пар matrixA, matrixB.Моя проблема в том, что эта программа работает очень медленно, компилируется в режиме Release со всеми активированными оптимизациями.Используя технику отладки «пауза при занятии и проверке», я установил, что программа находится внутри этого цикла практически каждый раз, хотя, как и следовало ожидать, эта процедура окружена целымкуча условий и веток управления.Больше всего меня озадачивает то, что во время исполнения в двухпроцессорной системе на базе Xeon программа использует одно из 4 ядер (что неудивительно, пока что она однопоточная), но только до 25% от ее предела.и с относительно большими колебаниями, где я ожидал бы постоянной 100% загрузки до завершения программы.

Текущая версия на самом деле является переписанной, созданной с учетом оптимизации производительности.Я был опустошен, когда узнал, что это на самом деле медленнее, чем оригинал.В предыдущей версии использовались матрицы Boost, которые я заменил на матрицы OpenCV, после того, как установил их в 10 раз быстрее при сравнении времени выполнения умножения двух матриц 1000x100.Я получаю доступ к матрице, вручную разыменовывая необработанный указатель на ее данные, который, как я надеялся, даст мне некоторую производительность.Я сделал процедуру вычисления многострочным макросом #define, чтобы обеспечить его встраивание и избежать вызовов и возвратов функций.Я улучшил математику вычислений, чтобы окончательное значение вычислялось за один проход через матрицы (старая версия требует двух проходов).Я ожидал получить огромный выигрыш, и все же все наоборот.Я совсем не близок к эффективности моей старой программы, не говоря уже о коммерческом программном обеспечении для конкретного приложения.

Мне было интересно, возможно, оно как-то связано с матричными данными, представляющими собой 8-битные символы, я однажды увидел, чтов моей старой программе доступ к числам с плавающей запятой был на самом деле медленнее, чем к двойным, возможно, символы даже медленнее, поскольку процессор извлекает данные в виде 32-битных блоков (этот Xeon, вероятно, захватывает даже 64 бита).Я также подумал о том, чтобы превратить матрицы в векторы, чтобы избежать конструкции внутри цикла, а также при некоторой форме векторизации, например, при расчете данных для 4 (меньше? Больше?) Последовательных ячеек матрицы за одну итерацию цикла.Любые другие идеи, пожалуйста?

РЕДАКТИРОВАТЬ: актуальный код в новой версии, основанной на OpenCV:

const char *Aptr, *Bptr;
double sumA = 0, sumB = 0, sumAsq = 0, sumBsq = 0, diffsum = 0, diffsumsq = 0;
char Aval, Bval;

for (int y=0; y < height; ++y)
{
    Aptr = (char*)(AMatrix.imageData + AMatrix.widthStep * y);
    Bptr = (char*)(BMatrix.imageData + BMatrix.widthStep * y);
    for (int x=0; x < width; ++x)
    {
        Aval = Aptr[x];
        Bval = Bptr[x];

        sumA+=Aval;
        sumB+=Bval;
        sumAsq+=Aval*Aval;
        sumBsq+=Bval*Bval;
        diffsum+=Aval-Bval;
        diffsumsq+=(Aval-Bval)*(Aval-Bval);
    }
}

Answer 1

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

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

Answer 2

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

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

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

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

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

Answer 3

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

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

Answer 4

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

Никогда не угадай, когда сможешь просто узнать. Тем не менее, вот мое предположение :-) Вы делаете все суммирование в переменных с плавающей точкой, но получаете исходные числа в виде целых символов, верно? Тогда вы можете ожидать, что преобразование из int в double займет некоторое время, и если это так, вы увидите, что ваши паузы в этих инструкциях происходят большую часть времени. В общем, мне интересно, почему вы не делаете все это в целочисленной арифметике.

Вы говорите, что использование никогда не превышает 25%. Может ли это быть потому, что он использует только одно из 4 ядер?

Вы говорите, что использование часто падает ниже 25%. Это говорит о том, что, возможно, поток блокирует выполнение файлового ввода-вывода. Если это так, ваши паузы должны поймать это в акте и подтвердить это. Если это так, вы можете ускорить ввод-вывод, используя более крупные блоки, или, возможно, реже открывать / закрывать. Обратите внимание, что улучшения в вашем внутреннем цикле сократят количество времени, проведенного в этом цикле, но не уменьшат время, потраченное на ввод-вывод, поэтому процент времени на ввод-вывод увеличится (что приведет к очевидному уменьшению использования) До тех пор, пока вы не уменьшите это.

Использование на самом деле не очень полезное число. На самом деле это только индикатор разделения CPU / IO, и он вообще не говорит вам, выполняете ли вы слишком много одного из них.

Как сказал @renick, избавьтесь от вычисления адреса. Вы должны быть в состоянии пройти этот цикл на уровне ассемблера и увидеть, что он не делает ничего больше, чем сделал бы, если бы вы надели шляпу "гуру" и написали сборку самостоятельно.

В любом случае векторизация может быть большой победой.

Answer 5

Вы должны попытаться избавиться от своих циклов и попробовать вместо этого векторизовать операции. Используя библиотеку типа 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;

Answer 6

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

Answer 7

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

Answer 8

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

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

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

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

Я не уверен, как он реализован в вашем случае, но если это интуитивный алгоритм (как тройной цикл 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 (во втором варианте).

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

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

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

Еще одна вещь:

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

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

Answer 9

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

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

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

Answer 10

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