SIMD data communication algorithms for multiply twisted hypercubes

摘要

The paper explores the effectiveness of multiply-twisted hypercubenetworks for parallel computing by considering interprocessorcommunication problems. It presents SIMD parallel data broadcasting,census, and shortest path finding algorithms for multiply-twistedhypercube networks. The data broadcasting algorithms take[(n+1)/2] communication steps to broadcast a message from aprocessor 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 thebroadcasted message from exactly one of its adjacent processors, and atmost one send operation to send the broadcasted message to a subset ofits adjacent processors. The data broadcasting algorithms can be easilyconverted into census algorithms with similar performance. Moreover, itis shown that the data broadcasting algorithms can be used to send amessage from any processor P_i to any other processorP_j in a multiply-twisted hypercube in no more thanL(i,j)+i communication steps, whereL(i,j) is the length of the shortest pathfrom P_i to P_j