Intel Corporation
EFFICIENT TOPOLOGY-AWARE TREE SEARCH ALGORITHM FOR A BROADCAST OPERATION

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.