But I’m not sure how many real-world problems there are of high economic value which can soak up a year of serial processing.
Think of any real-world problem that takes one day on modern hardware. When computers were 365 times slower (that is, 12 − 13 years ago), it would have taken one year to solve such problems.
Don’t you think there is any real-world problem that would benefit from 365x faster hardware, even if you can interact with it only once a day?
(Even if individual tasks take less than one year to complete, you can pool several of them and run them serially on the 365x computer)
The first thing that comes to mind is evolutionary algorithms, which eat up tons of ram and keeping running at a decent pace while keeping track of dozens variables is an enormous engineering challenge.
Doesn’t circuit design (and therefore computer processor design) require fairly large computational resources (for mathematical modelling)? Thus faster hardware now can be used to create even faster hardware.. faster.
Yes, but how much of the work that goes into the next generation is just layout? It doesn’t solve all of your chemical or quantum mechanical issues, or fixes your photomasks for the next shrunken generation, etc. If layout were a major factor, we should expect to hear of ‘layout farms’ or supercomputers or datacenters devoted devoted to the task. I, at least, haven’t. (I’m sure Intel has a datacenter or two, but so do many >billion tech multinationals.)
And if layout is just a fraction of the effort like 10%, then Amdahl’s law especially applies.
it doesn’t give many actual current details, but http://en.wikipedia.org/wiki/Computational_lithography implies that as of 2006 designing the photomask for a given chip required ~100 CPU years of processing, and presumably that has only gone up.
Etching a 22nm line with 193nm light is a hard problem, and a lot of the techniques used certainly appear to require huge amounts of processing. It’s close to impossible to say how much of a bottle neck this particular step in the process is, but based on how much really knowing what is going on in even just simple mechanical design requires lots of simulation I would actually expect that every step in chip design has similar types of simulation requirements.
There is some positive feedback in circuit design (although sublinear, I think), but hardware serial speed is essentially limited by the size of the surface features on the IC, which is in turn limited by the manufacturing process and ultimately by the physical limits of CMOS technology.
Most of the examples people would come up with of extremely compute-intensive tasks are parallel algorithms, and those would be cheaper to run in the real-world on server farms which do not need self-contained powersources fitting in an HTC or similar special setups or attendants paid handsomely to be willing to spend a year isolated in the prison of HTC. There’s simply no reason to take a highly parallel task and run it in an HTC when you can get the same result at less cost and less latency by running it on a perfectly normal server farm or cloud computing platform.
(The genetic algorithm will spit out similar answers if you run it on 1 CPU in a HTC at >$1/day for >$365 or if you run it on 365 CPUs on Amazon EC2 at $1/day for 1 day total for $365.)
Remember, electricity is already the dominant cost to running a server these days!
Are there serial tasks which people do not run because they would take a fraction of a year but if they could be run overnight would justify a years’ worth of premium power bills? I’m sure there’s some and the introduction of an HTC would conjure up some uses which no one had bothered to work out because it was obviously pointless, but I can’t help but think that there being no obvious candidates means the candidates wouldn’t be fantastically useful.
Even the so-called Embarrassingly parallel problems, those whose theoretical performance scales almost linearly with the number of cpus, in practice scale sublinearly in the amount of work done per dollar: massive parallelization comes with all kinds of overheads, from synchronization to cache contention to network communication costs to distributed storage issues. More trivially, large data centers have significant heat dissipation issues: they all need active cooling and many are also housed in high-tech buildings specifically designed to address this issue. Many companies even place data centers in northern countries to take advantage of the colder climate, instead of putting them in, say, China, India or Brazil where labor costs much less.
Problems that are not embarrassingly parallel are limited by Amdahl’s law: as you increase the number of cpus, the performance quickly reach an asymptote where the sequential parts of the algorithms dominate.
I can’t help but think that there being no obvious candidates means the candidates wouldn’t be fantastically useful.
Take P-complete problems, for instance. These are problems which are efficient (polynomial time) on a sequential computer, but are conjectured to be inherently difficult to parallelize (the NC != P conjecture). This class contains problems of practical interest, notably linear programming and various problems for model checking. Being able to run these tasks overnight instead of in one year would a significant advantage.
A HTC would come with serious overhead costs too; the cooling is just the flip side of the electricity—a HTC isn’t in Iceland and the obvious interpretation of a HTC as a very small pocket universe means that you have serious cooling issues as well (a years’ worth of heat production to eject each opening).
Take P-complete problems, for instance. These are problems which are efficient (polynomial time) on a sequential computer, but are conjectured to be inherently difficult to parallelize (the NC != P conjecture). This class contains problems of practical interest, notably linear programming and various problems for model checking. Being able to run these tasks overnight instead of in one year would a significant advantage.
I’m not sure how much of an advantage that would be: there are pretty good approximations for some (most/all?) problems like linear programming (remember Grötschel’s report citing a 43 million times speedup of a benchmark linear programming problem since 1988) and such stuff tends to asymptote. How much of an advantage is running for a year rather than the otherwise available days/weeks? Is it large enough to pay for a year of premium HTC computing power?
a HTC isn’t in Iceland and the obvious interpretation of a HTC as a very small pocket universe means that you have serious cooling issues as well (a years’ worth of heat production to eject each opening).
Of course given that the HTC is a fictional device you can always imagine arbitrary issues that make it uneconomical. I was considering the HTC just as a computer that had 365x the serial speed of present day computers, and considering whether there would be economically interesting batch (~1 day long) computations to run on it.
I’m not sure how much of an advantage that would be: there are pretty good approximations for some (most/all?) problems like linear programming (remember Grötschel’s report citing a 43 million times speedup of a benchmark linear programming problem since 1988) and such stuff tends to asymptote.
These problems have polynomial time complexity, they don’t asymptote. Linear programming, for instance has quadratic worst-case time complexity in the size of problem instance (and O(n^3.5) time complexity in the number of variables). For problems related to model checking (circuit value problem, Horn-satisfiability, type inference) approximate solutions don’t seem particularly useful.
Of course given that the HTC is a fictional device you can always imagine arbitrary issues that make it uneconomical. I was considering the HTC just as a computer that had 365x the serial speed of present day computers, and considering whether there would be economically interesting batch (~1 day long) computations to run on it.
Hm, I wasn’t, except in the shift to the upload scenario where the speedup is not from executing regular algorithms (presumably anything capable of executing emulated brains at 365x realtime will have much better serial performance than current CPUs). As an ordinary computer there’s still heat considerations—how is it taking care of putting out 365x a regular computer’s heat even if it’s doing 365x the work? And as a pocket universe as specified, heat is an issue—in fact, now that I think about it Stephen Baxter invented an space-faring alien race in his Ring hard sf universe which lives inside tiny pocket universes as the ultimate in heat insulation.
These problems have polynomial time complexity, they don’t asymptote. Linear programming, for instance has quadratic worst-case time complexity in the size of problem instance (and O(n^3.5) time complexity in the number of variables).
I was referring to the quality of the solution produced by the approximating algorithms.
For problems related to model checking (circuit value problem, Horn-satisfiability, type inference) approximate solutions don’t seem particularly useful.
In this paper, we propose an approximation method to verify quantitative properties on discrete Markov chains. We give a randomized algorithm to approximate the probability that a property expressed by some positive LTL formula is satisfied with high confidence by a probabilistic system. Our randomized algorithm requires only a succinct representation of the system and is based on an execution sampling method. We also present an implementation and a few classical examples to demonstrate the effectiveness of our approach.
I’ll admit I don’t know much about the model checking field, though.
Think of any real-world problem that takes one day on modern hardware. When computers were 365 times slower (that is, 12 − 13 years ago), it would have taken one year to solve such problems.
Don’t you think there is any real-world problem that would benefit from 365x faster hardware, even if you can interact with it only once a day?
(Even if individual tasks take less than one year to complete, you can pool several of them and run them serially on the 365x computer)
The first thing that comes to mind is evolutionary algorithms, which eat up tons of ram and keeping running at a decent pace while keeping track of dozens variables is an enormous engineering challenge.
Doesn’t circuit design (and therefore computer processor design) require fairly large computational resources (for mathematical modelling)? Thus faster hardware now can be used to create even faster hardware.. faster.
Yes, but how much of the work that goes into the next generation is just layout? It doesn’t solve all of your chemical or quantum mechanical issues, or fixes your photomasks for the next shrunken generation, etc. If layout were a major factor, we should expect to hear of ‘layout farms’ or supercomputers or datacenters devoted devoted to the task. I, at least, haven’t. (I’m sure Intel has a datacenter or two, but so do many >billion tech multinationals.)
And if layout is just a fraction of the effort like 10%, then Amdahl’s law especially applies.
it doesn’t give many actual current details, but http://en.wikipedia.org/wiki/Computational_lithography implies that as of 2006 designing the photomask for a given chip required ~100 CPU years of processing, and presumably that has only gone up.
Etching a 22nm line with 193nm light is a hard problem, and a lot of the techniques used certainly appear to require huge amounts of processing. It’s close to impossible to say how much of a bottle neck this particular step in the process is, but based on how much really knowing what is going on in even just simple mechanical design requires lots of simulation I would actually expect that every step in chip design has similar types of simulation requirements.
There is some positive feedback in circuit design (although sublinear, I think), but hardware serial speed is essentially limited by the size of the surface features on the IC, which is in turn limited by the manufacturing process and ultimately by the physical limits of CMOS technology.
Most of the examples people would come up with of extremely compute-intensive tasks are parallel algorithms, and those would be cheaper to run in the real-world on server farms which do not need self-contained powersources fitting in an HTC or similar special setups or attendants paid handsomely to be willing to spend a year isolated in the prison of HTC. There’s simply no reason to take a highly parallel task and run it in an HTC when you can get the same result at less cost and less latency by running it on a perfectly normal server farm or cloud computing platform.
(The genetic algorithm will spit out similar answers if you run it on 1 CPU in a HTC at >$1/day for >$365 or if you run it on 365 CPUs on Amazon EC2 at $1/day for 1 day total for $365.)
Remember, electricity is already the dominant cost to running a server these days!
Are there serial tasks which people do not run because they would take a fraction of a year but if they could be run overnight would justify a years’ worth of premium power bills? I’m sure there’s some and the introduction of an HTC would conjure up some uses which no one had bothered to work out because it was obviously pointless, but I can’t help but think that there being no obvious candidates means the candidates wouldn’t be fantastically useful.
Even the so-called Embarrassingly parallel problems, those whose theoretical performance scales almost linearly with the number of cpus, in practice scale sublinearly in the amount of work done per dollar: massive parallelization comes with all kinds of overheads, from synchronization to cache contention to network communication costs to distributed storage issues. More trivially, large data centers have significant heat dissipation issues: they all need active cooling and many are also housed in high-tech buildings specifically designed to address this issue. Many companies even place data centers in northern countries to take advantage of the colder climate, instead of putting them in, say, China, India or Brazil where labor costs much less.
Problems that are not embarrassingly parallel are limited by Amdahl’s law: as you increase the number of cpus, the performance quickly reach an asymptote where the sequential parts of the algorithms dominate.
Take P-complete problems, for instance. These are problems which are efficient (polynomial time) on a sequential computer, but are conjectured to be inherently difficult to parallelize (the NC != P conjecture). This class contains problems of practical interest, notably linear programming and various problems for model checking. Being able to run these tasks overnight instead of in one year would a significant advantage.
A HTC would come with serious overhead costs too; the cooling is just the flip side of the electricity—a HTC isn’t in Iceland and the obvious interpretation of a HTC as a very small pocket universe means that you have serious cooling issues as well (a years’ worth of heat production to eject each opening).
I’m not sure how much of an advantage that would be: there are pretty good approximations for some (most/all?) problems like linear programming (remember Grötschel’s report citing a 43 million times speedup of a benchmark linear programming problem since 1988) and such stuff tends to asymptote. How much of an advantage is running for a year rather than the otherwise available days/weeks? Is it large enough to pay for a year of premium HTC computing power?
Of course given that the HTC is a fictional device you can always imagine arbitrary issues that make it uneconomical. I was considering the HTC just as a computer that had 365x the serial speed of present day computers, and considering whether there would be economically interesting batch (~1 day long) computations to run on it.
These problems have polynomial time complexity, they don’t asymptote. Linear programming, for instance has quadratic worst-case time complexity in the size of problem instance (and O(n^3.5) time complexity in the number of variables). For problems related to model checking (circuit value problem, Horn-satisfiability, type inference) approximate solutions don’t seem particularly useful.
Hm, I wasn’t, except in the shift to the upload scenario where the speedup is not from executing regular algorithms (presumably anything capable of executing emulated brains at 365x realtime will have much better serial performance than current CPUs). As an ordinary computer there’s still heat considerations—how is it taking care of putting out 365x a regular computer’s heat even if it’s doing 365x the work? And as a pocket universe as specified, heat is an issue—in fact, now that I think about it Stephen Baxter invented an space-faring alien race in his Ring hard sf universe which lives inside tiny pocket universes as the ultimate in heat insulation.
I was referring to the quality of the solution produced by the approximating algorithms.
Quickly googling, there seems to be plenty of work on approximate solutions and approaches in model checking; for example http://cs5824.userapi.com/u11728334/docs/77a8b8880f48/Bernhard_Steffen_Verification_Model_Checking_an.pdf includes a paper:
I’ll admit I don’t know much about the model checking field, though.