Load balancing computations in a multiprocessor system
AssigneeSun Microsystems, Inc.
InventorWilliam T. Zaumen
Life of this patent
Estimating the term…
Abstract
A system and method for load-balancing routing of a computation within a multiprocessor system. The computation includes multiple branches of execution, not just a linear sequence of steps, and thus cannot be efficiently routed by existing minimum-delay routing schemes. The cost of a single step of the computation is calculated, possibly using a ratio of outgoing data rates from the step to the incoming data rate. That cost may then be scaled for different branches of execution of the computation leading to or from that single step. For example, the calculated cost may be multiplied by each branch's probability of being executed.
Claims21
A computer-implemented method of calculating routing costs for a multi-step computation in a multiprocessor computing system, comprising:
- calculating a link cost at a current step of the computation, wherein said link cost comprises:
- a communication cost of routing data from a current processor configured to execute the current step of the computation to a subsequent processor configured to execute a subsequent step of the computation;
- and
- a link cost at the subsequent step of the computation multiplied by a ratio of data input rates to data output rates at the current processor;
- determining whether multiple paths of execution of the computation exist from the current step;
- and
- if multiple paths of execution exist from the current node, adjusting the calculated link cost by a probability that execution of the computation will follow a path proceeding directly from the current step to the subsequent step.
A computer readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of calculating routing costs for a multi-step computation in a multiprocessor computing system, comprising:
- calculating a link cost at a current step of the computation, wherein said link cost comprises:
- a communication cost of routing data from a current processor configured to execute the current step of the computation to a subsequent processor configured to execute a subsequent step of the computation;
- and
- a link cost at the subsequent step of the computation multiplied by a ratio of data input rates to data output rates at the current processor;
- determining whether multiple paths of execution of the computation exist from the current step;
- and
- if multiple paths of execution exist from the current node, adjusting the calculated link cost by a probability that execution of the computation will follow a path proceeding directly from the current step to the subsequent step.
A computer-implemented method for load-balanced data routing in a multiprocessor computing system, the method comprising:
- determining a link cost for routing data for a computation through at least one processor node in a multiprocessor computing system in which the computation is executed, the link cost including:
- a communication cost for a given current node configured to execute a first step of the computation;
- a processing node cost for the given current node, the processing node cost including a link cost update from a successor node adjusted by a scaling factor to account for traffic generated by the given current node, wherein the successor node is configured to execute a second step of the computation;
- and
- a probability that said first step of the computation and said second step of the computation will be consecutively executed;
- and
- routing data from a given current node to at least one successor node until a destination node is reached, said routing being in accordance with the determined link costs for the at least one current node in the multiprocessor computing system.
A computer-implemented method for minimizing delay in routing data in a multiprocessor computing system, the method comprising:
- for each current node of the multiprocessor computing system, beginning from a destination node, determining a successor set of nodes to a given current node;
- determining a link cost associated with routing data from the given current node to each node in the successor set, said determining comprising:
- factoring in a scaling factor to account for additional traffic generated by the given current node, the scaling factor comprising a ratio of data input rates to data output rates at the given current node;
- and
- adjusting the link cost by the probability of routing data from the given current node to the node in the successor set;
- and
- at each current node, beginning from a source node, routing data to one or more nodes in a successor set corresponding to the current node, the routing being in accordance with the determined link costs.
A computer-implemented method for minimizing delay in routing data in a multiprocessor computing system configured to execute a non-linear multi-step computation, the method comprising:
- for each current node of the multiprocessor computing system, beginning from a destination node, determining a successor set of successor nodes to a given current node, wherein:
- the given current node corresponds to execution of a first step of the computation;
- and
- a subset of the successor nodes correspond to execution of steps of the computation immediately subsequent to the first step;
- for each successor node in the successor set, calculating a link cost of routing data from the given current node to a successor node, said calculating comprising:
- calculating a processing node cost by adjusting a link cost update from a given successor node by a scaling factor corresponding to the given current node, the scaling factor accounting for additional traffic generated by the given current node;
- combining the processing node cost with a communication cost, the communication cost corresponding to a cost of routing data on a communication channel between the given current node and the given successor node;
- and
- if the given successor node corresponds to execution of a step of the computation immediately subsequent to the given current node, adjusting the link cost by a probability of executing the subsequent step immediately after the first step is executed;
- and
- for each current node between the source node and the destination node in the multiprocessing computing system, including the source node, routing the data from the current node to a successor node in accordance with the determined link costs.
A computer readable medium storing instructions that, when executed by a computer, cause the computer to perform a method for minimizing delay in routing data in a multiprocessor computing system configured to execute a non-linear multi-step computation, the method comprising:
- for each current node of the multiprocessor computing system, beginning from a destination node, determining a successor set of successor nodes to a given current node, wherein:
- the given current node corresponds to execution of a first step of the computation;
- and
- a subset of the successor nodes correspond to execution of steps of the computation immediately subsequent to the first step;
- for each successor node in the successor set, calculating a link cost of routing data from the given current node to a successor node, said calculating comprising:
- calculating a processing node cost by adjusting a link cost update from a given successor node by a scaling factor corresponding to the given current node, the scaling factor accounting for additional traffic generated by the given current node;
- combining the processing node cost with a communication cost, the communication cost corresponding to a cost of routing data on a communication channel between the given current node and the given successor node;
- and
- if the given successor node corresponds to execution of a step of the computation immediately subsequent to the given current node, adjusting the link cost by a probability of executing the subsequent step immediately after the first step is executed;
- and
- for each current node between the source node and the destination node in the multiprocessing computing system, including the source node, routing the data from the current node to a successor node in accordance with the determined link costs.
Dependencies are inferred from the claim text.