Distributed Procedure for Breadth-First Graph Traversal on Asymmetric Communication Topologies

Patent metadata

Field	Value
Publication number	US-2017346715-A1
Application number	US-201615169074-A
Country	US
Kind code	A1
Filing date	May 31, 2016
Priority date	May 31, 2016
Publication date	Nov 30, 2017
Grant date	—

Abstract

The breadth-first search (BFS) starts with a root node. In the first stage, all neighbors of the root node are discovered and added to the nodes frontier. In the following stages, unvisited nodes from the neighbors of the frontier nodes are discovered and added to the frontier. To improve the parallelization of the BFS, the bottom-up search iterates over all unvisited nodes, where each unvisited node searches for its visited neighbors. Communication between nodes and clusters is pipelined with the execution of the BFS.

First claim

What is claimed is:

1 . A method of distributed graph traversal comprising the steps of:
sending local bitmap B( 0 ) to next cluster; receiving local bitmap B( 1 ) from previous cluster; broadcasting local bitmap B( 0 ) to neighbor nodes within local cluster; executing bottom up (BU) algorithm on neighbor nodes within local cluster; executing the following steps n−1 times where n equals the number of clusters;
waiting for completion of receipt of local bitmap N(n);
waiting for completion of transmission of local bitmap B(n−1);
initiating transmission of local bitmap B(n) to next cluster;
initiating receipt of local bitmap B(n+1) from previous cluster;
broadcasting local bitmap B(n) to local neighbor nodes within the cluster;
executing bottom up (BU) algorithm on neighbor nodes within local cluster.

2 . The method of claim 1 , wherein:
said BU algorithm comprises of the following steps:

Input: Graph, root

Output: parent array

Mark the root node as visited

While not all nodes are visited

  for every node v in the graph

    if v is not visited

      for every neighbor b of v

        if b is visited

          mark v as visited

          set parent[v] = b

          BREAK

        endif

      endfor

    endif.

3 . The method of claim 1 , wherein:
said bitmap transmission and receipt is pipelined with the execution of the BU algorithm.

4 . The method of claim 1 , wherein:
said nodes are connected with a high speed communication link.

5 . The method of claim 1 , wherein:
said clusters are connected with a lower speed communication link.

6 . An apparatus for distributed graph traversal comprising of:
a processor operable to: send the local bitmap B( 0 ) to next cluster; receive the local bitmap B( 1 ) from previous cluster; broadcast local bitmap B( 0 ) to neighbor nodes within local cluster; execute bottom up (BU) algorithm on neighbor nodes within local cluster; execute the following steps n−1 times where n equals the number of clusters; wait for completion of receipt of local bitmap N(n); wait for completion of transmission of local bitmap B(n−1); initiate transmission of local bitmap B(n) to next cluster; initiate receipt of local bitmap B(n+1) from previous cluster; broadcast local bitmap B(n) to local neighbor nodes within the cluster; execute bottom up (BU) algorithm on neighbor nodes within local cluster.

7 . The apparatus of claim 6 , wherein;
said processor is further operable to execute the BU algorithm comprising of the following steps:

Input: Graph, root

Output: parent array

Mark the root node as visited

  While not all nodes are visited

    for every node v in the graph

      if v is not visited

        for every neighbor b of v

          if b is visited

            mark v as visited

            set parent[v] = b

            BREAK

          endif

        endfor

      endif.

8 . The apparatus of claim 6 , wherein:
said processor is further operable to execute said bitmap transmission and reception in a pipelined manner with the execution of the BU algorithm.

9 . The apparatus of claim 6 , wherein:
said nodes are interconnected with a high speed communication link.

10 . The apparatus of claim 6 , wherein:
said clusters are interconnected with a lower speed communication link.

Assignees

• Texas Instruments Inc

Inventors

• Mansour Mohamed Farouk

Classifications

• H04L45/02 Primary

  Topology update or discovery · CPC title

• H04L45/20 Primary

  Hop count for routing purposes, e.g. TTL · CPC title