Moore’s Law Problem

Question

Suppose you need to run a program on the world’s fastest supercomputer which will take 10 years to complete. You could:

• Spend $250M now
• Program for 9 years, Moore’s law speedup (4,000x faster), spend $1M in 10years, complete in 2 weeks.

What is the optimum strategy?

_{Question from "Long Term Storage Trends and You"}

Answer 1

But Moore's law does not speed up programming.

9 years of programming will never be condensed into 2 weeks.

Unless you successfully spend the 9 years programming an automated thought reading machine I suppose.

Answer 2

Spend the money now - the price/value of the dollar now vs an estimate in 10 years is like trying to forecast weather 3 months from now. Plus this fails to consider factors like programming trends in 10 years and whether things will actually be 4,000 times faster or 4,000 times more scalable/parallel which seems to be the trend of late.

Also, according to the Mayans the world will end in 2012 so spend the loot now!

Answer 3

Program for 4 years and then run it in 2.5?

(I'm sure there's a "perfect" answer somwehere between 4 and 5 years...)

Answer 4

Moore's Law is not about speed, it's about the number of transistors in a given area of silicon. There is no guarantee that in 9 years the speed will increase 4000x. If anything, GHz speed has levelled off in recent years. What is increasing, currently, is the number of cores in a CPU.

In your question, if the program does not lend itself to vectorisation (i.e. can be split into distinct parts that can be computed in parallel) then waiting 9 years will not provide any benefit, it won't be that much faster as clock speeds are unlikely to raise much in the intervening years.

Skizz

Answer 5

The optimum strategy depends on the reason you have to run the program.

In this scenario, the second option is the best one, because the moment you'll have the result (which is what actualy matters) would be the same.

Actually, I believe that if everybody choose the first one (and had the money to do that) ... the Moore's Law would be compromised. I assume that if all our computational needs were satisfied ... we wouldn't be so commited in keep the technology development moving forward.

Answer 6

Simplify the model to make an estimate that you can run now. As more/better resources become available, refine the model for more accurate results.

Answer 7

Make sure your program can pause and continue, and then put it on faster and faster machines as they come along. Best of both worlds...

Answer 8

The fastest way to complete it would be to:

• Write a version for current technology that could be migrated to each new generation.
• Alongside migrations, continue programming for any improvements algorithmically etc.

The cheapest way would obviously be to leave it for longer. You do need to factor in programming time (which would be near enough constant).

Also, I wouldn't want to stake too much on moore's law continuing.

Also remember that moore's law relates to the density of transistors not to computing speed for a particular problem. Even if computing power in general improves by that much, it doesn't necessarily mean your application will benefit.

Answer 9

Moore's Law is concerned with the number of transistors that will be placed into one single chip and does not relate to the speed of microprocessors in general.

That said, from the current trend we are seeing, we'll probably see more and more cores being fit into a single processor die, so concurrent programming is going to become more and more important to take advantage of the raw processing power available in a processor.

So, it's hard to say whether to do it now or wait -- however, either way, concurrent programming or distributed computing is going to come into play, as we won't be seeing a single core processor becoming exponentially faster (in terms of clock speed) due to the physical limitations of current semiconductor technology and the laws of nature.

Answer 10

This makes a flawed assumption that Moore's Law is actually a Law. It would probably be better named Moore's Theory. The risk you run by waiting is that in 10 years, it may still take 10 years to run. Start the program now (with pause and restart built in if possible), start a team looking at other ways to solve the problem that will be faster. Once you have confidence that one or the other will provide a quicker solution, switch.

EDIT: As a problem I think the best value in this question is that it makes you examine whether your assumptions are valid. The obvious solution -- since according to the problem definition you get the same result in the same amount of time with less money -- is to wait, but it depends on some implicit assumptions. If those assumptions don't hold, then the obvious solution is not necessarily the best as many answers here attest.

Answer 11

It's specified in the question that the problem runs on a super-computer, thus the problem must be vectorizable. The speed of of a super-computers is going up vastly faster than Moores law, so depending on the actual problem space one approach would be to hire hacker banditos to create a world wide distributed Warhol Worm that acquired the resources of 85% of the computers on the net for a short massively distributed grid like the Mersenne prime search (GIMPS) and solve the problem in 20 minutes.

(many ways to solve a problem but I sure hope this is labeled as humor)

Answer 12

Assuming the program is infinitely parallelizable (so it can always take advantage of all cores of all CPUs available)...
Assuming the program cannot be paused and moved to a different machine in mid-run...
Assuming time is the only issue (maybe we have a big research grant and we always use the best computers available)...

We have four equations (well, actually two of them are functions):

1. endtime(startyear) = startyear + (calculations / speed(startyear))
2. speed(year) = speed(year-1.5)⁴ (the problem assumes both hardware and software double in speed every 18 months)
3. endtime(0) = 0 + (calculations/speed(0)) = 10 years
4. speed(0) = calculations/(10 years) (implied by #3)

I started to use derivatives to minimize endtime, but I realized I can't remember my differential equations very well. So I transformed #2 into the equivalent exponential-growth formula:

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

Then I wrote this little BeanShell script:

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;
}

Output:

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

So, with the assumptions I stated before, the answer is to wait 2.406149... years (or approximately 2 years, 148 days, according to Google).

---

Edit: I noticed that with second formula rewritten as above, solving only requires simple calculus.

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))

Critical point is when d/dx = 0, so

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

Take log4 of both sides: (remember that log4(x) = ln(x)/ln(4), and that 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)

That looks like an awful mess (it doesn't help that there's no good way to show math formulas here). But if you plug it into your calculator, you should get 2.4061494159159814141268120293221 (at least if you use the Windows calculator, like I just did). So my previous answer was correct to seven decimal places (which are meaningless in a problem like this, of course).

(I should note that this is just a critical point, not necessarily a minimum. But the second derivative (which is of the form -(some constant)*4^-2x/3) is always negative. So the function is always concave up, therefore the only critical point is the minimum.)