Efficient Multiprocessor Communication Networks

A parallel multiprocessor system includes a packet-switching communication network comprising a plurality of processor nodes operating concurrently in parallel. Each processor node generates messages to be sent simultaneously to a plurality of other processor nodes in the communication network. Each message is divided into a plurality of packets having a common destination processor node. Each processor node has an arbiter that determines an order in which to forward the packets onto the network toward their destination processor nodes and a network interface that sends the packets onto the network in accordance with the determined order. The determined order operates to substantially avoid sending consecutive packets from a given source processor node to a given destination processor node and to randomize the destination processor nodes of those packets presently traversing the communication network.