CCC has lower hardware complexity than hypercube and is suited for current VLSI technology LC-permutations are a large set of important permutations frequently used in various parallel computations. Existing routing a...CCC has lower hardware complexity than hypercube and is suited for current VLSI technology LC-permutations are a large set of important permutations frequently used in various parallel computations. Existing routing algorithms for CCC cannot realize LC-permutations without network conflict. Wepresent an algorithm to realize LC-permutations on CCC. The algorithm consists of two periods of inter-cycle transmissions and one period of inner-cycletransmissions. In the inter-cycle transmissions the dimensional links of CCCare used in a 'pipeline' manner and in the innercycle transmissions the datapackets are sorted by a part of its destination address. The algorithm is fast(O(log2 N)) and no conflict will occur.展开更多
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...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.展开更多
文摘CCC has lower hardware complexity than hypercube and is suited for current VLSI technology LC-permutations are a large set of important permutations frequently used in various parallel computations. Existing routing algorithms for CCC cannot realize LC-permutations without network conflict. Wepresent an algorithm to realize LC-permutations on CCC. The algorithm consists of two periods of inter-cycle transmissions and one period of inner-cycletransmissions. In the inter-cycle transmissions the dimensional links of CCCare used in a 'pipeline' manner and in the innercycle transmissions the datapackets are sorted by a part of its destination address. The algorithm is fast(O(log2 N)) and no conflict will occur.
基金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.
