System for randomly modifying virtual channel allocation and accepting the random modification based on the cost function

Claim 3

The method of claim 1 further comprising the step of predicting a traffic distribution of messages though the multiprocessor computer system, and wherein the cost function is based on the predicted traffic distribution.

Claim 4

The method of claim 2 wherein the steps of predicting the traffic distribution and defining the cost function are performed to account for a partitioned workload.

Claim 5

The method of claim 1 further comprising the steps of: generating routing information having the modified virtual channel allocation stored therein; and routing the messages between the processing dement nodes based on the routing information.

Claim 6

The method of claim 1 wherein the step of restraining includes the step of logically pre-scheduling messages to virtual channels such that any message that would cross the dateline associated to the first type of virtual channel is pre-scheduled to the second type of virtual channel and any message that would cross the dateline associated to the second type of virtual channel is pre-scheduled to the first type of virtual channel.

Claim 7

The method of claim 1 wherein one dateline is associated to both types of virtual channels, and wherein the step of restraining includes the steps of: assigning all messages that will be routed across the one dateline to the first type of virtual channel; and switching the messages from the first type of virtual channel to the second type of virtual channel when a message crosses the one dateline.

Claim 8

The method of claim 6 further comprising the step of providing an error signal if a message attempts to cross the one dateline from the second type of virtual channel.

Claim 9

A multiprocessor computer system comprising: a plurality of processing element nodes; physical communication links interconnecting the processing element nodes in an n-dimensional topology; two types of virtual channels, each type of virtual channel having virtual channel buffers assigned to each physical communication link and capable of storing messages communicated between the processing element nodes over the physical communication links, wherein a dateline is associated with each type of virtual channel, each dateline representing a communication link between two virtual channel buffers, which complete a cyclic path in their associated type of virtual channel wherein if messages cross the dateline a cyclic buffer dependency can occur which creates a deadlock; means for restraining messages from crossing a dateline on its associated type of virtual channel to avoid deadlock; and means for assigning unrestrained messages between the two types of virtual channels based on calculated virtual channel allocation information which minimizes a defined cost function correlated to imbalances in the utilization of the two types of virtual channels by defining an initial virtual channel allocation and randomly modifying the initial virtual channel allocation, wherein the random modification is accepted if the modification decreases the cost function, and is otherwise accepted based on a probability that slowly decreases during the allocating step.

Claim 10

A multiprocessor computer system comprising: a plurality of processing element nodes; physical communication links interconnecting the processing element nodes in an n-dimensional topology; two types of virtual channels, each type of virtual channel having virtual channel buffers assigned to each physical communication link and capable of storing messages communicated between the processing element nodes over the physical communication links, wherein a dateline is associated with each type of virtual channel, each dateline representing a communication link between two virtual channel buffers, which complete a cyclic path in their associated type of virtual channel wherein if messages cross the dateline a cyclic buffer dependency can occur which creates a deadlock; means for restraining messages from crossing a dateline on its associated type of virtual channel to avoid deadlock; and means for assigning unrestrained messages between the two types of virtual channels based on calculated virtual channel allocation information which minimizes a defined cost function correlated to imbalances in the utilization of the two types of virtual channels by defining an initial virtual channel allocation and randomly modifying the initial virtual channel allocation, wherein the random modification is accepted if the modification decreases the cost function, and is otherwise accepted based on a probability that slowly decreases during the allocating step.

Claim 11

The multiprocessor computer system of claim 8 wherein the means for assigning unrestrained messages comprises a virtual channel look-up table, wherein routing information in said virtual channel look-up table includes the calculated virtual channel allocation information.

Claim 12

The multiprocessor computer system of claim 9 further comprising a network router coupled to the virtual channel look-up table for transferring the messages through the multiprocessor computer system based on the routing information.

Claim 13

The multiprocessor computer system of claim 8 wherein the means for restraining includes means for logically pre-scheduling messages to virtual channels such that any message that would cross the dateline associated to the first type of virtual channel is pre-scheduled to the second type of virtual channel and any message that would cross the dateline associated to the second type of virtual channel is pre-scheduled to the first type of virtual channel.

Claim 14

The multiprocessor computer system of claim 8 wherein one dateline is associated to both types of virtual/channels, and wherein the means for restraining includes: means for assigning all messages that will be routed across the one dateline to the first type of virtual channel; and switching means for physically switching the messages from the first type of virtual channel to the second type of virtual channel when a message crosses the one dateline.

Claim 15

The multiprocessor computer system of claim 12 further comprising means for providing an error signal if a message attempts to cross the one dateline from the second type of virtual channel.