Deadlock free all-to-all collective communication schedules
AssigneeRtx Bbn Technologies, Inc.
InventorsPrithwish Basu, Joud Khoury
Life of this patent
Estimating the term…
Abstract
This disclosure relates to determining a first bandwidth of one or more first links for one or more nodes in the network; determining a second bandwidth of one or more second links for the one or more nodes; determining that a demand constraint has been met on the network; and determining that a conservation constraint has been met on the network.
Claims20
A method of preventing deadlock in a network, the method comprising:
- determining a first bandwidth of one or more first links for one or more nodes in the network;
- determining a second bandwidth of one or more second links for the one or more nodes;
- determining that a demand constraint has been met on the network;
- and
- determining that a conservation constraint has been met on the network, wherein determining that the conservation constraint has been met comprises, for each link in a channel dependency graph of the network:
- simultaneously determining an amount of fictitious flow along the link and a link capacity associated with the link;
- and
- determining that the amount of fictitious flow along the link is less than or equal to the link capacity associated with the link.
A non-transitory computer-readable medium containing thereon computer-executable instructions for instructing at least one processor to prevent deadlock on a network, the instructions instructing the at least one processor to:
- determine a first bandwidth of one or more first links for one or more nodes in the network;
- determine a second bandwidth of one or more second links for the one or more nodes;
- determine whether a demand constraint has been met on the network;
- and
- determine whether a conservation constraint has been met on the network, wherein the instructions for instructing the at least one processor to determine that the conservation constraint has been met further instruct the at least one processor to, for each link in a channel dependency graph of the network:
- simultaneously determine an amount of fictitious flow along the link and a link capacity associated with the link;
- and
- determine that the amount of fictitious flow along the link is less than or equal to the link capacity associated with the link.
A system for preventing deadlocks on a network, the system comprising:
- a first cluster including one or more nodes having one or more intracluster connections;
- a second cluster having at least one intercluster connection to the first cluster, the second cluster including one or more nodes having one or more intracluster connections;
- and
- a controller coupled to the network and configured to control the network by:
- determining a first bandwidth of one or more first links for one or more nodes in the network;
- determining a second bandwidth of one or more second links for the one or more nodes;
- determining that a demand constraint has been met on the network;
- and
- determining that a conservation constraint has been met on the network, wherein determining that the conservation constraint has been met comprises, for each link in a channel dependency graph of the network:
- simultaneously determining an amount of fictitious flow along the link and a link capacity associated with the link;
- and
- determining that the amount of fictitious flow along the link is less than or equal to the link capacity associated with the link.
Dependencies are inferred from the claim text.