EFFICIENT MULTICAST IN ALL-PORT WORMHOLE-ROUTED HYPERCUBES

This paper addresses the problem of collective data distribution, spec ifically multicast, in wormhole-routed hypercubes, The system model al lows a processor to send and receive data in all dimensions simultaneo usly, New theoretical results that characterize contention among messa ges in wormhole-routed hypercubes are developed and used to design new multicast routing algorithms, The algorithms are compared in terms of the number of steps required in each, their measured execution times when implemented on a relatively small-scale nCUBE-2, and their simula ted execution times on larger hypercubes, The results indicate that si gnificant performance improvement is possible when the multicast algor ithm actively identifies and uses multiple ports in parallel. (C) 1995 Academic Press, Inc.