оптимизировать алгоритм MSE с использованием OpenMP

Question

Я хотел оптимизировать ниже кода с использованием OpenMP

double val; 
double m_y = 0.0f; 
double m_u = 0.0f; 
double m_v = 0.0f; 

#define _MSE(m, t) \ 
val = refData[t] - calData[t]; \ 
m += val*val; 

#pragma omp parallel 
{ 
#pragma omp for 
for(i=0; i<(width*height)/2; i++) { //yuv422: 2 pixels at a time 
    _MSE(m_u, 0); 
    _MSE(m_y, 1); 
    _MSE(m_v, 2); 
    _MSE(m_y, 3); 

    #pragma omp reduction(+:refData) reduction(+:calData) 
    refData += 4; 
    calData += 4; 
// int id = omp_get_thread_num(); 
//printf("Thread %d performed %d iterations of the loop\n",id ,i); 
} 

} 

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

Answer 1

Я думаю, что самое легкое, что вы можете сделать, это разрешить его разбиение на 4 потока и вычислить ошибки UYVY в каждом из них. Вместо того, чтобы их отдельные значения, сделать их массив:

double sqError[4] = {0}; 
const int numBytes = width * height * 2; 

#pragma omp parallel for 
for(int elem = 0; elem < 4; elem++) { 
    for(int i = elem; i < numBytes; i += 4) { 
     int val = refData[i] - calData[i]; 
     sqError[elem] += (double)(val*val); 
    } 
} 

Таким образом, каждый поток работает исключительно на одном и нет никаких разногласий.

Возможно, это не самое продвинутое использование OMP, но вы должны увидеть ускорение.

---

После вашего комментария об ударе производительности я сделал несколько экспериментов и обнаружил, что производительность была еще хуже. Я подозреваю, что это может быть из-за промахов в кеше.

Вы сказали:

производительность удар на этот раз с OpenMP: Время: 0.040637 с последовательным Время: 0,018670

Так что я переработал его с помощью сокращения на каждой переменной и с помощью одного цикла :

#pragma omp parallel for reduction(+:e0) reduction(+:e1) reduction(+:e2) reduction(+:e3) 
    for(int i = 0; i < numBytes; i += 4) { 
     int val = refData[i] - calData[i]; 
     e0 += (double)(val*val); 
     val = refData[i+1] - calData[i+1]; 
     e1 += (double)(val*val); 
     val = refData[i+2] - calData[i+2]; 
     e2 += (double)(val*val); 
     val = refData[i+3] - calData[i+3]; 
     e3 += (double)(val*val); 
    } 

с моим теста на 4-ядерный машине, я заметил, немного меньше, чем 4-кратное улучшение:

serial:    2025 ms 
omp with 2 loops: 6850 ms 
omp with reduction: 455 ms 

---

[Редактировать] По вопросу о том, почему первая часть кода выполняется хуже, чем не-параллельной версии, Христо Илиев сказал:

Ваш первый кусок код - ужасный пример того, что ложное разделение делает в многопоточных кодах. Поскольку sqError имеет только 4 элемента по 8 байт каждый, он вписывается в одну строку кеша (даже в половине кэша на современных процессорах x86). С 4 потоками, постоянно записывающимися в соседние элементы , это создало бы огромное количество межядерных кешей недействительности из-за ложного обмена. Можно обойти это, используя вместо структуры, подобной этой структуре _error {double val; двойной накладка [7]; } sqError [4]; Теперь каждый sqError [i] .val будет в отдельной строке кеша , следовательно, не будет обмена ложью.

Answer 2

Код выглядит так, как будто он вычисляет MSE, но добавляет к той же сумме, m. Чтобы параллелизм работал правильно, вам необходимо устранить совместное использование m, один из подходов будет предубирать массив (ширина * высота/2, я думаю) только для хранения разных сумм, или m. Наконец, суммируем все суммы в конце.

Кроме того, проверьте, что это на самом деле быстрее!