公开(公告)号：US10127025B2

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

申请号：US14805897

申请日：2015-07-22

Applicant: Oracle International Corporation

Inventor： Martin Sevenich ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F8/41

Abstract: Techniques for optimizing program code through property merging are described. In an embodiment, a compiler identifies, from a plurality of properties of a particular data object that are referenced by the program code, one or more candidate sets of properties that are eligible for merging. For a respective candidate set of properties of the one or more candidate set of properties, the compiler determines whether to merge different properties of the particular data object that belong to the respective candidate set of properties. After determining to merge the different properties, a particular data structure is generated, within the memory of a computing device, that stores the different properties of the particular data object that belong to the respective candidate set.

公开(公告)号：US20180246986A1

公开(公告)日：2018-08-30

申请号：US15443327

申请日：2017-02-27

Applicant: Oracle International Corporation

Inventor： Michael Haubenschild ,  Sungpack Hong ,  Hassan Chafi ,  Korbinian Schmid ,  Martin Sevenich ,  Alexander Weld

IPC: G06F17/30

CPC classification number: G06F17/30958 ,  G06F17/30587

Abstract: Techniques herein are for navigation data structures for graph traversal. In an embodiment, navigation data structures that a computer stores include: a source vertex array of vertices; a neighbor array of dense identifiers of target vertices terminating edges; a bidirectional map associating, for each vertex, a sparse identifier of the vertex with a dense identifier of the vertex; and a vertex array containing, when a dense identifier of a source vertex is used as an offset, a pair of offsets defining an offset range, for use with the neighbor array. The source vertex array, using the dense identifier of a particular vertex as an offset, contains an offset, into a neighbor array, of a target vertex terminating an edge originating at the particular vertex. The neighbor array contiguously stores dense identifiers of target vertices terminating edges originating from a same source vertex.

公开(公告)号：US09928310B2

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

申请号：US14461184

申请日：2014-08-15

Applicant: Oracle International Corporation

Inventor： Raghavan Raman ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F17/30

CPC classification number: G06F17/30958 ,  G06F17/30979

Abstract: Techniques for identifying, in a target graph, subgraphs that match a query graph are provided. Processing a query graph comprises multiple stages, one for each query node in the query graph. In the first stage, a query node is selected, different portions of the target graph are assigned to different threads, each thread identifies nodes that match the selected query node and stores the identities of those nodes in storage that is local to the thread. The results of each thread are then stored in a “global” data structure. In the second stage, a second query node is selected and different portions of the global data structure are assigned to different threads. Each thread identifies nodes that match the second query node and that are connected to a previously-matched node. The second stage repeats until all nodes in the query graph are processed.

公开(公告)号：US09928113B2

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

申请号：US14543058

申请日：2014-11-17

Applicant: Oracle International Corporation

Inventor： 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: An analyzer (such as a compiler) searches for a program portion that matches a pattern that may suffer from workload imbalance due to nodes with high degrees (i.e., relatively many edges). Such a pattern involves iteration over at least a subset (or all) of the nodes in a graph. If a program portion that matches the pattern is found, then the analyzer determines whether the body of the iteration contains an iteration over edges or neighbors of each node in the subset. If so, then the analyzer transforms the graph analytic program by adding code and, optionally, modifying existing code so that high-degree nodes are processed differently than low-degree nodes. High-degree nodes are processed sequentially while low-degree nodes are processed in parallel. Conversely, edges of high-degree nodes are processed in parallel while edges of low-degree nodes are processed sequentially.

公开(公告)号：US20170351551A1

公开(公告)日：2017-12-07

申请号：US15175920

申请日：2016-06-07

Applicant: Oracle International Corporation

Inventor： Thomas Manhardt ,  Sungpack Hong ,  Siegfried Depner ,  Jinsu Lee ,  Nicholas Roth ,  Hassan Chafi

IPC: G06F9/50

CPC classification number: G06F9/5061 ,  G06F9/5038 ,  G06F9/5066 ,  G06F9/5083 ,  G06F9/522 ,  H04L67/10

Abstract: Techniques are provided for dynamically self-balancing communication and computation. In an embodiment, each partition of application data is stored on a respective computer of a cluster. The application is divided into distributed jobs, each of which corresponds to a partition. Each distributed job is hosted on the computer that hosts the corresponding data partition. Each computer divides its distributed job into computation tasks. Each computer has a pool of threads that execute the computation tasks. During execution, one computer receives a data access request from another computer. The data access request is executed by a thread of the pool. Threads of the pool are bimodal and may be repurposed between communication and computation, depending on workload. Each computer individually detects completion of its computation tasks. Each computer informs a central computer that its distributed job has finished. The central computer detects when all distributed jobs of the application have terminated.

公开(公告)号：US09575736B2

公开(公告)日：2017-02-21

申请号：US14805882

申请日：2015-07-22

Applicant: Oracle International Corporation

Inventor： Sungpack Hong ,  Korbinian Schmid ,  Felix Kaser ,  Hassan Chafi

IPC: G06F9/45 ,  G06F9/44

CPC classification number: G06F8/41 ,  G06F8/30 ,  G06F8/441 ,  G06F8/443 ,  G06F8/445 ,  G06F9/45512

Abstract: Systems and methods for interactive front-end graph analysis are provided herein. According to one embodiment, a front-end application receives, from a compiler, first meta-information for a particular graph analysis procedure, where the first meta-information identifies a set of input parameters for passing graph information to the particular graph analysis procedure. The front-end application registers, using the first meta-information, the particular graph analysis procedure as an available command. The front-end application also receives second meta-information that identifies, for each respective graph object of a set of one or more graph objects, a respective set of graph characteristics. In response to receiving a request to apply the particular graph analysis procedure to the set of one or more graph objects, the front-end application enforces a set of one or more constraints based on the first meta-information and the second meta-information.

Abstract translation: 本文提供了交互式前端图分析的系统和方法。 根据一个实施例，前端应用从编译器接收用于特定图分析过程的第一元信息，其中第一元信息识别用于将图信息传递到特定图分析过程的一组输入参数。 前端应用程序使用第一个元信息将特定图分析过程注册为可用命令。 前端应用还接收第二元信息，其针对一个或多个图形对象的集合的每个相应图形对象标识相应的图形特征集合。 响应于接收到将特定图形分析过程应用于一个或多个图形对象的集合的请求，前端应用基于第一元信息和第二元信息强制执行一组或多个约束。

公开(公告)号：US20160299991A1

公开(公告)日：2016-10-13

申请号：US14680150

申请日：2015-04-07

Applicant: Oracle International Corporation

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

IPC: G06F17/30

CPC classification number: G06F17/30958 ,  G06F17/30327 ,  G06F2201/80

Abstract: Techniques for efficiently loading graph data into memory are provided. A plurality of node ID lists are retrieved from storage. Each node ID list is ordered based on one or more order criteria, such as node ID, and is read into memory. A new list of node IDs is created in memory and is initially empty. From among the plurality of node ID lists, a particular node ID is selected based on the one or more order criteria, removed from the node ID list where the particular node ID originates, and added to the new list. This process of selecting, removing, and adding continues until no more than one node ID list exists, other than the new list. In this way, the retrieval of the plurality of node ID lists from storage may be performed in parallel while the selecting and adding are performed sequentially.

Abstract translation: 提供了有效地将图形数据加载到存储器中的技术。 从存储器检索多个节点ID列表。 每个节点ID列表根据一个或多个订单标准（如节点ID）进行排序，并被读入存储器。 节点ID的新列表在内存中创建，最初为空。 从多个节点ID列表中，基于从特定节点ID发起的节点ID列表中移除并添加到新列表的一个或多个顺序标准来选择特定节点ID。 除了新的列表之外，这个选择，删除和添加的过程将继续存在，直到不再有一个节点ID列表存在。 以这种方式，可以在顺序执行选择和添加的同时并行执行从存储器检索多个节点ID列表。

公开(公告)号：US20160140152A1

公开(公告)日：2016-05-19

申请号：US14543058

申请日：2014-11-17

Applicant: Oracle International Corporation

Inventor： Martin Sevenich ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F17/30

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

Abstract: Techniques for analyzing and modifying a graph analytic program are provided. An analyzer (such as a compiler) searches for a program portion that matches a pattern that may suffer from workload imbalance due to nodes with high degrees (i.e., relatively many edges). Such a pattern involves iteration over at least a subset (or all) of the nodes in a graph. If a program portion that matches the pattern is found, then the analyzer determines whether the body of the iteration contains an iteration over edges or neighbors of each node in the subset. If so, then the analyzer transforms the graph analytic program by adding code and, optionally, modifying existing code so that high-degree nodes are processed differently than low-degree nodes. High-degree nodes are processed sequentially while low-degree nodes are processed in parallel. Conversely, edges of high-degree nodes are processed in parallel while edges of low-degree nodes are processed sequentially.

Abstract translation: 提供了分析和修改图解分析程序的技术。 分析器（例如编译器）搜索与由于具有高度的节点（即，相对多的边缘）而可能遭受工作负载不平衡的模式匹配的程序部分。 这种模式涉及图中的至少一个子集（或全部）节点的迭代。 如果找到与模式匹配的程序部分，则分析器确定迭代的主体是否包含在子集中的每个节点的边缘或邻居上的迭代。 如果是这样，那么分析器通过添加代码和可选地修改现有代码来转换图形分析程序，使得高度节点的处理方式与低度节点不同。 顺序处理高度节点，并且并行处理低度节点。 相反地​​，高度节点的边缘被并行处理，而低度节点的边缘被顺序地处理。

公开(公告)号：US20160048607A1

公开(公告)日：2016-02-18

申请号：US14461184

申请日：2014-08-15

Applicant: Oracle International Corporation

Inventor： Raghavan Raman ,  Sungpack Hong ,  Hassan Chafi

IPC: G06F17/30

CPC classification number: G06F17/30958 ,  G06F17/30979

Abstract: Techniques for identifying, in a target graph, subgraphs that match a query graph are provided. Processing a query graph comprises multiple stages, one for each query node in the query graph. In the first stage, a query node is selected, different portions of the target graph are assigned to different threads, each thread identifies nodes that match the selected query node and stores the identities of those nodes in storage that is local to the thread. The results of each thread are then stored in a “global” data structure. In the second stage, a second query node is selected and different portions of the global data structure are assigned to different threads. Each thread identifies nodes that match the second query node and that are connected to a previously-matched node. The second stage repeats until all nodes in the query graph are processed.

Abstract translation: 提供了在目标图中识别与查询图匹配的子图的技术。 处理查询图包括多个阶段，一个查询图中的每个查询节点。 在第一阶段中，选择查询节点，目标图的不同部分被分配给不同的线程，每个线程标识与所选查询节点匹配的节点，并将那些节点的身份存储在线程本地的存储中。 然后将每个线程的结果存储在“全局”数据结构中。 在第二阶段中，选择第二查询节点，并将全局数据结构的不同部分分配给不同的线程。 每个线程标识与第二个查询节点匹配并且连接到先前匹配的节点的节点。 第二阶段重复，直到查询图中的所有节点被处理。

公开(公告)号：US20150178405A1

公开(公告)日：2015-06-25

申请号：US14139237

申请日：2013-12-23

Applicant: Oracle International Corporation

Inventor： Sungpack Hong ,  Martin Sevenich ,  Hassan Chafi

IPC: G06F17/30

CPC classification number: G06F17/30958

Abstract: Techniques for identifying common neighbors of two nodes in a graph are provided. One technique involves performing a binary split search and/or a linear search. Another technique involves creating a segmenting index for a first neighbor list. A second neighbor list is scanned and, for each node indicated in the second neighbor list, the segmenting index is used to determine whether the node is also indicated in the first neighbor list. Techniques are also provided for counting the number of triangles. One technique involves pruning nodes from neighbor lists based on the node values of the nodes whose neighbor lists are being pruned. Another technique involves sorting the nodes in a node array (and, thus, their respective neighbor lists) based on the nodes' respective degrees prior to identifying common neighbors. In this way, when pruning the neighbor lists, the neighbor lists of the highly connected nodes are significantly reduced.

Abstract translation: 提供了用于识别图中两个节点的公共邻居的技术。 一种技术涉及执行二分割搜索和/或线性搜索。 另一种技术涉及为第一邻居列表创建分段索引。 扫描第二邻居列表，并且对于第二邻居列表中指示的每个节点，使用分段索引来确定节点是否也在第一邻居列表中指示。 还提供了用于计数三角形数量的技术。 一种技术是根据邻居列表被修剪的节点的节点值从邻居列表中修剪节点。 另一技术涉及在识别公共邻居之前基于节点的相应度来对节点阵列（以及因此其相应的邻居列表）中的节点进行排序。 这样，当修剪邻居列表时，高度连接的节点的邻居列表显着减少。