Back to results
US 9,003,419 B2Granted
Network balancing procedure that includes redistributing flows on arcs incident on a batch of vertices
AssigneeHewlett-Packard Development Company, L.P.
InventorsBin Zhang, Meichun Hsu, Ren Wu
Life of this patent
Estimating the term…
Abstract
A representation of a flow network having vertices connected by arcs is provided. The vertices include a first set of vertices that provide flow to a second set of vertices over arcs connecting the first set and second set of vertices. A balancing procedure in the network is performed that includes redistributing flows on arcs incident on the second set of vertices. The balancing procedure includes selecting a batch of the vertices in the second set, and redistributing flows on arcs incident on the selected batch of vertices. The selecting and redistributing are repeated for other batches of vertices in the second set.
Claims14
A method comprising:
- providing a representation of a flow network comprising a first set of vertices that provide flow to a second set of vertices over arcs connecting the first set and second set of vertices;
- performing, by a computer system, a balancing procedure in the flow network that includes redistributing flows on arcs incident on the second set of vertices, wherein the balancing procedure comprises:
- selecting a batch of the vertices in the second set;
- redistributing flows on arcs incident on the selected batch of vertices, wherein the redistributing comprises:
- reading flows incident on at least a portion of the first set of vertices;
- using the flows incident on the at least the portion of the first set of vertices to update the flows on the arcs incident on the selected batch of vertices;
- and
- updating at least some of the flows incident on the at least the portion of the first set of vertices in response to the updated flows on the arcs incident on the selected batch of vertices,
- wherein the reading, using, and updating are performed by plural threads executing in the computer system;
- repeating the selecting and redistributing for other batches of vertices in the second set;
- and
- establishing synchronization to prevent the updating of the at least some of the flows incident on the at least the portion of the first set of vertices from being performed by any of the plural threads until each of the threads has completed the reading.
9 more elements
A computer system comprising:
- a storage media to store a representation of a flow network comprising a first set of vertices that provide flow to a second set of vertices over arcs connecting the first set and second set of vertices;
- and
- one or more processors to:
- select a batch of the vertices from the second set;
- redistribute flows on arcs incident on the selected batch of vertices, wherein the redistributing is performed by a plurality of threads corresponding to the respective vertices of the selected batch, wherein the redistributing comprises:
- reading flows incident on at least a portion of the first set of vertices;
- using the flows incident on the at least the portion of the first set of vertices to update the flows on the arcs incident on the selected batch of vertices;
- and
- updating at least some of the flows incident on the at least the portion of the first set of vertices in response to the updated flows on the arcs incident on the selected batch of vertices;
- repeat the selecting and redistributing until flow in the flow network is balanced;
- and
- perform synchronization to ensure that all of the plurality of threads have completed the reading before the updating by any of the plurality of threads is started.
9 more elements
An article comprising at least one non-transitory computer-readable storage medium containing instructions that upon execution cause a computer system to:
- provide a representation of a flow network comprising a first set of vertices that provide flow to a second set of vertices of the flow network over arcs connecting the first set and second set of vertices;
- perform, in parallel, flow redistribution on arcs incident on a selected batch of vertices in the second set, wherein performing the flow redistribution comprises:
- reading flows incident on at least a portion of the first set of vertices;
- using the flows incident on the at least the portion of the first set of vertices to update flows on the arcs incident on the selected batch of vertices;
- and
- updating at least some of the flows incident on the at least the portion of the first set of vertices in response to the updated flows on the arcs incident on the selected batch of vertices;
- iteratively select different batches of vertices in the second set and reiterating the flow redistribution on each of the iteratively selected batch of vertices for balancing the flow network,
- wherein performing the flow redistribution is performed by a plurality of threads for corresponding vertices of each selected batch;
- and
- perform synchronization to ensure that a reading phase in the flow redistribution is completed by each of the plurality of threads before a writing phase in the flow redistribution is begun by any of the plurality of threads.
7 more elements
Dependencies are inferred from the claim text.