3

非常に非効率的なプログラムが与えられ、コードを最適化して実行速度を上げる必要があるという課題があります。これらの 2 つを除いて、私はそれらのほとんどを非常に高速に実行しています。1 つは基本的に 2 次元配列のすべての値を同じ値に設定し、もう 1 つは基本的に 2 つの 2 次元配列の値を交換します。そして、それが問題です。それらは最も多くの時間を占めていますが、非常に単純であるため、関数を壊さずにそれらを削減する方法がわかりません。そして、クラスの他の学生が途方もないスピードアップを得ているので、それらをより速く走らせることが可能であることを私は知っています. 問題の2つは次のとおりです。

fSetArray(int rows, int cols, float val)
{
    int i, j;
    F2D *out;
    out = fMallocHandle(rows, cols);

    for(i=0; i<rows; i++)
    for(j=0; j<cols; j++)
        subsref(out,i,j) = val;

    return out;

}

唯一の重要な部分は、そこにある 2 つのループです。基本的に、特定の幅 (行) と特定の高さ (列) を持つ 2 次元配列があり、すべての値を val に設定しています。しかし、ループの 1 つを排除する方法はありません (ループを高速化するには、これが最善の方法です)。明らかな何かが欠けていない限り。列と行が同じ数である場合、これは非常に簡単になります。

他の機能は次のとおりです。

fDeepCopy(F2D* in)
{
    int i, j;
    F2D* out;
    int rows, cols;

    rows = in->height;
    cols = in->width;

    out = fMallocHandle(rows, cols);

    for(i=0; i<rows; i++)
    for(j=0; j<cols; j++)
        subsref(out,i,j) = subsref(in,i,j);

    return out;
}

out 配列は常に in 配列よりも大きいため、オーバーフローなどを心配する必要はありません。この関数は基本的には 2 つの配列の値を交換するだけですが、これも非常に単純であるため、これ以上減らすことはできません。

そして、誰かが並列化と言う前に、サンプルのサイズとサーバーのために、スレッドを作成するために必要なオーバーヘッドが実際にプログラムを遅くします。私はもう試した。これら 2 つの関数は短すぎるため、スレッドを作成して、1 つの並列処理の後でスレッドを強制終了するだけの価値はありません。

しかし参考までに、これは技術的には OpenMP プロジェクトであり、並列化を使用することになっていますが、これら 2 つの関数については、実際にはプログラム全体の速度が低下します。チェックするために並列 for ループでタイミングを計りました。

編集: アイデアをくれた皆さん、ありがとうございました! 私はそれを起動して実行し、今フルスピードです！

4

2 に答える 2

1

最適化の1つのタイプは、ループ展開です。インデックスの取得、更新、メモリへの保存に関して多くのアクティビティが発生するため、パイプラインが停止する必要がある場合があります。これがおそらくマルチスレッドの実装がうまくいかなかった主な理由であり、すべてのスレッドがおそらくインデックスへのアクセスをめぐって争っていました。

マルチスレッドの実装を再試行する場合は、スレッド数に基づいて「オフセット」であることを各スレッドに認識させ、モジュラス除算によって検出された異なる剰余を各スレッドに処理させます。

thread 0 works on i*rows+j % (thread count) = 0
thread 1 works on i*rows+j % (thread count) = 1
(and so on)

マルチスレッドの実装を再試行したくない場合でも、パフォーマンスを向上させることができるいくつかの手法があります。場合によっては、単一のスレッドでさえ、インデックス変数で不必要にストールする可能性があります（プロセッサパイプラインの非効率的な使用を引き起こすため）。このタイプの問題の修正を試みるには、インデックスを特定の数だけインクリメントし、ループ内でその回数だけメソッドを呼び出します。

fDeepCopy(F2D* in)
{
    int i, j;
    F2D* out;
    int rows, cols;

    rows = in->height;
    cols = in->width;

    out = fMallocHandle(rows, cols);

    for(i=0; i<rows; i++) {
      // rewrite to ensure we don't walk off "4 long" pads
      int j = 0;
      int pads = (cols / 4)*4;
      for(; j < pads; j = j + 4) {
        subsref(out,i,j) = subsref(in,i,j);
        subsref(out,i,j+1) = subsref(in,i,j+1);
        subsref(out,i,j+2) = subsref(in,i,j+2);
        subsref(out,i,j+3) = subsref(in,i,j+3);
      }
      // process the remainders
      for(; j < pads; j++) {
        subsref(out,i,j) = subsref(in,i,j);
      }
    }
    return out;
}

現在CPU設計者は良くなっているので、実際に実行のプロファイルを作成して、CPUが既にそのような最適化を行っているかどうかを判断することが重要です。そうしないと、そのような手法によってコードが実際に遅くなる可能性があります。

最後に、SSE拡張命令を活用することもできます。これは、適切な条件下で、すべてMMXレジスタに格納されている複数の値に対して同じ操作を実行できます。たとえば、アセンブリのインライン化を使用して、4つの32ビット単精度浮動小数点数の2つのセットをMMXレジスタにパックし、一度に4つの浮動小数点を一括で加算することができます。

だから、

vec_res.x = v1.x + v2.x;
vec_res.y = v1.y + v2.y;
vec_res.z = v1.z + v2.z;
vec_res.w = v1.w + v2.w;

これには、8つのメモリルックアップ、4つの追加、および4つのストア（最適化されていない16の操作）が必要になります。

movaps xmm0, [v1]          ;xmm0 = v1.w | v1.z | v1.y | v1.x 
addps xmm0, [v2]           ;xmm0 = v1.w+v2.w | v1.z+v2.z | v1.y+v2.y | v1.x+v2.x               
movaps [vec_res], xmm0

これは、最適化されていない3つの操作のみを必要とします。

ここでも重要なのはプロファイリングであるため、ボトルネックを検出し、コードを調整して、許容できる最小限のパフォーマンスの範囲内に収めることができます。

于 2012-05-24T15:24:38.533 に答える
0

memset最初の機能に役立つはずです。

于 2012-05-24T14:49:09.987 に答える