Multiscattering on the cube-connected cycles

✍ Scribed by Jian-jin Li

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 589 KB
• Volume: 20
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(06)80015-3

✦ Synopsis

This paper presents several multiscattering algorithms on the Cube-Connected Cycles (CCC). We first implement a network-independent greedy algorithm. Then we propose two specialized algorithms for multiscattering on the CCC: the first approach uses only one hypercube link of each cycle, but the second approach uses all hypercube links at each phase. The theoretical formulas given in this paper show that multiscattering on the CCC with N ---H*2 s (H >__ S) processors can be performed in time [(H + 1)S + 1H/2]]/3 + [(H + 1)SH + [H/2J([H/2] + 1)]2S-lLz or [2S + tS/21]/3 + [(S 2 -1)2 s + ls/2J(ts/21 + 1)2 s-1 + 1]L~-, where L is the message length, fl is the startup and ~-is the inverse of the bandwidth of communication. The difference between the complexity of the two approaches is due to the number of hypercube links used at each phase. We carry out experiments with the greedy algorithm on the ring and the exchange-perfect shuffle, and we compare the two multiscattering algorithms on the CCC with the greedy algorithm and the non-oriented ring algorithm on a transputer-based machine with 32 processors.