Invention Grant
- Patent Title: Vectorized queues for shortest-path graph searches
-
Application No.: US16803832Application Date: 2020-02-27
-
Publication No.: US11630864B2Publication Date: 2023-04-18
- Inventor: Benjamin Schlegel , Martin Sevenich , Pit Fender , Matthias Brantner , Hassan Chafi
- Applicant: Oracle International Corporation
- Applicant Address: US CA Redwood Shores
- Assignee: Oracle International Corporation
- Current Assignee: Oracle International Corporation
- Current Assignee Address: US CA Redwood Shores
- Agency: Hickman Becker Bingham Ledesma LLP
- Main IPC: G06F16/901
- IPC: G06F16/901 ; G06F9/38 ; G06F9/54

Abstract:
Techniques are described for a vectorized queue, which implements a vectorized ‘contains’ function that determines whether a value is in the queue. A three-phase vectorized shortest-path graph search splits each expanding and probing iteration into three phases that utilize vectorized instructions: (1) The neighbors of nodes that are in a next queue are fetched and written into a current queue. (2) It is determined whether the destination node is among the fetched neighbor nodes in the current queue. (3) The fetched neighbor nodes that have not yet been visited are put into the next queue. According to an embodiment, a vectorized copy operation performs vector-based data copying using vectorized load and store instructions. Specifically, vectors of data are copied from a source to a destination. Any invalid data copied to the destination is overwritten, either with a vector of additional valid data or with a vector of nonce data.
Public/Granted literature
- US20210271711A1 VECTORIZED QUEUES FOR SHORTEST-PATH GRAPH SEARCHES Public/Granted day:2021-09-02
Information query