11

研究プロジェクトのために、並列計算を行うために多数の先物を使用する Scala アプリケーションを作成しました。私のローカル マシン (4 コア) では、コンピューター サイエンス研究所のメニー コア サーバー (64 コア) よりもコードが高速に実行されることに気付きました。今、私はこれがなぜなのか知りたいです。

タスクの詳細

タスクは、m 節にランダムに分散された n 個の異なる変数を使用してランダムなブール k-CNF 式を作成し、どの m/n の組み合わせで式が解ける確率がさまざまなランダム分布で 50% を下回るかを確認することでした。このために、確率論的 k-SAT アルゴリズム、節ジェネレーター、およびその他のコードを実装しました。コアは、ジェネレーター関数と同様に n と m を受け取り、100 個の先物を実行して結果を待つ関数です。関数は次のようになります。

問題のコード

def avgNonvalidClauses(n: Int, m: Int)(implicit clauseGenerator: ClauseGenerator) = {

    val startTime = System.nanoTime

    /** how man iteration to build the average **/
    val TRIES = 100

    // do TRIES iterations in parallel 
    val tasks = for (i <- 0 until TRIES) yield future[Option[Config]] {
        val clause = clauseGenerator(m, n)
        val solution = CNFSolver.probKSat(clause)
        solution
    }

    /* wait for all threads to finish and collect the results. we will only wait
     * at most TRIES * 100ms (note: flatten filters out all
     * None's) */
    val results = awaitAll(100 * TRIES, tasks: _*).asInstanceOf[List[Option[Option[Config]]]].flatten

    val millis = Duration(System.nanoTime - startTime, NANOSECONDS).toMillis
    val avg = (results count (_.isDefined)) /  results.length.toFloat

    println(s"n=$n, m=$m => $avg ($millis ms)")

    avg
  }

問題

私のローカルマシンでは、これらの結果が得られます

[info] Running Main 
n=20, m=120 => 0.0 (8885 ms)
n=21, m=121 => 0.0 (9115 ms)
n=22, m=122 => 0.0 (8724 ms)
n=23, m=123 => 0.0 (8433 ms)
n=24, m=124 => 0.0 (8544 ms)
n=25, m=125 => 0.0 (8858 ms)
[success] Total time: 53 s, completed Jan 9, 2013 8:21:30 PM

64 コアのサーバーでは、次のようになります。

[info] Running Main 
n=20, m=120 => 0.0 (43200 ms)
n=21, m=121 => 0.0 (38826 ms)
n=22, m=122 => 0.0 (38728 ms)
n=23, m=123 => 0.0 (32737 ms)
n=24, m=124 => 0.0 (41196 ms)
n=25, m=125 => 0.0 (42323 ms)
[success] Total time: 245 s, completed 09.01.2013 20:28:22

ただし、両方のマシンで全負荷 (サーバーの平均負荷は約 60 ～ 65) であるため、十分なスレッドが実行されています。どうしてこれなの？私は何か完全に間違っていますか？

私のローカルマシンには「AMD Phenom(tm) II X4 955 Processor」CPU が搭載されており、サーバーは「AMD Opteron(TM) Processor 6272」を使用しています。ローカル CPU には 6800 の bogomips があり、サーバーには 4200 があります。したがって、ローカル CPU は 1/3 高速ですが、サーバーには 12 倍のコアがあります。

追加

私のコードの縮小された例が github にプッシュされている場合は、興味がある場合は自分で試すことができます: https://github.com/Blattlaus/algodemo (これは Scala 2.10 を使用する sbt プロジェクトです)。

アップデート

  1. 乱数ジェネレーターに 42 をシードすることでランダム性を排除しました。これは何も変更しません
  2. テストセットを変更しました。結果はさらに驚くべきものになりました (サーバーは 5 倍遅いです!) 注: 解決できない節の平均パーセンテージのすべての出力は、入力のために zeor です。これは正常であり、予期されたものです。
  3. CPU に関する追加情報
  4. サーバー上で Random.nextInt() の呼び出しが 10 倍遅いことに気付きました。すべての呼び出しをヘルパーでラップしました。これは、出力が 10 ミリ秒よりも遅い場合にコンソールに出力されるランタイムを測定します。私のローカルマシンでは、いくつか取得できますが、通常は約 10 ～ 20 ミリ秒です。サーバーでは、多くの mure 呼び出しが発生し、それらは 100 ミリ秒を超える傾向があります。これが問題でしょうか？
4

2 に答える 2

2

問題は AtomicLong() を使用する Random.nextInt() であるという点で、すでに答えを見つけています。これが異なるスレッドから頻繁にアクセスされている場合、キャッシュのスラッシングが発生します。これは、64 コアのコンピューターではさらに悪化します。これは、キャッシュが (電気的に) 離れているため、必要なキャッシュ ライン ロックを取得するのに時間がかかるためです。

詳細については、このスタックオーバーフローの回答と、この問題を回避する方法の解決策 (基本的にスレッドローカル乱数ジェネレーターを使用すること) を参照してください: Java.util.Random の同時使用における競合

于 2015-05-19T13:58:33.140 に答える
1

非正規化された浮動小数点数の操作は、x86 アーキテクチャでは桁違いに時間がかかる可能性があります。見る：

0.1f を 0 に変更するとパフォーマンスが 10 倍遅くなるのはなぜですか?

コードを調べてNaNいませんが、そうである可能性があります。その仮説を検証するために、テストからランダム性を取り除いてみてください。

于 2013-01-09T19:09:27.077 に答える