Including Data Return

Note that results are returned in the inverted order of data distribution. After finishing the computations the last processor returns the results to the penultimate processor. This one may still keep finishing its computations while obtaining results from the last processor. On receipt of these results processor $m-1$ starts returning its own results and the results of processor $m$. Hence, while $P_i$ computes, the spare data is sent to $P_{i+1}$, processed on $P_{i+1},\dots,P_m$ and results are returned to $P_i$. Thus, the first line in equations (1) has the form:

$$\!\alpha_iA_i\!\!=\!\!2S_i\!+\!(\!\alpha_{i+1}\!+\!\dots\!+\... ...\dots\!+\!\alpha_m\!)C_i {\rm\hspace{2mm}} i=1,\!\dots,m\!-\!1$$ (2)

where $\beta(x)$ is the amount of results returned for $x$ units of data. In simple cases $\beta(x)$ can be constant (when a simple answer is required e.g. "yes/no", "found at address/not found") or a linear function of $x$ (e.g. distributed FFT, sorting, etc.).