An efficient implementation of tree-based multicast routing for distributed shared-memory multiprocessors

This paper presents an efficient routing and flow control mechanism to impl ement multidestination message passing in wormhole networks. The mechanism is a variation of tree-based multicast with pruning to recover from deadloc ks and it is well suited for distributed shared-memory multiprocessors (DSM s) with hardware cache coherence. It does not require any preprocessing of multicast messages reducing notably the software overhead required to send a multicast message. Also, it allows messages to use any deadlock-free rout ing function. The new scheme has been evaluated by simulation using synthet ic loads. It achieves multicast latency reductions of 30% on average. Also it was compared with other multicast mechanisms proving its benefits. Final ly, it can be easily implemented in hardware with minimal changes to existi ng unicast wormhole routers. (C) 2000 Elsevier Science B.V. All rights rese rved.