1

この 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;
}
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

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 命令を使用することでこれを改善できると提案しました。

興味深いことに、dy_matrix ルーチンで費やされた時間はわずか約 19% でした。

これは 10k x 10k のマトリックスで実行されていました (約 1.6 秒)。

別のコンパイラ、別の OS などを使用している場合、結果が異なる場合があることに注意してください。

于 2010-10-08T07:26:09.647 に答える
1

まず、「[ (j-1) * width + i]」と「in_matrix[ (j+1) * width + i]」を取り除くために dy ループを書き直して、次のようにします。

  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; 
      }

しかし、それはコンパイラがすでに行っているかもしれない簡単な最適化です。

「-1.f*p[i]+q[i]」の代わりに「q[i]-p[i]」を実行する方がわずかに高速ですが、コンパイラはそれを行うのに十分賢いかもしれませんあなたの後ろに。

全体として、SSE2 とマルチスレッドからかなりのメリットが得られます。私は、SSE2 から少なくとも 3 倍のスピードアップにすぐに賭けます。マルチスレッドは OpenMP を使用して追加でき、数行のコードしか必要ありません。

于 2010-10-08T00:23:22.933 に答える
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

コンパイラはこれに気付くかもしれませんが、スコープ演算子 {} に出入りするときに、スタック上で多くの変数を作成/解放しています。それ以外の：

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 に答える