[steerb]

I tend to agree.

Let's assume a sufficiently smart compiler can parallelize 90% of our hot code. Now considering Amdahl's Law, we cannot achieve a speedup greater than 10 and are therefore stuck. Adding 10 or more cores won't do any good to our running time, because it is dominated by the sequential code.

[evincarofautumn]

I have a hunch that the trick to writing the sufficiently smart compiler of legend is in deriving nondeterministic parallel cousins to sequential algorithms. In simple terms, if you could quickly compute potential solutions and verify them, then you could get a speedup in the average case. I doubt NC=P (that no problem is inherently sequential), but we could perhaps tackle many real-world problems with this line of thinking.

[steerb]

This sounds somewhat similar to (software) transactional memory.