Оптимизация вложенного цикла в C

Question

У меня есть следующий фрагмент кода c,

double findIntraClustSimFullCoverage(cluster * pCluster)
{
    double sum = 0;
    register int i = 0, j = 0;
    double perElemSimilarity = 0;

    for (i = 0; i < 10000; i++)
    {
        perElemSimilarity = 0;

        for (j = 0; j < 10000; j++)
        {

            perElemSimilarity += arr[i][j];

        }
        perElemSimilarity /= pCluster->size;
        sum += perElemSimilarity;
    }
    return (sum / pCluster->size);
}

NOTE: arr - матрица размером 10000 X 10000

Это часть кода GA, поэтому этот вложенный цикл for выполняется много раз. Это влияет на производительность кода, т. Е. На получение результатов уходит много времени. Я профилировал код, используя valgrind / kcachegrind. Это указывало на то, что 70% времени выполнения процесса было потрачено на выполнение этого вложенного цикла for. Переменные регистра i и j, похоже, не сохраняются в значениях регистра (профилирование с ключевым словом «register» и без него указывает на это)

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

Answer 1

Я предполагаю, что вы часто меняете матрицу arr, иначе вы могли бы просто вычислить сумму (см. Ответ Люциана) один раз и запомнить ее.

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

double arr[10000][10000];
< initialize it to all zeros >
double sum = 0;

// you want set arr[27][53] to 82853
sum -= arr[27][53];
arr[27][53] = 82853;
sum += arr[27][53];

// you want set arr[27][53] to 473
sum -= arr[27][53];
arr[27][53] = 473;
sum += arr[27][53];

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

Answer 2

Как эта проблема сформулирована, вы мало что можете сделать.Вы обрабатываете 10000 x 10000 двойных входных значений, то есть 800 МБ.Что бы вы ни делали, это ограничено временем чтения 800 МБ данных.

С другой стороны, вы также пишете 10 000 x 10 000 значений каждый раз, когда это вызывается?Если нет, вы можете, например, сохранить суммы для каждой строки и иметь логическую строку, указывающую, что необходимо вычислить сумму строки, которая устанавливается каждый раз при изменении элемента строки.Или вы можете даже обновить сумму для строки каждый раз, когда изменяется элемент массива.

Answer 3

1. Ключевое слово register является подсказкой оптимизатора, если оптимизатор не считает, что регистр там тратится хорошо, он не будет.
2. Хорошо ли упакована матрица, т.е.это непрерывный блок памяти?
3. Является ли 'j' второстепенным индексом (т.е. вы переходите от одного элемента к другому в памяти), или вы переходите от одного элемента к этому плюс 1000?
4. Является ли arr довольно статичным?Это вызывается более одного раза на одном arr?Результат внутреннего цикла зависит только от строки / столбца, который j пересекает, поэтому его вычисление лениво и сохранение для дальнейшего использования будет иметь большое значение

Answer 4

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

Вероятно, что в какой-то момент узкое место операции вытягивает значения arr из памяти.Поэтому убедитесь, что ваши данные размещены в линейном кеше.То есть &arr[i][j+1] - &arr[i][j] == sizeof(double).

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

    for (j = 0; j < 10000; j++)
    {
        perElemSimilarity += arr[i][j];
    }

Например, станет:

    for (j = 0; j < 10000; j+=10)
    {
        perElemSimilarity += arr[i][j+0];
        perElemSimilarity += arr[i][j+1];
        perElemSimilarity += arr[i][j+2];
        perElemSimilarity += arr[i][j+3];
        perElemSimilarity += arr[i][j+4];
        perElemSimilarity += arr[i][j+5];
        perElemSimilarity += arr[i][j+6];
        perElemSimilarity += arr[i][j+7];
        perElemSimilarity += arr[i][j+8];
        perElemSimilarity += arr[i][j+9];
    }

Это основные идеи, которые сложно сказать больше, не зная вашей платформы, компилятора, глядя на сгенерированный код сборки.

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

Если вам нужна еще большая производительность, вы можете взглянуть на SIMDвстроенные средства для вашей платформы, например, попытка использовать, скажем, OpenMP, для распределения вычислений по нескольким потокам.

---

Еще одним шагом будет попытка использовать OpenMP, что-то из следующего (непроверенного):

#pragma omp parallel for private(perElemSimilarity) reduction(+:sum)
for (i = 0; i < 10000; i++)
{
    perElemSimilarity = 0;
    /* INSERT INNER LOOP HERE */
    perElemSimilarity /= pCluster->size;
    sum += perElemSimilarity;
}

Но учтите, что даже если вы доведите эту часть кода до 0% (что невозможно) от вашего времени выполнения, ваш алгоритм GA все равно будет работать несколько часов.Ваше узкое место в производительности теперь в другом месте, поскольку эта часть кода занимает «только» 22% вашего времени выполнения.

Answer 5

Я могу ошибаться, но это не следующий эквивалент:

for (i = 0; i < 10000; i++)
{
    for (j = 0; j < 10000; j++)
    {
        sum += arr[i][j];
    }
}
return (sum / ( pCluster->size * pCluster->size ) );