Title :
Average distance and routing algorithms in the star-connected cycles interconnection network
Author :
De Azevedo, Marcelo Moraes ; Bagherzadeh, Nader ; Dowd, Martin ; Latifi, S. Hahram
Author_Institution :
Dept. of Electr. & Comput. Eng., California Univ., Irvine, CA, USA
Abstract :
The star-connected cycles (SCC) graph was recently proposed as an attractive interconnection network for parallel processing, using a star graph to connect cycles of nodes. The paper presents an analytical solution for the problem of the average distance of the SCC graph. They divide the cost of a route in the SCC graph into three components, and show that one of such components is affected by the routing algorithm being used. Three routing algorithms for the SCC graph are presented, which respectively employ random, greedy and minimal routing rules. The computational complexities of the algorithms, and the average costs of the paths they produce, are compared. Finally, they discuss how the algorithms presented in the paper can be used in association with wormhole routing
Keywords :
computational complexity; graph theory; multiprocessor interconnection networks; network routing; parallel algorithms; average distance; average path costs; computational complexities; greedy routing rules; minimal routing rules; node cycle connection; parallel processing; random routing rules; routing algorithms; star-connected cycle graph; star-connected cycles interconnection network; wormhole routing; Communication switching; Computer networks; Concurrent computing; Costs; Delay; Intelligent networks; Multiprocessor interconnection networks; Network topology; Routing; Switching circuits;
Conference_Titel :
Parallel and Distributed Processing, 1996., Eighth IEEE Symposium on
Conference_Location :
New Orleans, LA
Print_ISBN :
0-8186-7683-3
DOI :
10.1109/SPDP.1996.570367
