Data broadcasting and reduction, prefix computation, and sorting on reduced hypercube (RH) parallel computers

The binary hypercube parallel computer has been very popular due to its rich interconnection structure and small average internode distance which allow the efficient embedding of frequently used topologies. Communication patterns of many parallel algorithms also match the hypercube topology. The hypercube has high VLSI complexity. however. due to the logarithmic increase in the number of connections to each node with the increase in the number of dimensions of the hypercube. The reduced hypercube (RH) interconnection network. which is obtained by a uniform reduction in the number of links for each hypercube node. yields lower-complexity interconnection networks when compared to hypercubes with the same number of nodes. It has been shown elsewhere that the RH interconnection network achieves performance comparable to that of the hypercube. at lower hardware cost. The reduced VLSI complexity of the RH also permits the construction of larger systems. thus. making the RH suitable for massively parallel processing. This thesis proposes algorithms for data broadcasting and reduction. prefix computation, and sorting on the RH parallel computer. All these operations are fundamental to many parallel algorithms. A worst case analysis of each algorithm is given and compared with equivalent- algorithms for the regular hypercube. It is shown that the proposed algorithms for the RH yield performance comparable to that for the regular hypercube