8 ms·
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 grea
by steerb 14y ago
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 14y agoI 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 14y agoThis sounds somewhat similar to (software) transactional memory.
- deleted 14y ago[deleted]
- evincarofautumn 14y agoCould you elaborate? I was thinking of automatically converting sequential algorithms to run in parallel at the expense of determinism and precision. You could then get an average speedup for a guaranteed correct result by running the parallel version repeatedly till the correct answer were to arise. How does that relate to STM?