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?