公开(公告)号：US08707275B2

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

申请号：US12882163

申请日：2010-09-14

Applicant: Massimo Mascaro ,  Igor Ostrovsky ,  Emad A. Omara

Inventor： Massimo Mascaro ,  Igor Ostrovsky ,  Emad A. Omara

IPC: G06F9/44

CPC classification number: G06F11/3664 ,  G06F8/20 ,  G06F8/443 ,  G06F9/4881 ,  G06F9/5066 ,  G06Q10/06315

Abstract: A scheduler receives a job graph which includes a graph of computational vertices that are designed to be executed on multiple distributed computer systems. The scheduler queries a graph manager to determine which computational vertices of the job graph are ready for execution in a local execution environment. The scheduler queries a cluster manager to determine the organizational topology of the distributed computer systems to simulate the determined topology in the local execution environment. The scheduler queries a data manager to determine data storage locations for each of the computational vertices indicated as being ready for execution in the local execution environment. The scheduler also indicates to a vertex spawner that an instance of each computational vertex is to be spawned in the local execution environment based on the organizational topology and indicated data storage locations, and indicates to the local execution environment that the spawned vertices are to be executed.

Abstract translation: 调度器接收作业图，该作业图包括被设计为在多个分布式计算机系统上执行的计算顶点的图形。 调度程序查询图表管理器以确定作业图的哪些计算顶点准备好在本地执行环境中执行。 调度程序查询集群管理器以确定分布式计算机系统的组织拓扑，以模拟本地执行环境中确定的拓扑。 调度器查询数据管理器以确定指示为准备在本地执行环境中执行的每个计算顶点的数据存储位置。 调度器还向顶点指示器根据组织拓扑和指示的数据存储位置，在本地执行环境中产生每个计算顶点的实例，并向本地执行环境指示要执行所产生的顶点 。

公开(公告)号：US08521721B2

公开(公告)日：2013-08-27

申请号：US12882168

申请日：2010-09-14

Applicant: Stephen Harris Toub ,  Igor Ostrovsky ,  Mike Liddell

Inventor： Stephen Harris Toub ,  Igor Ostrovsky ,  Mike Liddell

IPC: G06F7/00 ,  G06F17/30

CPC classification number: G06F17/30445

Abstract: Embodiments are directed to implementing custom operators in a query for a parallel query engine and to generating a partitioned representation of a sequence of query operators in a parallel query engine. A computer system receives a portion of partitioned input data at a parallel query engine, where the parallel query engine is configured to process data queries in parallel, and where the queries include a sequence of built-in operators. The computer system incorporates a custom operator into the sequence of built-in operators for a query and accesses the sequence of operators to determine how the partitioned input data is to be processed. The custom operator is accessed in the same manner as the built-in operators. The computer system also processes the sequence of operators including both the built-in operators and at least one custom operator according to the determination indicating how the data is to be processed.

Abstract translation: 实施例涉及在并行查询引擎的查询中实现自定义运算符并且在并行查询引擎中生成查询运算符序列的分区表示。 计算机系统在并行查询引擎处接收分割的输入数据的一部分，其中并行查询引擎被配置为并行处理数据查询，并且查询包括一系列内置运算符。 计算机系统将定制运算符合并到用于查询的内置运算符序列中，并访问运算符序列以确定如何处理分区输入数据。 以与内置运算符相同的方式访问定制运算符。 计算机系统还根据指示如何处理数据的确定来处理包括内置运算符和至少一个定制运算符的运算符序列。

公开(公告)号：US08276154B2

公开(公告)日：2012-09-25

申请号：US12642233

申请日：2009-12-18

Applicant: Stephen H. Toub ,  Igor Ostrovsky

Inventor： Stephen H. Toub ,  Igor Ostrovsky

IPC: G06F9/46

CPC classification number: G06F9/5033 ,  G06F2209/5018

Abstract: The present invention extends to methods, systems, and computer program products for partitioning streaming data. Embodiments of the invention can be used to hash partition a stream of data and thus avoids unnecessary memory usage (e.g., associated with buffering). Hash partitioning can be used to split an input sequence (e.g., a data stream) into multiple partitions that can be processed independently. Other embodiments of the invention can be used to hash repartition a plurality of streams of data. Hash repartitioning converts a set of partitions into another set of partitions with the hash partitioned property. Partitioning and repartitioning can be done in a streaming manner at runtime by exchanging values between worker threads responsible for different partitions.

Abstract translation: 本发明扩展到用于划分流数据的方法，系统和计算机程序产品。 本发明的实施例可用于对数据流进行散列分区，从而避免不必要的存储器使用（例如，与缓冲相关联）。 散列分区可用于将输入序列（例如，数据流）拆分成可独立处理的多个分区。 本发明的其他实施例可用于对多个数据流重新分区。 哈希重新分区将一组分区转换为具有哈希分区属性的另一组分区。 在运行时可以通过在负责不同分区的工作线程之间交换值来进行分区和重新分区。

公开(公告)号：US20110307905A1

公开(公告)日：2011-12-15

申请号：US12816165

申请日：2010-06-15

Applicant: Edward G. Essey ,  Igor Ostrovsky ,  Pooja Nagpal ,  Huseyin S. Yildiz ,  Hazim Shafi ,  William T. Colburn

Inventor： Edward G. Essey ,  Igor Ostrovsky ,  Pooja Nagpal ,  Huseyin S. Yildiz ,  Hazim Shafi ,  William T. Colburn

IPC: G06F9/44 ,  G06F3/048

CPC classification number: G06F11/323 ,  G06F11/3409 ,  G06F11/3476 ,  G06F2201/86

Abstract: The present invention extends to methods, systems, and computer program products for indicating parallel operations with user-visible events. Event markers can be used to indicate an abstracted outer layer of execution as well as expose internal specifics of parallel processing systems, including systems that provide data parallelism. Event markers can be used to show a variety of execution characteristics including higher-level markers to indicate the beginning and end of an execution program (e.g., a query). Inside the execution program (query) individual fork/join operations can be indicated with sub-levels of markers to expose their operations. Additional decisions made by an execution engine, such as, for example, when elements initially yield, when queries overlap or nest, when the query is cancelled, when the query bails to sequential operation, when premature merging or re-partitioning are needed can also be exposed.

Abstract translation: 本发明扩展到用于指示与用户可见事件并行操作的方法，系统和计算机程序产品。 事件标记可用于指示抽象的外层执行，以及公开并行处理系统的内部细节，包括提供数据并行性的系统。 事件标记可用于显示各种执行特征，包括用于指示执行程序（例如，查询）的开始和结束的更高级标记。 在执行程序（查询）中，可以使用子级别的标记来显示单独的fork / join操作，以显示其操作。 执行引擎做出的其他决定，例如当元素最初产生时，当查询重叠或嵌套时，当查询被取消时，当查询需要顺序操作时，当需要提前合并或重新分区时也可以 被暴露

公开(公告)号：US08606791B2

公开(公告)日：2013-12-10

申请号：US13163260

申请日：2011-06-17

Applicant: Igor Ostrovsky

Inventor： Igor Ostrovsky

IPC: G06F17/30

CPC classification number: G06F17/30949 ,  G06F17/30348

Abstract: A method of resizing a concurrently accessed hash table is disclosed. The method includes acquiring the locks in the hash table. The hash table, in a first state, is dynamically reconfigured in size into a second state. Additionally, the amount of locks is dynamically adjusted based on comparing the size of the hash table in the second state to the size of the hash table in the second state.

Abstract translation: 公开了一种调整并发访问的散列表的大小的方法。 该方法包括获取哈希表中的锁。 处于第一状态的哈希表在大小上被动态地重新配置成第二状态。 此外，基于将第二状态中的散列表的大小与第二状态中的散列表的大小进行比较，动态地调整锁的量。

公开(公告)号：US20130132684A1

公开(公告)日：2013-05-23

申请号：US13300464

申请日：2011-11-18

Applicant: Igor Ostrovsky ,  Zachary David Johnson

Inventor： Igor Ostrovsky ,  Zachary David Johnson

IPC: G06F12/00 ,  G06F12/16

CPC classification number: G06F11/3471 ,  G06F11/3409

Abstract: The present invention extends to methods, systems, and computer program products for automatically optimizing memory accesses by kernel functions executing on parallel accelerator processors. A function is accessed. The function is configured to operate over a multi-dimensional matrix of memory cells through invocation as a plurality of threads on a parallel accelerator processor. A layout of the memory cells of the multi-dimensional matrix and a mapping of memory cells to global memory at the parallel accelerator processor are identified. The function is analyzed to identify how each of the threads access the global memory to operate on corresponding memory cells when invoked from the kernel function. Based on the analysis, the function altered to utilize a more efficient memory access scheme when performing accesses to the global memory. The more efficient memory access scheme increases coalesced memory access by the threads when invoked over the multi-dimensional matrix.

Abstract translation: 本发明扩展到用于通过在并行加速器处理器上执行的内核功能自动优化存储器访问的方法，系统和计算机程序产品。 访问一个功能。 该功能被配置为通过调用作为并行加速器处理器上的多个线程在多维矩阵的存储器单元上进行操作。 识别多维矩阵的存储单元的布局以及在并行加速器处理器处的存储单元与全局存储器的映射。 分析该功能以识别当从内核功能调用时，每个线程如何访问全局存储器以对相应的存储器单元进行操作。 基于分析，当执行对全局存储器的访问时，功能被改变以利用更有效的存储器访问方案。 当通过多维矩阵调用时，更有效的存储器访问方案增加了线程的合并的存储器访问。

公开(公告)号：US08392920B2

公开(公告)日：2013-03-05

申请号：US12695049

申请日：2010-01-27

Applicant: Igor Ostrovsky ,  John J. Duffy ,  Stephen Harris Toub

Inventor： Igor Ostrovsky ,  John J. Duffy ,  Stephen Harris Toub

IPC: G06F9/40 ,  G06F9/44 ,  G06F9/46

CPC classification number: G06F9/4881 ,  G06F2209/483

Abstract: Partitioning query execution work of a sequence including a plurality of elements. A method includes a worker core requesting work from a work queue. In response, the worker core receives a task from the work queue. The task is a replicable sequence-processing task including two distinct steps: scheduling a copy of the task on the scheduler queue and processing a sequence. The worker core processes the task by: creating a replica of the task and placing the replica of the task on the work queue, and beginning processing the sequence. The acts are repeated for one or more additional worker cores, where receiving a task from the work queue is performed by receiving one or more replicas of tasks placed on the task queue by earlier performances of creating a replica of the task and placing the replica of the task on the work queue by a different worker core.

Abstract translation: 分割包含多个元素的序列的查询执行工作。 一种方法包括从工作队列请求工作的工作者核心。 作为响应，工作核心从工作队列接收任务。 该任务是可重复的序列处理任务，其包括两个不同的步骤：在调度器队列上调度任务的副本并处理序列。 工作核心通过以下方式来处理任务：创建任务的副本并将任务的副本放在工作队列上，并开始处理序列。 对于一个或多个额外的工作核心重复执行动作，其中从工作队列接收任务通过接收一个或多个放置在任务队列上的任务的副本来执行，以通过较早的创建该任务副本的性能并将副本 工作队列中的任务由不同的工作人员核心。

公开(公告)号：US20120331475A1

公开(公告)日：2012-12-27

申请号：US13165421

申请日：2011-06-21

Applicant: Igor Ostrovsky ,  Joseph E. Hoag ,  Stephen H. Toub ,  Mike Liddell

Inventor： Igor Ostrovsky ,  Joseph E. Hoag ,  Stephen H. Toub ,  Mike Liddell

IPC: G06F9/46

CPC classification number: G06F12/023 ,  G06F3/0608 ,  G06F3/061 ,  G06F3/0631 ,  G06F3/0673 ,  G06F9/5016 ,  G06F2212/1016 ,  G06F2212/1044

Abstract: Dynamically allocated thread storage in a computing device is disclosed. The dynamically allocated thread storage is configured to work with a process including two or more threads. Each thread includes a statically allocated thread-local slot configured to store a table. Each table is configured to include a table slot corresponding with a dynamically allocated thread-local value. A dynamically allocated thread-local instance corresponds with the table slot.

Abstract translation: 公开了在计算设备中动态分配的线程存储。 动态分配的线程存储被配置为使用包括两个或更多个线程的进程。 每个线程包括一个静态分配的线程本地插槽，用于存储一个表。 每个表被配置为包括与动态分配的线程本地值相对应的表时隙。 动态分配的线程本地实例对应于表槽。

公开(公告)号：US08276111B2

公开(公告)日：2012-09-25

申请号：US12339556

申请日：2008-12-19

Applicant: Igor Ostrovsky ,  John Duffy

Inventor： Igor Ostrovsky ,  John Duffy

IPC: G06F17/00

CPC classification number: G06F8/437

Abstract: A method of providing access to a dataset in a type-safe manner includes storing a dataset including a plurality of data elements and a corresponding plurality of order keys for indicating an ordering of the data elements. Each order key is associated with one of the data elements. An interface to the dataset is generated that is parameterized by an element type parameter and a key type parameter. The interface is configured to provide access to the data elements and the order keys in the dataset in a type-safe manner.

Abstract translation: 以类型安全的方式提供对数据集的访问的方法包括存储包括多个数据元素的数据集和用于指示数据元素的排序的对应的多个顺序密钥。 每个订单密钥与其中一个数据元素相关联。 生成与数据集的接口，该接口由元素类型参数和键类型参数进行参数化。 该接口被配置为以类型安全的方式提供对数据集中的数据元素和订单键的访问。

公开(公告)号：US20120066250A1

公开(公告)日：2012-03-15

申请号：US12882168

申请日：2010-09-14

Applicant: Stephen Harris Toub ,  Igor Ostrovsky ,  Mike Liddell

Inventor： Stephen Harris Toub ,  Igor Ostrovsky ,  Mike Liddell

IPC: G06F17/30

CPC classification number: G06F17/30445

Abstract: Embodiments are directed to implementing custom operators in a query for a parallel query engine and to generating a partitioned representation of a sequence of query operators in a parallel query engine. A computer system receives a portion of partitioned input data at a parallel query engine, where the parallel query engine is configured to process data queries in parallel, and where the queries include a sequence of built-in operators. The computer system incorporates a custom operator into the sequence of built-in operators for a query and accesses the sequence of operators to determine how the partitioned input data is to be processed. The custom operator is accessed in the same manner as the built-in operators. The computer system also processes the sequence of operators including both the built-in operators and at least one custom operator according to the determination indicating how the data is to be processed.

Abstract translation: 实施例涉及在并行查询引擎的查询中实现自定义运算符并且在并行查询引擎中生成查询运算符序列的分区表示。 计算机系统在并行查询引擎处接收分割的输入数据的一部分，其中并行查询引擎被配置为并行处理数据查询，并且查询包括一系列内置运算符。 计算机系统将定制运算符合并到用于查询的内置运算符序列中，并访问运算符序列以确定如何处理分区输入数据。 以与内置运算符相同的方式访问定制运算符。 计算机系统还根据指示如何处理数据的确定来处理包括内置运算符和至少一个定制运算符的运算符序列。