Return to Answer

At the end, hopefully it should be clear that in your example there is no superlinear speedup phenomenon: it is forbidden by the theory and the analysis does not contradict the theory, since the ratio $S_\infty = \frac{n^3}{\lg^2 n}$ does not involve $p$ and refers to an infinite number of processors.

At the end, hopefully it should be clear that in your example there is no superlinear speedup phenomenon: it is forbidden by the theory and the analysis does not contradict the theory, since the ratio $S_\infty = \frac{n^3}{\lg^2 n}$ does not involve $p$ and refers to an infinite number of processors. The problem is that you can not simply put $p = n$ and simultaneously maintain the same meaning of the ratio. To preserve the exact meaning, you must use the true problem size, i.e., you need to put $p = n^3$. But then, the ratio becomes $\frac{p}{\lg ^{2} \sqrt[3]{p}}=O\left(\frac{p}{\lg ^{2} p}\right)$ which, definitely, is not superlinear.

At the end, hopefully it should be clear that in your example there is no superlinear speedup phenomenon: it is forbidden by the theory and the analysis does not contradict the theory, since the ratio $S_\infty = \frac{n^3}{\lg^2 n}$ does not involve $p$ and refers to an infinite number of processors. If you insist on substituting $p$, you need to address this correctly, since the true problem size is $n^3$, not $n$ as noted. For $p = n^3$ you get the ratio $\frac{p}{\lg^2 (\sqrt[3] p)}$ (i.e., $O(\frac{p}{\lg^2 p}$)) which, definitely (starting from $p = 8$) is not superlinear.

At the end, hopefully it should be clear that in your example there is no superlinear speedup phenomenon: it is forbidden by the theory and the analysis does not contradict the theory, since the ratio $S_\infty = \frac{n^3}{\lg^2 n}$ does not involve $p$ and refers to an infinite number of processors.

At the end, hopefully it should be clear that in your example there is no superlinear speedup phenomenon: it is forbidden by the theory and the analysis does not contradict the theory, since the ratio $S_\infty = \frac{n^3}{\lg^2 n}$ does not involve $p$ and refers to an infinite number of processors. If you insist on substituting $p$, you need to address this correctly: you can not substitute $p = n$, since the true problem size is $n^3$, not $n$ as noted. For $p = n^3$ you get the ratio $\frac{p}{\lg^2 (\sqrt[3] p)}$ (i.e., $O(\frac{p}{\lg^2 p}$)) which, definitely (starting from $p = 8$) is not superlinear.

At the end, hopefully it should be clear that in your example there is no superlinear speedup phenomenon: it is forbidden by the theory and the analysis does not contradict the theory, since the ratio $S_\infty = \frac{n^3}{\lg^2 n}$ does not involve $p$ and refers to an infinite number of processors. If you insist on substituting $p$, you need to address this correctly, since the true problem size is $n^3$, not $n$ as noted. For $p = n^3$ you get the ratio $\frac{p}{\lg^2 (\sqrt[3] p)}$ (i.e., $O(\frac{p}{\lg^2 p}$)) which, definitely (starting from $p = 8$) is not superlinear.