公开(公告)号：US08645429B1

公开(公告)日：2014-02-04

申请号：US13432806

申请日：2012-03-28

Applicant: Aart J. C. Bik ,  Matthew H. Austern ,  James C. Dehnert ,  Grzegorz Czajkowski ,  Grzegorz Malewicz ,  Naty Leiser

Inventor： Aart J. C. Bik ,  Matthew H. Austern ,  James C. Dehnert ,  Grzegorz Czajkowski ,  Grzegorz Malewicz ,  Naty Leiser

IPC: G06F7/00 ,  G06F17/30 ,  G06F11/20

CPC classification number: G06T11/206 ,  G06F7/00 ,  G06F8/457 ,  G06F9/46 ,  G06F9/5005 ,  G06F11/1464 ,  G06F11/1469 ,  G06F11/2082 ,  G06F15/17312 ,  G06F17/30 ,  G06F17/30958 ,  G06F17/30961 ,  G06F2201/84 ,  G06F2221/0793 ,  G06N99/00 ,  G06N99/005 ,  G06T2210/32 ,  H04L5/0032 ,  H04L29/08135 ,  H04L67/10

Abstract: Resolving conflicting graph mutations in a distributed computing system. Graph data for at least a partition of a graph is stored in a worker system of a distributed computing system. The graph represents relationships among a set of tangible items that model a real-world condition having an associated problem. A plurality of conflicting mutation requests are received to mutate the graph. A conflict between the mutation requests is resolved with a conflict resolution function that lacks direct access to the graph data. The graph data is updated responsive to a result generated by resolving the conflict using the conflict resolution function.

Abstract translation: 解决分布式计算系统中的冲突图突变。 至少图形分区的图形数据存储在分布式计算系统的工作系统中。 该图表示对具有相关问题的真实世界条件建模的一组有形项目之间的关系。 接收多个冲突变异请求以使图形变异。 突变请求之间的冲突由解决冲突的功能解决，缺少对图形数据的直接访问。 响应于通过使用冲突解决功能解决冲突而产生的结果来更新图形数据。

公开(公告)号：US09135565B1

公开(公告)日：2015-09-15

申请号：US13451894

申请日：2012-04-20

Applicant: Mohamed Elbassiony Mohamed Abou El Alaa Khalefa ,  Matthew H. Austern ,  James C. Dehnert ,  Aart J. C. Bik ,  Grzegorz Czajkowski ,  Grzegorz Malewicz

Inventor： Mohamed Elbassiony Mohamed Abou El Alaa Khalefa ,  Matthew H. Austern ,  James C. Dehnert ,  Aart J. C. Bik ,  Grzegorz Czajkowski ,  Grzegorz Malewicz

IPC: G06F15/17 ,  G06N99/00 ,  G06F15/173

CPC classification number: G06T11/206 ,  G06F7/00 ,  G06F8/457 ,  G06F9/46 ,  G06F9/5005 ,  G06F11/1464 ,  G06F11/1469 ,  G06F11/2082 ,  G06F15/17312 ,  G06F17/30 ,  G06F17/30958 ,  G06F17/30961 ,  G06F2201/84 ,  G06F2221/0793 ,  G06N99/00 ,  G06N99/005 ,  G06T2210/32 ,  H04L5/0032 ,  H04L29/08135 ,  H04L67/10

Abstract: Data are maintained in a distributed computing system that describe a directed graph representing relationships among items. The directed graph has a plurality of vertices representing the items and has edges with values representing distances between the items connected by the vertices. A multiple reference point algorithm is executed for a plurality of the vertices in the directed graph in parallel for a series of synchronized iterations to determine shortest distances between the vertices and the source vertex. After executing the algorithm on the vertices, value pairs associated with the vertices are aggregated. The aggregated value pairs indicate shortest distances from the respective vertices to the source vertex. The aggregated value pairs are outputted.

Abstract translation: 在分布式计算系统中维护数据，该分布式计算系统描述表示项目之间的关系的有向图。 有向图具有表示项目的多个顶点，并且具有表示由顶点连接的项目之间的距离的值的边。 针对一系列同步迭代并行地对有向图中的多个顶点执行多参考点算法，以确定顶点与源顶点之间的最短距离。 在对顶点执行算法之后，聚合与顶点相关联的值对。 聚合值对表示从各个顶点到源顶点的最短距离。 输出聚合值对。

公开(公告)号：US09104665B1

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

申请号：US13451420

申请日：2012-04-19

Applicant: Aart J. C. Bik ,  James C. Dehnert ,  Matthew H. Austern ,  Grzegorz Czajkowski

Inventor： Aart J. C. Bik ,  James C. Dehnert ,  Matthew H. Austern ,  Grzegorz Czajkowski

IPC: G06F7/00 ,  G06F17/30

CPC classification number: G06T11/206 ,  G06F7/00 ,  G06F8/457 ,  G06F9/46 ,  G06F9/5005 ,  G06F11/1464 ,  G06F11/1469 ,  G06F11/2082 ,  G06F15/17312 ,  G06F17/30 ,  G06F17/30958 ,  G06F17/30961 ,  G06F2201/84 ,  G06F2221/0793 ,  G06N99/00 ,  G06N99/005 ,  G06T2210/32 ,  H04L5/0032 ,  H04L29/08135 ,  H04L67/10

Abstract: Data are received at a worker system in a distributed computing system that describe a graph representing relationships among a set of items. The graph models a condition having an associated problem. The graph has graph components having associated data fields. The received data are stored in a backup table, and the relationships are analyzed to identify a solution to the problem. As part of the analysis, a new value for the data field associated with a graph component is identified and compared with an existing value of the data field, and the data field is modified. The modified data field is stored in a delta table representing a change to the backup table.

Abstract translation: 在分布式计算系统中的工作者系统处接收数据，该分布式计算系统描述表示一组项目之间的关系的图表。 图表模拟具有相关问题的条件。 该图具有具有相关数据字段的图形组件。 接收的数据存储在备份表中，并分析关系以识别问题的解决方案。 作为分析的一部分，识别与图形组件相关联的数据字段的新值，并与数据字段的现有值进行比较，并修改数据字段。 修改的数据字段存储在表示对备份表的更改的增量表中。

公开(公告)号：US09385845B1

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

申请号：US13449249

申请日：2012-04-17

Applicant: Matthew H. Austern ,  James C. Dehnert ,  Aart J. C. Bik ,  Grzegorz Czajkowski ,  Grzegorz Malewicz

Inventor： Matthew H. Austern ,  James C. Dehnert ,  Aart J. C. Bik ,  Grzegorz Czajkowski ,  Grzegorz Malewicz

IPC: H04L29/08 ,  H04L5/00

CPC classification number: G06T11/206 ,  G06F7/00 ,  G06F8/457 ,  G06F9/46 ,  G06F9/5005 ,  G06F11/1464 ,  G06F11/1469 ,  G06F11/2082 ,  G06F15/17312 ,  G06F17/30 ,  G06F17/30958 ,  G06F17/30961 ,  G06F2201/84 ,  G06F2221/0793 ,  G06N99/00 ,  G06N99/005 ,  G06T2210/32 ,  H04L5/0032 ,  H04L29/08135 ,  H04L67/10

Abstract: A value is distributed in a distributed computing system having a master system in communication with a plurality of worker systems. Partitions of a graph are assigned to the worker systems. The graph represents relationships among a set of tangible items that model a real-world condition having an associated problem. Configuration information is determined that describes a configuration of the distributed computing system. A distribution scheme is selected for distributing a value from the master system to the plurality of worker systems based on the configuration information. The value is distributed from the master system to the worker systems according to the selected distribution scheme. The worker systems are configured to use the value to produce an output representing a solution to the real-world problem.

Abstract translation: 值分布在具有与多个工作者系统通信的主系统的分布式计算系统中。 图形的分区分配给工作系统。 该图表示对具有相关问题的真实世界条件建模的一组有形项目之间的关系。 确定描述分布式计算系统的配置的配置信息。 选择分配方案，用于基于配置信息将值从主系统分配给多个工作者系统。 该值根据选定的分配方案从主系统分配给工作系统。 工作者系统被配置为使用该值来产生表示对现实世界问题的解决方案的输出。

公开(公告)号：US09026850B1

公开(公告)日：2015-05-05

申请号：US13451450

申请日：2012-04-19

Applicant: Grzegorz Malewicz ,  Matthew H. Austern ,  James C. Dehnert ,  Aart J. C. Bik ,  Grzegorz Czajkowski

Inventor： Grzegorz Malewicz ,  Matthew H. Austern ,  James C. Dehnert ,  Aart J. C. Bik ,  Grzegorz Czajkowski

IPC: G06F11/00 ,  G06F9/45

CPC classification number: G06T11/206 ,  G06F7/00 ,  G06F8/457 ,  G06F9/46 ,  G06F9/5005 ,  G06F11/1464 ,  G06F11/1469 ,  G06F11/2082 ,  G06F15/17312 ,  G06F17/30 ,  G06F17/30958 ,  G06F17/30961 ,  G06F2201/84 ,  G06F2221/0793 ,  G06N99/00 ,  G06N99/005 ,  G06T2210/32 ,  H04L5/0032 ,  H04L29/08135 ,  H04L67/10

Abstract: Executing a confined recovery in a distributed system having a plurality of worker systems including a failed worker system at a current superstep. The confined recovery includes determining states of the partitions of the worker systems during the supersteps preceding the current superstep, and determining a recovery initiation superstep preceding the current superstep in which all messages for recovery initiation superstep are available. The recovery initiation superstep is determined responsive to determining the states of the partitions. Additionally, a recovery set of partitions is determined for which messages in supersteps after the recovery initiation superstep are not available. The worker systems having the partitions in the recovery set are instructed to execute the defined function for the partitions in the recovery set starting at the recovery initiation superstep to recover the lost exchanged messages.

Abstract translation: 在具有多个工作系统的分布式系统中执行限制恢复，包括当前超级步骤中的故障工作系统。 限制恢复包括在当前超级步骤之前的超级步骤中确定工作者系统的分区的状态，以及确定在当前超级步骤之前的恢复启动超级步骤，其中用于恢复启动超级步骤的所有消息都可用。 响应于确定分区的状态来确定恢复启动超级步骤。 另外，确定在恢复启动超级步骤之后的超级步骤中哪些消息不可用的恢复分区集合。 指示具有恢复组中的分区的工作系统对在恢复启动超级步骤开始的恢复集中的分区执行定义的功能，以恢复丢失的交换的消息。

公开(公告)号：US09495477B1

公开(公告)日：2016-11-15

申请号：US13353556

申请日：2012-01-19

Applicant: James C. Dehnert ,  Matthew H. Austern ,  Aart J. C. Bik ,  Grzegorz Czajkowski ,  Grzegorz Malewicz ,  Ilan Horn ,  Naty Leiser

Inventor： James C. Dehnert ,  Matthew H. Austern ,  Aart J. C. Bik ,  Grzegorz Czajkowski ,  Grzegorz Malewicz ,  Ilan Horn ,  Naty Leiser

IPC: G06F7/00 ,  G06F17/30

CPC classification number: G06T11/206 ,  G06F7/00 ,  G06F8/457 ,  G06F9/46 ,  G06F9/5005 ,  G06F11/1464 ,  G06F11/1469 ,  G06F11/2082 ,  G06F15/17312 ,  G06F17/30 ,  G06F17/30958 ,  G06F17/30961 ,  G06F2201/84 ,  G06F2221/0793 ,  G06N99/00 ,  G06N99/005 ,  G06T2210/32 ,  H04L5/0032 ,  H04L29/08135 ,  H04L67/10

Abstract: Data are maintained in a distributed computing system that describe a directed graph representing relationships among a set of items. The directed graph models a condition having an associated problem. The directed graph has graph components having associated data fields. The relationships are analyzed to identify a solution to the problem. As part of the analysis, a new value for the data field associated with a graph component is identified responsive to an operation performed during the analysis. The new value is compared with an existing value of the data field, and the data field is modified. The modification may include inserting the new value into an overflow vector of data, and replacing the existing value in the data field with exception information identifying the location of the new value. An exception flag associated with the data field is set to indicate that the exception information is being used.

Abstract translation: 在分布式计算系统中维护数据，该分布式计算系统描述表示一组项目之间的关系的有向图。 有向图模型具有相关问题的条件。 有向图具有具有相关数据字段的图形分量。 分析关系以确定问题的解决方案。 作为分析的一部分，响应于在分析期间执行的操作，识别与图形组件相关联的数据字段的新值。 将新值与数据字段的现有值进行比较，并修改数据字段。 修改可以包括将新值插入到数据的溢出向量中，并且用标识新值的位置的异常信息替换数据字段中的现有值。 与数据字段相关联的异常标志被设置为指示正在使用异常信息。

公开(公告)号：US08880941B1

公开(公告)日：2014-11-04

申请号：US13452299

申请日：2012-04-20

Applicant: Charles Reiss ,  Grzegorz Malewicz ,  Matthew H. Austern ,  James C. Dehnert ,  Aart J. C. Bik ,  Grzegorz Czajkowski

Inventor： Charles Reiss ,  Grzegorz Malewicz ,  Matthew H. Austern ,  James C. Dehnert ,  Aart J. C. Bik ,  Grzegorz Czajkowski

IPC: G06F11/00

CPC classification number: G06T11/206 ,  G06F7/00 ,  G06F8/457 ,  G06F9/46 ,  G06F9/5005 ,  G06F11/1464 ,  G06F11/1469 ,  G06F11/2082 ,  G06F15/17312 ,  G06F17/30 ,  G06F17/30958 ,  G06F17/30961 ,  G06F2201/84 ,  G06F2221/0793 ,  G06N99/00 ,  G06N99/005 ,  G06T2210/32 ,  H04L5/0032 ,  H04L29/08135 ,  H04L67/10

Abstract: Instructing a plurality of worker systems in a distributed computing system to perform a checkpoint. Instructing the worker systems includes receiving timing messages from the plurality of worker systems and determining, based on the received timing messages, a common checkpoint time indicating an estimated amount of time to be taken by the plurality of worker systems to write data to the persistent storage for a subsequent checkpoint. The common checkpoint time is used to determine a checkpoint threshold, and responsive to the determined checkpoint threshold, it is determined whether to perform the checkpoint. Responsive to determining to perform the checkpoint, messages are transmitted to the plurality of worker systems instructing the worker systems to perform the checkpoint.

Abstract translation: 指示分布式计算系统中的多个工作系统执行检查点。 指示工作者系统包括接收来自多个工作者系统的定时消息，并且基于接收到的定时消息来确定指示多个工作者系统将持续存储器写入数据所估计的时间量的公共检查点时间 用于后续检查点。 公共检查点时间用于确定检查点阈值，并且响应于确定的检查点阈值，确定是否执行检查点。 响应于确定执行检查点，消息被发送到指示工作者系统执行检查点的多个工作者系统。

公开(公告)号：US08793283B1

公开(公告)日：2014-07-29

申请号：US13452275

申请日：2012-04-20

Applicant: Matthew H. Austern ,  James C. Dehnert ,  Aart J. C. Bik ,  Grzegorz Czajkowski ,  Grzegorz Malewicz

Inventor： Matthew H. Austern ,  James C. Dehnert ,  Aart J. C. Bik ,  Grzegorz Czajkowski ,  Grzegorz Malewicz

IPC: G06F17/30

CPC classification number: G06T11/206 ,  G06F7/00 ,  G06F8/457 ,  G06F9/46 ,  G06F9/5005 ,  G06F11/1464 ,  G06F11/1469 ,  G06F11/2082 ,  G06F15/17312 ,  G06F17/30 ,  G06F17/30958 ,  G06F17/30961 ,  G06F2201/84 ,  G06F2221/0793 ,  G06N99/00 ,  G06N99/005 ,  G06T2210/32 ,  H04L5/0032 ,  H04L29/08135 ,  H04L67/10

Abstract: Data are maintained in a distributed computing system that describe a graph. The graph represents relationships among items. The graph has a plurality of vertices that represent the items and a plurality of edges connecting the plurality of vertices. At least one vertex of the plurality of vertices includes a set of label values indicating the at least one vertex's strength of association with a label from a set of labels. The set of labels describe possible characteristics of an item represented by the at least one vertex. At least one edge of the plurality of edges includes a set of label weights for influencing label values that traverse the at least one edge. A label propagation algorithm is executed for a plurality of the vertices in the graph in parallel for a series of synchronized iterations to propagate labels through the graph.

Abstract translation: 数据保存在描述图形的分布式计算系统中。 该图表示各项之间的关系。 该图形具有多个表示项目的顶点和连接多个顶点的多个边缘。 所述多个顶点中的至少一个顶点包括一组标签值，该组标签值指示所述至少一个顶点与来自一组标签的标签的关联强度。 标签集描述由至少一个顶点表示的项目的可能特征。 多个边缘中的至少一个边缘包括用于影响穿过至少一个边缘的标签值的一组标签权重。 针对图形中的多个顶点并行执行标签传播算法，用于一系列同步迭代，以通过图形传播标签。

公开(公告)号：US07020873B2

公开(公告)日：2006-03-28

申请号：US10176503

申请日：2002-06-21

Applicant: Aart J. C. Bik ,  Milind Girkar

Inventor： Aart J. C. Bik ,  Milind Girkar

IPC: G06F9/45

CPC classification number: G06F8/452

Abstract: An apparatus and method for vectorization of detected saturation and clipping operations in serial code loops of a source program are described. In one embodiment, the method includes the analysis of source program code to identify source code utilizing conditional constructs to perform saturation/clipping operations. Once analysis is complete, identified source code is vectorized to implement identified saturation/clipping operations utilizing single instruction, multiple data (SIMD) saturation/clipping instructions. Accordingly, utilizing embodiments of the present invention, conditional statements utilized to implement saturation arithmetic, as well as clipping of data values, such as pixel values within graphics applications, are replaced with SIMD saturation arithmetic instructions, as well as clipping instructions.

Abstract translation: 描述了用于在源程序的串行代码循环中向量化检测到的饱和度和削波操作的装置和方法。 在一个实施例中，该方法包括源程序代码的分析，以利用条件构造来识别源代码来执行饱和/剪切操作。 一旦分析完成，识别的源代码被矢量化，以利用单指令，多数据（SIMD）饱和/剪辑指令来实现识别的饱和/剪切操作。 因此，利用本发明的实施例，用于实现饱和度算术的条件语句以及诸如图形应用中的像素值的数据值的削波被SIMD饱和算术指令以及削波指令所替代。