Как оптимизировать следующий общий цикл?

Question

У меня есть код

#include <iostream> 
#include <vector> 
#include <ctime> 
using namespace std; 

void foo(int n, double* a, double* b, double *c, double*d, double* e, double* f, double* g) 
{ 
    for (int i = 0; i < n; ++i) 
     a[i] = b[i] * a[i] + c[i] * (d[i] + e[i] + f[i] + g[i]); 
} 

int main() 
{ 
    int m = 1001001; 
    vector<double> a(m), b(m), c(m), d(m), f(m); 

    clock_t start = std::clock(); 

    for (int i = 0; i < 1000; ++i) 
     foo(1000000, &a[0], &b[0], &c[0], &d[0], &d[1], &f[0], &f[1000]); 

    double duration = (std::clock() - start)/(double)CLOCKS_PER_SEC; 
    cout << "Finished in " << duration << " seconds [CPU Clock] " << endl; 
} 

Можете ли вы дать мне работоспособный пример, чтобы оптимизировать его с более высокой производительностью? Любой компилятор хорош, как компилятор Intel C++ и визуальный компилятор C++. Пожалуйста, предложите процессор с хорошей производительностью, чтобы выполнить такую ​​работу.

Answer 1

На яблочного звоном, я попробовал:

• с помощью __restict__ на аргументы, чтобы убедить компилятор, что не было никакого сглаживания.

Результат: без изменений

• распределения вычислений по 8 потоков в foo()

результат: вычисление времени увеличилось от ~ 3 секунд до ~ 18seconds!

• использования #pragma omp parallel for

результата: компилятор проигнорировал меня и остался с оригинальным решением. ~ 3 секунды.

• установки опции командной строки -march=native разрешить полный обалденный КПУ блестеть

результат: другой вывод ассемблера (векторизация применяется), но во время выполнения все еще без изменений на уровне ~ 3s

первоначальные выводы :

Эта проблема связана с доступом к памяти, а не с CPU.

Answer 2

Я думаю, вы должны использовать многопоточность. измените foo, чтобы получить fromIndex, toIndex, вместо n и распределить векторы по потокам.

void foo(int fromIndex, int toIndex, double* a, double* b, double *c, double*d, double* e, double* f, double* g) 
{ 
    for (int i = fromIndex; i < toIndex; ++i) 
     a[i] = b[i] * a[i] + c[i] * (d[i] + e[i] + f[i] + g[i]); 
} 

Answer 3

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

В C вы должны указывать указатели как «const double * restrict», за исключением того, что будет двойным * ограничением, сообщая компилятору, что все указатели, кроме первого, указывают на данные, которые не будут изменены во время петля; это позволяет компилятору векторизовать. Не функция C++, к сожалению, afaik.

Если бы это была ваша реальная проблема, вы бы просто поменять местами внутреннюю и внешнюю петлю, и удалить инварианты цикла, как это:

void foo(int iter, int n, double* a, double* b, double *c, double*d, double* e, double* f, double* g) 
{ 
    for (int i = 0; i < n; ++i) { 
     double xa = a [i]; 
     double xb = b [i]; 
     double xr = c[i] * (d[i] + e[i] + f[i] + g[i]); 

     for (int j = 0; j < iter; ++j) 
      xa = xb * xa + xr; 

     a [i] = xa; 
    } 
} 

Вы бы, наверное, четыре итерации параллельно, чтобы избежать задержек.

Но в реальной ситуации вы заметили, что в каждом вызове вы читаете около 40 МБ, что выходит за пределы кеша. Таким образом, вы ограничены скоростью ОЗУ. Обычным решением является разделение работы на более мелкие части, например 500 элементов за раз, поэтому все вписывается в кеш L1, а затем выполняет операцию с теми же данными 1000 раз.

Answer 4

Вы можете поэкспериментировать с предварительной выборкой векторов в строках кеша, а затем работать с ними в кусках 8 (8 двухместных номеров будут вписываться в каждую строку кеша).

Убедитесь, что во время работы с x [i] до x [i + 7] вы предварительно устанавливаете x [i + 8] на x [i + 15].

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