3

假设你需要在世界上最快的超级计算机上运行一个需要 10 年才能完成的程序。你可以：

  • 现在花费 2.5 亿美元
  • 计划 9 年，摩尔定律加速（快 4,000 倍），10 年花费 100 万美元，2 周内完成。

什么是最优策略？

“长期存储趋势与你”的问题

4

12 回答 12

11

摩尔定律与速度无关，它与给定硅区域中晶体管的数量有关。不能保证在 9 年内速度会提高 4000 倍。如果有的话，GHz 速度近年来已经趋于平稳。目前正在增加的是 CPU 中的内核数量。

在您的问题中，如果程序不适合矢量化（即可以拆分为可以并行计算的不同部分），那么等待 9 年不会带来任何好处，它不会像时钟速度那样快得多在随后的几年中不太可能筹集到太多资金。

于 2008-12-10T14:34:36.880 回答
7

假设程序是无限可并行化的（因此它总是可以利用所有可用 CPU 的所有内核）......
假设程序不能在运行中暂停并移动到另一台机器......
假设时间是唯一的问题（也许我们有一大笔研究经费，而且我们总是使用最好的电脑）......

我们有四个方程（嗯，实际上其中两个是函数）：

  1. endtime(startyear) = startyear + (calculations / speed(startyear))
  2. speed(year) = speed(year-1.5)4（问题假设硬件和软件速度每 18 个月翻一番）
  3. endtime(0) = 0 + (calculations/speed(0)) = 10 years
  4. speed(0) = calculations/(10 years)（由#3暗示）

我开始使用导数来最小化结束时间，但我意识到我不能很好地记住我的微分方程。所以我将#2 转换为等效的指数增长公式：

speed(year) = speed(0)*4(年/1.5) = (calculations/10)*4(年/1.5)

然后我写了这个小 BeanShell 脚本：

calculations() {
    return 10000000; // random constant (gets cancelled out anyway)
}
speed(year) {
    speed0 = calculations()/10; // constant factor
    return speed0*Math.pow(4.0, year/1.5);
}
endtime(startyear) {
    return startyear + calculations()/speed(startyear);
}
findmin() {
    start = 0.0;
    finish = 10.0;
    result = 0.0;
    // home in on the best solution (there should only be one minimum)
    for (inc = 1; inc > 0.00000001; inc /= 2.0) {
        result = findmin(start,finish,inc);
        start = result-2*inc;
        finish = result+inc;
    }
    print("Minimum value is " + result + ", taking a total of " +
            endtime(result) + " years");
}
findmin(start,finish,inc) {
    lastNum = 0;
    lastVal = Double.MAX_VALUE;
    for (i = start; i < finish; i += inc) {
        result = endtime(i);
        if (result > lastVal) {
            print("Minimum value between " + start + " and " + finish +
                    " is " + lastVal + ", occurring at " + lastNum);
            return i;
        }
        lastNum = i;
        lastVal = result;
    }
    return lastNum;
}

输出：

bsh % source("moore.bsh");
bsh % findmin();
Minimum value between 0.0 and 10.0 is 3.5749013123685915, occurring at 2.0
Minimum value between 1.0 and 4.0 is 3.4921256574801243, occurring at 2.5
Minimum value between 2.0 and 3.5 is 3.4921256574801243, occurring at 2.5
Minimum value between 2.25 and 3.0 is 3.4886233976754246, occurring at 2.375
Minimum value between 2.25 and 2.625 is 3.488620519067143, occurring at 2.4375
Minimum value between 2.375 and 2.5625 is 3.488170701257679, occurring at 2.40625
Minimum value between 2.375 and 2.46875 is 3.488170701257679, occurring at 2.40625
Minimum value between 2.390625 and 2.4375 is 3.488170701257679, occurring at 2.40625
(snip)
Minimum value between 2.406149387359619 and 2.4061494767665863 is 3.4881706965827037,
occurring at 2.4061494171619415
Minimum value is 2.4061494320631027, taking a total of 3.488170696582704 years

因此，根据我之前所说的假设，答案是等待2.406149... 年（或大约2 年 148 天，根据谷歌）。

编辑：我注意到用上面重写的第二个公式，解决只需要简单的微积分。

endtime(x) = x + c/speed(x) (where c = calculations)
speed(x) = speed(0) * 4^(x/1.5) = (c/10)*4^(2x/3)
=> endtime(x) = x + c/((c/10)*4^(2x/3))
              = x + 10*(4^(-2x/3))
d/dx endtime(x) = 1 + 10*ln(4)*(-2/3)*(4^(-2x/3))

临界点是当 d/dx = 0 时，所以

1 + 10*ln(4)*(-2/3)*(4^(-2x/3)) = 0
=> 4^(-2x/3) = 1/(10*ln(4)*(2/3))

取两边的 log4：（记住log4(x) = ln(x)/ln(4)和ln(1/x) = -ln(x)）

-2x/3 = ln(1/(10*ln(4)*(2/3))) / ln(4)
      = -ln(10*ln(4)*2/3) / ln(4)
=> x = (-3/2) * -ln(1/(10*ln(4)*2/3)) / ln(4)
     = 3*ln(10*ln(4)*(2/3)) / 2*ln(4)

这看起来像一团糟（这里没有显示数学公式的好方法也无济于事）。但是如果你把它插入你的计算器，你应该得到2.4061494159159814141268120293221（至少如果你使用 Windows 计算器，就像我刚刚做的那样）。所以我之前的回答正确到小数点后七位（当然，这在这样的问题中毫无意义）。

（我应该注意，这只是一个临界点，不一定是最小值。但是二阶导数（形式为-(some constant)*4-2x/3）总是负数。所以函数总是向上凹的，因此唯一的临界点是最低。）

于 2008-12-10T17:42:05.393 回答
4

摩尔定律与将放置在单个芯片中的晶体管数量有关，通常与微处理器的速度无关。

也就是说，从我们所看到的当前趋势来看，我们可能会看到越来越多的内核被装入单个处理器芯片中，因此并发编程将变得越来越重要，以利用处理器中可用的原始处理能力。处理器。

所以，很难说是现在做还是等待——然而，无论哪种方式，并发编程或分布式计算都将发挥作用，因为我们不会看到单核处理器以指数级速度增长（就时钟速度）由于当前半导体技术的物理限制和自然规律。

于 2008-12-10T14:38:27.323 回答
3

确保您的程序可以暂停和继续，然后在它们出现时将其放在越来越快的机器上。两全其美...

于 2008-12-10T14:37:05.533 回答
1

现在花钱——现在美元的价格/价值与 10 年后的估计相比，就像试图预测 3 个月后的天气一样。另外，这没有考虑到诸如 10 年内编程趋势之类的因素，以及事情实际上是否会快 4,000 倍或可扩展/并行性提高 4,000 倍，这似乎是最近的趋势。

此外，根据玛雅人的说法，世界将在 2012 年结束，所以现在就花掉战利品吧！

于 2008-12-10T14:33:41.250 回答
1

简化模型以做出您现在可以运行的估计。随着更多/更好的资源可用，优化模型以获得更准确的结果。

于 2008-12-10T14:36:34.847 回答
1

完成它的最快方法是：

  • 为当前的技术编写一个可以移植到每一代新一代的版本。
  • 除了迁移之外，继续对算法等方面的任何改进进行编程。

最便宜的方法显然是将其放置更长时间。您确实需要考虑编程时间（这将是足够恒定的）。

另外，我不想在摩尔定律继续上投入太多。

还要记住，摩尔定律与晶体管的密度有关，而不是与特定问题的计算速度有关。即使总体上计算能力提高了这么多，也并不一定意味着您的应用程序会受益。

于 2008-12-10T14:37:24.580 回答
0

但是摩尔定律并没有加速编程。

9年的编程永远不会浓缩为2周。

除非你成功地用了 9 年的时间来编写一台自动思维阅读机，否则我想。

于 2008-12-10T14:32:33.640 回答
0

编程 4 年，然后在 2.5 中运行？

（我敢肯定在 4 到 5 年之间会有一个“完美”的答案......）

于 2008-12-10T14:34:03.713 回答
0

最佳策略取决于您必须运行程序的原因。

在这种情况下，第二个选项是最好的，因为您将获得结果（这实际上很重要）的那一刻将是相同的。

实际上，我相信如果每个人都选择第一个（并且有钱这样做）......摩尔定律将受到损害。我假设如果我们所有的计算需求都得到满足……我们就不会如此致力于保持技术发展向前发展。

于 2008-12-10T14:35:28.407 回答
0

这是一个有缺陷的假设，即摩尔定律实际上是一个定律。它可能会更好地命名为摩尔理论。你等待的风险是，10 年后，它可能还需要 10 年才能运行。现在启动程序（如果可能，内置暂停和重新启动），组建一个团队，寻找其他更快的方法来解决问题。一旦您确信其中一个会提供更快的解决方案，请切换。

编辑：作为一个问题，我认为这个问题的最佳价值是它让你检查你的假设是否有效。显而易见的解决方案——因为根据问题定义，你在相同的时间内用更少的钱得到相同的结果——是等待，但这取决于一些隐含的假设。如果这些假设不成立，那么显而易见的解决方案不一定是这里许多答案所证明的最佳解决方案。

于 2008-12-10T14:38:56.497 回答
0

问题中指定问题在超级计算机上运行，​​因此问题必须是可向量化的。超级计算机的速度比摩尔定律快得多，因此根据实际问题空间，一种方法是聘请黑客土匪创建一个全球分布式沃霍尔蠕虫，获取 85% 计算机的资源在网上寻找像梅森素数搜索（GIMPS）这样的短的大规模分布式网格，并在 20 分钟内解决问题。

（解决问题的方法很多，但我当然希望这被标记为幽默）

于 2008-12-10T15:17:57.213 回答