公开(公告)号：US20210271710A1

公开(公告)日：2021-09-02

申请号：US16803819

申请日：2020-02-27

Applicant: Oracle International Corporation

Inventor： Benjamin Schlegel ,  Martin Sevenich ,  Pit Fender ,  Matthias Brantner ,  Hassan Chafi

IPC: G06F16/901 ,  G06F9/38

Abstract: Techniques are described herein for a vectorized hash table that uses very efficient grow and insert techniques. A single-probe hash table is grown via vectorized instructions that split each bucket, of the hash table, into a respective upper and lower bucket of the expanded hash table. Further, vacant slots are indicated using a vacant-slot-indicator value, e.g., ‘0’, and all vacant slots follow to the right of all occupied slots in a bucket. A vectorized compare instruction determines whether a value is already in the bucket. If not, the vectorized compare instruction is also used to determine whether the bucket has a vacant slot based on whether the bucket contains the vacant-slot-indicator value. To insert the value into the bucket, vectorized instructions are used to shift the values in the bucket to the right by one slot and to insert the new value into the left-most slot.

公开(公告)号：US20200133663A1

公开(公告)日：2020-04-30

申请号：US16176853

申请日：2018-10-31

Applicant: Oracle International Corporation

Inventor： Martijn Dwars ,  Martin Sevenich ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F8/75 ,  G06F8/51 ,  G06F17/30 ,  G06F8/30 ,  G06F8/41

Abstract: Techniques are described herein for automatic generation of multi-source breadth-first search (MS-BFS) from high-level graph processing language that can be executed in a distributed computing environment. In an embodiment, a method involves a computer analyzing original software instructions. The original software instructions are configured to perform multiple breadth-first searches to determine a particular result. Each breadth-first search originates at each of a subset of vertices of a graph. Each breadth-first search is encoded for independent execution. Based on the analyzing, the computer generates transformed software instructions configured to perform a MS-BFS to determine the particular result. Each of the subset of vertices is a source of the MS-BFS. In an embodiment, the second plurality of software instructions comprises a node iteration loop and a neighbor iteration loop, and the plurality of vertices of the distributed graph comprise active vertices and neighbor vertices. The node iteration loop is configured to iterate once per each active vertex of the plurality of vertices of the distributed graph, and the node iteration loop is configured to determine the particular result. The neighbor iteration loop is configured to iterate once per each active vertex of the plurality of vertices of the distributed graph, and each iteration of the neighbor iteration loop is configured to activate one or more neighbor vertices of the plurality of vertices for the following iteration of the neighbor iteration loop.

公开(公告)号：US20180307777A1

公开(公告)日：2018-10-25

申请号：US15495193

申请日：2017-04-24

Applicant: Oracle International Corporation

Inventor： Martin Sevenich ,  Sungpack Hong ,  Alexander Weld ,  Hassan Chafi ,  Daniel Lehmann

IPC: G06F17/30

CPC classification number: G06F16/9024 ,  G06F16/23 ,  G06F16/90335

Abstract: Techniques herein minimize memory needed to store distances between vertices of a graph for use during a multi-source breadth-first search (MS-BFS). In an embodiment, during each iteration of a first sequence of iterations of a MS-BFS, a computer updates a first matrix that contains elements that use a first primitive integer type having a first width to record a distance from a source vertex of a graph to another vertex. The computer detects that a count of iterations of the first sequence of iterations exceeds a threshold. Responsively, the computer creates a second matrix that contains elements that use a second primitive integer type having a second width that is larger than the first width to record a distance from a source vertex of the graph to another vertex. During each iteration of a second sequence of iterations of the MS-BFS, the computer updates the second matrix.

公开(公告)号：US10019536B2

公开(公告)日：2018-07-10

申请号：US14332182

申请日：2014-07-15

Applicant: Oracle International Corporation

Inventor： Sungpack Hong ,  Zhe Wu ,  Martin Sevenich ,  Jayanta Banerjee ,  Hassan Chafi ,  Korbinian Schmid

IPC: G06F7/00 ,  G06F17/30

CPC classification number: G06F16/9024 ,  G06F16/2246 ,  G06F2201/80

Abstract: Techniques for storing and processing graph data in a database system are provided. Graph data (or a portion thereof) that is stored in persistent storage is loaded into memory to generate an instance of a particular graph. The instance is consistent as of a particular point in time. Graph analysis operations are performed on the instance. The instance may be used by multiple users to perform graph analysis operations. Subsequent changes to the graph are stored separate from the instance. Later, the changes may be applied to the instance (or a copy thereof) to refresh the instance.

公开(公告)号：US09971570B2

公开(公告)日：2018-05-15

申请号：US14969231

申请日：2015-12-15

Applicant: Oracle International Corporation

Inventor： Martin Sevenich ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F9/44

CPC classification number: G06F8/456

Abstract: Techniques generate memory-optimization logic for concurrent graph analysis. A computer analyzes domain-specific language logic that analyzes a graph having vertices and edges. The computer detects parallel execution regions that create thread locals. Each thread local is associated with a vertex or edge. For each parallel region, the computer calculates how much memory is needed to store one instance of each thread local. The computer generates instrumentation that determines how many threads are available and how many vertices and edges will create thread locals. The computer generates tuning logic that determines how much memory is originally needed for the parallel region based on how much memory is needed to store the one instance, how many threads are available, and graph size. The tuning logic detects a memory shortage based on the original amount of memory needed exceeding how much memory is available and accordingly adjusts the execution of the parallel region.

公开(公告)号：US09916187B2

公开(公告)日：2018-03-13

申请号：US14524838

申请日：2014-10-27

Applicant: Oracle International Corporation

Inventor： Korbinian Schmid ,  Martin Sevenich ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F17/30 ,  G06F9/50 ,  G06F9/44 ,  G06F9/45 ,  H04L29/08

CPC classification number: G06F9/5083 ,  G06F8/31 ,  G06F8/456 ,  G06F17/30321 ,  G06F17/30386 ,  G06F17/30442 ,  G06F17/30958 ,  H04L67/10

Abstract: Techniques are provided for a graph database system that accepts custom graph analytic programs that are written in a high-level graph-specific programming language and compiles the programs into executables that, when executed, directly access graph data of a graph that is stored in the graph database. In this way, a low-level data-access API is avoided. Also, a graph analytic program, which only describes an abstract description of an algorithm, does not include any details regarding data access. In one technique, a user is not required to include explicit parallelization in a graph analytic program in order for the graph analytic program to take advantage of parallelization. A compiler of the graph database system identifies portions of the graph analytic program that can benefit from parallelization and, in response, generates parallelized executable code that corresponds to those portions.

公开(公告)号：US20150331683A1

公开(公告)日：2015-11-19

申请号：US14276895

申请日：2014-05-13

Applicant: Oracle International Corporation

Inventor： Martin Sevenich ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F9/45

CPC classification number: G06F8/443 ,  G06F8/437

Abstract: An implementation of an abstract data type is automatically selected by a compiler. The compiler chooses an implementation for each instance of an abstract data type in a program based on operations performed in the instance within the program.

Abstract translation: 抽象数据类型的实现由编译器自动选择。 编译器根据程序中的实例执行的操作，在程序中为抽象数据类型的每个实例选择一个实现。

公开(公告)号：US11630864B2

公开(公告)日：2023-04-18

申请号：US16803832

申请日：2020-02-27

Applicant: Oracle International Corporation

Inventor： Benjamin Schlegel ,  Martin Sevenich ,  Pit Fender ,  Matthias Brantner ,  Hassan Chafi

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.

公开(公告)号：US11222070B2

公开(公告)日：2022-01-11

申请号：US16803819

申请日：2020-02-27

Applicant: Oracle International Corporation

Inventor： Benjamin Schlegel ,  Martin Sevenich ,  Pit Fender ,  Matthias Brantner ,  Hassan Chafi

IPC: G06F16/00 ,  G06F16/901 ,  G06F9/38

Abstract: Techniques are described herein for a vectorized hash table that uses very efficient grow and insert techniques. A single-probe hash table is grown via vectorized instructions that split each bucket, of the hash table, into a respective upper and lower bucket of the expanded hash table. Further, vacant slots are indicated using a vacant-slot-indicator value, e.g., ‘0’, and all vacant slots follow to the right of all occupied slots in a bucket. A vectorized compare instruction determines whether a value is already in the bucket. If not, the vectorized compare instruction is also used to determine whether the bucket has a vacant slot based on whether the bucket contains the vacant-slot-indicator value. To insert the value into the bucket, vectorized instructions are used to shift the values in the bucket to the right by one slot and to insert the new value into the left-most slot.

公开(公告)号：US20210240456A1

公开(公告)日：2021-08-05

申请号：US16776792

申请日：2020-01-30

Applicant: Oracle International Corporation

Inventor： Martijn Dwars ,  Martin Sevenich ,  Sungpack Hong ,  Hassan Chafi ,  Guido Wachsmuth

IPC: G06F8/41 ,  G06F8/34 ,  G06F9/30 ,  G06F8/72 ,  G06F9/54

Abstract: Techniques are described for compiling source code to generate graph-optimized intermediate representation instructions of the source code that implement techniques for optimizing algorithms for graph analysis. A compiler, executing on a computing device, receives source code instructions for a program to be compiled. The compiler identifies a target expression, within the source code instructions, that invokes a particular method call on a particular object type. The target expression contains a target block of code to be translated into an intermediate representation using graph-optimized compilation techniques. The compiler generates a block of graph-specific intermediate representation instructions to replace the target expression. The compiler compiles the source code instructions to generate intermediate representation instructions, where the intermediate representation instructions include the block of graph-specific intermediate representation instructions in place of the target expression.