10

私は次の機能を持っています（オープンソースプロジェクト「recastnavigation」から）：

/// Derives the dot product of two vectors on the xz-plane. (@p u . @p v)
///  @param[in]     u       A vector [(x, y, z)]
///  @param[in]     v       A vector [(x, y, z)]
/// @return The dot product on the xz-plane.
///
/// The vectors are projected onto the xz-plane, so the y-values are ignored.
inline float dtVdot2D(const float* u, const float* v)
{
    return u[0]*v[0] + u[2]*v[2];
}

VS2010 CPUパフォーマンステストを実行したところ、この関数のすべてのリキャストコードベースコードラインでu[0]*v[0] + u[2]*v[2]CPUが最もホットであることがわかりました。

この行をCPUで最適化するにはどうすればよいですか（たとえば、GLMのようなSSEまたはGLSLを介して（このような場合に、より簡単または高速で適切な場合））？

編集：呼び出しが表示されるコンテキスト：

bool dtClosestHeightPointTriangle(const float* p, const float* a, const float* b, const float* c, float& h) {
    float v0[3], v1[3], v2[3];
    dtVsub(v0, c,a);
    dtVsub(v1, b,a);
    dtVsub(v2, p,a);

    const float dot00 = dtVdot2D(v0, v0);
    const float dot01 = dtVdot2D(v0, v1);
    const float dot02 = dtVdot2D(v0, v2);
    const float dot11 = dtVdot2D(v1, v1);
    const float dot12 = dtVdot2D(v1, v2);

    // Compute barycentric coordinates
    const float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
    const float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
    const float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
4

4 に答える 4

21

紙の上でいくつかのことを試した後、私はあなたのために働くかもしれない何かを思いついた。これは、SSEの関数の適切に並列化/ベクトル化された実装です。

ただし、一度に4つの三角形の並列処理を行うため、データの再編成が必要です。

私はそれを段階的に分割し、あちこちで命令名を使用しますが、C組み込み関数（_mm_load_ps（）、_ mm_sub_ps（）などを使用してください。これらはVCのxmmintrin.hにあります）-レジスタについて話すとき、これ単に__m128を意味します。

ステップ1。

Y座標はまったく必要ないため、XとZのペアへのポインターを設定します。呼び出しごとに少なくとも4つのペア（つまり、合計4つの三角形）を提供します。XとZの各ペアを頂点と呼びます。

ステップ2。

MOVAPS（ポインターを16ビットに揃える必要があります）を使用して、各ポインターが指す最初の2つの頂点をレジスターにロードします。

aからロードされたレジスタは次のようになります：[a0.x、a0.z、a1.x、a1.z]

ステップ3。

これで、1つの減算命令を使用して、2つの頂点のデルタ（ v0、v1、v2）を一度に計算できます。

最初の2つの三角形だけでなく、後の2つの三角形についてもv0、v1、v2を計算してください。私が言ったように、入力ごとに合計4つの頂点、つまり8つのフロートを指定する必要があります。そのデータに対して手順2と3を繰り返すだけです。

これで、 vxレジスタのペアが2つあり、各ペアには2つの三角形の結果が含まれています。これらをvx_0（最初のペア）およびvx_1（2番目のペア）と呼びます。ここで、xは0から2です。

ステップ4。

ドット積。重心計算（後で）を並列化するために、1つの単一レジスタ内の4つの三角形のそれぞれの各内積の結果が必要です。

たとえば、 dot01を計算する場合、同じことを行いますが、一度に4つの三角形に対して行います。各vレジスタには、2つのベクトルの結果が含まれているため、それらを乗算することから始めます。

uとv（ドット積関数のパラメーター）がv0_0とv1_0になっているとしましょう（ dot01の計算に関して）：

uとvを乗算して、次の値を取得します。 （v1_0.z1）]

これは、.x0 / .z0および.x1 / .z1のために混乱しているように見えるかもしれませんが、ステップ2でロードされたものを見てください：a0、a1。

それでもまだぼやけていると感じる場合は、一枚の紙を手に取り、最初から書き留めてください。

次に、同じ内積に対して、v0_1とv1_1（つまり、三角形の2番目のペア）の乗算を実行します。

これで、それぞれ2つのXとZのペア（合計4つの頂点）を持つ2つのレジスタがあり、乗算されて加算され、4つの個別の内積が形成されます。SSE3には、これを正確に実行するための命令があり、HADDPSと呼ばれます。

xmm0 = [A、B、C、D] xmm1 = [E、F、G、H]

HADDPS xmm0、xmm1はこれを行います：

xmm0 = [A + B、C + D、E + F、G + H]

最初のレジスタからXとZのペアを取得し、2番目のレジスタからそれらを取得し、それらを合計して、宛先レジスタの1番目、2番目、3番目、4番目のコンポーネントに格納します。エルゴ：この時点で、4つの三角形すべてにこの特定のドット積があります！

**ここで、すべてのドット積（dot00など）に対してこのプロセスを繰り返します。****

ステップ5。

最後の計算（提供されたコードで確認できる限り）は、重心の計算です。これは、コード内の100％スカラー計算です。ただし、入力はスカラードット積の結果（つまり、単一の浮動小数点数）ではなく、4つの三角形のそれぞれのドット積を持つSSEベクトル/レジスターです。

したがって、4つのフロートすべてで動作する並列SSE演算を使用してこれをフラット化すると、最終的には、三角形ごとに1つずつ、4つの高さを持つ1つのレジスタ（または結果）になります。

私の昼休みはかなり過ぎているので、これを詳しく説明するつもりはありませんが、私が与えたセットアップ/アイデアを考えると、これは最後のステップであり、理解するのは難しいことではありません。

このアイデアは少し難しいものであり、その上にあるコードからの愛情と、おそらく鉛筆と紙での質の高い時間を必要とすることを私は知っていますが、それは高速です（そして必要に応じて後でOpenMPを追加することもできます）。

幸運を ：）

（そして私のあいまいな説明を許してください、必要に応じて関数を作成することができます=））

アップデート

実装を作成しましたが、期待どおりに機能しませんでした。主な理由は、Yコンポーネントが、最初に質問に貼り付けたコードの一部を超えて関与したためです（調べました）。ここで行ったことは、すべてのポイントをXZペアに再配置して、4ごとにフィードするだけでなく、4つの三角形のそれぞれのY値を3つのポインター（ポイントA、B、C用）にフィードすることです。ローカルの観点からは、これが最速です。呼び出し先側からの邪魔にならない変更が必要になるように変更することはできますが、何が望ましいかを教えてください。

次に、免責事項：このコードは地獄のように単純です（SSEの観点からコンパイラーで非常にうまく機能することがわかりました...彼らは適切と思われるように再編成でき、x86 / x64 CPUもそのシェアを占めます）。また、ネーミング、それは私のスタイルではなく、誰のスタイルでもありません。あなたが適切だと思うものでそれを使ってください。

それがお役に立てば幸いです。そうでない場合は、もう一度喜んで説明します。そして、これが商業プロジェクトである場合、私を乗せるオプションもあります;）

とにかく、私はそれをペーストビンに入れました：http: //pastebin.com/20u8fMEb

于 2012-06-27T12:09:56.920 に答える
4

SSE命令を使用してシングルドット積を実装できますが、結果は現在記述されているコードよりも大幅に速くなることはありません（さらに遅くなることもあります）。書き直しは、現在のバージョンを支援しているコンパイラの最適化を無効にする可能性があります。

SSEまたはCUDAでそれを書き直すことで利益を得るには、その内積を要求するループを最適化する必要があります。これは、1つのドット積を実行するオーバーヘッドが非常に大きいCUDAに特に当てはまります。数千の内積を計算するために数千のベクトルをGPUに送信した場合にのみ、スピードアップを確認できます。同じ考え方がCPU上のSSEにも当てはまりますが、少数の操作で改善が見られる場合があります。ただし、それでも複数の内積になります。

試すのが最も簡単なのはですg++ -ftree-vectorize。GCCは、小さな関数をインライン化してから、ループの最適化を試みることができます（実際には、おそらくすでにそうなっていますが、SSE命令はありません）。ツリーベクトライザーは、手動で提案したことを自動的に実行しようとします。常に成功するとは限りません。

于 2012-06-20T18:31:00.963 に答える
3

SSE命令は、整数または浮動小数点数として表されるデータの大きなブロックを処理するアルゴリズムを最適化するためのものです。一般的なサイズは、なんらかの方法で処理する必要のある数百万から数十億の数値です。4つ（または20）のスカラーのみを処理する関数を最適化することは意味がありません。SSEで得られるものは、関数呼び出しのオーバーヘッドで失われる可能性があります。1回の関数呼び出しで処理される合理的な数は少なくとも1000です。SSE組み込み関数を使用することで、パフォーマンスを大幅に向上させることができます。しかし、あなたが提供した情報に基づいてあなたのニーズに合わせた具体的なアドバイスを与えるのは難しいです。質問を編集して、問題のより高レベルのビューを提供する必要があります（コールスタックのより深い位置にある関数）。たとえば、dtClosestHeightPointTriangleメソッドが1秒間に何回呼び出されるかは明らかではありませんか？この数値は、SSEへの移行が実用的な価値があるかどうかを客観的に判断するために重要です。データの整理も非常に重要です。理想的には、CPUのキャッシュサブシステムを効率的に利用するために、データをメモリの可能な限り少ない線形セグメントに格納する必要があります。

于 2012-06-27T13:54:23.897 に答える
2

アルゴリズムのSSEバージョンを要求したので、ここにあります。

// Copied and modified from xnamathvector.inl
XMFINLINE XMVECTOR XMVector2DotXZ
(
    FXMVECTOR V1, 
    FXMVECTOR V2
)
{
#if defined(_XM_NO_INTRINSICS_)

    XMVECTOR Result;

    Result.vector4_f32[0] =
    Result.vector4_f32[1] =
    Result.vector4_f32[2] =
    Result.vector4_f32[3] = V1.vector4_f32[0] * V2.vector4_f32[0] + V1.vector4_f32[2] * V2.vector4_f32[2];

    return Result;

#elif defined(_XM_SSE_INTRINSICS_)
    // Perform the dot product on x and z
    XMVECTOR vLengthSq = _mm_mul_ps(V1,V2);
    // vTemp has z splatted
    XMVECTOR vTemp = _mm_shuffle_ps(vLengthSq,vLengthSq,_MM_SHUFFLE(2,2,2,2));
    // x+z
    vLengthSq = _mm_add_ss(vLengthSq,vTemp);
    vLengthSq = _mm_shuffle_ps(vLengthSq,vLengthSq,_MM_SHUFFLE(0,0,0,0));
    return vLengthSq;
#else // _XM_VMX128_INTRINSICS_
#endif // _XM_VMX128_INTRINSICS_
}

bool dtClosestHeightPointTriangle(FXMVECTOR p, FXMVECTOR a, FXMVECTOR b, FXMVECTOR c, float& h)
{
    XMVECTOR v0 = XMVectorSubtract(c,a);
    XMVECTOR v1 = XMVectorSubtract(b,a);
    XMVECTOR v2 = XMVectorSubtract(p,a);

    XMVECTOR dot00 = XMVector2DotXZ(v0, v0);
    XMVECTOR dot01 = XMVector2DotXZ(v0, v1);
    XMVECTOR dot02 = XMVector2DotXZ(v0, v2);
    XMVECTOR dot11 = XMVector2DotXZ(v1, v1);
    XMVECTOR dot12 = XMVector2DotXZ(v1, v2);

    // Compute barycentric coordinates
    XMVECTOR invDenom = XMVectorDivide(XMVectorReplicate(1.0f), XMVectorSubtract(XMVectorMultiply(dot00, dot11), XMVectorMultiply(dot01, dot01)));

    XMVECTOR u = XMVectorMultiply(XMVectorSubtract(XMVectorMultiply(dot11, dot02), XMVectorMultiply(dot01, dot12)), invDenom);
    XMVECTOR v = XMVectorMultiply(XMVectorSubtract(XMVectorMultiply(dot00, dot12), XMVectorMultiply(dot01, dot02)), invDenom);
}

XMVector2Dotはxnamathvector.inlから取得され、名前を変更して、X/Z座標で動作するように変更しました。

XNAMathは、Microsoftによる優れたベクトル化されたクロスプラットフォームの数学ライブラリです。私はsal.hヘッダーをインポートすることでOSXでも使用しています（ライセンスの問題についてはよくわかりませんので注意してください）。
実際、組み込みSSEをサポートするプラットフォームはすべてそれをサポートする必要があります。

注意すべき点がいくつかあります。

  • XMLoadFloat3メソッドを使用してフロートをXMVECTORにロードする必要があります。これにより、位置合わせされていないfloat3が__m128構造体にロードされます。
  • アラインされていないフロートをSSEレジスタにロードするとパフォーマンスが低下するため、このSSEコード（プロファイル!!）によるパフォーマンスの向上はおそらく見られません。
  • これは、アルゴリズムからSSEへのブルートフォース変換です。私よりも賢く、実際にアルゴリズムを理解し、SSEに適したバージョンを実装することで、幸運を得ることができます。
  • アプリケーション全体を、その小さな部分だけでなくXNA Math / SSEコードを使用するように変換することで、幸運を得ることができます。少なくとも、整列されたベクトル型（XMFLOAT3Aまたはstruct __declspec（align（16））myvectortype {};）の使用を強制します。
  • ストレートSSEアセンブリは、組み込み関数を優先して、特にx64では推奨されません。
于 2012-06-27T13:29:54.963 に答える