I'm wondering if there are any parallel algorithms whose runtime is not linearly dependent on processor count. (Assuming the problem-size remains constant for different processor counts)

For example, suppose p processors has a O(n^2) runtime and p+1 is O(n^1.5). To me, it seems if that were the case, you would just use the O(n^1.5) for p processors. You might want to use the O(n^2) if the overhead of the O(n^1.5) algorithm outweighs it's benefits. But if that were the case, the execution time vs processor count curve would still be bounded by n^1.5 (since execution time includes overhead).

There is also the case of super-linear speedup, when comparing two architectures. However, it seems the execution times are still linearly dependent on the number of processors (albeit the slope is > 1). The common case of super-linear speedup is from memory limitations. This should still be bounded by a linear function though, since memory access is inherently linear.

Apparently, branch-and-bound search algorithms can get super-linear speedup; but I haven't seen any data to determine whether these speedups are linear. Are parallel search algorithms an example of greater than linear speedups? If so, what function are the speedups bounded by?

  • 1
    $\begingroup$ You can simulate parallel algorithms sequentially. In fact, your computer is probably doing that right now. $\endgroup$ – Yuval Filmus May 20 '17 at 21:23
  • $\begingroup$ Superlinear speed up is still linear, just with unaccounted cache and other constants. No search algorithm are linear. Here also other factors are significant - the memory access patern differs (which fits GPU but not CPU so in that case emulating it would fail with benefits). $\endgroup$ – Evil May 20 '17 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.