0

最大 240 のスレッドを持つ Intel Xeon Phi コプロセッサーを使用しており、特定のアプリケーションに使用されるスレッドの数を最小化 (またはパフォーマンスを最大化) しながら、最高の実行時間のパーセンテージ内に収まるように取り組んでいます。たとえば、次の測定値があるとします。

  • スレッド | 実行時間
  • 240 100秒
  • 200 105秒
  • 150 107秒
  • 120 109秒
  • 100 120秒

120 から 150 の間のスレッド数を選択したいと思います。これは、そこでの「パフォーマンス曲線」が安定しているように見え、実行時間の短縮がそれほど重要ではないためです (この場合、測定された最良の時間の約 15% です。私はこれを行いました)。徹底的な検索アルゴリズム (1 から 240 のスレッドを測定) を使用していますが、私の問題は、スレッドの数が少ないと時間がかかりすぎることです (明らかに問題のサイズによって異なります)。

測定回数を減らすために、一種の「二分探索」アルゴリズムを開発しました。基本的に、上限と下限 (0 スレッドと 240 スレッドから始まる) があり、中間の値を取り、240 で測定します。両方の値のパーセント差を取得し、15% 以内の場合 (この値は徹底的な検索の結果を分析した後に選択された) 新しい下限または上限を割り当てます。差が 15% より大きい場合、これは新しい下限 (120-240) であり、それより小さい場合は新しい上限 (0-120) であり、実行時間が改善された場合は、次のように保存します。最高の実行時間。

このアルゴリズムの問​​題は、まず第一に、これは必ずしも実行時間の並べ替えられた配列ではないことです。問題のサイズによっては、網羅的な検索結果に 2 つの異なる最小値が表示されるため、たとえば 1 つは 80 スレッドで最高のパフォーマンスが得られ、検索の結果、170 スレッドではなく 80 スレッドを返すことができるようにしたいと考えています。ただし、最小値が 1 つしかない他のケースでは、アルゴリズムは予想される値に非常に近い値を検出しました。

誰かが私を助けることができる既存の検索アルゴリズムまたはヒューリスティックについてより良いアイデアを持っているか知っているなら、私は本当に感謝しています.

4

1 に答える 1

1

あなたの目標は、可能な限り最高のパフォーマンスの係数 (<=1) に基づいてパフォーマンスの制限を維持しながら、最小量のスレッドで最高の相対パフォーマンスを得ることだと私は考えています。IE: 係数が 0.85 の場合、パフォーマンスはすべてのスレッドを使用したパフォーマンスの 85% 以上になるはずです。

あなたがやろうとしていることは、パフォーマンスの限界を得るために必要なスレッドの最小数を見つけることです。1 ～ 240 スレッドを調べるのではなく、240 スレッドから始めて、パフォーマンス制限の下限を設定できるまでスレッド数を減らします。次に、下限を超えずに最小値を見つけることができるように、下限から上に移動できます。定義済みのパフォーマンス バウンドがない場合は、収穫逓減に基づいてオンザフライで計算できます。

  1. パフォーマンスの制限を超えていない限り、半分のスレッド数 (最大スレッド数から開始)。パフォーマンス制限を超える数は、必要なスレッド数の下限です。
  2. スレッド数の下限 Z から始めて、パフォーマンスの制限内に収まらずに追加できる場合は、m 個のスレッドを追加します。パフォーマンスの制限内になるまで、追加するスレッドの数を繰り返し 2 倍にします。スレッドの追加が性能限界内に収まる場合は、最後の追加を差し引いて、追加するスレッドの数を m に再設定します。m を追加するだけでも制限内に収まる場合は、最後の m スレッドを追加し、スレッドの数を返します。

プロセスがどのように見えるかの例を段階的に示す方が明確かもしれません. Passed は、スレッドの数がパフォーマンス制限の範囲外であることを意味し、Failed は、パフォーマンス制限内またはパフォーマンス制限内にあることを意味します。

Try adding 1m (Z + 1m). Passed. Threads = Z + m.
Try adding 2m (Z + 3m). Passed. Threads = Z + 3m.
Try adding 4m (Z + 7m). Failed. Threads = Z + 3m. Reset.
Try adding 1m. Passed. Threads = Z + 4m.
Try adding 2m. Passed. Threads = Z + 6m.
Z + 7m failed earlier so reset. 
  Comparisons/lookups are cheap, use them to prevent duplication of work.
Try adding 1m. Failed. Threads = Z + 6m. Reset.
Cannot add less than 1m and still in outside of performance limit.
The solution is Z + 7m threads. 
  Since Z + 6m is m threads short of the performance limit.

これは少し非効率的ですが、m-1 スレッドの誤差内に収まるパフォーマンスを得るために必要なスレッドの最小数 (>= Z) を見つけ、O(log (NZ)) テストのみを必要とします。ほとんどの場合、これで十分ですが、そうでない場合は、手順 1 をスキップして Z=m を使用します。Z が非常に小さい場合、スレッドの数を増やすと実行時間が急速に減少し、実行時間が非常に遅くなる場合を除きます。その場合、ステップ 1 を実行して補間を使用すると、スレッド数が減少するにつれてランタイムがどれだけ速く増加するかを知ることができます。これは、何も指定されていない場合に適切なパフォーマンス制限を決定するのにも役立ちます。

于 2014-05-27T00:33:01.260 に答える