AN EFFECTIVE MULTICAST WORMHOLE ROUTEING IN HYPERCUBES

Efficient routeing of messages is critical to the performance of hypercube computers. Commercial hypercube computers have only supported one-to-one and one-to-all message passing. More recently, the demand of multicast communication is increasing in many parallel programs, including simulation of computer networks and electronic circuits, particle dynamic calculations, and image processing. It is desirable to have efficient mechanisms for routeing multicast messages. Wormhole routeing is becoming the most promising switching techniques in more advanced multicomputers. A dual-path routeing algorithm has been proposed for routeing multicast messages with deadlock-free in wormhole-routeing hypercubes. However, it has been found that there exists unbalanced traffic in the systems which results in a significant performance degradation. In this paper, we develop an effective single-path routeing algorithm so as to achieve balanced traffic in the systems, and yet prevent deadlocks. The simulation results indicate that the mean latency for a single-path routeing algorithm is significantly reduced owing to balanced traffic when the system load grows. This significant reduction in latency could translate to a respectable performance improvement.