SIMD data communication algorithms for multiply twisted hypercubes

The paper explores the effectiveness of multiply-twisted hypercube networks for parallel computing by considering interprocessor communication problems. It presents SIMD parallel data broadcasting, census, and shortest path finding algorithms for multiply-twisted hypercube networks. The data broadcasting algorithms take [(n+1)/2] communication steps to broadcast a message from a processor to all other processors in Q_n^MT (an n-dimensional multiply-twisted hypercube and its graph). Each processor performs at most one receive operation to receive the broadcasted message from exactly one of its adjacent processors, and at most one send operation to send the broadcasted message to a subset of its adjacent processors. The data broadcasting algorithms can be easily converted into census algorithms with similar performance. Moreover, it is shown that the data broadcasting algorithms can be used to send a message from any processor P_i to any other processor P_j in a multiply-twisted hypercube in no more than L(i,j)+i communication steps, where L(i,j) is the length of the shortest path from P_i to P_j