大量の配列に関連する計算のスピードアップVisual Studio

Question

多量の配列計算を高速化するための最良のアプローチが何であるか疑問に思っています。もちろん

int template_t[] = {1, 2, 3, 4, 5, 6, ...., 125}; 
int image[3200][5600]; 
int template_image[3200][5600]; 

for(int i = 0; i < 3200; i++) { 
    for(int j = 0; j < 5600; j++) { 

     // iterate over template to find template value per pixel 
     for(int h = 0; h < template_length; h++) 
      template_image[i][j] += template_t[h] * image[i][j]; 

    } 
} 

私の状況ははるかに複雑ですが、同じ考え方が適用されます。私はこのシナリオを考えてみましょう。私はイメージ内のピクセルを表す大きな配列をいくつか持っており、テンプレートイメージに配置する値を計算するために、各ピクセルにいくつかのテンプレート配列を適用する必要があります。

私はこれをスピードアップするカップルの方法について考えた：

• SIMD命令？しかし、私はVisual StudioでSIMD固有のコードを書くためのリソースを見つけることができないようです。
• パラレル化 - 私はすでに実行自体をパラレル化しているので、プログラムはXコアに基づいて自身のXインスタンスを実行します。プログラムの入力は大量の画像ファイルなので、これらのXインスタンスはすべて別々のファイルを処理します。

私の負担のために私に最も魅力的なものは何ですか？何か提案ありがとう！

Answer 1

一つの簡単な最適化、コンパイラはすでにあなたのため、だろうかべきではないこと：

int p = template_image[i][j], p2= image[i][j]; 
    // iterate over template to find template value per pixel 
    for(int h = 0; h < template_length; h++) 
     p += template_t[h] * p2; 

    template[i][j]= p; 

これをさらに見て、1、2、3、あなたのテンプレートの定義、... 125、次いでp2が一定である1 * 2 * 3 * 4 .. * 125で乗算されるように（米国CTそれを呼ぼう）と：

for (h.. 
    template_image[i][j] += template_t[h] * image[i][j]; 

template_image[i][j] += CT * image[i][j]; 

と等価です

ので、アルゴリズムは次のようになる。

#define CT 1*2*3*4*5*6*7...*125 // must stil lbe completed 
int image[3200][5600]; 
int template_image[3200][5600]; 

for(int i = 0; i < 3200; i++) { 
    for(int j = 0; j < 5600; j++) { 
     template_image[i][j] += CT * image[i][j]; 
    } 
} 

これはj上に並列化することができます。

Answer 2

まず、型ではなく配列では_tの名前を使用します。配列template_multipliers[]を呼んでみましょう。

がconstで、変数がunsignedの場合、コンパイラはコンパイル時にそれを合計して、内側のループを完全に最適化できます。

gccの場合、ループの外にtemplate_tの合計を吊り上げるより良いコードが得られます。この場合、unsigned intではなく、intとコンパイル時に合計することができます。

署名されたオーバーフローは未定義の動作です。これは、最適化されているターゲットマシンで実際に何が起きるかを把握していないことが原因です。 （例えば、x86上では避ける必要があるわけではありません。）一連の追加の最終結果は、一時的な結果で署名付きのオーバーフローを引き起こし、そうでないものがあっても操作の順序に依存しません。署名された場合には常に加算の結合性を利用する）。

これは純粋にgccの制限です。あなたのコードは、ソースレベルの操作の順序で符号付きオーバーフローを避けなければなりませんが、コンパイラが同じ結果を他の操作から得ることがわかっている場合、それはより高速です。

---

// aligning the arrays makes gcc's asm output *MUCH* shorter: no fully-unrolled prologue/epilogue for handling unaligned elements 
#define DIM1 320 
#define DIM2 1000 
alignas(32) unsigned int image[DIM1][DIM2]; 
alignas(32) unsigned int template_image[DIM1][DIM2]; 

// with const, gcc can sum them at compile time. 
const 
static unsigned int template_multipliers[] = {1, 2, 3, 4, 5, 6, 7, 8, 8, 10, 11, 12, 13, 125}; 
const static int template_length = sizeof(template_multipliers)/sizeof(template_multipliers[0]); 


void loop_hoisted(void) { 
    for(int i = 0; i < DIM1; i++) { 
    for(int j = 0; j < DIM2; j++) { 
     // iterate over template to find template value per pixel 
     unsigned int tmp = 0; 
     for(int h = 0; h < template_length; h++) 
      tmp += template_multipliers[h]; 
     template_image[i][j] += tmp * image[i][j]; 

    } 
    } 
} 

の内部ループと-O3 -fverbose-asm -march=haswellauto-vectorizes thisとGCC 5.3：

# gcc inner loop: ymm1 = set1(215) = sum of template_multipliers 
.L2: 
    vpmulld ymm0, ymm1, YMMWORD PTR [rcx+rax] # vect__16.10, tmp115, MEM[base: vectp_image.8_4, index: ivtmp.18_90, offset: 0B] 
    vpaddd ymm0, ymm0, YMMWORD PTR [rdx+rax] # vect__17.12, vect__16.10, MEM[base: vectp_template_image.5_84, index: ivtmp.18_90, offset: 0B] 
    vmovdqa YMMWORD PTR [rdx+rax], ymm0  # MEM[base: vectp_template_image.5_84, index: ivtmp.18_90, offset: 0B], vect__17.12 
    add  rax, 32 # ivtmp.18, 
    cmp  rax, 4000 # ivtmp.18, 
    jne  .L2  #, 

pmulldがハズウエルオン2つのuopであるので、これは、インテルハズウエルに内部ループ9融合ドメインのuopであります（1レジスタアドレッシングモードでもマイクロヒューズできません）。つまり、ループは3クロックごとに1回だけ実行できます。 gccは、宛先のポインタインクリメントを使用して2 uops（2クロックごとに1回の反復で実行される）を保存することができ、dst + src-dst 2レジスタのアドレス指定モード（これはマイクロヒューズできないため） 。

template_multipliersの合計を持たないOPのコードの修正されていないバージョンの完全なソースについては、godbolt Compiler Explorer linkを参照してください。それは奇妙なASMを作る：それはtemplate_multipliersの加算のいくつかのループを通るたびにやっている

unsigned int tmp = template_image[i][j]; 
    for(int h = 0; h < template_length; h++) 
     tmp += template_multipliers[h] * image[i][j]; 
    template_image[i][j] = tmp; 

.L8: # ymm4 is a vector of set1(198) 
    vmovdqa ymm2, YMMWORD PTR [rcx+rax]  # vect__22.42, MEM[base: vectp_image.41_73, index: ivtmp.56_108, offset: 0B] 
    vpaddd ymm1, ymm2, YMMWORD PTR [rdx+rax] # vect__1.47, vect__22.42, MEM[base: vectp_template_image.38_94, index: ivtmp.56_108, offset: 0B] 
    vpmulld ymm0, ymm2, ymm4 # vect__114.43, vect__22.42, tmp110 
    vpslld ymm3, ymm2, 3  # vect__72.45, vect__22.42, 
    vpaddd ymm0, ymm1, ymm0 # vect__2.48, vect__1.47, vect__114.43 
    vpaddd ymm0, ymm0, ymm3 # vect__29.49, vect__2.48, vect__72.45 
    vpaddd ymm0, ymm0, ymm3 # vect_tmp_115.50, vect__29.49, vect__72.45 
    vmovdqa YMMWORD PTR [rdx+rax], ymm0  # MEM[base: vectp_template_image.38_94, index: ivtmp.56_108, offset: 0B], vect_tmp_115.50 
    add  rax, 32 # ivtmp.56, 
    cmp  rax, 4000 # ivtmp.56, 
    jne  .L8  #, 

。ループ内の加算数は、配列内の値（値の数だけではなく）に応じて変化します。

---

プログラム全体のリンク時の最適化は、それがtemplate_multipliersは非constであっても、その後の和を行うことができますしない限り、これらの最適化のほとんどは、MSVCに適用可能であるべきです。