Amdahl's Law generally divides a task into "things that can be parallelized" and "things that can't". Now, I know what "things that can be parallelized", and it's not too hard to imagine things whose parallelizations aren't obvious, but it's not clear to me what makes a task fundamentally non-parallelizable, whether such a thing is known to exist, or whether the question is even well-formed. The best example I can think of is, say, hashing an input 100 times - but I'm not sure it's been proven there is no parallelization, or just that we haven't found one.

One conceivable outcome, if non-parallelization can't be proven - it's vaguely plausible that there could be some way of processing arbitrary algorithms that, at some cost of memory and/or efficiency, allows parallelization across an arbitrary number of cores.

Has it been proven there exist algorithms/tasks cannot be parallelized? (Or the opposite?) Have any specific algorithms been proven to be fundamentally serial? Is there a commonly used set of definitions/rules/assumptions for talking about the issue?

  • 1
    $\begingroup$ Does this answer your question? Which algorithms can not be parallelized? $\endgroup$ – user114966 Nov 8 '20 at 3:12
  • $\begingroup$ @Dmitry Oh, thanks; I'd say that's similar enough to close my question as a duplicate. Briefly looking through the responses, it seems like the answer is "we're not sure yet; we're working on it." $\endgroup$ – Erhannis Nov 8 '20 at 4:06