Including Data Return

There are at least two ways of returning results in a star network. Firstly, results can be returned in the inverted order of activating PEs (Fig.4(a)). Secondly, they can be returned in the order of activating the PEs (Fig.4(b)).

Figure 4: Returning results in the star architecture. (a) in the inverted order of activating the PEs, (b) in the order of activating the PEs.

In the first case computing on $P_i$ lasts as long as sending data to $P_{i+1}$, processing on it and returning the results from $P_{i+1}$. Therefore, distribution of the load can be found by (1) with modified first line:

$$\alpha_iA_i=2S_{i+1}+C_{i+1}(\alpha_{i+1}\!+\beta(\alpha_{i+... ...i+1}\!\alpha_{i+1} {\rm\hspace{2mm}} i\!=\!1,\!\dots\!,m\!-\!1$$ (6)

In the second case the time of processing on $P_i$ and returning results from processor $P_i$ is equal to the time of sending to $P_{i+1}$ and processing on $P_{i+1}$. Hence, the following modification of the basic equation set can be used to calculate $\alpha_i$'s:

$$\alpha_iA_i\!+\!S_i\!+\!\beta(\alpha_i)C_i = S_{i+1}\!+\!\alpha_{i+1}\!(C_{i+1}\!+\!A_{i+1}\!), {\rm\hspace{2mm}} i\!=\!2,\!\dots\!,m\!-\!1$$ (7)

$$\alpha_1A_1 = \sum_{i=2}^m(S_i+\alpha_iC_i)+\alpha_mA_m+S_m+C_m\beta(\alpha_m)$$

Both (6), and (7) can be solved in $O(m)$ time. However, equations (7) have a solution even if $V$ is so small that no schedule of the exact form presented in Fig.4b exists. To avoid such a case one should verify whether a non-negative idle time on the network processor of $P_1$ exists, i.e. whether the following condition holds: $\alpha_1A_1>\sum_{i=2}^m(2S_i+C_i(\alpha_i+\beta(\alpha_i)))$. Otherwise, a shorter schedule using fewer processors may be possible.