1

有没有办法加速这个一维卷积？我试图提高 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;
}
4

5 回答 5

2

使用局部变量来计算最小值和最大值。每次你这样做：

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

max 和 min 必须写入内存。在指针上添加限制会有所帮助（表明写入是独立的），但更好的方法是

//Setup
float tempMin = ...
float tempMax = ...
...
    // Inner loop
    tempMin = (res < tempMin) ? res : tempMin;
    tempMax = (res > tempMax) ? res : tempMax;
...
// End
*min = tempMin;
*max = tempMax;
于 2010-10-08T06:40:32.677 回答
1

好吧，编译器可能会处理这些问题，但这里有一些小事情：

a) 为什么要乘以 -1.F？为什么不直接减去？例如：

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

可能只是：

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

b) 这：

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 ]在最后。

于 2010-10-08T00:22:14.947 回答
1

首先，我会重写 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 和多线程中受益匪浅。我敢打赌，SSE2 的速度至少会提高 3 倍。可以使用 OpenMP 添加多线程，并且只需要几行代码。

于 2010-10-08T00:23:22.933 回答
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];

怎么样：

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];
于 2010-10-08T00:35:52.790 回答
1

使用 OS X 上的 clang 和 g++ 编译器版本使用 -O3 和 -O2 对此进行分析，我发现

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 中的条件句上。我将它们分成一个单独的循环，看看是否有帮助，但它并没有改变太多。

Shark 建议可以通过使用 SSE 指令来改进这一点。

有趣的是，只有大约 19% 的时间花在 dy_matrix 例程上。

这是在 10k x 10k 矩阵上运行的（大约 1.6 秒）

请注意，如果您使用不同的编译器、不同的操作系统等，您的结果可能会有所不同。

于 2010-10-08T07:26:09.647 回答