中科微点-全球专利检索

  1. Login
  2. Sign Up

Search Results

42 records (took 0.024 seconds)

    INTELLIGENT COMPILER FOR PARALLEL GRAPH PROCESSING
    31.
    发明申请
    INTELLIGENT COMPILER FOR PARALLEL GRAPH PROCESSING 有权
    用于并行图形处理的智能编译器

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

    FINDING COMMON NEIGHBORS BETWEEN TWO NODES IN A GRAPH
    32.
    发明申请
    FINDING COMMON NEIGHBORS BETWEEN TWO NODES IN A GRAPH 审中-公开
    在图中找到两个声音之间的共同邻居

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

    Method for applying graph-specific compiler optimizations to graph analysis programs
    35.
    发明授权
    Method for applying graph-specific compiler optimizations to graph analysis programs 有权

    公开(公告)号：US11379200B2

    公开(公告)日：2022-07-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 ,  G06F8/72 ,  G06F9/30 ,  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.

    Methods of graph-type specialization and optimization in graph algorithm DSL compilation
    37.
    发明授权
    Methods of graph-type specialization and optimization in graph algorithm DSL compilation 有权

    公开(公告)号：US10585945B2

    公开(公告)日：2020-03-10

    申请号：US15666310

    申请日：2017-08-01

    Applicant: Oracle International Corporation

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

    IPC: G06F17/30 ,  G06F16/901 ,  G06F8/30 ,  G06F8/41 ,  G06F16/2453 ,  G06F8/34

    Abstract: Techniques herein generate, such as during compilation, polymorphic dispatch logic (PDL) to switch between specialized implementations of a polymorphic graph algorithm. In an embodiment, a computer detects, within source logic of a graph algorithm, that the algorithm processes an instance of a generic graph type. The computer generates several alternative implementations of the algorithm. Each implementation is specialized to process the graph instance as an instance of a respective graph subtype. The computer generates PDL that performs dynamic dispatch as follows. At runtime, the PDL receives a graph instance of the generic graph type. The PDL detects which particular graph subtype is the graph instance. The PDL then invokes whichever alternative implementation that is specialized to process the graph instance as an instance of the detected particular graph subtype. In embodiments, the source logic is expressed in a domain specific language (DSL), e.g. for analysis, traversal, or querying of graphs.

    Constructing an in-memory representation of a graph
    40.
    发明授权
    Constructing an in-memory representation of a graph 有权

    公开(公告)号：US10055509B2

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

    申请号：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 ,  G06F17/00

    CPC classification number: G06F16/9024 ,  G06F16/2246 ,  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.

Patent Agency Ranking