оптимизации вложенный цикла в с

Question

У меня есть следующий кусок кода С,

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, следовательно, этот вложенный цикл loop работает много раз. Это влияет на производительность кода, то есть занимает много времени, чтобы дать результаты. Я профилировал код, используя valgrind/kcachegrind. Это указывало, что 70% времени выполнения процесса было потрачено на выполнение этого цикла вложенных циклов. Регистровые переменные i и j, по-видимому, не хранятся в значениях регистров (профилирование с ключевым словом «без регистрации» указано)

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

Answer 1

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

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

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

Я мог бы быть неправильно здесь, но не следующий эквивалент:

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

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]; 
    } 

Would, например, стать:

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]; 
    } 

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

Для получения более полных примеров возможностей оптимизации вы можете взглянуть на this presentation.

Если вам нужна еще большая производительность, вы можете взглянуть на встроенные средства 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

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

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