JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]


Journal of Information Science and Engineering, Vol. 19 No. 2, pp. 183-203


Broadcasting on Uni-directional Hypercubes and Its Applications


Huang-Ming Huang, Chang-Biau Yang and Kuo-Tsung Tseng
Department of Computer Science and Engineering 
National Sun Yat-Sen University 
Kaohsiung, 804 Taiwan 
E-mail: cbyang@cse.nsysu.edu.tw


    In this paper, we present three kinds of broadcasting tree for the even dimensional uni-directional hypercube (UHC) and its applications (ASCEND/DESCEND algorithms and bitonic sorting). For the n-dimensional UHC, under the constant evaluation model, one of our all-port broadcasting trees has height n + 1, which is optimal. Whereas the best one of our one-port broadcasting trees needs at most steps steps exactly). We also propose an all-port fault-tolerant broadcasting tree (a family of arc-disjoint spanning trees) whose height is no more than At last, we show that the SCEND/DESCEND algorithms and bitonic sorting can be implemented in the UHC with the same complexity as the hypercube under the half duplex mode. All of our algorithms can be easily applied to the odd dimensional UHC.


Keywords: interconnection network, uni-directional hypercube, broadcasting, fault-tolerance, ASCEND/DESCEND

  Retrieve PDF document (JISE_200302_01.pdf)