整数除算の最適化MSVC C++

Question

私はコードの一部のCPU使用量を削減しようとしていますが、CPU消費量の40％を占めています。その部分は次のとおりです。

void CalibrationFunction(cv::Mat* pMatSrc, cv::Mat* pMatDst, 
         cv::Mat* pBlack, cv::Mat* pWhite, INT32 nRadioFactor) 
{ 
    if (pMatSrc && pMatDst && pMatSrc->data && pMatDst->data) 
    {  
    for (int i = 0; i < pMatSrc->size[0]; i++) 
    { 
     UINT16* pBlackVal = (UINT16*)(pBlack->data + i*pBlack->step[0]); 
     UINT16* pWhiteVal = (UINT16*)(pWhite->data + i*pWhite->step[0]); 
     UINT16* pData = (UINT16*)(pMatSrc->data + i*pMatSrc->step[0]); 
     INT32 nDif; 
     UINT16 un16Value; 
     for (int j = 0; j < pMatSrc->size[1]; j++) 
     { 
     nDif = (*pData) - (*pBlackVal); 
     un16Value = (UINT16)min(65535, (max(0, nDif) * nRadioFactor/max(1, (*pWhiteVal)))); 
     pBlackVal++; 
     pWhiteVal++; 
     pData++; 

     int i0 = 0, i1 = j, i2 = i; 
     *(UINT16*)(pMatDst->data + i0 * pMatDst->step[0] + i1 * pMatDst->step[1] + i2 * pMatDst->step[2]) = un16Value; 
     } 
    } 
    } 
} 

マルチスレッドはすでに実装されています.8スレッドが使用されています。

私は整数演算でSIMDを見ましたが、整数除算があるので、これは進める方法ではないようです。私は最適化された整数除算ライブラリを調べましたが、すべての整数が同じ分母で除算されている場合にのみ有効であるように見えますが、ここではそうではありません。

誰かがリードするつもりはありますか？私は非常にエキゾチックなソリューション（別の言語でコードをコンパイルし、現在のソリューションから呼び出すなど）を開いていますが、唯一の制限はMSVCコンパイラを使用してMSVCプロジェクトを維持することです。

IntelはSMIDで整数部を実装していますが、このコードをIntelコンパイラでコンパイルし、現行のソリューション（Intelコンパイラを使用しています）から生成したバイナリを呼び出す必要があります。私のコンピュータ上でのみ動作し、私の意見では、 "あまりにもカスタム"です。私は最終的にしかし、SIMDを使用するために管理

EDIT

。そのトリックは、分割のために、16ビットの8つの整数のベクトルを32ビットの4つの浮動小数点の2つのベクトルにキャストすることでした。そして、SIMDで浮動小数点を分割する関数があるので、分割することができました。除算後、16ビットの整数結果を得るために再作成します。 SIMDを使用する新しい機能は6倍高速ですが、これで十分です。私のソリューションのこの部分が再びボトルネックになった場合に役立つ可能性があるので、皆さんの発言を心に留めておきます。

EDIT 2

要求されたとして、ここに新しいコードは次のとおりです。

void CalibrationRadioSIMD(UINT16* pBlackVal, UINT16* pWhiteVal, UINT16* pData, UINT16* pResult, int size, int nRadioFactor = 2) 
{ 

    for (int hop = 0; hop < 100; hop++) { 
     UINT16* pResultTmp = pResult; 
     UINT16* pDataTmp = pData; 
     UINT16* pBlackValTmp = pBlackVal; 
     UINT16* pWhiteValTmp = pWhiteVal; 
     __m128i radio; 

     radio.m128i_i32[0] = nRadioFactor; 
     radio.m128i_i32[1] = nRadioFactor; 
     radio.m128i_i32[2] = nRadioFactor; 
     radio.m128i_i32[3] = nRadioFactor; 
     for (int j = 0; j < size/8; j++) 
     { 
      // 
      // nDif = max(0, (*pData) - (*pBlackVal)); 
      // 
      // 1/ Loads 128-bit value 
      // Address p must be 16-byte aligned. 
      // For the unaligned version, see _mm_loadu_si128. 
      __m128i reg_a = _mm_load_si128((__m128i*)pDataTmp); 
      __m128i reg_B = _mm_load_si128((__m128i*)pBlackValTmp); 
      __m128i reg_white = _mm_load_si128((__m128i*)pWhiteValTmp); 
      pDataTmp += 8; 
      pBlackValTmp += 8; 
      pWhiteValTmp += 8; 

      // 2/ Subtracts the 8 unsigned 16-bit integers of b from the 8 unsigned 16-bit integers of a and saturates. 
      __m128i reg_diff = _mm_subs_epu16(reg_a, reg_B); 


      ///////////////////////////////////////////////////////////////////////////// 

      // unpack your vector of 8 x 16 bit unsigned shorts into two vectors of 32 bit unsigned ints, : 
      __m128i xlo = _mm_unpacklo_epi16(reg_diff, _mm_set1_epi16(0)); 
      __m128i xhi = _mm_unpackhi_epi16(reg_diff, _mm_set1_epi16(0)); 

      // This instruction multiplies two sets of 32-bit signed integers. 
      __m128i mullo = _mm_mullo_epi32(xlo, radio); 
      __m128i mulhi = _mm_mullo_epi32(xhi, radio); 

      // convert each of these vectors to float 
      __m128 ylo = _mm_cvtepi32_ps(mullo); 
      __m128 yhi = _mm_cvtepi32_ps(mulhi); 


      // Meme question que pour xlo et xhi 
      __m128i i32_whitelo = _mm_unpacklo_epi16(reg_white, _mm_set1_epi16(0)); 
      __m128i i32_whitehi = _mm_unpackhi_epi16(reg_white, _mm_set1_epi16(0)); 

      __m128 f32_white_lo = _mm_cvtepi32_ps(i32_whitelo); 
      __m128 f32_white_hi = _mm_cvtepi32_ps(i32_whitehi); 

      __m128 f32_res_lo = _mm_div_ps(ylo, f32_white_lo); 
      __m128 f32_res_hi = _mm_div_ps(yhi, f32_white_hi); 

      // Reconvertir en entier 16 bits 

      __m128i n32_res_lo = _mm_cvtps_epi32(f32_res_lo); 
      __m128i n32_res_hi = _mm_cvtps_epi32(f32_res_hi); 

      // Put result into result vector 
      UINT16* f32_res_lo_i16 = (UINT16*)&n32_res_lo; 
      UINT16* f32_res_hi_i16 = (UINT16*)&n32_res_hi; 
      int l = 0; 
      for (int k = 0; k < 4; k++) { 
       *(pResultTmp + k + 0) = *(f32_res_lo_i16 + l); 
       *(pResultTmp + k + 4) = *(f32_res_hi_i16 + l); 
       l += 2; 
      } 
      pResultTmp += 8; 

     } 
    } 
} 

Answer 1

あなたはそのための逆（私は逆数を意味する）テーブルを作成することができます。多少の不正確さを許すなら、このテーブルは128kに収まるでしょう。 L1キャッシュには適合しません。したがって、パフォーマンスを最大化するためにプリフェッチする必要があるかもしれません。 SIMDを使用すると、このソリューションは現在のソリューションよりも速くなければなりません。

白いイメージが一定している場合（同じ白いイメージでCalibrationFunctionを複数回呼び出すと）、前に反転することができるので、逆のテーブルは必要ありません。さらに速く

Answer 2

メモリ関連のパフォーマンス上の問題が解消されるまで、SIMDルートを停止することはお勧めしません。

私が意味することは、コードを見れば、計算ではなくメモリ上の不必要な待機によってコードのパフォーマンスが制限される可能性があるということです。

ベンチマーク

まず第一に、あなたのコードのベンチマークの再現可能な方法を確立します。私は、CPU時間の40％を使っていると考えているので、すでにこれを行っていると仮定しています。このコードのランタイムを測定し、それ以外は何もせず、5回行い、最速の時間を記録します。それは5つの価値の最高のものです。

ランタイムを測定するためのNベストアプローチは、コンピュータで起こっているランダムな他の事象によって引き起こされる減速という前提のもとでは良好です。これは、例えばバックグラウンド作業を行う他のプログラムでもよい。そのアイデアは、記録する最速のランタイムが、ランダムな外部ノイズの影響を最も受けないことです。

ヘルプコンパイラ

次のステップは、メモリを移動するような単純なコード変換はループである必要はないループの外側に読み出し実行することです。これを過度に使うように聞こえ、コンパイラが理解できるように思えるかもしれません。実際、コンパイラはしばしばそうではありません。私は何を意味

がキャッシュから追い出さすることができ、データへのポインタを追いかけるだろう任意のコードを生成を回避するために、この

// Before first loop: 
UINT16* blackData = (UINT16*) pBlack->data; 
yourType blackStep = (yourType) pBlack->step[0]; 

... 

UINT16* pBlackVal = (UINT16*)(blackData + i*blackStep); 

にこの

UINT16* pBlackVal = (UINT16*)(pBlack->data + i*pBlack->step[0]); 

のようにコードを変更することです。同じことがpMatSrc->size[0]とpWhite->step[0]などになります。特に(*pData)の場合はnDif = (*pData) - (*pBlackVal);になります。

パフォーマンスの影響を受けやすいコードの一般的な推奨事項です。特に、メモリの読み書きに関しては、コンパイラが問題を解決することを盲目的に想定していません。

postfixの代わりに接頭辞表記を使用して変数を増分すると、ヘルプが表示されますが、ここではコンパイラが十分にスマートであると思われます。しかし、それはなぜチャンスですか？その理由は、接頭辞を使用する場合は、変数の前の値を記憶する必要がないからです。接頭辞の増分表記は、後ではなく使用できるように値を増やすためです。私はここでもやっかいすぎるかもしれない。 :)

これらの変換が役立つかどうかを判断するために、ツールを使用してキャッシュミスを検査できます。例えば、https://msdn.microsoft.com/en-us/library/bb385772.aspxを参照してください。

記憶パターン

次に、私はあなたがそれをよりキャッシュフレンドリーになるだろうな方法でメモリにデータを保存することができるかどうかを確認するためにあなたのメモリリードパターンに目を通すことをお勧めします。

マトリックスで効果的に2D配列を処理しているので、最初に気になるのは、データのレイアウトに合わせて行列を反復しなければならないということです。そうしないと、パフォーマンスが損なわれます。私は何を意味

あなたは行列

a b c 
d e f 
g h i 

メモリ内のこのような

abcdefghi 

を保存する場合は、すべての反復処理、つまり、あなたはこの

for r in [0, rowLength-1] 
    for c in [0, columnLength-1] 
     // do thing with data[rowLength * r + c] here 

のように繰り返すべきであるということです次の行にスキップする前に行内の列を削除します。あなたが周りにそれを行う場合、あなたはプログラムが超低速で実行されます。

これを既に行っているかどうかは不明です。それはpMatDst->step[1]とpMatDst->step[2]の値に依存します。内側のループが配列を通って可能な最短距離をジャンプすることを確認してください。pMatDst->step[1]はpMatDst->step[2]よりはるかに小さくなります。

あなたがしたいのは、メモリを直線的に読み取ることです。コンピュータのメモリシステムは、データをプリフェッチしてキャッシュすることで高速化が可能です。あなたがそれを手伝うことができれば、最高の記憶は全く読まないことです。また、それを読んだ後に、何か別のもので何かをしなければならないことをやり直してください。

リンク

メモリの使用とレイアウトがパフォーマンスにどのような影響を与えるかについての詳細を学ぶために、私は、プレゼンテーション（これはhttp://harmful.cat-v.org/software/OO_programming/_pdf/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdfを作品願っています）「オブジェクト指向プログラミングの落とし穴」を読んでお勧めします。

また、もう少し具体的ではありませんが、CppCon https://www.youtube.com/watch?v=rX0ItVEVjHcのデータ指向設計に関するMike Actonの講演もあります。