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

公开(公告)号：US20110208872A1

公开(公告)日：2011-08-25

申请号：US12712986

申请日：2010-02-25

Applicant: Michael Liddell ,  Igor Ostrovsky ,  Stephen Toub

Inventor： Michael Liddell ,  Igor Ostrovsky ,  Stephen Toub

IPC: G06F15/16

CPC classification number: G06F9/505

Abstract: Dynamic data partitioning is disclosed for use with a multiple node processing system that consumes items from a data stream of any length and independent of whether the length is undeclared. Dynamic data partitioning takes items from the data stream when a thread is idle and assigns the taken items to an idle thread, and it varies the size of data chunks taken from the stream and assigned to a thread to efficiently distribute work loads among the nodes. In one example, data chunk sizes taken from the beginning of the data stream are relatively smaller than data chunk sizes taken towards the middle or end of the data stream. Dynamic data partitioning employs a growth function where chunks have a size related to single aligned cache lines and efficiently increases the size of the data chunks to occasionally double the amount of data assigned to concurrent threads.

Abstract translation: 公开了与多节点处理系统一起使用的动态数据分区，其从任何长度的数据流消耗项目，并且与长度是否未声明无关。 动态数据分区在线程空闲时从数据流中获取项目，并将所获取的项目分配给空闲线程，并且将从流中分配给分配给线程的数据块的大小变化，从而有效地在节点之间分配工作负载。 在一个示例中，从数据流的开头获取的数据块大小相对于数据流的中间或结尾所采取的数据块大小相对较小。 动态数据分区使用增长函数，其中块与单个对齐的高速缓存行相关联，并有效地增加数据块的大小，以偶尔将分配给并发线程的数据量加倍。

公开(公告)号：US20110154359A1

公开(公告)日：2011-06-23

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

公开(公告)号：US20100250613A1

公开(公告)日：2010-09-30

申请号：US12413814

申请日：2009-03-30

Applicant: Igor Ostrovsky ,  John Duffy ,  Stephen H. Toub

Inventor： Igor Ostrovsky ,  John Duffy ,  Stephen H. Toub

IPC: G06F17/30

CPC classification number: G06F16/24539

Abstract: A method of processing a query includes receiving a language integrated query including at least one operator, and operating on an input array with the at least one operator. An output array is generated by the at least one operator based on the operation on the input array.

Abstract translation: 一种处理查询的方法包括：接收包括至少一个运算符的语言集成查询，以及使用所述至少一个运算符对输入阵列进行操作。 基于输入阵列上的操作，由至少一个运算符产生输出数组。

公开(公告)号：US20090320005A1

公开(公告)日：2009-12-24

申请号：US12132614

申请日：2008-06-04

Applicant: Stephen Toub ,  Igor Ostrovsky ,  Joe Duffy ,  Vance Morrison ,  Huseyin Yildiz

Inventor： Stephen Toub ,  Igor Ostrovsky ,  Joe Duffy ,  Vance Morrison ,  Huseyin Yildiz

IPC: G06F9/45 ,  G06F15/76

CPC classification number: G06F8/45

Abstract: A parallelism policy object provides a control parallelism interface whose implementation evaluates parallelism conditions that are left unspecified in the interface. User-defined and other parallelism policy procedures can make recommendations to a worker program for transitioning between sequential program execution and parallel execution. Parallelizing assistance values obtained at runtime can be used in the parallelism conditions on which the recommendations are based. A consistent parallelization policy can be employed across a range of parallel constructs, and inside recursive procedures.

Abstract translation: 并行策略对象提供了一个控制并行接口，其实现评估了界面中未指定的并行条件。 用户定义和其他并行性策略程序可以向工作程序提出在顺序程序执行和并行执行之间转换的建议。 在运行时获得的并行化辅助值可以在建议所基于的并行条件中使用。 在一系列并行构造和内部递归过程中可以采用一致的并行化策略。

公开(公告)号：US20090319992A1

公开(公告)日：2009-12-24

申请号：US12132613

申请日：2008-06-04

Applicant: Joe Duffy ,  Igor Ostrovsky ,  Huseyin Yildiz ,  Stephen Toub

Inventor： Joe Duffy ,  Igor Ostrovsky ,  Huseyin Yildiz ,  Stephen Toub

IPC: G06F9/44

CPC classification number: G06F8/00

Abstract: A data partitioning interface provides procedure headings to create data partitions for processing data elements in parallel, and for obtaining data elements to process, without specifying the organizational structure of a data partitioning. A data partitioning implementation associated with the data partitioning interface provides operations to implement the interface procedures, and may also provide dynamic partitioning to facilitate load balancing.

Abstract translation: 数据分区界面提供用于创建用于并行处理数据元素的数据分区的过程标题，并且用于获取要处理的数据元素，而不指定数据分区的组织结构。 与数据分区接口相关联的数据分区实现提供了实现接口过程的操作，并且还可以提供动态分区以便于负载平衡。