Подсчет FLOP и размера данных и проверка, связана ли функция с памятью или с процессором

Question

Я собираюсь проанализировать и оптимизировать некоторый C-код, и поэтому сначала я должен проверить, связаны ли функции, которые я хочу оптимизировать, с памятью или с процессором. В общем, я знаю, как это сделать, но у меня есть несколько вопросов о подсчете операций с плавающей запятой и анализе размера используемых данных. Посмотрите на следующий цикл for, который я хочу проанализировать. Значения массива являются двойными (это означает 8 байтов каждое):

for(int j=0 ;j<N;j++){
    for(int i=1 ;i<Nt;i++){
        matrix[j*Nt+i] = matrix[j*Nt+i-1] * mu + matrix[j*Nt+i]*sigma;
    }
}

1) Сколько операций с плавающей запятой вы считаете? Я думал о 3*(Nt-1)*N... но нужно ли мне подсчитывать и операции внутри массивов (матрица [j*Nt+i], которые на 2 больше FLOP для этого массива)?

2) Сколько данных передается? 2 * ((Nt-1) * N) 8байт или 3 ((Nt-1) * N) * 8 байт. Я имею в виду, что каждая запись матрицы должна быть загружена. После расчета новые значения сохраняются в этом индексе массива (теперь это 1load и 1 store). Но это значение используется для следующего расчета. Следовательно, нужны ли другие операции загрузки или это значение (матрица [j*Nt+i-1]) уже доступно без операции загрузки?

Большое спасибо!!!

Answer 1

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

Это связано с тем, что современные компиляторы и процессоры очень умны в отношении оптимизации кода, подобного этому, и в конечном итоге он будет выполняться не так, как ваш простой анализ. Компилятор оптимизирует код, переставляя отдельные операции. Процессор сам попытается выполнить отдельные подоперации параллельно и / или конвейерно, так что, например, вычисления происходят, пока данные выбираются из памяти.

Полезно думать об алгоритмической сложности, различать O(n) и O(n²) и т. Д., Но постоянные факторы (как вы спрашиваете о 2*... или 3*...) полностью спорны, потому что они различаются на практике в зависимости от множества деталей.