Fundamental Operations

In a data broadcast we begin with data in the A register of processor zero of the hypercube. This data is to be transmitted to the A register of each of the remaining processors in the hypercube. This may be accomplished using the binary tree transmitting scheme of Figure 2.1. This figure is for the case of a dimension 3 hypercube. The data to be broadcast is initially only in processor 0 (root of the broadcast tree). It is transmitted along bit 0 to processor 1 (001). This is denoted by the arrow from the root to its right child. Now processors 0 and 1 (level 2 processors) have the data. Both transmit along bit 1. The data is now contained in all level 3 processors (0, 2, 1, 3). These processors now send the data to their neighbor processors along bit 2. As a result, all processors in the hypercube have the data.