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

@

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


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

Full Text () Retrieve PDF document (200303_01.pdf)

Received June 22, 2000; revised November 29, 2000, May 8 & June 26, 2001; accepted July 23, 2001.
Communicated by Gen-Huey Chen.
*This work was partially supported by the National Science Council of the Republic of China under contact NSC 84-2213-E-110-005.