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?
Are there parallel algorithms that give more than linear speedup?
parallel computing