4 ms·

Knuth comes across as living in a bit of denial here... Sure the frequency speedups were much nicer, but faced with hardware limits that make this impossible, h

by mrich 15y ago

Knuth comes across as living in a bit of denial here... Sure the frequency speedups were much nicer, but faced with hardware limits that make this impossible, he should point out that the future lies in finding algorithms best suited to multicore. They surely deserve their own volume of TAOCP, and I don't see how this would be wasted research for the next 10+ years. There are some amazing lock-free data structures/algorithms out there which should be taught in any CS curriculum. Intel has been releasing some great tools to aid with multicore development since they realized years ago that this was the only way to get more performance. http://software.intel.com/en-us/parallel/ http://software.intel.com/en-us/parallel/

sliverstorm 15y ago
Knuth comes across as living in a bit of denial here... Sure the frequency speedups were much nicer, but faced with hardware limits that make this impossible It's easier to say "the hardware guys are dropping the ball" than to acknowledge silly things like "Physics". Now, he could try to argue that hardware should be responsible for paralleling things under the covers, and that would be a bit more reasonable- though I would still have to disagree. CS folks are the ones supposed to be discovering algorithms; find them, and have the hardware guys stick them in once they are known.
marshray 15y ago
Yes, some of those lock-free structures are amazing. However, if you read the fine print it turns out that they are quite often slower than lock-based exclusion on top of one of Knuth's structures. The atomic primitive operations still require cross-core communication which only gets more expensive with more cores. Most applications simply don't parallelize perfectly. We're going to have to face the fact that not only is the free lunch over, the lunch we have to pay for isn't always as satisfying.

by mrich 15y ago

sliverstorm 15y ago

Knuth comes across as living in a bit of denial here... Sure the frequency speedups were much nicer, but faced with hardware limits that make this impossible It's easier to say "the hardware guys are dropping the ball" than to acknowledge silly things like "Physics". Now, he could try to argue that hardware should be responsible for paralleling things under the covers, and that would be a bit more reasonable- though I would still have to disagree. CS folks are the ones supposed to be discovering algorithms; find them, and have the hardware guys stick them in once they are known.

marshray 15y ago

Yes, some of those lock-free structures are amazing. However, if you read the fine print it turns out that they are quite often slower than lock-based exclusion on top of one of Knuth's structures. The atomic primitive operations still require cross-core communication which only gets more expensive with more cores. Most applications simply don't parallelize perfectly. We're going to have to face the fact that not only is the free lunch over, the lunch we have to pay for isn't always as satisfying.