Efficient topology-aware tree search algorithm for a broadcast operation

Patent metadata

Field	Value
Publication number	US-12483492-B2
Application number	US-202217702652-A
Country	US
Kind code	B2
Filing date	Mar 23, 2022
Priority date	Mar 23, 2022
Publication date	Nov 25, 2025
Grant date	Nov 25, 2025

Abstract

Methods and apparatus for efficient topology-aware tree search algorithm for a broadcast operation. A broadcast tree for a broadcast operation in a network having a hierarchical structure including nodes logically partitioned at group and switch levels. Lists of visited nodes (vnodes) and unvisited nodes (unodes) are initialized. Beginning at a root node, search iterations are performed in a progressive manner to build the tree, wherein a given search iteration finds a unode that can be reached earliest from a vnode, moves the unode that is found from the unode list to the vnode list and adds new unodes to the unode list based on the location of the unode. Beginning with the switch the root node is connected to, the algorithm progressively adds nodes from other switches in the root group and then from other groups and switches within those other groups and continues until all nodes have been visited.

First claim

What is claimed is:

1 . A method for building a broadcast tree for a broadcast operation in a network including nodes partitioned into a plurality of groups, each group including one or more switches, each switch coupled to a plurality of nodes, comprising:
obtaining a network topology for the network including a root node; initializing a list of visited nodes (vnodes) and a list of unvisited nodes (unodes), a first vnode comprising the root node; a) searching to find a unode that can be reached earliest from vnodes in the vnode list; b) moving the unode that is found from the unode list to the vnode list; and c) adding new unodes to the unode list based on a location of the unode that is moved to the vnode list; and using selected group leader nodes and selected switch leader nodes during iterations of the search to find unodes that can be reached earliest from vnodes.

2 . The method of claim 1 , further comprising: repeating operations a), b), and c) until all nodes are in the list of visited nodes.

3 . The method of claim 1 , wherein the root node is coupled to a root switch and is in a root group, further comprising:
identifying group leader nodes for respective groups of nodes; and identifying switch leader nodes for sets of nodes coupled to respective switches.

4 . The method of claim 1 , further comprising:
for sets of multiple nodes having a same distance, marking one of the nodes; and for a given search iteration, only considering unodes that are marked when searching to find the unode that can be reached earliest from a vnode.

5 . The method of claim 4 , wherein an overall latency is determined as a sum of a predetermined latency to send a message plus a predetermined latency to receive the message plus a latency that is a function of a distance along a transmission path that is traversed between the vnode and the unode plus latencies added at one or more switches along the transmission path.

6 . The method of claim 1 , wherein searching to find a unode that can be reached earliest from a vnode comprises:
determining an overall latency for sending a message from the vnode to the unode; and when the vnode is not the root node, adding the overall latency that is determined to a time at which the vnode receives the message.

7 . The method of claim 1 , wherein adding new unodes to the unode list based on the location of the unode that is moved to the vnode list comprises:
when the unode is a switch leader node,
adding nodes connected to the same switch as the unode other than the unode; and
marking one of the nodes that is added to participate in at least one subsequent iteration of the search.

8 . The method of claim 1 , further comprising:
determining the list of visited nodes is empty; when there are unvisited switch leader nodes from switches in the group of the unode that is found,
adding switch leader nodes from other switches in the group of the unode; and
marking one of the switch leader nodes to participate on the search.

9 . The method of claim 1 , wherein the broadcast tree that is generated employs a nearest neighbor heuristic.

10 . The method of claim 1 , wherein the broadcast tree that is built is optimized such that it is configured to obtain a minimal overall time to broadcast a message to all the nodes in the network other than the root node.

11 . The method of claim 1 , further comprising:
maintaining min-heaps for vnodes; maintaining min-heaps for unodes; and employing the min-heaps for the vnodes and unodes to select which vnodes and unodes to search on.

12 . One or more non-transitory machine-readable storage mediums having instructions stored thereon configured to be executed on one or more processors to build a broadcast tree for a broadcast operation in a network including nodes partitioned into a plurality of groups, each group including one or more switches, each switch coupled to a plurality of nodes, wherein building the broadcast tree comprises:
retrieving or obtaining a network topology for the network including a root node; initializing a list of visited nodes (vnodes) and a list of unvisited nodes (unodes), a first vnode comprising the root node; a) searching to find a unode that can be reached earliest from vnodes in the vnode list; b) moving the unode that is found from the unode list to the vnode list; c) adding new unodes to the unode list based on a location of the unode that is moved to the vnode list; for sets of multiple nodes having a same distance, marking one of the nodes; and for a given search iteration, only considering unodes that are marked when searching to find the unode that can be reached earliest from a vnode.

13 . The non-transitory machine-readable storage medium of claim 12 , wherein building the broadcast tree via execution of the instructions further comprises repeating operations a), b), and c) until all nodes are in the list of visited nodes.

14 . The non-transitory machine-readable storage medium of claim 12 , wherein searching to find a unode that can be reached earliest from a vnode comprises:
determining respective overall latencies for transmitting a message from the vnode to marked unodes in the unode list; and when the vnode is not the root node, adding the overall latency that is determined to a time at which the vnode receives the message.

15 . The non-transitory machine-readable storage medium of claim 12 , wherein adding new unodes to the unode list based on the location of the unode that is moved to the vnode list comprises:
when the unode is a switch leader node,
adding nodes connected to the same switch as the unode other than the unode; and
marking one of the nodes that is added to participate in at least one subsequent iteration of the search.

16 . The non-transitory machine-readable storage medium of claim 12 , wherein building the broadcast tree via execution of the instructions further comprises:
determining the list of visited nodes is empty; when there are unvisited switch leader nodes from switches in the group of the unode that is found,
adding switch leader nodes from other switches in the group of the unode; and
marking one of the switch leader nodes to participate on the search.

17 . The non-transitory machine-readable storage medium of claim 12 , wherein the broadcast tree is optimized such that it is configured to obtain a minimal overall time to broadcast a message to all the nodes in the network other than the root node.

18 . A system having a plurality of nodes interconnected via a plurality of switches in a network having a hierarchical topology including a group level, a switch level, and node level, wherein the nodes are used to perform distributed processing using broadcast messages, and wherein the system is configured to:
build a broadcast tree that is optimized such that it is configured to obtain a minimal overall time to broadcast a message originating at a root node to all the nodes in the network other than the root node; and employ the broadcast tree for broadcasting messages to perform a distributed processing task, wherein the network has N nodes and S switches, and the broadcast tree is built using an algorithm have a complexity on the order of N*S*S.

19 . The system of claim 18 , wherein the network has a dragonfly topology.

20 . The system of claim 18 , wherein N is greater than 10,000.

21 . The system of claim 18 , wherein the broadcast tree is built by:
obtaining a network

Assignees

• Intel Corp

Inventors

• Zheng Gengbin
• Garzaran Maria

Classifications

• H04L12/18

  for broadcast or conference {, e.g. multicast} · CPC title

• H04L45/02 Primary

  Topology update or discovery · CPC title