Hypercube

A $d$-dimensional hypercube network consists of $2^d$ PEs. Each of the PEs can be labeled by a unique $d$-bit binary word such that directly connected processors have their labels differing in exactly one bit. The idea of divisible task was applied to hypercubes in [BD95,BD97]. The scattering method was based on consecutively activating the nearest neighbors of the active processors. Thus, the originator $P_0$ (labeled (0,...,0)) activated $d$ PEs with exactly one 1 in the label. Those PEs, in turn, activated PEs with exactly two 1's in the label etc. Let us call by a layer the set of PEs activated in the same step of scattering, i.e. the set of PEs with the same number of 1's in their labels. Note that each PE in layer $i$ can be reached by $i$ links (the number of 1's in the label), and has $d-i$ inactive neighbors in layer $i+1$. The number of PEs in layer $i$ is ${\left(d \atop i\right)}$. We assume that PEs are identical, each PE has a network processor and the time of returning the results is negligible. Then, the diagram of computing and communication is the same as the one in Fig.1, and processors of the layer activated earlier compute as long as it is required to send data to the next layer and compute on the next layer. Thus, distribution of the load can be found from the following equations:

$$\alpha_iA\!\!\!\! =\!\!\!\! S\!+\!%% \frac{\left(V\!\!-\!\sum_{j=0}^i {\scriptscriptstyle\lef... ...end{array}\right)}(d-i)}+ \alpha_{i+1}A {\rm\hspace{4mm}} i\!=\!0,\dots,d\!-\!1$$ (11)

$$V = \sum_{i=0}^d {\scriptscriptstyle\left(\begin{array}{c} d \\ i\end{array}\right)} \alpha_i$$

where $\alpha_i$ is the load computed by one processor of layer $i$; $S,C$ are parameters of the communication links in the homogeneous hypercube network; $A$ is the processing rate of all PEs. Different scattering methods were proposed in [D97]. In one of them the PEs started working on their share of data as soon as it was received instead of waiting for the whole message including data for the following layers. Network processors were re-routing the rest of data to the next layer. In two other algorithms data were first sent from $P_0$ to $P_{2^d-1}$ on the opposite 'end' of the hypercube. Then the hypercube was activated from the directions of the two antipodes. The above three algorithms were advantageous only for hypercubes of dimension 8 and bigger. Other scattering algorithms considered in [D97] turned out to be less efficient.