11

对于一个研究项目，我编写了一个 Scala 应用程序，它使用一堆期货来进行并行计算。我注意到在我的本地机器（4 核）上，代码运行速度比在我们计算机科学研究所的多核服务器（64 核）上运行得更快。现在我想知道为什么会这样。

任务详解

任务是创建随机布尔 k-CNF 公式，其中 n 个不同变量随机分布在 m 个子句中，然后查看在哪个 m/n 组合下，对于不同的随机分布，公式可解的概率下降到 50% 以下。为此，我实现了一个概率 k-SAT 算法、一个子句生成器和一些其他代码。核心是一个函数，它接受 n 和 m es 以及生成器函数，运行 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，但服务器上的 cors 是 12 倍。

额外的

如果将我的代码的精简示例推送到 github，如果您有兴趣可以自己尝试：https ://github.com/Blattlaus/algodemo （这是一个使用 Scala 2.10 的 sbt 项目）。

更新

  1. 我通过用 42 播种随机数生成器来消除任何随机性。这没有任何改变
  2. 我已经更改了测试集。现在结果更加惊人（服务器慢了 5 倍！） 注意：由于输入，所有不可解决子句的平均百分比的输出都是零。这是正常的，也是意料之中的。
  3. 添加了有关 CPU 的信息
  4. 我注意到对 Random.nextInt() 的调用在服务器上慢了 10 倍。我已经将所有调用包装在一个帮助程序中，该帮助程序测量打印到控制台的运行时间（如果它们慢于 10 毫秒）。在我的本地机器上，我得到了一些，通常在 10-20 毫秒左右。在服务器上，我接到了很多电话，它们往往超过 100 毫秒。会不会是这个问题？？？
4

2 回答 2

2

您已经找到了答案，因为问题是使用 AtomicLong() 的 Random.nextInt()。如果从不同的线程频繁访问它，那么您将遇到缓存抖动，这在您的 64 核计算机上会更糟，因为缓存将更远（电气上），因此获得必要的缓存行锁定需要更长的时间。

有关更多详细信息，请参阅此 stackoverflow 答案，以及如何避免此问题的解决方案（基本上是使用线程本地随机数生成器）：Contention in concurrent use of java.util.Random

于 2015-05-19T13:58:33.140 回答
1

Operations on denormalized floating numbers, could take an order of magnitude longer on x86 architecture. See:

Why does changing 0.1f to 0 slow down performance by 10x?

Haven't examined your code, but given that you return NaN that might be the case. Try removing randomness from your test to verify that hypothesis.

于 2013-01-09T19:09:27.077 回答