3 ms·
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
by evincarofautumn 15y ago
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 15y agoThis sounds somewhat similar to (software) transactional memory.
- deleted 15y ago[deleted]
- evincarofautumn 15y 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?