摩尔定律问题

Question

假设您需要在世界上最快的超级计算机上运行程序,这需要10年才能完成.你可以:

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

什么是最佳策略？

_{来自" 长期存储趋势和您 "的问题}

Answer 1

摩尔定律不是关于速度,而是关于给定硅片区域中晶体管的数量.无法保证在9年内速度将提高4000倍.如果有的话,近年来GHz的速度已经稳定下来.目前,增加的是CPU中的核心数量.

在你的问题中,如果程序不适合矢量化(即可以分成可以并行计算的不同部分),那么等待9年将不会带来任何好处,因为时钟速度不会快得多.在这几年里不太可能筹集到太多.

Answer 2

假设程序是无限可并行化的(所以它总是可以利用所有可用CPU的核心)...
假设程序无法暂停并在中期运行到另一台机器......
假设时间是唯一的问题(也许我们有大量的研究经费,我们总是使用最好的电脑)...

我们有四个方程式(实际上,其中两个是函数):

1. endtime(startyear) = startyear + (calculations / speed(startyear))
2. speed(year) = speed(year-1.5)⁴(该问题假设硬件和软件每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天,根据Google的说法).

编辑:我注意到,如上所述重写第二个公式,求解只需要简单的微积分.

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)总是负的.所以函数总是凹陷的,因此唯一的关键点是最低.)