Invention Grant
- Patent Title: Distributed procedure for breadth-first graph traversal on asymmetric communication topologies
-
Application No.: US15169074Application Date: 2016-05-31
-
Publication No.: US10355970B2Publication Date: 2019-07-16
- Inventor: Mohamed Farouk Mansour
- Applicant: Texas Instruments Incorporated
- Applicant Address: US TX Dallas
- Assignee: TEXAS INSTRUMENTS INCORPORATED
- Current Assignee: TEXAS INSTRUMENTS INCORPORATED
- Current Assignee Address: US TX Dallas
- Agent Kenneth Liu; Charles A. Brill; Frank D. Cimino
- Main IPC: H04L12/733
- IPC: H04L12/733 ; H04L12/751

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.
Public/Granted literature
- US20170346715A1 Distributed Procedure for Breadth-First Graph Traversal on Asymmetric Communication Topologies Public/Granted day:2017-11-30
Information query