An Optimal Multicast Algorithm for Cube-Connected Cycles  

作　　者：宋建平 侯紫峰 史云涛 

出　　处：《Journal of Computer Science & Technology》2000年第6期572-583,共12页计算机科学技术学报（英文版）

基　　金：The work of this paper is supported by the National Natural Science Foundation of China under grant ! No.69896250.

摘　　要：This paper presents an efficient algorithm that implements one to-many, or multicast, communication in one-port wormhole-routed cube-connected cycles (CCCs) in the absence of hardware multicast support. By exploiting the properties of the switching technology and the use of virtual channels, a minimumtime multicast algorithm is presented for n-dimensional CCCs that use deterministic routing of unicast messages. The algorithm can deliver a multicast message to m - 1 destinations in [log2, m] message-passing steps, while avoiding contention among the constituent unicast messages. Performance results of a simulation study on CCCs with up to 10,240 nodes are also given.This paper presents an efficient algorithm that implements one to-many, or multicast, communication in one-port wormhole-routed cube-connected cycles (CCCs) in the absence of hardware multicast support. By exploiting the properties of the switching technology and the use of virtual channels, a minimumtime multicast algorithm is presented for n-dimensional CCCs that use deterministic routing of unicast messages. The algorithm can deliver a multicast message to m - 1 destinations in [log2, m] message-passing steps, while avoiding contention among the constituent unicast messages. Performance results of a simulation study on CCCs with up to 10,240 nodes are also given.

关 键 词：MULTICAST cube-connected cycle wormhole routing dimensionordered routing one-port architecture 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]