Оптимизация 1D свертки

Question

Есть ли способ ускорить эту 1D свертку? Я пытался сделать кэш DY эффективным но компиляция с g ++ и -O3 дала худшие результаты.

Я сворачиваюсь с [-1. , 0., 1] в обоих направлениях. Это не домашнее задание.

#include<iostream>
#include<cstdlib>
#include<sys/time.h>

void print_matrix( int height, int width, float *matrix){
    for (int j=0; j < height; j++){
      for (int i=0; i < width; i++){
        std::cout << matrix[j * width + i] << ",";
    }
      std::cout << std::endl;
  }
}

void fill_matrix( int height, int width,  float *matrix){
    for (int j=0; j < height; j++){
      for (int i=0; i < width; i++){
        matrix[j * width + i] = ((float)rand() / (float)RAND_MAX) ;
    }
  }
}

#define RESTRICT __restrict__

void dx_matrix( int height, int width, float * RESTRICT in_matrix,  float * RESTRICT out_matrix, float *min, float *max){
  //init min,max
  *min = *max = -1.F * in_matrix[0] + in_matrix[1]; 

    for (int j=0; j < height; j++){
      float* row = in_matrix + j * width;
      for (int i=1; i < width-1; i++){
        float res = -1.F * row[i-1] + row[i+1]; /* -1.F * value + 0.F * value + 1.F * value; */ 
        if (res > *max ) *max = res;
        if (res < *min ) *min = res;
        out_matrix[j * width + i] = res;
      }
    }
}

void dy_matrix( int height, int width, float * RESTRICT in_matrix,  float * RESTRICT out_matrix, float *min, float *max){
  //init min,max
  *min = *max = -1.F * in_matrix[0] + in_matrix[ width + 1]; 

  for (int j=1; j < height-1; j++){
      for (int i=0; i < width; i++){
        float res = -1.F * in_matrix[ (j-1) * width + i] + in_matrix[ (j+1) * width + i] ;
        if (res > *max ) *max = res;
        if (res < *min ) *min = res;
        out_matrix[j * width + i] =  res;
      }
    }
}

double now (void)                                                                                          
{                                                                                                                    
  struct timeval tv;                                                                                               
  gettimeofday(&tv, NULL);                                                                                         
  return (double)tv.tv_sec + (double)tv.tv_usec / 1000000.0;
}


int main(int argc, char **argv){

  int width, height;
  float *in_matrix;
  float *out_matrix;

  if(argc < 3){
    std::cout  << argv[0] << "usage: width height " << std::endl;
    return -1;
  }

  srand(123);

  width = atoi(argv[1]);
  height = atoi(argv[2]);

  std::cout << "Width:"<< width << " Height:" << height << std::endl;

  if (width < 3){
    std::cout << "Width too short " << std::endl;
    return -1;
  }
  if (height < 3){
    std::cout << "Height too short " << std::endl;
    return -1;
  }

  in_matrix = (float *) malloc( height * width * sizeof(float));
  out_matrix = (float *) malloc( height * width * sizeof(float));

  fill_matrix(height, width, in_matrix);
  //print_matrix(height, width, in_matrix);

  float min, max;

  double a = now();
  dx_matrix(height, width, in_matrix, out_matrix, &min, &max);
  std::cout << "dx min:" << min << " max:" << max << std::endl;

  dy_matrix(height, width, in_matrix, out_matrix, &min, &max);
  double b = now();
  std::cout << "dy min:" << min << " max:" << max << std::endl;
  std::cout << "time: " << b-a << " sec" << std::endl;


  return 0;
}

Answer 1

Используйте локальные переменные для вычисления мин и макс. Каждый раз, когда вы делаете это:

if (res > *max ) *max = res;
if (res < *min ) *min = res;

Макс и мин должны быть записаны в память. Добавление restrict к указателям помогло бы (указав, что записи независимы), но еще лучше было бы что-то вроде

//Setup
float tempMin = ...
float tempMax = ...
...
    // Inner loop
    tempMin = (res < tempMin) ? res : tempMin;
    tempMax = (res > tempMax) ? res : tempMax;
...
// End
*min = tempMin;
*max = tempMax;

Answer 2

Профилируя это с -O3 и -O2, используя версии компиляторов clang и g ++ на OS X, я обнаружил, что

30% времени было потрачено на заполнение исходной матрицы

  matrix[j * width + i] = ((float)rand() / (float)RAND_MAX) ;

40% времени было потрачено в строке dx_matrix.

  out_matrix[j * width + i] = row[i+1] -row[i-1];

Около 9% времени было потрачено в условных выражениях в dx_matrix. Я разделил их на отдельный цикл, чтобы посмотреть,это помогло, но ничего не изменило.

Акула высказала предположение, что это можно улучшить с помощью инструкций SSE.

Интересно, что было потрачено только около 19% временив подпрограмме dy_matrix.

Это выполнялось на матрице 10k на 10k (около 1,6 секунды)

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

Answer 3

Прежде всего, я бы переписал цикл dy, чтобы избавиться от "[(j-1) * width + i]" и "in_matrix [(j + 1) * width + i]", и сделал бы что-то вроде:

  float* p, *q, *out;
 p = &in_matrix[(j-1)*width];
 q = &in_matrix[(j+1)*width];
 out = &out_matrix[j*width];
  for (int i=0; i < width; i++){ 
        float res = -1.F * p[i] + q[i] ; 
        if (res > *max ) *max = res; 
        if (res < *min ) *min = res; 
        out[i] =  res; 
      } 

Но это тривиальная оптимизация, которую компилятор, возможно, уже делает для вас.

Это будет немного быстрее выполнить "q [i] -p [i]"вместо «-1.f * p [i] + q [i]», но, опять же, компилятор может быть достаточно умен, чтобы сделать это за вашей спиной.

Все это значительно выиграет от SSE2и многопоточность.Я бы сразу сделал ставку на 3-кратное ускорение от SSE2.Многопоточность может быть добавлена ​​с использованием OpenMP и займет всего несколько строк кода.

Answer 4

Компилятор может заметить это, но вы создаете / освобождаете много переменных в стеке, когда входите и выходите из операторов области видимости {}.Вместо:

for (int j=0; j < height; j++){ 
      float* row = in_matrix + j * width; 
      for (int i=1; i < width-1; i++){ 
        float res = -1.F * row[i-1] + row[i+1];

Как насчет:

int i, j;
float *row;
float res;

for (j=0; j < height; j++){ 
      row = in_matrix + j * width; 
      for (i=1; i < width-1; i++){ 
        res = -1.F * row[i-1] + row[i+1];

Answer 5

Что ж, об этом может позаботиться компилятор, но вот пара небольших вещей:

а) Почему вы умножаете на -1.F? Почему бы просто не вычесть? Например:

float res = -1.F * row[i-1] + row[i+1];

может быть просто:

float res = row[i+1] - row[i-1];

б) Это:

if (res > *max ) *max = res;
if (res < *min ) *min = res;

можно превратить в

if (res > *max ) *max = res;
else if (res < *min ) *min = res;

и в других местах. Если первое верно, второе не может быть, поэтому давайте не будем проверять это.

Дополнительно:

Вот еще одна вещь. Чтобы минимизировать умножения, измените

for (int j=1; j < height-1; j++){
  for (int i=0; i < width; i++){
    float res = -1.F * in_matrix[ (j-1) * width + i] + in_matrix[ (j+1) * width + i] ;

до

int h = 0;
int width2 = 2 * width;
for (int j=1; j < height-1; j++){
  h += width;
  for (int i=h; i < h + width; i++){
    float res = in_matrix[i + width2] - in_matrix[i];

и в конце цикла

    out_matrix[i + width] =  res;

Вы можете делать подобные вещи в других местах, но, надеюсь, вы поняли идею. Также есть небольшая ошибка,

*min = *max = -1.F * in_matrix[0] + in_matrix[ width + 1 ];

должно быть просто in_matrix[ width ] в конце.