Я реализовал Summed Area Table (или Integral image) в C ++, используя OpenMP.
Проблема в том, что последовательный код всегда быстрее, чем параллельный код, даже при изменении количества потоков и размеров изображения.
Например, я пробовал изображения от (100x100) до (10000x10000) и потоки от 1 до 64, но ни одна из комбинаций никогда не бывает быстрее.
Я также пробовал этот код на разных машинах, таких как:
- Mac OSX, 1,4 ГГц, двухъядерный процессор Intel Core i5
- Mac OSX 2,3 ГГц четырехъядерный процессор Intel Core i7
- Ubuntu 16.04, Intel Xeon E5-2620, 2,4 ГГц, 12 ядер
Время было измерено с помощью функции OpenMP: omp_get_wtime().
Для компиляции я использую: g++ -fopenmp -Wall main.cpp.
Вот параллельный код:
void transpose(unsigned long *src, unsigned long *dst, const int N, const int M) {
#pragma omp parallel for
for(int n = 0; n<N*M; n++) {
int i = n/N;
int j = n%N;
dst[n] = src[M*j + i];
}
}
unsigned long * integralImageMP(uint8_t*x, int n, int m){
unsigned long * out = new unsigned long[n*m];
unsigned long * rows = new unsigned long[n*m];
#pragma omp parallel for
for (int i = 0; i < n; ++i)
{
rows[i*m] = x[i*m];
for (int j = 1; j < m; ++j)
{
rows[i*m + j] = x[i*m + j] + rows[i*m + j - 1];
}
}
transpose(rows, out, n, m);
#pragma omp parallel for
for (int i = 0; i < n; ++i)
{
rows[i*m] = out[i*m];
for (int j = 1; j < m; ++j)
{
rows[i*m + j] = out[i*m + j] + rows[i*m + j - 1];
}
}
transpose(rows, out, m, n);
delete [] rows;
return out;
}
Вот последовательный код:
unsigned long * integralImage(uint8_t*x, int n, int m){
unsigned long * out = new unsigned long[n*m];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
unsigned long val = x[i*m + j];
if (i>=1)
{
val += out[(i-1)*m + j];
if (j>=1)
{
val += out[i*m + j - 1] - out[(i-1)*m + j - 1];
}
} else {
if (j>=1)
{
val += out[i*m + j -1];
}
}
out[i*m + j] = val;
}
}
return out;
}
Я также пытался без transpose, но это было еще медленнее, вероятно, из-за доступа к кешу.
Пример кода вызова:
int main(int argc, char **argv){
uint8_t* image = //read image from file (gray scale)
int height = //height of the image
int width = //width of the image
double start_omp = omp_get_wtime();
unsigned long* integral_image_parallel = integralImageMP(image, height, width); //parallel
double end_omp = omp_get_wtime();
double time_tot = end_omp - start_omp;
std::cout << time_tot << std::endl;
start_omp = omp_get_wtime();
unsigned long* integral_image_serial = integralImage(image, height, width); //sequential
end_omp = omp_get_wtime();
time_tot = end_omp - start_omp;
std::cout << time_tot << std::endl;
return 0;
}
Каждый поток работает над блоком строк (может быть полезна иллюстрация того, что делает каждый поток):
Где ColumnSum выполняется транспонированием матрицы и повторением RowSum.