SIMD data communication algorithms for multiply twisted hypercubes
Si-Qing Zheng · 2002
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/sub n//sup 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/sub i/ to any other processor P/sub 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/sub i/ to P/sub j/.>