# US 2014/0153399 A1 · Multiprocessor communication networks > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0153399 A1 - Document ID: US20140153399A1 - Status: Published application - Kind: A1 - Application number: 12/703,938 - Filed: 2010-02-11 - Published: 2014-06-05 - Earliest claimed: 2010-02-11 - Assignees: Massachusetts Institute of Technology - Inventors: William S. Song - Web page: https://patentgrep.com/patent/US20140153399A1 ## CPC - H04L 47/125: by balancing the load, e.g. traffic engineering - G06F 15/17381: {Two dimensional, e.g. mesh, torus} - G06F 15/17387: {Three dimensional, e.g. hypercubes} - H04L 45/06: {Deflection routing, e.g. hot-potato routing} - H04L 45/12: Shortest path evaluation - H04L 45/24: Multipath - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract 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. ## Claims ### Claim 1 A packet-switching communication network, comprising: a plurality of processor nodes operating concurrently in parallel, each processor node generating messages to be sent simultaneously to a plurality of other processor nodes in the communication network, each message being divided into a plurality of packets having a common destination processor node, each processor node having an arbiter that determines an order in which to forward the packets from that processor node onto the communication network toward their destination processor nodes and a network interface that sends the packets onto the network in accordance with the determined order, the arbiter of each processor node substantially avoiding selecting two packets consecutively from any one of the messages when determining the order in which to forward the packets from that processor node onto the communication network, the order determined by the arbiter of each processor node operating 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. ### Claim 2 (depends on 1) The packet-switching communication network of claim 1, further comprising a router that routes each packet received by the router towards its destination processor node in accordance with a shortest path only algorithm. ### Claim 3 (depends on 1) The packet-switching communication network of claim 1, wherein the arbiter of each processor node determines the order in which to forward the packets by selecting a packet from each message in round-robin fashion. ### Claim 4 (depends on 3) The packet-switching communication network of claim 3, wherein each of the processor nodes starts with a different message from each of the other processor nodes when selecting a packet from each message in round-robin fashion. ### Claim 5 (depends on 1) The packet-switching communication network of claim 1, wherein the arbiter of each processor node determines the order in which to forward the packets by randomly selecting a message from which to take a packet. ### Claim 6 (depends on 1) The packet-switching communication network of claim 1, wherein the order in which to forward the packets is pseudo-random. ### Claim 7 (depends on 1) The packet-switching communication network of claim 1, wherein the order in which to forward the packets has an effect of randomizing packet routing throughout the communication network. ### Claim 8 (depends on 1) The packet-switching communication network of claim 1, wherein, when determining the order, the arbiter selects a first packet from each message before selecting a second packet from each message. ### Claim 9 (depends on 1) The packet-switching communication network of claim 1, wherein each processor node receives a fixed-size message having a plurality of packet slots, removes each packet addressed to that processor node from a packet slot, and inserts a packet addressed to a destination processor node into an empty packet slot. ### Claim 10 (depends on 1) The packet-switching communication network of claim 1, wherein each processor node takes priority of a packet into consideration when determining the order. ### Claim 11 (depends on 1) The packet-switching communication network of claim 1, wherein the processor nodes are cooperatively performing parallel processing of a graph algorithm. ### Claim 12 (depends on 1) The packet-switching communication network of claim 1, wherein the determined order further operates to substantially avoid sending near-consecutive packets from a given source processor node to a given destination processor node. ### Claim 13 A processor node in a parallel multiprocessor system, comprising: a processor generating messages to be sent simultaneously to a plurality of destination processor nodes over communication links in a packet-switching communication network, the processor dividing each message into a plurality of packets having a common destination processor node; an arbiter determining an order in which to forward the packets onto the packet-switching communication network toward their destination processor nodes, the arbiter substantially avoiding selecting two packets consecutively from any one of the messages when determining the order in which to forward the packets onto the packet-switching communication network; and a network interface sending the packets onto the network in accordance with the determined order, the determined order operating to substantially avoid sending consecutive packets from the processor node to a given destination processor node and to randomize the destination processor nodes of those packets presently traversing the communication network. ### Claim 14 (depends on 13) The processor node of claim 13, further comprising a router that routes each packet toward its destination processor node in accordance with a shortest path only algorithm. ### Claim 15 (depends on 13) The processor node of claim 13, wherein the arbiter determines the order in which to forward the packets by selecting a packet from each message in round-robin fashion. ### Claim 16 (depends on 15) The processor node of claim 15, wherein the arbiter starts with a different message from each other processor node in the communication network when selecting a packet from each message in round-robin fashion. ### Claim 17 (depends on 13) The processor node of claim 13, wherein the arbiter determines the order in which to forward the packets by randomly selecting a message from which to take a packet. ### Claim 18 (depends on 13) The processor node of claim 13, wherein the order in which to forward the packets is pseudo-random. ### Claim 19 (depends on 13) The processor node of claim 13, wherein the order in which to forward the packets has an effect of randomizing packet routing throughout the communication network. ### Claim 20 (depends on 13) The processor node of claim 13, wherein, when determining the order, the arbiter selects a first packet from each message before selecting a second packet from each message. ### Claim 21 (depends on 13) The processor node of claim 13, wherein the network interface receives a fixed-size message having a plurality of packet slots, removes each packet addressed to the processor node from a packet slot, inserts a packet addressed to a destination processor node into an empty packet slot, and forwards the message. ### Claim 22 (depends on 13) The processor node of claim 13, wherein the arbiter takes priority of a packet into consideration when determining the order. ### Claim 23 (depends on 13) The processor node of claim 13, wherein the determined order further operates to substantially avoid sending near-consecutive packets from a given source processor node to a given destination processor node. ### Claim 24 In a parallel multiprocessor system, a method for exchanging messages among processor nodes interconnected by a packet-switching communication network, the method comprising: identifying data to be sent simultaneously to a plurality of destination processor nodes; generating a message for each destination processor node of the plurality of destination processor nodes for carrying the data to that destination processor node; dividing each message into a plurality of packets having a common destination processor node; determining an order in which to forward the packets onto the communication network toward their destination processor nodes that substantially avoids sending consecutive packets from a given source processor node to a given destination processor node and randomizes the destination processor nodes of those packets presently traversing the communication network by substantially avoiding selecting two packets consecutively from any one of the messages. ### Claim 25 (depends on 24) The method of claim 24, further comprising routing each packet toward the destination processor node of that packet in accordance with a shortest path only algorithm. ### Claim 26 (depends on 24) The method of claim 24, wherein determining the order in which to forward the packets includes selecting a packet from each message in round-robin fashion. ### Claim 27 (depends on 24) The method of claim 24, wherein determining the order in which to forward the packets includes randomly selecting each message from which to take a packet. ### Claim 28 (depends on 24) The method of claim 24, wherein the order in which to forward the packets is pseudo-random. ### Claim 29 (depends on 24) The method of claim 24, wherein the order in which to forward the packets has an effect of randomizing packet routing throughout the communication network. ### Claim 30 (depends on 24) The method of claim 24, wherein determining the order includes selecting a first packet from each message before selecting a second packet from each message. ### Claim 31 (depends on 24) The method of claim 24, wherein the order in which to forward the packets further operates to substantially avoid sending near-consecutive packets from a given source processor node to a given destination processor node.